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> |
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> |
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> |
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> |
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> |
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> |
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> |
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> |
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> |
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> |
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 | } |
174 | vertex_descriptor v = *comp.begin(); |
175 | if (hasSelfLoop(v, g)) { |
176 | rv.insert(v); |
177 | } |
178 | } |
179 | |
180 | return rv; |
181 | } |
182 | |
183 | template <class Graph> |
184 | bool 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 | |
198 | struct found_back_edge {}; |
199 | struct 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 | |
213 | template <class Graph> |
214 | bool 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 | |
224 | template<typename Cont> |
225 | class vertex_recorder : public boost::default_dfs_visitor { |
226 | public: |
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 | |
235 | template<typename Cont> |
236 | vertex_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 | */ |
245 | template<typename Bitset> |
246 | class vertex_index_bitset_recorder : public boost::default_dfs_visitor { |
247 | public: |
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 | |
257 | template<typename Bitset> |
258 | vertex_index_bitset_recorder<Bitset> |
259 | make_vertex_index_bitset_recorder(Bitset &o) { |
260 | return vertex_index_bitset_recorder<Bitset>(o); |
261 | } |
262 | |
263 | template <class Graph> |
264 | std::pair<typename Graph::edge_descriptor, bool> |
265 | add_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 | |
274 | template <class Graph> |
275 | std::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 | |
287 | template <class Graph> |
288 | bool 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 | |
302 | template <class Graph> |
303 | bool 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 | |