1/*
2 * Copyright (c) 2015-2017, Intel Corporation
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 *
7 * * Redistributions of source code must retain the above copyright notice,
8 * this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of Intel Corporation nor the names of its contributors
13 * may be used to endorse or promote products derived from this software
14 * without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** \file
30 * \brief Functions for graph manipulation that aren't in the base BGL toolkit.
31 */
32
33#ifndef UTIL_GRAPH_H
34#define UTIL_GRAPH_H
35
36#include "container.h"
37#include "ue2common.h"
38#include "util/flat_containers.h"
39#include "util/graph_range.h"
40#include "util/unordered.h"
41
42#include <boost/graph/depth_first_search.hpp>
43#include <boost/graph/strong_components.hpp>
44#include <boost/range/adaptor/map.hpp>
45
46#include <algorithm>
47#include <map>
48#include <set>
49#include <utility>
50#include <vector>
51
52namespace ue2 {
53
54/** \brief True if the given vertex has no out-edges. */
55template<class Graph>
56bool isLeafNode(const typename Graph::vertex_descriptor& v, const Graph& g) {
57 return out_degree(v, g) == 0;
58}
59
60/** \brief True if vertex \a v has an edge to itself. */
61template<class Graph>
62bool hasSelfLoop(const typename Graph::vertex_descriptor &v, const Graph &g) {
63 return edge(v, v, g).second;
64}
65
66/** \brief True if any vertex in [it, end) has an edge to itself. */
67template<class Graph, class Iterator>
68bool anySelfLoop(const Graph &g, Iterator it, const Iterator &end) {
69 for (; it != end; ++it) {
70 if (hasSelfLoop(*it, g)) {
71 return true;
72 }
73 }
74
75 return false;
76}
77
78/** \brief Returns the out-degree of vertex \a v, ignoring self-loops. */
79template<class Graph>
80size_t proper_out_degree(const typename Graph::vertex_descriptor &v,
81 const Graph &g) {
82 return out_degree(v, g) - (edge(v, v, g).second ? 1 : 0);
83}
84
85/** \brief Returns the in-degree of vertex \a v, ignoring self-loops. */
86template<class Graph>
87size_t proper_in_degree(const typename Graph::vertex_descriptor &v,
88 const Graph &g) {
89 return in_degree(v, g) - (edge(v, v, g).second ? 1 : 0);
90}
91
92/** \brief True if vertex \a v has at least one successor. */
93template<class Graph>
94bool has_successor(const typename Graph::vertex_descriptor &v, const Graph &g) {
95 return out_degree(v, g) > 0;
96}
97
98/** \brief True if vertex \a v has at least one successor other than itself. */
99template<class Graph>
100bool has_proper_successor(const typename Graph::vertex_descriptor &v,
101 const Graph &g) {
102 typename Graph::adjacency_iterator ai, ae;
103 std::tie(ai, ae) = adjacent_vertices(v, g);
104 if (ai == ae) {
105 return false;
106 }
107 if (*ai == v) {
108 ++ai; // skip self-loop
109 }
110
111 return ai != ae;
112}
113
114/** \brief Find the set of vertices that are reachable from the vertices in \a
115 * sources. */
116template<class Graph, class SourceCont, class OutCont>
117void find_reachable(const Graph &g, const SourceCont &sources, OutCont *out) {
118 using vertex_descriptor = typename Graph::vertex_descriptor;
119 std::unordered_map<vertex_descriptor, boost::default_color_type> colours;
120
121 for (auto v : sources) {
122 boost::depth_first_visit(g, v,
123 boost::make_dfs_visitor(boost::null_visitor()),
124 boost::make_assoc_property_map(colours));
125 }
126
127 for (const auto &e : colours) {
128 out->insert(e.first);
129 }
130}
131
132/** \brief Find the set of vertices that are NOT reachable from the vertices in
133 * \a sources. */
134template<class Graph, class SourceCont, class OutCont>
135void find_unreachable(const Graph &g, const SourceCont &sources, OutCont *out) {
136 using vertex_descriptor = typename Graph::vertex_descriptor;
137 std::unordered_set<vertex_descriptor> reachable;
138
139 find_reachable(g, sources, &reachable);
140
141 for (const auto &v : vertices_range(g)) {
142 if (!contains(reachable, v)) {
143 out->insert(v);
144 }
145 }
146}
147
148template <class Graph>
149flat_set<typename Graph::vertex_descriptor>
150find_vertices_in_cycles(const Graph &g) {
151 using vertex_descriptor = typename Graph::vertex_descriptor;
152
153 std::map<vertex_descriptor, size_t> comp_map;
154
155 boost::strong_components(g, boost::make_assoc_property_map(comp_map));
156
157 std::map<size_t, std::vector<vertex_descriptor>> comps;
158
159 for (const auto &e : comp_map) {
160 comps[e.second].push_back(e.first);
161 }
162
163 flat_set<vertex_descriptor> rv;
164
165 for (const auto &comp : comps | boost::adaptors::map_values) {
166 /* every vertex in a strongly connected component is reachable from
167 * every other vertex in the component. A vertex is involved in a cycle
168 * therefore if it is in a strongly connected component with more than
169 * one vertex or if it is the only vertex and it has a self loop. */
170 assert(!comp.empty());
171 if (comp.size() > 1) {
172 insert(&rv, comp);
173 }
174 vertex_descriptor v = *comp.begin();
175 if (hasSelfLoop(v, g)) {
176 rv.insert(v);
177 }
178 }
179
180 return rv;
181}
182
183template <class Graph>
184bool has_parallel_edge(const Graph &g) {
185 using vertex_descriptor = typename Graph::vertex_descriptor;
186 ue2_unordered_set<std::pair<vertex_descriptor, vertex_descriptor>> seen;
187
188 for (const auto &e : edges_range(g)) {
189 auto u = source(e, g);
190 auto v = target(e, g);
191 if (!seen.emplace(u, v).second) {
192 return true;
193 }
194 }
195 return false;
196}
197
198struct found_back_edge {};
199struct detect_back_edges : public boost::default_dfs_visitor {
200 explicit detect_back_edges(bool ignore_self_in)
201 : ignore_self(ignore_self_in) {}
202 template <class Graph>
203 void back_edge(const typename Graph::edge_descriptor &e,
204 const Graph &g) const {
205 if (ignore_self && source(e, g) == target(e, g)) {
206 return;
207 }
208 throw found_back_edge();
209 }
210 bool ignore_self;
211};
212
213template <class Graph>
214bool is_dag(const Graph &g, bool ignore_self_loops = false) {
215 try {
216 depth_first_search(g, visitor(detect_back_edges(ignore_self_loops)));
217 } catch (const found_back_edge &) {
218 return false;
219 }
220
221 return true;
222}
223
224template<typename Cont>
225class vertex_recorder : public boost::default_dfs_visitor {
226public:
227 explicit vertex_recorder(Cont &o) : out(o) {}
228 template<class G>
229 void discover_vertex(typename Cont::value_type v, const G &) {
230 out.insert(v);
231 }
232 Cont &out;
233};
234
235template<typename Cont>
236vertex_recorder<Cont> make_vertex_recorder(Cont &o) {
237 return vertex_recorder<Cont>(o);
238}
239
240/**
241 * \brief A vertex recorder visitor that sets the bits in the given bitset
242 * type (e.g. boost::dynamic_bitset) corresponding to the indices of the
243 * vertices encountered.
244 */
245template<typename Bitset>
246class vertex_index_bitset_recorder : public boost::default_dfs_visitor {
247public:
248 explicit vertex_index_bitset_recorder(Bitset &o) : out(o) {}
249 template<class Graph>
250 void discover_vertex(typename Graph::vertex_descriptor v, const Graph &g) {
251 assert(g[v].index < out.size());
252 out.set(g[v].index);
253 }
254 Bitset &out;
255};
256
257template<typename Bitset>
258vertex_index_bitset_recorder<Bitset>
259make_vertex_index_bitset_recorder(Bitset &o) {
260 return vertex_index_bitset_recorder<Bitset>(o);
261}
262
263template <class Graph>
264std::pair<typename Graph::edge_descriptor, bool>
265add_edge_if_not_present(typename Graph::vertex_descriptor u,
266 typename Graph::vertex_descriptor v, Graph &g) {
267 std::pair<typename Graph::edge_descriptor, bool> e = edge(u, v, g);
268 if (!e.second) {
269 e = add_edge(u, v, g);
270 }
271 return e;
272}
273
274template <class Graph>
275std::pair<typename Graph::edge_descriptor, bool> add_edge_if_not_present(
276 typename Graph::vertex_descriptor u, typename Graph::vertex_descriptor v,
277 const typename Graph::edge_property_type &prop, Graph &g) {
278 std::pair<typename Graph::edge_descriptor, bool> e = edge(u, v, g);
279 if (!e.second) {
280 e = add_edge(u, v, prop, g);
281 }
282 return e;
283}
284
285#ifndef NDEBUG
286
287template <class Graph>
288bool hasCorrectlyNumberedVertices(const Graph &g) {
289 auto count = num_vertices(g);
290 std::vector<bool> ids(count, false);
291 for (auto v : vertices_range(g)) {
292 auto id = g[v].index;
293 if (id >= count || ids[id]) {
294 return false; // duplicate
295 }
296 ids[id] = true;
297 }
298 return std::find(ids.begin(), ids.end(), false) == ids.end()
299 && count == vertex_index_upper_bound(g);
300}
301
302template <class Graph>
303bool hasCorrectlyNumberedEdges(const Graph &g) {
304 auto count = num_edges(g);
305 std::vector<bool> ids(count, false);
306 for (const auto &e : edges_range(g)) {
307 auto id = g[e].index;
308 if (id >= count || ids[id]) {
309 return false; // duplicate
310 }
311 ids[id] = true;
312 }
313 return std::find(ids.begin(), ids.end(), false) == ids.end()
314 && count == edge_index_upper_bound(g);
315}
316
317#endif
318
319} // namespace ue2
320
321#endif // UTIL_GRAPH_H
322