C++ Reference

C++ Reference: Graph

util.h
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14// A collections of utilities for the Graph classes in ./graph.h.
15
16#ifndef UTIL_GRAPH_UTIL_H_
17#define UTIL_GRAPH_UTIL_H_
18
19#include <algorithm>
20#include <map>
21#include <memory>
22#include <set>
23#include <string>
24#include <vector>
25
26#include "absl/container/flat_hash_map.h"
27#include "absl/container/inlined_vector.h"
28#include "ortools/base/hash.h"
29#include "ortools/base/map_util.h"
31#include "ortools/graph/graph.h"
33
34namespace util {
35
36// Here's a set of simple diagnosis tools. Notes:
37// - A self-arc is an arc from a node to itself.
38// - We say that an arc A->B is duplicate when there is another arc A->B in the
39// same graph.
40// - A graph is said "weakly connected" if it is connected when considering all
41// arcs as undirected edges.
42// - A graph is said "symmetric" iff for all (a, b), the number of arcs a->b
43// is equal to the number of arcs b->a.
44//
45// All these diagnosis work in O(graph size), since the inverse Ackerman
46// function is <= 5 for all practical instances, and are very fast.
47//
48// If the graph is a "static" kind, they must be finalized, except for
49// GraphHasSelfArcs() and GraphIsWeaklyConnected() which also support
50// non-finalized StaticGraph<>.
51template <class Graph>
52bool GraphHasSelfArcs(const Graph& graph);
53template <class Graph>
54bool GraphHasDuplicateArcs(const Graph& graph);
55template <class Graph>
56bool GraphIsSymmetric(const Graph& graph);
57template <class Graph>
58bool GraphIsWeaklyConnected(const Graph& graph);
59
60// Returns a fresh copy of a given graph.
61template <class Graph>
62std::unique_ptr<Graph> CopyGraph(const Graph& graph);
63
64// Creates a remapped copy of graph "graph", where node i becomes node
65// new_node_index[i].
66// "new_node_index" must be a valid permutation of [0..num_nodes-1] or the
67// behavior is undefined (it may die).
68// Note that you can call IsValidPermutation() to check it yourself.
69template <class Graph>
70std::unique_ptr<Graph> RemapGraph(const Graph& graph,
71 const std::vector<int>& new_node_index);
72
73// Gets the induced subgraph of "graph" restricted to the nodes in "nodes":
74// the resulting graph will have exactly nodes.size() nodes, and its
75// node #0 will be the former graph's node #nodes[0], etc.
76// See https://en.wikipedia.org/wiki/Induced_subgraph .
77// The "nodes" must be a valid subset (no repetitions) of
78// [0..graph.num_nodes()-1], or the behavior is undefined (it may die).
79// Note that you can call IsSubsetOf0N() to check it yourself.
80//
81// Current complexity: O(num old nodes + num new arcs). It could easily
82// be done in O(num new nodes + num new arcs) but with a higher constant.
83template <class Graph>
84std::unique_ptr<Graph> GetSubgraphOfNodes(const Graph& graph,
85 const std::vector<int>& nodes);
86
87// This can be used to view a directed graph (that supports reverse arcs)
88// from graph.h as un undirected graph: operator[](node) returns a
89// pseudo-container that iterates over all nodes adjacent to "node" (from
90// outgoing or incoming arcs).
91// CAVEAT: Self-arcs (aka loops) will appear twice.
92//
93// Example:
94// ReverseArcsStaticGraph<> dgraph;
95// ...
96// UndirectedAdjacencyListsOfDirectedGraph<decltype(dgraph)> ugraph(dgraph);
97// for (int neighbor_of_node_42 : ugraph[42]) { ... }
98template <class Graph>
100 public:
102 : graph_(graph) {}
103
104 typedef typename Graph::OutgoingOrOppositeIncomingArcIterator ArcIterator;
106 public:
107 explicit AdjacencyListIterator(const Graph& graph, ArcIterator&& arc_it)
108 : ArcIterator(arc_it), graph_(graph) {}
109 // Overwrite operator* to return the heads of the arcs.
110 typename Graph::NodeIndex operator*() const {
111 return graph_.Head(ArcIterator::operator*());
112 }
113
114 private:
115 const Graph& graph_;
116 };
117
118 // Returns a pseudo-container of all the nodes adjacent to "node".
120 const auto& arc_range = graph_.OutgoingOrOppositeIncomingArcs(node);
121 return {AdjacencyListIterator(graph_, arc_range.begin()),
122 AdjacencyListIterator(graph_, arc_range.end())};
123 }
124
125 private:
126 const Graph& graph_;
127};
128
129// Computes the weakly connected components of a directed graph that
130// provides the OutgoingOrOppositeIncomingArcs() API, and returns them
131// as a mapping from node to component index. See GetConnectedComponens().
132template <class Graph>
133std::vector<int> GetWeaklyConnectedComponents(const Graph& graph) {
136}
137
138// Returns true iff the given vector is a subset of [0..n-1], i.e.
139// all elements i are such that 0 <= i < n and no two elements are equal.
140// "n" must be >= 0 or the result is undefined.
141bool IsSubsetOf0N(const std::vector<int>& v, int n);
142
143// Returns true iff the given vector is a permutation of [0..size()-1].
144inline bool IsValidPermutation(const std::vector<int>& v) {
145 return IsSubsetOf0N(v, v.size());
146}
147
148// Returns a copy of "graph", without self-arcs and duplicate arcs.
149template <class Graph>
150std::unique_ptr<Graph> RemoveSelfArcsAndDuplicateArcs(const Graph& graph);
151
152// Given an arc path, changes it to a sub-path with the same source and
153// destination but without any cycle. Nothing happen if the path was already
154// without cycle.
155//
156// The graph class should support Tail(arc) and Head(arc). They should both
157// return an integer representing the corresponding tail/head of the passed arc.
158//
159// TODO(user): In some cases, there is more than one possible solution. We could
160// take some arc costs and return the cheapest path instead. Or return the
161// shortest path in term of number of arcs.
162template <class Graph>
163void RemoveCyclesFromPath(const Graph& graph, std::vector<int>* arc_path);
164
165// Returns true iff the given path contains a cycle.
166template <class Graph>
167bool PathHasCycle(const Graph& graph, const std::vector<int>& arc_path);
168
169// Returns a vector representing a mapping from arcs to arcs such that each arc
170// is mapped to another arc with its (tail, head) flipped, if such an arc
171// exists (otherwise it is mapped to -1).
172// If the graph is symmetric, the returned mapping is bijective and reflexive,
173// i.e. out[out[arc]] = arc for all "arc", where "out" is the returned vector.
174// If "die_if_not_symmetric" is true, this function CHECKs() that the graph
175// is symmetric.
176//
177// Self-arcs are always mapped to themselves.
178//
179// Note that since graphs may have multi-arcs, the mapping isn't necessarily
180// unique, hence the function name.
181//
182// PERFORMANCE: If you see this function taking too much memory and/or too much
183// time, reach out to viger@: one could halve the memory usage and speed it up.
184template <class Graph>
185std::vector<int> ComputeOnePossibleReverseArcMapping(const Graph& graph,
186 bool die_if_not_symmetric);
187
188// Implementations of the templated methods.
189
190template <class Graph>
191bool GraphHasSelfArcs(const Graph& graph) {
192 for (const auto arc : graph.AllForwardArcs()) {
193 if (graph.Tail(arc) == graph.Head(arc)) return true;
194 }
195 return false;
196}
197
198template <class Graph>
199bool GraphHasDuplicateArcs(const Graph& graph) {
200 typedef typename Graph::ArcIndex ArcIndex;
201 typedef typename Graph::NodeIndex NodeIndex;
202 std::vector<bool> tmp_node_mask(graph.num_nodes(), false);
203 for (const NodeIndex tail : graph.AllNodes()) {
204 for (const ArcIndex arc : graph.OutgoingArcs(tail)) {
205 const NodeIndex head = graph.Head(arc);
206 if (tmp_node_mask[head]) return true;
207 tmp_node_mask[head] = true;
208 }
209 for (const ArcIndex arc : graph.OutgoingArcs(tail)) {
210 tmp_node_mask[graph.Head(arc)] = false;
211 }
212 }
213 return false;
214}
215
216template <class Graph>
217bool GraphIsSymmetric(const Graph& graph) {
218 typedef typename Graph::NodeIndex NodeIndex;
219 typedef typename Graph::ArcIndex ArcIndex;
220 // Create a reverse copy of the graph.
221 StaticGraph<NodeIndex, ArcIndex> reverse_graph(graph.num_nodes(),
222 graph.num_arcs());
223 for (const NodeIndex node : graph.AllNodes()) {
224 for (const ArcIndex arc : graph.OutgoingArcs(node)) {
225 reverse_graph.AddArc(graph.Head(arc), node);
226 }
227 }
228 reverse_graph.Build();
229 // Compare the graph to its reverse, one adjacency list at a time.
230 std::vector<ArcIndex> count(graph.num_nodes(), 0);
231 for (const NodeIndex node : graph.AllNodes()) {
232 for (const ArcIndex arc : graph.OutgoingArcs(node)) {
233 ++count[graph.Head(arc)];
234 }
235 for (const ArcIndex arc : reverse_graph.OutgoingArcs(node)) {
236 if (--count[reverse_graph.Head(arc)] < 0) return false;
237 }
238 for (const ArcIndex arc : graph.OutgoingArcs(node)) {
239 if (count[graph.Head(arc)] != 0) return false;
240 }
241 }
242 return true;
243}
244
245template <class Graph>
246bool GraphIsWeaklyConnected(const Graph& graph) {
247 typedef typename Graph::NodeIndex NodeIndex;
248 static_assert(std::numeric_limits<NodeIndex>::max() <= INT_MAX,
249 "GraphIsWeaklyConnected() isn't yet implemented for graphs"
250 " that support more than INT_MAX nodes. Reach out to"
251 " or-core-team@ if you need this.");
252 if (graph.num_nodes() == 0) return true;
254 union_find.SetNumberOfNodes(graph.num_nodes());
255 for (typename Graph::ArcIndex arc = 0; arc < graph.num_arcs(); ++arc) {
256 union_find.AddEdge(graph.Tail(arc), graph.Head(arc));
257 }
258 return union_find.GetNumberOfComponents() == 1;
259}
260
261template <class Graph>
262std::unique_ptr<Graph> CopyGraph(const Graph& graph) {
263 std::unique_ptr<Graph> new_graph(
264 new Graph(graph.num_nodes(), graph.num_arcs()));
265 for (const auto node : graph.AllNodes()) {
266 for (const auto arc : graph.OutgoingArcs(node)) {
267 new_graph->AddArc(node, graph.Head(arc));
268 }
269 }
270 new_graph->Build();
271 return new_graph;
272}
273
274template <class Graph>
275std::unique_ptr<Graph> RemapGraph(const Graph& old_graph,
276 const std::vector<int>& new_node_index) {
277 DCHECK(IsValidPermutation(new_node_index)) << "Invalid permutation";
278 const int num_nodes = old_graph.num_nodes();
279 CHECK_EQ(new_node_index.size(), num_nodes);
280 std::unique_ptr<Graph> new_graph(new Graph(num_nodes, old_graph.num_arcs()));
281 typedef typename Graph::NodeIndex NodeIndex;
282 typedef typename Graph::ArcIndex ArcIndex;
283 for (const NodeIndex node : old_graph.AllNodes()) {
284 for (const ArcIndex arc : old_graph.OutgoingArcs(node)) {
285 new_graph->AddArc(new_node_index[node],
286 new_node_index[old_graph.Head(arc)]);
287 }
288 }
289 new_graph->Build();
290 return new_graph;
291}
292
293template <class Graph>
294std::unique_ptr<Graph> GetSubgraphOfNodes(const Graph& old_graph,
295 const std::vector<int>& nodes) {
296 typedef typename Graph::NodeIndex NodeIndex;
297 typedef typename Graph::ArcIndex ArcIndex;
298 DCHECK(IsSubsetOf0N(nodes, old_graph.num_nodes())) << "Invalid subset";
299 std::vector<NodeIndex> new_node_index(old_graph.num_nodes(), -1);
300 for (NodeIndex new_index = 0; new_index < nodes.size(); ++new_index) {
301 new_node_index[nodes[new_index]] = new_index;
302 }
303 // Do a first pass to count the arcs, so that we don't allocate more memory
304 // than needed.
305 ArcIndex num_arcs = 0;
306 for (const NodeIndex node : nodes) {
307 for (const ArcIndex arc : old_graph.OutgoingArcs(node)) {
308 if (new_node_index[old_graph.Head(arc)] != -1) ++num_arcs;
309 }
310 }
311 // A second pass where we actually copy the subgraph.
312 // NOTE(user): there might seem to be a bit of duplication with RemapGraph(),
313 // but there is a key difference: the loop below only iterates on "nodes",
314 // which could be much smaller than all the graph's nodes.
315 std::unique_ptr<Graph> new_graph(new Graph(nodes.size(), num_arcs));
316 for (NodeIndex new_tail = 0; new_tail < nodes.size(); ++new_tail) {
317 const NodeIndex old_tail = nodes[new_tail];
318 for (const ArcIndex arc : old_graph.OutgoingArcs(old_tail)) {
319 const NodeIndex new_head = new_node_index[old_graph.Head(arc)];
320 if (new_head != -1) new_graph->AddArc(new_tail, new_head);
321 }
322 }
323 new_graph->Build();
324 return new_graph;
325}
326
327template <class Graph>
328std::unique_ptr<Graph> RemoveSelfArcsAndDuplicateArcs(const Graph& graph) {
329 std::unique_ptr<Graph> g(new Graph(graph.num_nodes(), graph.num_arcs()));
330 typedef typename Graph::ArcIndex ArcIndex;
331 typedef typename Graph::NodeIndex NodeIndex;
332 std::vector<bool> tmp_node_mask(graph.num_nodes(), false);
333 for (const NodeIndex tail : graph.AllNodes()) {
334 for (const ArcIndex arc : graph.OutgoingArcs(tail)) {
335 const NodeIndex head = graph.Head(arc);
336 if (head != tail && !tmp_node_mask[head]) {
337 tmp_node_mask[head] = true;
338 g->AddArc(tail, head);
339 }
340 }
341 for (const ArcIndex arc : graph.OutgoingArcs(tail)) {
342 tmp_node_mask[graph.Head(arc)] = false;
343 }
344 }
345 g->Build();
346 return g;
347}
348
349template <class Graph>
350void RemoveCyclesFromPath(const Graph& graph, std::vector<int>* arc_path) {
351 if (arc_path->empty()) return;
352
353 // This maps each node to the latest arc in the given path that leaves it.
354 std::map<int, int> last_arc_leaving_node;
355 for (const int arc : *arc_path) last_arc_leaving_node[graph.Tail(arc)] = arc;
356
357 // Special case for the destination.
358 // Note that this requires that -1 is not a valid arc of Graph.
359 last_arc_leaving_node[graph.Head(arc_path->back())] = -1;
360
361 // Reconstruct the path by starting at the source and then following the
362 // "next" arcs. We override the given arc_path at the same time.
363 int node = graph.Tail(arc_path->front());
364 int new_size = 0;
365 while (new_size < arc_path->size()) { // To prevent cycle on bad input.
366 const int arc = gtl::FindOrDie(last_arc_leaving_node, node);
367 if (arc == -1) break;
368 (*arc_path)[new_size++] = arc;
369 node = graph.Head(arc);
370 }
371 arc_path->resize(new_size);
372}
373
374template <class Graph>
375bool PathHasCycle(const Graph& graph, const std::vector<int>& arc_path) {
376 if (arc_path.empty()) return false;
377 std::set<int> seen;
378 seen.insert(graph.Tail(arc_path.front()));
379 for (const int arc : arc_path) {
380 if (!gtl::InsertIfNotPresent(&seen, graph.Head(arc))) return true;
381 }
382 return false;
383}
384
385template <class Graph>
387 const Graph& graph, bool die_if_not_symmetric) {
388 std::vector<int> reverse_arc(graph.num_arcs(), -1);
389 // We need a multi-map since a given (tail,head) may appear several times.
390 // NOTE(user): It's free, in terms of space, to use InlinedVector<int, 4>
391 // rather than std::vector<int>. See go/inlined-vector-size.
392 absl::flat_hash_map<std::pair</*tail*/ int, /*head*/ int>,
393 absl::InlinedVector<int, 4>>
394 arc_map;
395
396 for (int arc = 0; arc < graph.num_arcs(); ++arc) {
397 const int tail = graph.Tail(arc);
398 const int head = graph.Head(arc);
399 if (tail == head) {
400 // Special case: directly map any self-arc to itself.
401 reverse_arc[arc] = arc;
402 continue;
403 }
404 // Lookup for the reverse arc of the current one...
405 auto it = arc_map.find({head, tail});
406 if (it != arc_map.end()) {
407 // Found a reverse arc! Store the mapping and remove the
408 // reverse arc from the map.
409 reverse_arc[arc] = it->second.back();
410 reverse_arc[it->second.back()] = arc;
411 if (it->second.size() > 1) {
412 it->second.pop_back();
413 } else {
414 arc_map.erase(it);
415 }
416 } else {
417 // Reverse arc not in the map. Add the current arc to the map.
418 arc_map[{tail, head}].push_back(arc);
419 }
420 }
421 // Algorithm check, for debugging.
422 if (DEBUG_MODE) {
423 int64 num_unmapped_arcs = 0;
424 for (const auto& p : arc_map) {
425 num_unmapped_arcs += p.second.size();
426 }
427 DCHECK_EQ(std::count(reverse_arc.begin(), reverse_arc.end(), -1),
428 num_unmapped_arcs);
429 }
430 if (die_if_not_symmetric) {
431 CHECK_EQ(arc_map.size(), 0)
432 << "The graph is not symmetric: " << arc_map.size() << " of "
433 << graph.num_arcs() << " arcs did not have a reverse.";
434 }
435 return reverse_arc;
436}
437
438} // namespace util
439
440#endif // UTIL_GRAPH_UTIL_H_
void AddEdge(int node1, int node2)
void SetNumberOfNodes(int num_nodes)
IntegerRange< ArcIndex > AllForwardArcs() const
Definition: graph.h:941
ArcIndexType num_arcs() const
Definition: graph.h:205
NodeIndexType num_nodes() const
Definition: graph.h:202
IntegerRange< NodeIndex > AllNodes() const
Definition: graph.h:935
NodeIndexType Tail(ArcIndexType arc) const
Definition: graph.h:1110
NodeIndexType Head(ArcIndexType arc) const
Definition: graph.h:1117
BeginEndWrapper< OutgoingArcIterator > OutgoingArcs(NodeIndexType node) const
void Build()
Definition: graph.h:435
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
Definition: graph.h:1285
NodeIndexType Head(ArcIndexType arc) const
Definition: graph.h:1313
BeginEndWrapper< OutgoingArcIterator > OutgoingArcs(NodeIndexType node) const
AdjacencyListIterator(const Graph &graph, ArcIterator &&arc_it)
Definition: util.h:107
UndirectedAdjacencyListsOfDirectedGraph(const Graph &graph)
Definition: util.h:101
Graph::OutgoingOrOppositeIncomingArcIterator ArcIterator
Definition: util.h:104
BeginEndWrapper< AdjacencyListIterator > operator[](int node) const
Definition: util.h:119
std::vector< int > ComputeOnePossibleReverseArcMapping(const Graph &graph, bool die_if_not_symmetric)
Definition: util.h:386
ListGraph Graph
Definition: graph.h:2360
bool PathHasCycle(const Graph &graph, const std::vector< int > &arc_path)
Definition: util.h:375
bool IsSubsetOf0N(const std::vector< int > &v, int n)
std::vector< int > GetConnectedComponents(int num_nodes, const UndirectedGraph &graph)
void RemoveCyclesFromPath(const Graph &graph, std::vector< int > *arc_path)
Definition: util.h:350
bool GraphHasDuplicateArcs(const Graph &graph)
Definition: util.h:199
std::vector< int > GetWeaklyConnectedComponents(const Graph &graph)
Definition: util.h:133
std::unique_ptr< Graph > RemoveSelfArcsAndDuplicateArcs(const Graph &graph)
Definition: util.h:328
std::unique_ptr< Graph > GetSubgraphOfNodes(const Graph &graph, const std::vector< int > &nodes)
Definition: util.h:294
bool GraphHasSelfArcs(const Graph &graph)
Definition: util.h:191
bool IsValidPermutation(const std::vector< int > &v)
Definition: util.h:144
bool GraphIsSymmetric(const Graph &graph)
Definition: util.h:217
std::unique_ptr< Graph > RemapGraph(const Graph &graph, const std::vector< int > &new_node_index)
Definition: util.h:275
bool GraphIsWeaklyConnected(const Graph &graph)
Definition: util.h:246
std::unique_ptr< Graph > CopyGraph(const Graph &graph)
Definition: util.h:262