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
52 namespace ue2 {
53
54 /** \brief True if the given vertex has no out-edges. */
55 template<class Graph>
isLeafNode(const typename Graph::vertex_descriptor & v,const Graph & g)56 bool 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. */
61 template<class Graph>
hasSelfLoop(const typename Graph::vertex_descriptor & v,const Graph & g)62 bool 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. */
67 template<class Graph, class Iterator>
anySelfLoop(const Graph & g,Iterator it,const Iterator & end)68 bool 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. */
79 template<class Graph>
proper_out_degree(const typename Graph::vertex_descriptor & v,const Graph & g)80 size_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. */
86 template<class Graph>
proper_in_degree(const typename Graph::vertex_descriptor & v,const Graph & g)87 size_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. */
93 template<class Graph>
has_successor(const typename Graph::vertex_descriptor & v,const Graph & g)94 bool 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. */
99 template<class Graph>
has_proper_successor(const typename Graph::vertex_descriptor & v,const Graph & g)100 bool 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. */
116 template<class Graph, class SourceCont, class OutCont>
find_reachable(const Graph & g,const SourceCont & sources,OutCont * out)117 void 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. */
134 template<class Graph, class SourceCont, class OutCont>
find_unreachable(const Graph & g,const SourceCont & sources,OutCont * out)135 void 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
148 template <class Graph>
149 flat_set<typename Graph::vertex_descriptor>
find_vertices_in_cycles(const Graph & g)150 find_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 continue;
174 }
175 vertex_descriptor v = *comp.begin();
176 if (hasSelfLoop(v, g)) {
177 rv.insert(v);
178 }
179 }
180
181 return rv;
182 }
183
184 template <class Graph>
has_parallel_edge(const Graph & g)185 bool has_parallel_edge(const Graph &g) {
186 using vertex_descriptor = typename Graph::vertex_descriptor;
187 ue2_unordered_set<std::pair<vertex_descriptor, vertex_descriptor>> seen;
188
189 for (const auto &e : edges_range(g)) {
190 auto u = source(e, g);
191 auto v = target(e, g);
192 if (!seen.emplace(u, v).second) {
193 return true;
194 }
195 }
196 return false;
197 }
198
199 struct found_back_edge {};
200 struct detect_back_edges : public boost::default_dfs_visitor {
detect_back_edgesdetect_back_edges201 explicit detect_back_edges(bool ignore_self_in)
202 : ignore_self(ignore_self_in) {}
203 template <class Graph>
back_edgedetect_back_edges204 void back_edge(const typename Graph::edge_descriptor &e,
205 const Graph &g) const {
206 if (ignore_self && source(e, g) == target(e, g)) {
207 return;
208 }
209 throw found_back_edge();
210 }
211 bool ignore_self;
212 };
213
214 template <class Graph>
215 bool is_dag(const Graph &g, bool ignore_self_loops = false) {
216 try {
217 depth_first_search(g, visitor(detect_back_edges(ignore_self_loops)));
catch(const found_back_edge &)218 } catch (const found_back_edge &) {
219 return false;
220 }
221
222 return true;
223 }
224
225 template<typename Cont>
226 class vertex_recorder : public boost::default_dfs_visitor {
227 public:
vertex_recorder(Cont & o)228 explicit vertex_recorder(Cont &o) : out(o) {}
229 template<class G>
discover_vertex(typename Cont::value_type v,const G &)230 void discover_vertex(typename Cont::value_type v, const G &) {
231 out.insert(v);
232 }
233 Cont &out;
234 };
235
236 template<typename Cont>
make_vertex_recorder(Cont & o)237 vertex_recorder<Cont> make_vertex_recorder(Cont &o) {
238 return vertex_recorder<Cont>(o);
239 }
240
241 /**
242 * \brief A vertex recorder visitor that sets the bits in the given bitset
243 * type (e.g. boost::dynamic_bitset) corresponding to the indices of the
244 * vertices encountered.
245 */
246 template<typename Bitset>
247 class vertex_index_bitset_recorder : public boost::default_dfs_visitor {
248 public:
vertex_index_bitset_recorder(Bitset & o)249 explicit vertex_index_bitset_recorder(Bitset &o) : out(o) {}
250 template<class Graph>
discover_vertex(typename Graph::vertex_descriptor v,const Graph & g)251 void discover_vertex(typename Graph::vertex_descriptor v, const Graph &g) {
252 assert(g[v].index < out.size());
253 out.set(g[v].index);
254 }
255 Bitset &out;
256 };
257
258 template<typename Bitset>
259 vertex_index_bitset_recorder<Bitset>
make_vertex_index_bitset_recorder(Bitset & o)260 make_vertex_index_bitset_recorder(Bitset &o) {
261 return vertex_index_bitset_recorder<Bitset>(o);
262 }
263
264 template <class Graph>
265 std::pair<typename Graph::edge_descriptor, bool>
add_edge_if_not_present(typename Graph::vertex_descriptor u,typename Graph::vertex_descriptor v,Graph & g)266 add_edge_if_not_present(typename Graph::vertex_descriptor u,
267 typename Graph::vertex_descriptor v, Graph &g) {
268 std::pair<typename Graph::edge_descriptor, bool> e = edge(u, v, g);
269 if (!e.second) {
270 e = add_edge(u, v, g);
271 }
272 return e;
273 }
274
275 template <class Graph>
add_edge_if_not_present(typename Graph::vertex_descriptor u,typename Graph::vertex_descriptor v,const typename Graph::edge_property_type & prop,Graph & g)276 std::pair<typename Graph::edge_descriptor, bool> add_edge_if_not_present(
277 typename Graph::vertex_descriptor u, typename Graph::vertex_descriptor v,
278 const typename Graph::edge_property_type &prop, Graph &g) {
279 std::pair<typename Graph::edge_descriptor, bool> e = edge(u, v, g);
280 if (!e.second) {
281 e = add_edge(u, v, prop, g);
282 }
283 return e;
284 }
285
286 #ifndef NDEBUG
287
288 template <class Graph>
hasCorrectlyNumberedVertices(const Graph & g)289 bool hasCorrectlyNumberedVertices(const Graph &g) {
290 auto count = num_vertices(g);
291 std::vector<bool> ids(count, false);
292 for (auto v : vertices_range(g)) {
293 auto id = g[v].index;
294 if (id >= count || ids[id]) {
295 return false; // duplicate
296 }
297 ids[id] = true;
298 }
299 return std::find(ids.begin(), ids.end(), false) == ids.end()
300 && count == vertex_index_upper_bound(g);
301 }
302
303 template <class Graph>
hasCorrectlyNumberedEdges(const Graph & g)304 bool hasCorrectlyNumberedEdges(const Graph &g) {
305 auto count = num_edges(g);
306 std::vector<bool> ids(count, false);
307 for (const auto &e : edges_range(g)) {
308 auto id = g[e].index;
309 if (id >= count || ids[id]) {
310 return false; // duplicate
311 }
312 ids[id] = true;
313 }
314 return std::find(ids.begin(), ids.end(), false) == ids.end()
315 && count == edge_index_upper_bound(g);
316 }
317
318 #endif
319
320 } // namespace ue2
321
322 #endif // UTIL_GRAPH_H
323