15656007340

Committed 14 Jun 2025 08:51PM UTC coverage: 13.234% (-49.9%) from 63.144%

Build # 15656007340

Build Type

Pull #76

github

Committed by

web-flow

Commit Message

Merge 9586c8161 into 413c53212

Pull Request Pull Request #76: New Loop Dependency Analysis

Run Details

361 of 465 new or added lines in 7 files covered. (77.63%)

6215 existing lines in 110 files now uncovered.

1612 of 12181 relevant lines covered (13.23%)

13.64 hits per line

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

35.22

/src/graph/graph.cpp

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

daisytuner / sdfglib / 15656007340

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