16 #ifndef UTIL_GRAPH_UTIL_H_
17 #define UTIL_GRAPH_UTIL_H_
26 #include "absl/container/flat_hash_map.h"
27 #include "absl/container/inlined_vector.h"
51 template <
class Graph>
53 template <
class Graph>
55 template <
class Graph>
57 template <
class Graph>
61 template <
class Graph>
69 template <
class Graph>
71 const std::vector<int>& new_node_index);
83 template <
class Graph>
85 const std::vector<int>& nodes);
98 template <
class Graph>
104 typedef typename Graph::OutgoingOrOppositeIncomingArcIterator
ArcIterator;
111 return graph_.
Head(ArcIterator::operator*());
120 const auto& arc_range = graph_.OutgoingOrOppositeIncomingArcs(node);
132 template <
class Graph>
149 template <
class Graph>
162 template <
class Graph>
166 template <
class Graph>
184 template <
class Graph>
186 bool die_if_not_symmetric);
190 template <
class Graph>
193 if (graph.
Tail(arc) == graph.
Head(arc))
return true;
198 template <
class Graph>
202 std::vector<bool> tmp_node_mask(graph.
num_nodes(),
false);
206 if (tmp_node_mask[
head])
return true;
207 tmp_node_mask[
head] =
true;
210 tmp_node_mask[graph.
Head(arc)] =
false;
216 template <
class Graph>
228 reverse_graph.
Build();
230 std::vector<ArcIndex> count(graph.
num_nodes(), 0);
233 ++count[graph.
Head(arc)];
236 if (--count[reverse_graph.
Head(arc)] < 0)
return false;
239 if (count[graph.
Head(arc)] != 0)
return false;
245 template <
class Graph>
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.");
261 template <
class Graph>
263 std::unique_ptr<Graph> new_graph(
265 for (
const auto node : graph.
AllNodes()) {
267 new_graph->AddArc(node, graph.
Head(arc));
274 template <
class Graph>
276 const std::vector<int>& new_node_index) {
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()));
285 new_graph->AddArc(new_node_index[node],
286 new_node_index[old_graph.
Head(arc)]);
293 template <
class Graph>
295 const std::vector<int>& nodes) {
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;
308 if (new_node_index[old_graph.
Head(arc)] != -1) ++num_arcs;
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];
319 const NodeIndex new_head = new_node_index[old_graph.
Head(arc)];
320 if (new_head != -1) new_graph->AddArc(new_tail, new_head);
327 template <
class Graph>
332 std::vector<bool> tmp_node_mask(graph.
num_nodes(),
false);
337 tmp_node_mask[
head] =
true;
342 tmp_node_mask[graph.
Head(arc)] =
false;
349 template <
class Graph>
351 if (arc_path->empty())
return;
354 std::map<int, int> last_arc_leaving_node;
355 for (
const int arc : *arc_path) last_arc_leaving_node[graph.
Tail(arc)] = arc;
359 last_arc_leaving_node[graph.
Head(arc_path->back())] = -1;
363 int node = graph.
Tail(arc_path->front());
365 while (new_size < arc_path->size()) {
367 if (arc == -1)
break;
368 (*arc_path)[new_size++] = arc;
369 node = graph.
Head(arc);
371 arc_path->resize(new_size);
374 template <
class Graph>
376 if (arc_path.empty())
return false;
378 seen.insert(graph.
Tail(arc_path.front()));
379 for (
const int arc : arc_path) {
385 template <
class Graph>
387 const Graph& graph,
bool die_if_not_symmetric) {
388 std::vector<int> reverse_arc(graph.
num_arcs(), -1);
392 absl::flat_hash_map<std::pair< int,
int>,
393 absl::InlinedVector<int, 4>>
396 for (
int arc = 0; arc < graph.
num_arcs(); ++arc) {
401 reverse_arc[arc] = arc;
405 auto it = arc_map.find({
head,
tail});
406 if (it != arc_map.end()) {
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();
418 arc_map[{
tail,
head}].push_back(arc);
423 int64 num_unmapped_arcs = 0;
424 for (
const auto& p : arc_map) {
425 num_unmapped_arcs += p.second.size();
427 DCHECK_EQ(std::count(reverse_arc.begin(), reverse_arc.end(), -1),
430 if (die_if_not_symmetric) {
432 <<
"The graph is not symmetric: " << arc_map.size() <<
" of "
433 << graph.
num_arcs() <<
" arcs did not have a reverse.";
#define CHECK_EQ(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
void AddEdge(int node1, int node2)
void SetNumberOfNodes(int num_nodes)
int GetNumberOfComponents() const
IntegerRange< ArcIndex > AllForwardArcs() const
ArcIndexType num_arcs() const
NodeIndexType num_nodes() const
IntegerRange< NodeIndex > AllNodes() const
NodeIndexType Tail(ArcIndexType arc) const
NodeIndexType Head(ArcIndexType arc) const
BeginEndWrapper< OutgoingArcIterator > OutgoingArcs(NodeIndexType node) const
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
NodeIndexType Head(ArcIndexType arc) const
BeginEndWrapper< OutgoingArcIterator > OutgoingArcs(NodeIndexType node) const
Graph::NodeIndex operator*() const
AdjacencyListIterator(const Graph &graph, ArcIterator &&arc_it)
UndirectedAdjacencyListsOfDirectedGraph(const Graph &graph)
Graph::OutgoingOrOppositeIncomingArcIterator ArcIterator
BeginEndWrapper< AdjacencyListIterator > operator[](int node) const
bool InsertIfNotPresent(Collection *const collection, const typename Collection::value_type &value)
const Collection::value_type::second_type & FindOrDie(const Collection &collection, const typename Collection::value_type::first_type &key)
std::vector< int > ComputeOnePossibleReverseArcMapping(const Graph &graph, bool die_if_not_symmetric)
bool PathHasCycle(const Graph &graph, const std::vector< int > &arc_path)
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)
bool GraphHasDuplicateArcs(const Graph &graph)
std::unique_ptr< Graph > RemoveSelfArcsAndDuplicateArcs(const Graph &graph)
std::unique_ptr< Graph > GetSubgraphOfNodes(const Graph &graph, const std::vector< int > &nodes)
bool GraphHasSelfArcs(const Graph &graph)
bool GraphIsSymmetric(const Graph &graph)
std::unique_ptr< Graph > RemapGraph(const Graph &graph, const std::vector< int > &new_node_index)
std::vector< int > GetWeaklyConnectedComponents(const Graph &graph)
bool GraphIsWeaklyConnected(const Graph &graph)
bool IsValidPermutation(const std::vector< int > &v)
std::unique_ptr< Graph > CopyGraph(const Graph &graph)