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

6

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

162✔

12

undirected(const Graph& graph) {

34✔

13

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

34✔

14

    std::unordered_map<Vertex, Vertex> mapping;

34✔

15

    std::unordered_map<Vertex, Vertex> reverse_mapping;

34✔

17

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

34✔

18

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

231✔

19

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

197✔

20

        mapping.emplace(*vi, new_vertex);

197✔

21

        reverse_mapping.emplace(new_vertex, *vi);

197✔

22

197✔

24

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

34✔

25

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

34✔

26

    for (const auto& edge : edges) {

173✔

27

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

173✔

28

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

173✔

29

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

173✔

30

173✔

32

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

34✔

33

};

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✔

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) {

33✔

64

    const auto& undirected_graph = undirected(graph);

33✔

66

    IndexMap vertex_index_map;

33✔

67

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

33✔

68

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

33✔

69

    size_t i = 0;

33✔

70

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

228✔

71

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

195✔

72

195✔

74

    std::unordered_map<Vertex, size_t> undirected_component_map;

33✔

75

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

33✔

77

    size_t num_ccs = boost::connected_components(

33✔

78

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

33✔

79

);

33✔

81

    std::unordered_map<Vertex, size_t> component_map;

33✔

82

    for (const auto& entry : undirected_component_map) {

195✔

83

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

195✔

84

195✔

86

    return {num_ccs, component_map};

33✔

87

};

33✔

89

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

158✔

90

    std::unordered_map<Vertex, Vertex> dom_tree;

158✔

92

    IndexMap vertex_index_map;

158✔

93

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

158✔

94

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

158✔

95

    size_t i = 0;

158✔

96

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

2,424✔

97

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

2,266✔

98

2,266✔

100

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

158✔

101

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

158✔

103

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

158✔

104

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

158✔

106

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

158✔

107

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

158✔

109

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

158✔

111

    boost::lengauer_tarjan_dominator_tree(

158✔

112

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

158✔

113

);

158✔

115

    for (const auto& entry : vertex_index_map) {

2,266✔

116

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

2,266✔

117

2,266✔

119

    return dom_tree;

158✔

120

};

158✔

122

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

161✔

124

    std::unordered_set<Vertex> terminal_vertices;

161✔

125

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

2,430✔

126

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

2,269✔

127

            terminal_vertices.insert(*vb);

162✔

128

162✔

129

2,269✔

130

    assert(!terminal_vertices.empty());

161✔

133

    bool modified = false;

161✔

134

    graph::Vertex src;

161✔

135

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

161✔

136

        src = *terminal_vertices.begin();

160✔

137

        modified = false;

160✔

138

    } else {

160✔

139

        src = boost::add_vertex(graph);

1✔

140

        for (const auto& v : terminal_vertices) {

2✔

141

            boost::add_edge(v, src, graph);

2✔

142

2✔

143

        modified = true;

1✔

144

1✔

146

    auto& rgraph = reverse(graph);

161✔

148

    std::unordered_map<Vertex, Vertex> pdom_tree;

161✔

150

    IndexMap vertex_index_map;

161✔

151

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

161✔

152

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

161✔

153

    size_t i = 0;

161✔

154

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

2,431✔

155

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

2,270✔

156

2,270✔

158

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

161✔

159

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

161✔

161

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

161✔

162

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

161✔

164

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

161✔

165

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

161✔

167

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

161✔

169

    boost::lengauer_tarjan_dominator_tree(

161✔

170

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

161✔

171

);

161✔

173

    for (const auto& entry : vertex_index_map) {

2,270✔

174

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

2,270✔

175

2,270✔

178

    if (modified) {

161✔

179

        boost::clear_vertex(src, graph);

1✔

180

1✔

182

    return pdom_tree;

161✔

183

};

161✔

185

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

647✔

186

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

647✔

187

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

647✔

188

    boost::topological_sort(

647✔

189

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

647✔

190

);

647✔

191

    order.reverse();

647✔

192

    return order;

647✔

193

};

647✔

195

bool is_acyclic(const Graph& graph) {

2✔

196

    try {

2✔

197

        topological_sort(graph);

2✔

198

        return true;

2✔

199

    } catch (boost::not_a_dag e) {

2✔

200

        return false;

1✔

201

1✔

202

};

2✔

204

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

17✔

205

    std::list<Vertex> nodes;

17✔

206

    std::list<Edge> back_edges;

17✔

207

    DFSVisitor visitor(back_edges, nodes);

17✔

209

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

17✔

210

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

17✔

212

    return back_edges;

17✔

213

};

17✔

222

) {

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✔

237

4✔

239

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

8✔

240

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

8✔

241

    for (auto next_edge : edges) {

8✔

242

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

8✔

243

8✔

245

    current_path.pop_back();

8✔

246

    visited.erase(u);

8✔

247

};

8✔

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);

2✔

257

    for (auto edge : edges) {

4✔

258

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

4✔

259

4✔

261

    return all_paths;

2✔

262

};

2✔

daisytuner / sdfglib / 20770413849

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); };	162✔
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) {	34✔
13	auto undirected_graph = std::make_unique<UndirectedGraph>();	34✔
14	std::unordered_map<Vertex, Vertex> mapping;	34✔
15	std::unordered_map<Vertex, Vertex> reverse_mapping;	34✔
16
17	boost::graph_traits<Graph>::vertex_iterator vi, vend;	34✔
18	for (boost::tie(vi, vend) = boost::vertices(graph); vi != vend; ++vi) {	231✔
19	auto new_vertex = boost::add_vertex(*undirected_graph);	197✔
20	mapping.emplace(*vi, new_vertex);	197✔
21	reverse_mapping.emplace(new_vertex, *vi);	197✔
22	}	197✔
23
24	auto [eb, ee] = boost::edges(graph);	34✔
25	auto edges = std::ranges::subrange(eb, ee);	34✔
26	for (const auto& edge : edges) {	173✔
27	const auto& u = boost::source(edge, graph);	173✔
28	const auto& v = boost::target(edge, graph);	173✔
29	boost::add_edge(mapping.at(u), mapping.at(v), *undirected_graph);	173✔
30	}	173✔
31
32	return {std::move(undirected_graph), mapping, reverse_mapping};	34✔
33	};	34✔
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) {	33✔
64	const auto& undirected_graph = undirected(graph);	33✔
65
66	IndexMap vertex_index_map;	33✔
67	boost::associative_property_map<IndexMap> boost_index_map(vertex_index_map);	33✔
68	boost::graph_traits<UndirectedGraph>::vertex_iterator vi, vend;	33✔
69	size_t i = 0;	33✔
70	for (boost::tie(vi, vend) = boost::vertices(*std::get<0>(undirected_graph)); vi != vend; ++vi, ++i) {	228✔
71	boost::put(boost_index_map, *vi, i);	195✔
72	}	195✔
73
74	std::unordered_map<Vertex, size_t> undirected_component_map;	33✔
75	boost::associative_property_map<std::unordered_map<Vertex, size_t>> boost_component_map(undirected_component_map);	33✔
76
77	size_t num_ccs = boost::connected_components(	33✔
78	*std::get<0>(undirected_graph), boost_component_map, boost::vertex_index_map(boost_index_map)	33✔
79	);	33✔
80
81	std::unordered_map<Vertex, size_t> component_map;	33✔
82	for (const auto& entry : undirected_component_map) {	195✔
83	component_map.emplace(std::get<2>(undirected_graph).at(entry.first), entry.second);	195✔
84	}	195✔
85
86	return {num_ccs, component_map};	33✔
87	};	33✔
88
89	const std::unordered_map<Vertex, Vertex> dominator_tree(const Graph& graph, const Vertex src) {	158✔
90	std::unordered_map<Vertex, Vertex> dom_tree;	158✔
91
92	IndexMap vertex_index_map;	158✔
93	boost::associative_property_map<IndexMap> boost_index_map(vertex_index_map);	158✔
94	boost::graph_traits<Graph>::vertex_iterator vi, vend;	158✔
95	size_t i = 0;	158✔
96	for (boost::tie(vi, vend) = boost::vertices(graph); vi != vend; ++vi, ++i) {	2,424✔
97	boost::put(boost_index_map, *vi, i);	2,266✔
98	}	2,266✔
99
100	std::vector<size_t> df_num(num_vertices(graph), 0);	158✔
101	auto df_num_map(boost::make_iterator_property_map(df_num.begin(), boost_index_map));	158✔
102
103	std::vector<Vertex> parent(num_vertices(graph), boost::graph_traits<Graph>::null_vertex());	158✔
104	auto parent_map(boost::make_iterator_property_map(parent.begin(), boost_index_map));	158✔
105
106	std::vector<Vertex> dom_tree_vec(num_vertices(graph), boost::graph_traits<Graph>::null_vertex());	158✔
107	auto dom_tree_pred_map(boost::make_iterator_property_map(dom_tree_vec.begin(), boost_index_map));	158✔
108
109	std::vector<Vertex> vertices_by_df_num(parent);	158✔
110
111	boost::lengauer_tarjan_dominator_tree(	158✔
112	graph, src, boost_index_map, df_num_map, parent_map, vertices_by_df_num, dom_tree_pred_map	158✔
113	);	158✔
114
115	for (const auto& entry : vertex_index_map) {	2,266✔
116	dom_tree.insert({entry.first, dom_tree_vec[entry.second]});	2,266✔
117	}	2,266✔
118
119	return dom_tree;	158✔
120	};	158✔
121
122	const std::unordered_map<Vertex, Vertex> post_dominator_tree(Graph& graph) {	161✔
123	// Determine terminal vertices
124	std::unordered_set<Vertex> terminal_vertices;	161✔
125	for (auto [vb, ve] = boost::vertices(graph); vb != ve; ++vb) {	2,430✔
126	if (boost::out_degree(*vb, graph) == 0) {	2,269✔
127	terminal_vertices.insert(*vb);	162✔
128	}	162✔
129	}	2,269✔
130	assert(!terminal_vertices.empty());	161✔
131
132	// add synthetic super-terminal if needed
133	bool modified = false;	161✔
134	graph::Vertex src;	161✔
135	if (terminal_vertices.size() == 1) {	161✔
136	src = *terminal_vertices.begin();	160✔
137	modified = false;	160✔
138	} else {	160✔
139	src = boost::add_vertex(graph);	1✔
140	for (const auto& v : terminal_vertices) {	2✔
141	boost::add_edge(v, src, graph);	2✔
142	}	2✔
143	modified = true;	1✔
144	}	1✔
145
146	auto& rgraph = reverse(graph);	161✔
147
148	std::unordered_map<Vertex, Vertex> pdom_tree;	161✔
149
150	IndexMap vertex_index_map;	161✔
151	boost::associative_property_map<IndexMap> boost_index_map(vertex_index_map);	161✔
152	boost::graph_traits<Graph>::vertex_iterator vi, vend;	161✔
153	size_t i = 0;	161✔
154	for (boost::tie(vi, vend) = boost::vertices(rgraph); vi != vend; ++vi, ++i) {	2,431✔
155	boost::put(boost_index_map, *vi, i);	2,270✔
156	}	2,270✔
157
158	std::vector<size_t> df_num(num_vertices(rgraph), 0);	161✔
159	auto df_num_map(boost::make_iterator_property_map(df_num.begin(), boost_index_map));	161✔
160
161	std::vector<Vertex> parent(num_vertices(rgraph), boost::graph_traits<Graph>::null_vertex());	161✔
162	auto parent_map(boost::make_iterator_property_map(parent.begin(), boost_index_map));	161✔
163
164	std::vector<Vertex> pdom_tree_vec(num_vertices(rgraph), boost::graph_traits<Graph>::null_vertex());	161✔
165	auto pdom_tree_pred_map(boost::make_iterator_property_map(pdom_tree_vec.begin(), boost_index_map));	161✔
166
167	std::vector<Vertex> vertices_by_df_num(parent);	161✔
168
169	boost::lengauer_tarjan_dominator_tree(	161✔
170	rgraph, src, boost_index_map, df_num_map, parent_map, vertices_by_df_num, pdom_tree_pred_map	161✔
171	);	161✔
172
173	for (const auto& entry : vertex_index_map) {	2,270✔
174	pdom_tree.insert({entry.first, pdom_tree_vec[entry.second]});	2,270✔
175	}	2,270✔
176
177	// Remove synthetic super-terminal if added
178	if (modified) {	161✔
179	boost::clear_vertex(src, graph);	1✔
180	}	1✔
181
182	return pdom_tree;	161✔
183	};	161✔
184
185	const std::list<graph::Vertex> topological_sort(const Graph& graph) {	647✔
186	std::unordered_map<graph::Vertex, boost::default_color_type> vertex_colors;	647✔
187	std::list<graph::Vertex> order;	647✔
188	boost::topological_sort(	647✔
189	graph, std::back_inserter(order), boost::color_map(boost::make_assoc_property_map(vertex_colors))	647✔
190	);	647✔
191	order.reverse();	647✔
192	return order;	647✔
193	};	647✔
194
195	bool is_acyclic(const Graph& graph) {	2✔
196	try {	2✔
197	topological_sort(graph);	2✔
198	return true;	2✔
199	} catch (boost::not_a_dag e) {	2✔
200	return false;	1✔
201	}	1✔
202	};	2✔
203
204	const std::list<Edge> back_edges(const Graph& graph, const graph::Vertex start) {	17✔
205	std::list<Vertex> nodes;	17✔
206	std::list<Edge> back_edges;	17✔
207	DFSVisitor visitor(back_edges, nodes);	17✔
208
209	std::unordered_map<graph::Vertex, boost::default_color_type> vertex_colors;	17✔
210	boost::depth_first_search(graph, visitor, boost::make_assoc_property_map(vertex_colors), start);	17✔
211
212	return back_edges;	17✔
213	};	17✔
214
215	void all_simple_paths_dfs(
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	) {	12✔
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	}	4✔
238
239	auto [eb, ee] = boost::out_edges(u, graph);	8✔
240	auto edges = std::ranges::subrange(eb, ee);	8✔
241	for (auto next_edge : edges) {	8✔
242	all_simple_paths_dfs(graph, next_edge, v, all_paths, current_path, visited);	8✔
243	}	8✔
244
245	current_path.pop_back();	8✔
246	visited.erase(u);	8✔
247	};	8✔
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);	2✔
257	for (auto edge : edges) {	4✔
258	all_simple_paths_dfs(graph, edge, dst, all_paths, current_path, visited);	4✔
259	}	4✔
260
261	return all_paths;	2✔
262	};	2✔
263
264	} // namespace graph
265	} // namespace sdfg

daisytuner / sdfglib / 20770413849

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