daisytuner/sdfglib | Build 17656823807 | src/graph/graph.cpp | Coveralls

6

const ReverseGraph reverse(const Graph& graph) { return boost::reverse_graph<Graph>(graph); };

149✔

12

undirected(const Graph& graph) {

4✔

13

    auto undirected_graph = std::make_unique<UndirectedGraph>();

4✔

14

    std::unordered_map<Vertex, Vertex> mapping;

4✔

15

    std::unordered_map<Vertex, Vertex> reverse_mapping;

4✔

17

    boost::graph_traits<Graph>::vertex_iterator vi, vend;

4✔

18

    for (boost::tie(vi, vend) = boost::vertices(graph); vi != vend; ++vi) {

24✔

19

        auto new_vertex = boost::add_vertex(*undirected_graph);

20✔

20

        mapping.emplace(*vi, new_vertex);

20✔

21

        reverse_mapping.emplace(new_vertex, *vi);

20✔

22

20✔

24

    auto [eb, ee] = boost::edges(graph);

4✔

25

    auto edges = std::ranges::subrange(eb, ee);

8✔

26

    for (const auto& edge : edges) {

18✔

27

        const auto& u = boost::source(edge, graph);

14✔

28

        const auto& v = boost::target(edge, graph);

14✔

29

        boost::add_edge(mapping.at(u), mapping.at(v), *undirected_graph);

14✔

32

    return {std::move(undirected_graph), mapping, reverse_mapping};

4✔

33

};

4✔

35

const std::list<Vertex> depth_first_search(const Graph& graph, const graph::Vertex start) {

1✔

36

    std::list<Vertex> nodes;

1✔

37

    std::list<Edge> back_edges;

1✔

38

    DFSVisitor visitor(back_edges, nodes);

1✔

40

    std::unordered_map<graph::Vertex, boost::default_color_type> vertex_colors;

1✔

41

    boost::depth_first_search(graph, visitor, boost::make_assoc_property_map(vertex_colors), start);

1✔

43

    return nodes;

1✔

44

};

1✔

46

std::pair<int, std::unordered_map<Vertex, size_t>> strongly_connected_components(const Graph& graph) {

1✔

47

    IndexMap vertex_index_map;

1✔

48

    boost::associative_property_map<IndexMap> boost_index_map(vertex_index_map);

1✔

49

    boost::graph_traits<Graph>::vertex_iterator vi, vend;

1✔

50

    size_t i = 0;

1✔

51

    for (boost::tie(vi, vend) = boost::vertices(graph); vi != vend; ++vi, ++i) {

4✔

52

        boost::put(boost_index_map, *vi, i);

3✔

53

3✔

55

    std::unordered_map<Vertex, size_t> component_map;

1✔

56

    boost::associative_property_map<IndexMap> boost_component_map(component_map);

1✔

58

    size_t num_ccs = boost::strong_components(graph, boost_component_map, boost::vertex_index_map(boost_index_map));

1✔

60

    return {num_ccs, component_map};

1✔

61

};

1✔

63

std::pair<size_t, const std::unordered_map<Vertex, size_t>> weakly_connected_components(const Graph& graph) {

3✔

64

    const auto& undirected_graph = undirected(graph);

3✔

66

    IndexMap vertex_index_map;

3✔

67

    boost::associative_property_map<IndexMap> boost_index_map(vertex_index_map);

3✔

68

    boost::graph_traits<UndirectedGraph>::vertex_iterator vi, vend;

3✔

69

    size_t i = 0;

3✔

70

    for (boost::tie(vi, vend) = boost::vertices(*std::get<0>(undirected_graph)); vi != vend; ++vi, ++i) {

21✔

71

        boost::put(boost_index_map, *vi, i);

18✔

72

18✔

74

    std::unordered_map<Vertex, size_t> undirected_component_map;

3✔

75

    boost::associative_property_map<std::unordered_map<Vertex, size_t>> boost_component_map(undirected_component_map);

3✔

77

    size_t num_ccs = boost::connected_components(

3✔

78

        *std::get<0>(undirected_graph), boost_component_map, boost::vertex_index_map(boost_index_map)

3✔

81

    std::unordered_map<Vertex, size_t> component_map;

3✔

82

    for (const auto& entry : undirected_component_map) {

21✔

83

        component_map.emplace(std::get<2>(undirected_graph).at(entry.first), entry.second);

18✔

86

    return {num_ccs, component_map};

3✔

87

};

3✔

89

const std::unordered_map<Vertex, Vertex> dominator_tree(const Graph& graph, const Vertex src) {

144✔

90

    std::unordered_map<Vertex, Vertex> dom_tree;

144✔

92

    IndexMap vertex_index_map;

144✔

93

    boost::associative_property_map<IndexMap> boost_index_map(vertex_index_map);

144✔

94

    boost::graph_traits<Graph>::vertex_iterator vi, vend;

144✔

95

    size_t i = 0;

144✔

96

    for (boost::tie(vi, vend) = boost::vertices(graph); vi != vend; ++vi, ++i) {

2,313✔

97

        boost::put(boost_index_map, *vi, i);

2,169✔

98

2,169✔

100

    std::vector<size_t> df_num(num_vertices(graph), 0);

144✔

101

    auto df_num_map(boost::make_iterator_property_map(df_num.begin(), boost_index_map));

144✔

103

    std::vector<Vertex> parent(num_vertices(graph), boost::graph_traits<Graph>::null_vertex());

144✔

104

    auto parent_map(boost::make_iterator_property_map(parent.begin(), boost_index_map));

144✔

106

    std::vector<Vertex> dom_tree_vec(num_vertices(graph), boost::graph_traits<Graph>::null_vertex());

144✔

107

    auto dom_tree_pred_map(boost::make_iterator_property_map(dom_tree_vec.begin(), boost_index_map));

144✔

109

    std::vector<Vertex> vertices_by_df_num(parent);

144✔

111

    boost::lengauer_tarjan_dominator_tree(

144✔

112

        graph, src, boost_index_map, df_num_map, parent_map, vertices_by_df_num, dom_tree_pred_map

144✔

115

    for (const auto& entry : vertex_index_map) {

2,313✔

116

        dom_tree.insert({entry.first, dom_tree_vec[entry.second]});

2,169✔

119

    return dom_tree;

144✔

120

};

144✔

122

const std::unordered_map<Vertex, Vertex> post_dominator_tree(Graph& graph) {

148✔

124

    std::unordered_set<Vertex> terminal_vertices;

148✔

125

    for (auto [vb, ve] = boost::vertices(graph); vb != ve; ++vb) {

2,482✔

126

        if (boost::out_degree(*vb, graph) == 0) {

2,186✔

127

            terminal_vertices.insert(*vb);

148✔

128

148✔

129

2,186✔

130

    assert(!terminal_vertices.empty());

148✔

133

    bool modified = false;

148✔

135

    if (terminal_vertices.size() == 1) {

148✔

136

        src = *terminal_vertices.begin();

148✔

137

        modified = false;

148✔

138

    } else {

148✔

146

    auto& rgraph = reverse(graph);

148✔

148

    std::unordered_map<Vertex, Vertex> pdom_tree;

148✔

150

    IndexMap vertex_index_map;

148✔

151

    boost::associative_property_map<IndexMap> boost_index_map(vertex_index_map);

148✔

152

    boost::graph_traits<Graph>::vertex_iterator vi, vend;

148✔

153

    size_t i = 0;

148✔

154

    for (boost::tie(vi, vend) = boost::vertices(rgraph); vi != vend; ++vi, ++i) {

2,334✔

155

        boost::put(boost_index_map, *vi, i);

2,186✔

156

2,186✔

158

    std::vector<size_t> df_num(num_vertices(rgraph), 0);

148✔

159

    auto df_num_map(boost::make_iterator_property_map(df_num.begin(), boost_index_map));

148✔

161

    std::vector<Vertex> parent(num_vertices(rgraph), boost::graph_traits<Graph>::null_vertex());

148✔

162

    auto parent_map(boost::make_iterator_property_map(parent.begin(), boost_index_map));

148✔

164

    std::vector<Vertex> pdom_tree_vec(num_vertices(rgraph), boost::graph_traits<Graph>::null_vertex());

148✔

165

    auto pdom_tree_pred_map(boost::make_iterator_property_map(pdom_tree_vec.begin(), boost_index_map));

148✔

167

    std::vector<Vertex> vertices_by_df_num(parent);

148✔

169

    boost::lengauer_tarjan_dominator_tree(

148✔

170

        rgraph, src, boost_index_map, df_num_map, parent_map, vertices_by_df_num, pdom_tree_pred_map

148✔

173

    for (const auto& entry : vertex_index_map) {

2,334✔

174

        pdom_tree.insert({entry.first, pdom_tree_vec[entry.second]});

2,186✔

178

    if (modified) {

148✔

182

    return pdom_tree;

148✔

183

};

148✔

185

const std::list<graph::Vertex> topological_sort(const Graph& graph) {

576✔

186

    std::unordered_map<graph::Vertex, boost::default_color_type> vertex_colors;

576✔

187

    std::list<graph::Vertex> order;

576✔

188

    boost::topological_sort(

576✔

189

        graph, std::back_inserter(order), boost::color_map(boost::make_assoc_property_map(vertex_colors))

576✔

191

    order.reverse();

575✔

192

    return order;

575✔

193

};

576✔

195

bool is_acyclic(const Graph& graph) {

2✔

197

        topological_sort(graph);

2✔

198

        return true;

1✔

199

    } catch (boost::not_a_dag e) {

1✔

200

        return false;

1✔

201

1✔

202

};

3✔

204

const std::list<Edge> back_edges(const Graph& graph, const graph::Vertex start) {

5✔

205

    std::list<Vertex> nodes;

5✔

206

    std::list<Edge> back_edges;

5✔

207

    DFSVisitor visitor(back_edges, nodes);

5✔

209

    std::unordered_map<graph::Vertex, boost::default_color_type> vertex_colors;

5✔

210

    boost::depth_first_search(graph, visitor, boost::make_assoc_property_map(vertex_colors), start);

5✔

212

    return back_edges;

5✔

213

};

5✔

215

void all_simple_paths_dfs(

12✔

223

    const Vertex u = boost::target(edge, graph);

12✔

224

    if (visited.find(u) != visited.end()) {

12✔

228

    current_path.push_back(edge);

12✔

229

    visited.insert(u);

12✔

231

    if (u == v) {

12✔

232

        all_paths.push_back(std::list<Edge>(current_path));

4✔

234

        current_path.pop_back();

4✔

235

        visited.erase(u);

4✔

236

        return;

4✔

239

    auto [eb, ee] = boost::out_edges(u, graph);

16✔

240

    auto edges = std::ranges::subrange(eb, ee);

16✔

241

    for (auto next_edge : edges) {

16✔

242

        all_simple_paths_dfs(graph, next_edge, v, all_paths, current_path, visited);

8✔

245

    current_path.pop_back();

8✔

246

    visited.erase(u);

8✔

247

};

12✔

249

const std::list<std::list<Edge>> all_simple_paths(const Graph& graph, const Vertex src, const Vertex dst) {

2✔

250

    std::list<std::list<Edge>> all_paths;

2✔

252

    std::set<Vertex> visited;

2✔

253

    std::list<Edge> current_path;

2✔

255

    auto [eb, ee] = boost::out_edges(src, graph);

2✔

256

    auto edges = std::ranges::subrange(eb, ee);

4✔

257

    for (auto edge : edges) {

6✔

258

        all_simple_paths_dfs(graph, edge, dst, all_paths, current_path, visited);

4✔

261

    return all_paths;

2✔

262

};

2✔

daisytuner / sdfglib / 17656823807

Source File
Press 'n' to go to next uncovered line, 'b' for previous

1	#include "sdfg/graph/graph.h"
2
3	namespace sdfg {
4	namespace graph {
5
6	const ReverseGraph reverse(const Graph& graph) { return boost::reverse_graph<Graph>(graph); };	149✔
7
8	const std::tuple<
9	std::unique_ptr<const UndirectedGraph>,
10	const std::unordered_map<Vertex, Vertex>,
11	const std::unordered_map<Vertex, Vertex>>
12	undirected(const Graph& graph) {	4✔
13	auto undirected_graph = std::make_unique<UndirectedGraph>();	4✔
14	std::unordered_map<Vertex, Vertex> mapping;	4✔
15	std::unordered_map<Vertex, Vertex> reverse_mapping;	4✔
16
17	boost::graph_traits<Graph>::vertex_iterator vi, vend;	4✔
18	for (boost::tie(vi, vend) = boost::vertices(graph); vi != vend; ++vi) {	24✔
19	auto new_vertex = boost::add_vertex(*undirected_graph);	20✔
20	mapping.emplace(*vi, new_vertex);	20✔
21	reverse_mapping.emplace(new_vertex, *vi);	20✔
22	}	20✔
23
24	auto [eb, ee] = boost::edges(graph);	4✔
25	auto edges = std::ranges::subrange(eb, ee);	8✔
26	for (const auto& edge : edges) {	18✔
27	const auto& u = boost::source(edge, graph);	14✔
28	const auto& v = boost::target(edge, graph);	14✔
29	boost::add_edge(mapping.at(u), mapping.at(v), *undirected_graph);	14✔
30	}
31
32	return {std::move(undirected_graph), mapping, reverse_mapping};	4✔
33	};	4✔
34
35	const std::list<Vertex> depth_first_search(const Graph& graph, const graph::Vertex start) {	1✔
36	std::list<Vertex> nodes;	1✔
37	std::list<Edge> back_edges;	1✔
38	DFSVisitor visitor(back_edges, nodes);	1✔
39
40	std::unordered_map<graph::Vertex, boost::default_color_type> vertex_colors;	1✔
41	boost::depth_first_search(graph, visitor, boost::make_assoc_property_map(vertex_colors), start);	1✔
42
43	return nodes;	1✔
44	};	1✔
45
46	std::pair<int, std::unordered_map<Vertex, size_t>> strongly_connected_components(const Graph& graph) {	1✔
47	IndexMap vertex_index_map;	1✔
48	boost::associative_property_map<IndexMap> boost_index_map(vertex_index_map);	1✔
49	boost::graph_traits<Graph>::vertex_iterator vi, vend;	1✔
50	size_t i = 0;	1✔
51	for (boost::tie(vi, vend) = boost::vertices(graph); vi != vend; ++vi, ++i) {	4✔
52	boost::put(boost_index_map, *vi, i);	3✔
53	}	3✔
54
55	std::unordered_map<Vertex, size_t> component_map;	1✔
56	boost::associative_property_map<IndexMap> boost_component_map(component_map);	1✔
57
58	size_t num_ccs = boost::strong_components(graph, boost_component_map, boost::vertex_index_map(boost_index_map));	1✔
59
60	return {num_ccs, component_map};	1✔
61	};	1✔
62
63	std::pair<size_t, const std::unordered_map<Vertex, size_t>> weakly_connected_components(const Graph& graph) {	3✔
64	const auto& undirected_graph = undirected(graph);	3✔
65
66	IndexMap vertex_index_map;	3✔
67	boost::associative_property_map<IndexMap> boost_index_map(vertex_index_map);	3✔
68	boost::graph_traits<UndirectedGraph>::vertex_iterator vi, vend;	3✔
69	size_t i = 0;	3✔
70	for (boost::tie(vi, vend) = boost::vertices(*std::get<0>(undirected_graph)); vi != vend; ++vi, ++i) {	21✔
71	boost::put(boost_index_map, *vi, i);	18✔
72	}	18✔
73
74	std::unordered_map<Vertex, size_t> undirected_component_map;	3✔
75	boost::associative_property_map<std::unordered_map<Vertex, size_t>> boost_component_map(undirected_component_map);	3✔
76
77	size_t num_ccs = boost::connected_components(	3✔
78	*std::get<0>(undirected_graph), boost_component_map, boost::vertex_index_map(boost_index_map)	3✔
79	);
80
81	std::unordered_map<Vertex, size_t> component_map;	3✔
82	for (const auto& entry : undirected_component_map) {	21✔
83	component_map.emplace(std::get<2>(undirected_graph).at(entry.first), entry.second);	18✔
84	}
85
86	return {num_ccs, component_map};	3✔
87	};	3✔
88
89	const std::unordered_map<Vertex, Vertex> dominator_tree(const Graph& graph, const Vertex src) {	144✔
90	std::unordered_map<Vertex, Vertex> dom_tree;	144✔
91
92	IndexMap vertex_index_map;	144✔
93	boost::associative_property_map<IndexMap> boost_index_map(vertex_index_map);	144✔
94	boost::graph_traits<Graph>::vertex_iterator vi, vend;	144✔
95	size_t i = 0;	144✔
96	for (boost::tie(vi, vend) = boost::vertices(graph); vi != vend; ++vi, ++i) {	2,313✔
97	boost::put(boost_index_map, *vi, i);	2,169✔
98	}	2,169✔
99
100	std::vector<size_t> df_num(num_vertices(graph), 0);	144✔
101	auto df_num_map(boost::make_iterator_property_map(df_num.begin(), boost_index_map));	144✔
102
103	std::vector<Vertex> parent(num_vertices(graph), boost::graph_traits<Graph>::null_vertex());	144✔
104	auto parent_map(boost::make_iterator_property_map(parent.begin(), boost_index_map));	144✔
105
106	std::vector<Vertex> dom_tree_vec(num_vertices(graph), boost::graph_traits<Graph>::null_vertex());	144✔
107	auto dom_tree_pred_map(boost::make_iterator_property_map(dom_tree_vec.begin(), boost_index_map));	144✔
108
109	std::vector<Vertex> vertices_by_df_num(parent);	144✔
110
111	boost::lengauer_tarjan_dominator_tree(	144✔
112	graph, src, boost_index_map, df_num_map, parent_map, vertices_by_df_num, dom_tree_pred_map	144✔
113	);
114
115	for (const auto& entry : vertex_index_map) {	2,313✔
116	dom_tree.insert({entry.first, dom_tree_vec[entry.second]});	2,169✔
117	}
118
119	return dom_tree;	144✔
120	};	144✔
121
122	const std::unordered_map<Vertex, Vertex> post_dominator_tree(Graph& graph) {	148✔
123	// Determine terminal vertices
124	std::unordered_set<Vertex> terminal_vertices;	148✔
125	for (auto [vb, ve] = boost::vertices(graph); vb != ve; ++vb) {	2,482✔
126	if (boost::out_degree(*vb, graph) == 0) {	2,186✔
127	terminal_vertices.insert(*vb);	148✔
128	}	148✔
129	}	2,186✔
130	assert(!terminal_vertices.empty());	148✔
131
132	// add synthetic super-terminal if needed
133	bool modified = false;	148✔
134	graph::Vertex src;
135	if (terminal_vertices.size() == 1) {	148✔
136	src = *terminal_vertices.begin();	148✔
137	modified = false;	148✔
138	} else {	148✔
NEW 139	src = boost::add_vertex(graph);	×
NEW 140	for (const auto& v : terminal_vertices) {	×
NEW 141	boost::add_edge(v, src, graph);	×
142	}
NEW 143	modified = true;	×
144	}
145
146	auto& rgraph = reverse(graph);	148✔
147
148	std::unordered_map<Vertex, Vertex> pdom_tree;	148✔
149
150	IndexMap vertex_index_map;	148✔
151	boost::associative_property_map<IndexMap> boost_index_map(vertex_index_map);	148✔
152	boost::graph_traits<Graph>::vertex_iterator vi, vend;	148✔
153	size_t i = 0;	148✔
154	for (boost::tie(vi, vend) = boost::vertices(rgraph); vi != vend; ++vi, ++i) {	2,334✔
155	boost::put(boost_index_map, *vi, i);	2,186✔
156	}	2,186✔
157
158	std::vector<size_t> df_num(num_vertices(rgraph), 0);	148✔
159	auto df_num_map(boost::make_iterator_property_map(df_num.begin(), boost_index_map));	148✔
160
161	std::vector<Vertex> parent(num_vertices(rgraph), boost::graph_traits<Graph>::null_vertex());	148✔
162	auto parent_map(boost::make_iterator_property_map(parent.begin(), boost_index_map));	148✔
163
164	std::vector<Vertex> pdom_tree_vec(num_vertices(rgraph), boost::graph_traits<Graph>::null_vertex());	148✔
165	auto pdom_tree_pred_map(boost::make_iterator_property_map(pdom_tree_vec.begin(), boost_index_map));	148✔
166
167	std::vector<Vertex> vertices_by_df_num(parent);	148✔
168
169	boost::lengauer_tarjan_dominator_tree(	148✔
170	rgraph, src, boost_index_map, df_num_map, parent_map, vertices_by_df_num, pdom_tree_pred_map	148✔
171	);
172
173	for (const auto& entry : vertex_index_map) {	2,334✔
174	pdom_tree.insert({entry.first, pdom_tree_vec[entry.second]});	2,186✔
175	}
176
177	// Remove synthetic super-terminal if added
178	if (modified) {	148✔
NEW 179	boost::clear_vertex(src, graph);	×
NEW 180	}	×
181
182	return pdom_tree;	148✔
183	};	148✔
184
185	const std::list<graph::Vertex> topological_sort(const Graph& graph) {	576✔
186	std::unordered_map<graph::Vertex, boost::default_color_type> vertex_colors;	576✔
187	std::list<graph::Vertex> order;	576✔
188	boost::topological_sort(	576✔
189	graph, std::back_inserter(order), boost::color_map(boost::make_assoc_property_map(vertex_colors))	576✔
190	);
191	order.reverse();	575✔
192	return order;	575✔
193	};	576✔
194
195	bool is_acyclic(const Graph& graph) {	2✔
196	try {
197	topological_sort(graph);	2✔
198	return true;	1✔
199	} catch (boost::not_a_dag e) {	1✔
200	return false;	1✔
201	}	1✔
202	};	3✔
203
204	const std::list<Edge> back_edges(const Graph& graph, const graph::Vertex start) {	5✔
205	std::list<Vertex> nodes;	5✔
206	std::list<Edge> back_edges;	5✔
207	DFSVisitor visitor(back_edges, nodes);	5✔
208
209	std::unordered_map<graph::Vertex, boost::default_color_type> vertex_colors;	5✔
210	boost::depth_first_search(graph, visitor, boost::make_assoc_property_map(vertex_colors), start);	5✔
211
212	return back_edges;	5✔
213	};	5✔
214
215	void all_simple_paths_dfs(	12✔
216	const Graph& graph,
217	const Edge edge,
218	const Vertex v,
219	std::list<std::list<Edge>>& all_paths,
220	std::list<Edge>& current_path,
221	std::set<Vertex>& visited
222	) {
223	const Vertex u = boost::target(edge, graph);	12✔
224	if (visited.find(u) != visited.end()) {	12✔
225	return;	×
226	}
227
228	current_path.push_back(edge);	12✔
229	visited.insert(u);	12✔
230
231	if (u == v) {	12✔
232	all_paths.push_back(std::list<Edge>(current_path));	4✔
233
234	current_path.pop_back();	4✔
235	visited.erase(u);	4✔
236	return;	4✔
237	}
238
239	auto [eb, ee] = boost::out_edges(u, graph);	16✔
240	auto edges = std::ranges::subrange(eb, ee);	16✔
241	for (auto next_edge : edges) {	16✔
242	all_simple_paths_dfs(graph, next_edge, v, all_paths, current_path, visited);	8✔
243	}
244
245	current_path.pop_back();	8✔
246	visited.erase(u);	8✔
247	};	12✔
248
249	const std::list<std::list<Edge>> all_simple_paths(const Graph& graph, const Vertex src, const Vertex dst) {	2✔
250	std::list<std::list<Edge>> all_paths;	2✔
251
252	std::set<Vertex> visited;	2✔
253	std::list<Edge> current_path;	2✔
254
255	auto [eb, ee] = boost::out_edges(src, graph);	2✔
256	auto edges = std::ranges::subrange(eb, ee);	4✔
257	for (auto edge : edges) {	6✔
258	all_simple_paths_dfs(graph, edge, dst, all_paths, current_path, visited);	4✔
259	}
260
261	return all_paths;	2✔
262	};	2✔
263
264	} // namespace graph
265	} // namespace sdfg

daisytuner / sdfglib / 17656823807

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous