A collections of i/o utilities for the Graph classes in ./graph.h. More...

Namespaces
namespace	graph

namespace	internal

Classes
class	BaseGraph

class	BeginEndReverseIteratorWrapper

class	BeginEndWrapper

class	CompleteBipartiteGraph

class	CompleteGraph

class	IntegerRange

class	IntegerRangeIterator
	Simple iterator on an integer range, see IntegerRange below. More...

class	ListGraph

struct	MutableVectorIteration
	Allow iterating over a vector<T> as a mutable vector<T*>. More...

class	ReverseArcListGraph

class	ReverseArcMixedGraph

class	ReverseArcStaticGraph

class	StaticGraph

class	StatusBuilder

class	SVector
	Forward declaration. More...

class	TopologicalSorter

class	UndirectedAdjacencyListsOfDirectedGraph

Typedefs
typedef ListGraph	Graph
	Defining the simplest Graph interface as Graph for convenience.

typedef ::util::internal::DenseIntTopologicalSorterTpl< true >	DenseIntStableTopologicalSorter

typedef ::util::internal::DenseIntTopologicalSorterTpl< false >	DenseIntTopologicalSorter

Enumerations
enum	GraphToStringFormat { PRINT_GRAPH_ARCS , PRINT_GRAPH_ADJACENCY_LISTS , PRINT_GRAPH_ADJACENCY_LISTS_SORTED }
	Returns a string representation of a graph. More...

Functions
StatusBuilder	AbortedErrorBuilder ()

StatusBuilder	AlreadyExistsErrorBuilder ()

StatusBuilder	CancelledErrorBuilder ()

StatusBuilder	DataLossErrorBuilder ()

StatusBuilder	DeadlineExceededErrorBuilder ()

StatusBuilder	FailedPreconditionErrorBuilder ()

StatusBuilder	InternalErrorBuilder ()

StatusBuilder	InvalidArgumentErrorBuilder ()

StatusBuilder	NotFoundErrorBuilder ()

StatusBuilder	OutOfRangeErrorBuilder ()

StatusBuilder	PermissionDeniedErrorBuilder ()

StatusBuilder	UnauthenticatedErrorBuilder ()

StatusBuilder	ResourceExhaustedErrorBuilder ()

StatusBuilder	UnavailableErrorBuilder ()

StatusBuilder	UnimplementedErrorBuilder ()

StatusBuilder	UnknownErrorBuilder ()

template<class UndirectedGraph , class NodeType >
std::vector< NodeType >	GetConnectedComponentsTpl (NodeType num_nodes, const UndirectedGraph &graph)

template<class UndirectedGraph >
std::vector< int >	GetConnectedComponents (int num_nodes, const UndirectedGraph &graph)

template<class IntVector , class Array , class ElementType >
void	PermuteWithExplicitElementType (const IntVector &permutation, Array *array_to_permute, ElementType unused)

template<class IntVector , class Array >
void	Permute (const IntVector &permutation, Array *array_to_permute)

template<class IntVector >
void	Permute (const IntVector &permutation, std::vector< bool > *array_to_permute)

	DEFINE_RANGE_BASED_ARC_ITERATION (ListGraph, Outgoing, Base::kNilArc)
	ListGraph implementation -------------------------------------------------—.

	DEFINE_RANGE_BASED_ARC_ITERATION (StaticGraph, Outgoing, DirectArcLimit(node))

	DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcListGraph, Outgoing, Base::kNilArc)
	ReverseArcListGraph implementation ---------------------------------------—.

	DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcListGraph, Incoming, Base::kNilArc)

	DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcListGraph, OutgoingOrOppositeIncoming, Base::kNilArc)

	DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcListGraph, OppositeIncoming, Base::kNilArc)

	DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcStaticGraph, Outgoing, DirectArcLimit(node))
	ReverseArcStaticGraph implementation -------------------------------------—.

	DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcStaticGraph, Incoming, ReverseArcLimit(node))

	DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcStaticGraph, OutgoingOrOppositeIncoming, DirectArcLimit(node))

	DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcStaticGraph, OppositeIncoming, ReverseArcLimit(node))

	DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcMixedGraph, Outgoing, DirectArcLimit(node))
	ReverseArcMixedGraph implementation --------------------------------------—.

	DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcMixedGraph, Incoming, Base::kNilArc)

	DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcMixedGraph, OutgoingOrOppositeIncoming, DirectArcLimit(node))

	DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcMixedGraph, OppositeIncoming, Base::kNilArc)

template<class Graph >
std::string	GraphToString (const Graph &graph, GraphToStringFormat format)
	Implementations of the templated methods.

template<class Graph >
absl::Status	WriteGraphToFile (const Graph &graph, const std::string &filename, bool directed, absl::Span< const int > num_nodes_with_color)

template<typename Iterator >
BeginEndWrapper< Iterator >	BeginEndRange (Iterator begin, Iterator end)

template<typename Iterator >
BeginEndWrapper< Iterator >	BeginEndRange (std::pair< Iterator, Iterator > begin_end)

template<typename MultiMap >
BeginEndWrapper< typename MultiMap::iterator >	EqualRange (MultiMap &multi_map, const typename MultiMap::key_type &key)

template<typename MultiMap >
BeginEndWrapper< typename MultiMap::const_iterator >	EqualRange (const MultiMap &multi_map, const typename MultiMap::key_type &key)

template<typename Container >
BeginEndReverseIteratorWrapper< Container >	Reverse (const Container &c)

std::unique_ptr< StaticGraph<> >	GenerateRandomMultiGraph (int num_nodes, int num_arcs, bool finalized, absl::BitGenRef gen)

std::unique_ptr< StaticGraph<> >	GenerateRandomDirectedSimpleGraph (int num_nodes, int num_arcs, bool finalized, absl::BitGenRef gen)

std::unique_ptr< StaticGraph<> >	GenerateRandomUndirectedSimpleGraph (int num_nodes, int num_edges, bool finalized, absl::BitGenRef gen)

template<typename T >
ABSL_MUST_USE_RESULT bool	TopologicalSort (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > *topological_order)

template<typename T >
ABSL_MUST_USE_RESULT bool	TopologicalSort (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > topological_order, std::vector< T > cycle)
	Override of the above that outputs the detected cycle.

template<typename T >
std::vector< T >	TopologicalSortOrDie (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs)
	OrDie() variant of the above.

template<typename T >
ABSL_MUST_USE_RESULT bool	StableTopologicalSort (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > *topological_order)

template<typename T >
ABSL_MUST_USE_RESULT bool	StableTopologicalSort (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > topological_order, std::vector< T > cycle)
	Override of the above that outputs the detected cycle.

template<typename T >
std::vector< T >	StableTopologicalSortOrDie (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs)
	OrDie() variant of the above.

ABSL_MUST_USE_RESULT std::vector< int >	FindCycleInDenseIntGraph (int num_nodes, const std::vector< std::pair< int, int > > &arcs)
	______________________ END OF THE RECOMMENDED API ___________________________

ABSL_MUST_USE_RESULT bool	DenseIntTopologicalSort (int num_nodes, const std::vector< std::pair< int, int > > &arcs, std::vector< int > *topological_order)
	Implementations of the "simple API" functions declared at the top.

std::vector< int >	DenseIntStableTopologicalSortOrDie (int num_nodes, const std::vector< std::pair< int, int > > &arcs)

ABSL_MUST_USE_RESULT bool	DenseIntStableTopologicalSort (int num_nodes, const std::vector< std::pair< int, int > > &arcs, std::vector< int > *topological_order)

std::vector< int >	DenseIntTopologicalSortOrDie (int num_nodes, const std::vector< std::pair< int, int > > &arcs)

template<typename T >
bool	TopologicalSort (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > *topological_order)

template<typename T >
bool	TopologicalSort (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > topological_order, std::vector< T > cycle)
	Override of the above that outputs the detected cycle.

template<typename T >
bool	StableTopologicalSort (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > *topological_order)

template<typename T >
bool	StableTopologicalSort (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs, std::vector< T > topological_order, std::vector< T > cycle)
	Override of the above that outputs the detected cycle.

bool	IsSubsetOf0N (absl::Span< const int > v, int n)

template<class Graph >
bool	GraphHasSelfArcs (const Graph &graph)
	Implementations of the templated methods.

template<class Graph >
bool	GraphHasDuplicateArcs (const Graph &graph)

template<class Graph >
bool	GraphIsSymmetric (const Graph &graph)

template<class Graph >
bool	GraphIsWeaklyConnected (const Graph &graph)

template<class Graph >
std::unique_ptr< Graph >	CopyGraph (const Graph &graph)
	Returns a fresh copy of a given graph.

template<class Graph >
std::unique_ptr< Graph >	RemapGraph (const Graph &graph, absl::Span< const int > new_node_index)

template<class Graph >
std::unique_ptr< Graph >	GetSubgraphOfNodes (const Graph &graph, absl::Span< const int > nodes)

template<class Graph >
std::vector< int >	GetWeaklyConnectedComponents (const Graph &graph)

bool	IsValidPermutation (absl::Span< const int > v)
	Returns true iff the given vector is a permutation of [0..size()-1].

template<class Graph >
std::unique_ptr< Graph >	RemoveSelfArcsAndDuplicateArcs (const Graph &graph)
	Returns a copy of "graph", without self-arcs and duplicate arcs.

template<class Graph >
void	RemoveCyclesFromPath (const Graph &graph, std::vector< int > *arc_path)

template<class Graph >
bool	PathHasCycle (const Graph &graph, absl::Span< const int > arc_path)
	Returns true iff the given path contains a cycle.

template<class Graph >
std::vector< int >	ComputeOnePossibleReverseArcMapping (const Graph &graph, bool die_if_not_symmetric)

Detailed Description

A collections of i/o utilities for the Graph classes in ./graph.h.

A collections of utilities for the Graph classes in ./graph.h.

Helper classes to make it easy to implement range-based for loops.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. These 3 functions give the full functionality of a BFS (Breadth-First-Search) on any type of Graph on dense integers that implements the [] operator to yield the adjacency list: graph[i] should yield a vector<int>-like object that lists all the (outgoing) neighbors of node #i.

If your graph is undirected, it means that for each edge (i,j), graph[i] must contain j and graph[j] must contain i.

Self-arcs and multi-arcs are supported, since they don't affect BFS.

These functions are fast: they have the optimal asymptotic complexity, and are reasonably optimized. You may still get performance gains if you implement your own BFS for your application. In particular, this API is optimized for repeated calls to GetBFSShortestPath(); if you only care about GetBFSDistances() there exists more optimized implementations.

ERRORS: This library does perform many checks at runtime, and returns an error Status if it detects a problem, but it doesn't fully protect you from crashes if the input is ill-formed in some ways this library can't check. For example, if calling graph[i] crashes for some i in 0..num_nodes-1, this won't detect it.

Example: const int num_nodes = 3; vector<vector<int>> graph(num_nodes) = {{1}, {0}, {1, 2}}; ///< 0↔1←2⟲ const int source = 1; vector<int> bfs_tree = GetBFSRootedTree(graph, num_nodes, source).value(); LOG(INFO) << DUMP_VARS(GetBFSDistances(bfs_tree)); for (int target : {0, 1, 2}) { vector<int> path = GetBFSShortestPath(bfs_tree, target); LOG(INFO) << DUMP_VARS(path); }

Would log this: GetBFSDistances(bfs_tree) = [1, 0, -1] path = [1, 0] path = [1] path = [] ///< no path from 1 to 2.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. Finds the connected components in an undirected graph: https://en.wikipedia.org/wiki/Connected_component_(graph_theory)

If you have a fixed graph where the node are dense integers, use GetConnectedComponents(): it's very fast and uses little memory.

If you have a more dynamic scenario where you want to incrementally add nodes or edges and query the connectivity between them, use the [Dense]ConnectedComponentsFinder class, which uses the union-find algorithm aka disjoint sets: https://en.wikipedia.org/wiki/Disjoint-set_data_structure.

Implementations of the method templates

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. This file defines a generic graph interface on which most algorithms can be built and provides a few efficient implementations with a fast construction time. Its design is based on the experience acquired by the Operations Research team in their various graph algorithm implementations.

The main ideas are:

Graph nodes and arcs are represented by integers.
Node or arc annotations (weight, cost, ...) are not part of the graph class, they can be stored outside in one or more arrays and can be easily retrieved using a node or arc as an index.

Terminology:

An arc of a graph is directed and going from a tail node to a head node.
Some implementations also store 'reverse' arcs and can be used for undirected graph or flow-like algorithm.
A node or arc index is 'valid' if it represents a node or arc of the graph. The validity ranges are always [0, num_nodes()) for nodes and [0, num_arcs()) for forward arcs. Reverse arcs are elements of [-num_arcs(), 0) and are also considered valid by the implementations that store them.

Provided implementations:

ListGraph<> for the simplest api. Also aliased to util::Graph.
StaticGraph<> for performance, but require calling Build(), see below
CompleteGraph<> if you need a fully connected graph
CompleteBipartiteGraph<> if you need a fully connected bipartite graph
ReverseArcListGraph<> to add reverse arcs to ListGraph<>
ReverseArcStaticGraph<> to add reverse arcs to StaticGraph<>
ReverseArcMixedGraph<> for a smaller memory footprint

Utility classes & functions:

Permute() to permute an array according to a given permutation.
SVector<> vector with index range [-size(), size()) for ReverseArcGraph.

Basic usage: typedef ListGraph<> Graph; ///< Choose a graph implementation. Graph graph; for (...) { graph.AddArc(tail, head); } ... for (int node = 0; node < graph.num_nodes(); ++node) { for (const int arc : graph.OutgoingArcs(node)) { head = graph.Head(arc); tail = node; ///< or graph.Tail(arc) which is fast but not as much. } }

Iteration over the arcs touching a node:

OutgoingArcs(node): All the forward arcs leaving the node.
IncomingArcs(node): All the forward arcs arriving at the node.

And two more involved ones:

OutgoingOrOppositeIncomingArcs(node): This returns both the forward arcs leaving the node (i.e. OutgoingArcs(node)) and the reverse arcs leaving the node (i.e. the opposite arcs of the ones returned by IncomingArcs(node)).
OppositeIncomingArcs(node): This returns the reverse arcs leaving the node.

Note on iteration efficiency: When re-indexing the arcs it is not possible to have both the outgoing arcs and the incoming ones form a consecutive range.

It is however possible to do so for the outgoing arcs and the opposite incoming arcs. It is why the OutgoingOrOppositeIncomingArcs() and OutgoingArcs() iterations are more efficient than the IncomingArcs() one.

If you know the graph size in advance, this already set the number of nodes, reserve space for the arcs and check in DEBUG mode that you don't go over the bounds: Graph graph(num_nodes, arc_capacity);

Storing and using node annotations: vector<bool> is_visited(graph.num_nodes(), false); ... for (int node = 0; node < graph.num_nodes(); ++node) { if (!is_visited[node]) ... }

Storing and using arc annotations: vector<int> weights; for (...) { graph.AddArc(tail, head); weights.push_back(arc_weight); } ... for (const int arc : graph.OutgoingArcs(node)) { ... weights[arc] ...; }

More efficient version: typedef StaticGraph<> Graph; Graph graph(num_nodes, arc_capacity); ///< Optional, but help memory usage. vector<int> weights; weights.reserve(arc_capacity); ///< Optional, but help memory usage. for (...) { graph.AddArc(tail, head); weights.push_back(arc_weight); } ... vector<Graph::ArcIndex> permutation; graph.Build(&permutation); ///< A static graph must be Build() before usage. Permute(permutation, &weights); ///< Build() may permute the arc index. ...

Encoding an undirected graph: If you don't need arc annotation, then the best is to add two arcs for each edge (one in each direction) to a directed graph. Otherwise you can do the following.

typedef ReverseArc... Graph; Graph graph; for (...) { graph.AddArc(tail, head); ///< or graph.AddArc(head, tail) but not both. edge_annotations.push_back(value); } ... for (const Graph::NodeIndex node : graph.AllNodes()) { for (const Graph::ArcIndex arc : graph.OutgoingOrOppositeIncomingArcs(node)) { destination = graph.Head(arc); annotation = edge_annotations[arc < 0 ? graph.OppositeArc(arc) : arc]; } }

Note: The graphs are primarily designed to be constructed first and then used because it covers most of the use cases. It is possible to extend the interface with more dynamicity (like removing arcs), but this is not done at this point. Note that a "dynamic" implementation will break some assumptions we make on what node or arc are valid and also on the indices returned by AddArc(). Some arguments for simplifying the interface at the cost of dynamicity are:

It is always possible to construct a static graph from a dynamic one before calling a complex algo.
If you really need a dynamic graph, maybe it is better to compute a graph property incrementally rather than calling an algorithm that starts from scratch each time.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. A collection of functions to be used in unit tests involving the ortools/graph/... library.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. This file provides topologically sorted traversal of the nodes of a directed acyclic graph (DAG) with up to INT_MAX nodes. It sorts ancestor nodes before their descendants. Multi-arcs are fine.

If your graph is not a DAG and you're reading this, you are probably looking for ortools/graph/strongly_connected_components.h which does the topological decomposition of a directed graph.

USAGE:

If performance matters, use FastTopologicalSort().
If your nodes are non-integers, or you need to break topological ties by node index (like "stable_sort"), use one of the DenseIntTopologicalSort() or TopologicalSort variants (see below).
If you need more control (cycle extraction?), or a step-by-step topological sort, see the TopologicalSorter classes below.

Typedef Documentation

◆ DenseIntStableTopologicalSorter

typedef ::util::internal::DenseIntTopologicalSorterTpl< true> util::DenseIntStableTopologicalSorter

Recommended version for general usage. The stability makes it more deterministic, and its behavior is guaranteed to never change.

Definition at line 288 of file topologicalsorter.h.

◆ DenseIntTopologicalSorter

typedef ::util::internal::DenseIntTopologicalSorterTpl< false> util::DenseIntTopologicalSorter

Use this version if you are certain you don't care about the tie-breaking order and need the 5 to 10% performance gain. The performance gain can be more significant for large graphs with large numbers of source nodes (for example 2 Million nodes with 2 Million random edges sees a factor of 0.7 difference in completion time).

Definition at line 297 of file topologicalsorter.h.

◆ Graph

typedef ListGraph util::Graph

Defining the simplest Graph interface as Graph for convenience.

Definition at line 2407 of file graph.h.

Enumeration Type Documentation

◆ GraphToStringFormat

enum util::GraphToStringFormat

Returns a string representation of a graph.

Enumerator
PRINT_GRAPH_ARCS	One arc per line, eg. "3->1".
PRINT_GRAPH_ADJACENCY_LISTS	One space-separated adjacency list per line, eg. "3: 5 1 3 1". Nodes with no outgoing arc get an empty list.
PRINT_GRAPH_ADJACENCY_LISTS_SORTED	Ditto, but the adjacency lists are sorted.

Definition at line 41 of file io.h.

Function Documentation

◆ AbortedErrorBuilder()

StatusBuilder util::AbortedErrorBuilder ( )

inline

Definition at line 79 of file status_builder.h.

◆ AlreadyExistsErrorBuilder()

StatusBuilder util::AlreadyExistsErrorBuilder ( )

inline

Definition at line 83 of file status_builder.h.

◆ BeginEndRange() [1/2]

template<typename Iterator >

BeginEndWrapper< Iterator > util::BeginEndRange	(	Iterator	begin,
		Iterator	end )

inline

Inline wrapper methods, to make the client code even simpler. The harm of overloading is probably less than the benefit of the nice, compact name, in this special case.

Definition at line 59 of file iterators.h.

◆ BeginEndRange() [2/2]

template<typename Iterator >

BeginEndWrapper< Iterator > util::BeginEndRange ( std::pair< Iterator, Iterator > begin_end )

inline

Definition at line 63 of file iterators.h.

◆ CancelledErrorBuilder()

StatusBuilder util::CancelledErrorBuilder ( )

inline

Definition at line 87 of file status_builder.h.

◆ ComputeOnePossibleReverseArcMapping()

template<class Graph >

std::vector< int > util::ComputeOnePossibleReverseArcMapping	(	const Graph &	graph,
		bool	die_if_not_symmetric )

Returns a vector representing a mapping from arcs to arcs such that each arc is mapped to another arc with its (tail, head) flipped, if such an arc exists (otherwise it is mapped to -1). If the graph is symmetric, the returned mapping is bijective and reflexive, i.e. out[out[arc]] = arc for all "arc", where "out" is the returned vector. If "die_if_not_symmetric" is true, this function CHECKs() that the graph is symmetric.

Self-arcs are always mapped to themselves.

Note: since graphs may have multi-arcs, the mapping isn't necessarily unique, hence the function name.

PERFORMANCE: If you see this function taking too much memory and/or too much time, reach out to viger@: one could halve the memory usage and speed it up.

We need a multi-map since a given (tail,head) may appear several times. NOTE(user): It's free, in terms of space, to use InlinedVector<int, 4> rather than std::vector<int>.

Special case: directly map any self-arc to itself.

Lookup for the reverse arc of the current one...

Found a reverse arc! Store the mapping and remove the reverse arc from the map.

Reverse arc not in the map. Add the current arc to the map.

Algorithm check, for debugging.

We need a multi-map since a given (tail,head) may appear several times. NOTE(user): It's free, in terms of space, to use InlinedVector<int, 4> rather than std::vector<int>.

Special case: directly map any self-arc to itself.

Lookup for the reverse arc of the current one...

Found a reverse arc! Store the mapping and remove the reverse arc from the map.

Reverse arc not in the map. Add the current arc to the map.

Algorithm check, for debugging.

Definition at line 390 of file util.h.

◆ CopyGraph()

template<class Graph >

std::unique_ptr< Graph > util::CopyGraph ( const Graph & graph )

Returns a fresh copy of a given graph.

Definition at line 266 of file util.h.

◆ DataLossErrorBuilder()

StatusBuilder util::DataLossErrorBuilder ( )

inline

Definition at line 91 of file status_builder.h.

◆ DeadlineExceededErrorBuilder()

StatusBuilder util::DeadlineExceededErrorBuilder ( )

inline

Definition at line 95 of file status_builder.h.

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [1/14]

util::DEFINE_RANGE_BASED_ARC_ITERATION	(	ListGraph	,
		Outgoing	,
		Base::kNilArc	)

ListGraph implementation -------------------------------------------------—.

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [2/14]

util::DEFINE_RANGE_BASED_ARC_ITERATION	(	ReverseArcListGraph	,
		Incoming	,
		Base::kNilArc	)

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [3/14]

util::DEFINE_RANGE_BASED_ARC_ITERATION	(	ReverseArcListGraph	,
		OppositeIncoming	,
		Base::kNilArc	)

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [4/14]

util::DEFINE_RANGE_BASED_ARC_ITERATION	(	ReverseArcListGraph	,
		Outgoing	,
		Base::kNilArc	)

ReverseArcListGraph implementation ---------------------------------------—.

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [5/14]

util::DEFINE_RANGE_BASED_ARC_ITERATION	(	ReverseArcListGraph	,
		OutgoingOrOppositeIncoming	,
		Base::kNilArc	)

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [6/14]

util::DEFINE_RANGE_BASED_ARC_ITERATION	(	ReverseArcMixedGraph	,
		Incoming	,
		Base::kNilArc	)

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [7/14]

util::DEFINE_RANGE_BASED_ARC_ITERATION	(	ReverseArcMixedGraph	,
		OppositeIncoming	,
		Base::kNilArc	)

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [8/14]

util::DEFINE_RANGE_BASED_ARC_ITERATION	(	ReverseArcMixedGraph	,
		Outgoing	,
		DirectArcLimit(node)	)

ReverseArcMixedGraph implementation --------------------------------------—.

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [9/14]

util::DEFINE_RANGE_BASED_ARC_ITERATION	(	ReverseArcMixedGraph	,
		OutgoingOrOppositeIncoming	,
		DirectArcLimit(node)	)

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [10/14]

util::DEFINE_RANGE_BASED_ARC_ITERATION	(	ReverseArcStaticGraph	,
		Incoming	,
		ReverseArcLimit(node)	)

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [11/14]

util::DEFINE_RANGE_BASED_ARC_ITERATION	(	ReverseArcStaticGraph	,
		OppositeIncoming	,
		ReverseArcLimit(node)	)

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [12/14]

util::DEFINE_RANGE_BASED_ARC_ITERATION	(	ReverseArcStaticGraph	,
		Outgoing	,
		DirectArcLimit(node)	)

ReverseArcStaticGraph implementation -------------------------------------—.

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [13/14]

util::DEFINE_RANGE_BASED_ARC_ITERATION	(	ReverseArcStaticGraph	,
		OutgoingOrOppositeIncoming	,
		DirectArcLimit(node)	)

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [14/14]

util::DEFINE_RANGE_BASED_ARC_ITERATION	(	StaticGraph	,
		Outgoing	,
		DirectArcLimit(node)	)

◆ DenseIntStableTopologicalSort()

bool util::DenseIntStableTopologicalSort	(	int	num_nodes,
		const std::vector< std::pair< int, int > > &	arcs,
		std::vector< int > *	topological_order )

inline

Definition at line 524 of file topologicalsorter.h.

◆ DenseIntStableTopologicalSortOrDie()

std::vector< int > util::DenseIntStableTopologicalSortOrDie	(	int	num_nodes,
		const std::vector< std::pair< int, int > > &	arcs )

inline

Definition at line 569 of file topologicalsorter.h.

◆ DenseIntTopologicalSort()

bool util::DenseIntTopologicalSort	(	int	num_nodes,
		const std::vector< std::pair< int, int > > &	arcs,
		std::vector< int > *	topological_order )

inline

Implementations of the "simple API" functions declared at the top.

Deprecated

DenseInt[Stable]TopologicalSort[OrDie]. Kept here for legacy reasons, but most new users should use FastTopologicalSort():

If your input is a list of edges, build you own StaticGraph<> (see ./graph.h) and pass it to FastTopologicalSort().
If you need the "stable sort" bit, contact viger@ and/or or-core-team@ to see if they can create FastStableTopologicalSort().

Definition at line 517 of file topologicalsorter.h.

◆ DenseIntTopologicalSortOrDie()

std::vector< int > util::DenseIntTopologicalSortOrDie	(	int	num_nodes,
		const std::vector< std::pair< int, int > > &	arcs )

inline

Definition at line 564 of file topologicalsorter.h.

◆ EqualRange() [1/2]

template<typename MultiMap >

BeginEndWrapper< typename MultiMap::const_iterator > util::EqualRange	(	const MultiMap &	multi_map,
		const typename MultiMap::key_type &	key )

inline

Definition at line 77 of file iterators.h.

◆ EqualRange() [2/2]

template<typename MultiMap >

BeginEndWrapper< typename MultiMap::iterator > util::EqualRange	(	MultiMap &	multi_map,
		const typename MultiMap::key_type &	key )

inline

Shortcut for BeginEndRange(multimap::equal_range(key)).

Todo: (user): go further and expose only the values, not the pairs (key, values) since the caller already knows the key.

Definition at line 72 of file iterators.h.

◆ FailedPreconditionErrorBuilder()

StatusBuilder util::FailedPreconditionErrorBuilder ( )

inline

Definition at line 99 of file status_builder.h.

◆ FindCycleInDenseIntGraph()

ABSL_MUST_USE_RESULT std::vector< int > util::FindCycleInDenseIntGraph	(	int	num_nodes,
		const std::vector< std::pair< int, int > > &	arcs )

inline

______________________ END OF THE RECOMMENDED API ___________________________

Deprecated: Use util::graph::FindCycleInGraph() directly.

Definition at line 145 of file topologicalsorter.h.

◆ GenerateRandomDirectedSimpleGraph()

std::unique_ptr< StaticGraph<> > util::GenerateRandomDirectedSimpleGraph	(	int	num_nodes,
		int	num_arcs,
		bool	finalized,
		absl::BitGenRef	gen )

Like GenerateRandomMultiGraph(), but with neither multi-arcs nor self-arcs: the generated graph will have exactly num_arcs arcs. It will be picked uniformly at random from the set of all simple graphs with that number of nodes and arcs.

Definition at line 161 of file random_graph.cc.

◆ GenerateRandomMultiGraph()

std::unique_ptr< StaticGraph<> > util::GenerateRandomMultiGraph	(	int	num_nodes,
		int	num_arcs,
		bool	finalized,
		absl::BitGenRef	gen )

Generates a random graph where multi-arcs and self-arcs are allowed (and therefore expected): exactly "num_arcs" are generated, each from a node picked uniformly at random to another node picked uniformly at random. Calls Build() on the graph iff "finalized" is true.

Definition at line 54 of file random_graph.cc.

◆ GenerateRandomUndirectedSimpleGraph()

std::unique_ptr< StaticGraph<> > util::GenerateRandomUndirectedSimpleGraph	(	int	num_nodes,
		int	num_edges,
		bool	finalized,
		absl::BitGenRef	gen )

Like GenerateRandomDirectedSimpleGraph(), but where an undirected edge is represented by two arcs: a->b and b->a. As a result, the amount of arcs in the generated graph is 2*num_edges.

Definition at line 167 of file random_graph.cc.

◆ GetConnectedComponents()

template<class UndirectedGraph >

std::vector< int > util::GetConnectedComponents	(	int	num_nodes,
		const UndirectedGraph &	graph )

Finds the connected components of the graph, using BFS internally. Works on any undirected graph class whose nodes are dense integers and that supports the [] operator for adjacency lists: graph[x] must be an integer container listing the nodes that are adjacent to node x. Example: std::vector<std::vector<int>>.

"Undirected" means that for all y in graph[x], x is in graph[y].

Returns the mapping from node to component index. The component indices are deterministic: Component #0 will be the one that has node #0, component #1 the one that has the lowest-index node that isn't in component #0, and so on.

Example on the following 6-node graph: 5–3–0–1 2–4 vector<vector<int>> graph = {{1, 3}, {0}, {4}, {0, 5}, {2}, {3}}; GetConnectedComponents(graph); ///< returns [0, 0, 1, 0, 1, 0].

Definition at line 78 of file connected_components.h.

◆ GetConnectedComponentsTpl()

template<class UndirectedGraph , class NodeType >

std::vector< NodeType > util::GetConnectedComponentsTpl	(	NodeType	num_nodes,
		const UndirectedGraph &	graph )

Generic version of GetConnectedComponents() (see below) that supports other integer types, e.g. int64_t for huge graphs with more than 2^31 nodes.

We use 'num_nodes' as special component id meaning 'unknown', because it's of the right type, and -1 is tricky to use with unsigned ints.

Definition at line 333 of file connected_components.h.

◆ GetSubgraphOfNodes()

template<class Graph >

std::unique_ptr< Graph > util::GetSubgraphOfNodes	(	const Graph &	graph,
		absl::Span< const int >	nodes )

Gets the induced subgraph of "graph" restricted to the nodes in "nodes": the resulting graph will have exactly nodes.size() nodes, and its node #0 will be the former graph's node nodes[0], etc. See https://en.wikipedia.org/wiki/Induced_subgraph . The "nodes" must be a valid subset (no repetitions) of [0..graph.num_nodes()-1], or the behavior is undefined (it may die).

Note: you can call IsSubsetOf0N() to check it yourself.

Current complexity: O(num old nodes + num new arcs). It could easily be done in O(num new nodes + num new arcs) but with a higher constant.

Do a first pass to count the arcs, so that we don't allocate more memory than needed.

A second pass where we actually copy the subgraph. NOTE(user): there might seem to be a bit of duplication with RemapGraph(), but there is a key difference: the loop below only iterates on "nodes", which could be much smaller than all the graph's nodes.

Do a first pass to count the arcs, so that we don't allocate more memory than needed.

A second pass where we actually copy the subgraph. NOTE(user): there might seem to be a bit of duplication with RemapGraph(), but there is a key difference: the loop below only iterates on "nodes", which could be much smaller than all the graph's nodes.

Definition at line 298 of file util.h.

◆ GetWeaklyConnectedComponents()

template<class Graph >

std::vector< int > util::GetWeaklyConnectedComponents ( const Graph & graph )

Computes the weakly connected components of a directed graph that provides the OutgoingOrOppositeIncomingArcs() API, and returns them as a mapping from node to component index. See GetConnectedComponents().

Definition at line 137 of file util.h.

◆ GraphHasDuplicateArcs()

template<class Graph >

bool util::GraphHasDuplicateArcs ( const Graph & graph )

Definition at line 203 of file util.h.

◆ GraphHasSelfArcs()

template<class Graph >

bool util::GraphHasSelfArcs ( const Graph & graph )

Implementations of the templated methods.

Here's a set of simple diagnosis tools. Notes:

A self-arc is an arc from a node to itself.
We say that an arc A->B is duplicate when there is another arc A->B in the same graph.
A graph is said "weakly connected" if it is connected when considering all arcs as undirected edges.
A graph is said "symmetric" iff for all (a, b), the number of arcs a->b is equal to the number of arcs b->a.

All these diagnosis work in O(graph size), since the inverse Ackerman function is <= 5 for all practical instances, and are very fast.

If the graph is a "static" kind, they must be finalized, except for GraphHasSelfArcs() and GraphIsWeaklyConnected() which also support non-finalized StaticGraph<>.

Definition at line 195 of file util.h.

◆ GraphIsSymmetric()

template<class Graph >

bool util::GraphIsSymmetric ( const Graph & graph )

Create a reverse copy of the graph.

Compare the graph to its reverse, one adjacency list at a time.

Create a reverse copy of the graph.

Compare the graph to its reverse, one adjacency list at a time.

Definition at line 221 of file util.h.

◆ GraphIsWeaklyConnected()

template<class Graph >

bool util::GraphIsWeaklyConnected ( const Graph & graph )

Definition at line 250 of file util.h.

◆ GraphToString()

template<class Graph >

std::string util::GraphToString	(	const Graph &	graph,
		GraphToStringFormat	format )

Implementations of the templated methods.

Definition at line 75 of file io.h.

◆ InternalErrorBuilder()

StatusBuilder util::InternalErrorBuilder ( )

inline

Definition at line 103 of file status_builder.h.

◆ InvalidArgumentErrorBuilder()

StatusBuilder util::InvalidArgumentErrorBuilder ( )

inline

Definition at line 107 of file status_builder.h.

◆ IsSubsetOf0N()

bool util::IsSubsetOf0N	(	absl::Span< const int >	v,
		int	n )

Returns true iff the given vector is a subset of [0..n-1], i.e. all elements i are such that 0 <= i < n and no two elements are equal. "n" must be >= 0 or the result is undefined.

Definition at line 22 of file util.cc.

◆ IsValidPermutation()

bool util::IsValidPermutation ( absl::Span< const int > v )

inline

Returns true iff the given vector is a permutation of [0..size()-1].

Definition at line 148 of file util.h.

◆ NotFoundErrorBuilder()

StatusBuilder util::NotFoundErrorBuilder ( )

inline

Definition at line 111 of file status_builder.h.

◆ OutOfRangeErrorBuilder()

StatusBuilder util::OutOfRangeErrorBuilder ( )

inline

Definition at line 115 of file status_builder.h.

◆ PathHasCycle()

template<class Graph >

bool util::PathHasCycle	(	const Graph &	graph,
		absl::Span< const int >	arc_path )

Returns true iff the given path contains a cycle.

Definition at line 379 of file util.h.

◆ PermissionDeniedErrorBuilder()

StatusBuilder util::PermissionDeniedErrorBuilder ( )

inline

Definition at line 119 of file status_builder.h.

◆ Permute() [1/2]

template<class IntVector , class Array >

void util::Permute	(	const IntVector &	permutation,
		Array *	array_to_permute )

Definition at line 758 of file graph.h.

◆ Permute() [2/2]

template<class IntVector >

void util::Permute	(	const IntVector &	permutation,
		std::vector< bool > *	array_to_permute )

We need a specialization for vector<bool>, because the default code uses (*array_to_permute)[0] as ElementType, which isn't 'bool' in that case.

Definition at line 769 of file graph.h.

◆ PermuteWithExplicitElementType()

template<class IntVector , class Array , class ElementType >

void util::PermuteWithExplicitElementType	(	const IntVector &	permutation,
		Array *	array_to_permute,
		ElementType	unused )

Permutes the elements of array_to_permute: element #i will be moved to position permutation[i]. permutation must be either empty (in which case nothing happens), or a permutation of [0, permutation.size()).

The algorithm is fast but need extra memory for a copy of the permuted part of array_to_permute.

Todo: (user): consider slower but more memory efficient implementations that follow the cycles of the permutation and use a bitmap to indicate what has been permuted or to mark the beginning of each cycle.

Some compiler do not know typeof(), so we have to use this extra function internally.

Definition at line 745 of file graph.h.

◆ RemapGraph()

template<class Graph >

std::unique_ptr< Graph > util::RemapGraph	(	const Graph &	graph,
		absl::Span< const int >	new_node_index )

Creates a remapped copy of graph "graph", where node i becomes node new_node_index[i]. "new_node_index" must be a valid permutation of [0..num_nodes-1] or the behavior is undefined (it may die).

Note: you can call IsValidPermutation() to check it yourself.

Definition at line 279 of file util.h.

◆ RemoveCyclesFromPath()

template<class Graph >

void util::RemoveCyclesFromPath	(	const Graph &	graph,
		std::vector< int > *	arc_path )

Given an arc path, changes it to a sub-path with the same source and destination but without any cycle. Nothing happen if the path was already without cycle.

The graph class should support Tail(arc) and Head(arc). They should both return an integer representing the corresponding tail/head of the passed arc.

Todo: (user): In some cases, there is more than one possible solution. We could take some arc costs and return the cheapest path instead. Or return the shortest path in term of number of arcs.

This maps each node to the latest arc in the given path that leaves it.

Special case for the destination.

Note: this requires that -1 is not a valid arc of Graph.

Reconstruct the path by starting at the source and then following the "next" arcs. We override the given arc_path at the same time.

This maps each node to the latest arc in the given path that leaves it.

Special case for the destination.

Note: this requires that -1 is not a valid arc of Graph.

Reconstruct the path by starting at the source and then following the "next" arcs. We override the given arc_path at the same time.

Definition at line 354 of file util.h.

◆ RemoveSelfArcsAndDuplicateArcs()

template<class Graph >

std::unique_ptr< Graph > util::RemoveSelfArcsAndDuplicateArcs ( const Graph & graph )

Returns a copy of "graph", without self-arcs and duplicate arcs.

Definition at line 332 of file util.h.

◆ ResourceExhaustedErrorBuilder()

StatusBuilder util::ResourceExhaustedErrorBuilder ( )

inline

Definition at line 127 of file status_builder.h.

◆ Reverse()

template<typename Container >

BeginEndReverseIteratorWrapper< Container > util::Reverse ( const Container & c )

Definition at line 99 of file iterators.h.

◆ StableTopologicalSort() [1/4]

template<typename T >

ABSL_MUST_USE_RESULT bool util::StableTopologicalSort	(	const std::vector< T > &	nodes,
		const std::vector< std::pair< T, T > > &	arcs,
		std::vector< T > *	topological_order )

The "Stable" variants are a little slower but preserve the input order of nodes, if possible. More precisely, the returned topological order will be the lexicographically minimal valid order, where "lexicographic" applies to the indices of the nodes.

Definition at line 548 of file topologicalsorter.h.

◆ StableTopologicalSort() [2/4]

template<typename T >

bool util::StableTopologicalSort	(	const std::vector< T > &	nodes,
		const std::vector< std::pair< T, T > > &	arcs,
		std::vector< T > *	topological_order )

The "Stable" variants are a little slower but preserve the input order of nodes, if possible. More precisely, the returned topological order will be the lexicographically minimal valid order, where "lexicographic" applies to the indices of the nodes.

Definition at line 548 of file topologicalsorter.h.

◆ StableTopologicalSort() [3/4]

template<typename T >

ABSL_MUST_USE_RESULT bool util::StableTopologicalSort	(	const std::vector< T > &	nodes,
		const std::vector< std::pair< T, T > > &	arcs,
		std::vector< T > *	topological_order,
		std::vector< T > *	cycle )

Override of the above that outputs the detected cycle.

Definition at line 556 of file topologicalsorter.h.

◆ StableTopologicalSort() [4/4]

template<typename T >

bool util::StableTopologicalSort	(	const std::vector< T > &	nodes,
		const std::vector< std::pair< T, T > > &	arcs,
		std::vector< T > *	topological_order,
		std::vector< T > *	cycle )

Override of the above that outputs the detected cycle.

Definition at line 556 of file topologicalsorter.h.

◆ StableTopologicalSortOrDie()

template<typename T >

std::vector< T > util::StableTopologicalSortOrDie	(	const std::vector< T > &	nodes,
		const std::vector< std::pair< T, T > > &	arcs )

OrDie() variant of the above.

Definition at line 581 of file topologicalsorter.h.

◆ TopologicalSort() [1/4]

template<typename T >

ABSL_MUST_USE_RESULT bool util::TopologicalSort	(	const std::vector< T > &	nodes,
		const std::vector< std::pair< T, T > > &	arcs,
		std::vector< T > *	topological_order )

[Stable]TopologicalSort[OrDie]:

These variants are much slower than FastTopologicalSort(), but support non-integer (or integer, but sparse) nodes.

Note: if performance matters, you're probably better off building your own mapping from node to dense index with a flat_hash_map and calling FastTopologicalSort(). Returns true if the graph was a DAG, and outputs the topological order in "topological_order". Returns false if the graph is cyclic, and outputs the detected cycle in "cycle".

Definition at line 532 of file topologicalsorter.h.

◆ TopologicalSort() [2/4]

template<typename T >

bool util::TopologicalSort	(	const std::vector< T > &	nodes,
		const std::vector< std::pair< T, T > > &	arcs,
		std::vector< T > *	topological_order )

[Stable]TopologicalSort[OrDie]:

These variants are much slower than FastTopologicalSort(), but support non-integer (or integer, but sparse) nodes.

Note: if performance matters, you're probably better off building your own mapping from node to dense index with a flat_hash_map and calling FastTopologicalSort(). Returns true if the graph was a DAG, and outputs the topological order in "topological_order". Returns false if the graph is cyclic, and outputs the detected cycle in "cycle".

Definition at line 532 of file topologicalsorter.h.

◆ TopologicalSort() [3/4]

template<typename T >

ABSL_MUST_USE_RESULT bool util::TopologicalSort	(	const std::vector< T > &	nodes,
		const std::vector< std::pair< T, T > > &	arcs,
		std::vector< T > *	topological_order,
		std::vector< T > *	cycle )

Override of the above that outputs the detected cycle.

Definition at line 540 of file topologicalsorter.h.

◆ TopologicalSort() [4/4]

template<typename T >

bool util::TopologicalSort	(	const std::vector< T > &	nodes,
		const std::vector< std::pair< T, T > > &	arcs,
		std::vector< T > *	topological_order,
		std::vector< T > *	cycle )

Override of the above that outputs the detected cycle.

Definition at line 540 of file topologicalsorter.h.

◆ TopologicalSortOrDie()

template<typename T >

std::vector< T > util::TopologicalSortOrDie	(	const std::vector< T > &	nodes,
		const std::vector< std::pair< T, T > > &	arcs )

OrDie() variant of the above.

Definition at line 575 of file topologicalsorter.h.

◆ UnauthenticatedErrorBuilder()

StatusBuilder util::UnauthenticatedErrorBuilder ( )

inline

Definition at line 123 of file status_builder.h.

◆ UnavailableErrorBuilder()

StatusBuilder util::UnavailableErrorBuilder ( )

inline

Definition at line 131 of file status_builder.h.

◆ UnimplementedErrorBuilder()

StatusBuilder util::UnimplementedErrorBuilder ( )

inline

Definition at line 135 of file status_builder.h.

◆ UnknownErrorBuilder()

StatusBuilder util::UnknownErrorBuilder ( )

inline

Definition at line 139 of file status_builder.h.

◆ WriteGraphToFile()

template<class Graph >

absl::Status util::WriteGraphToFile	(	const Graph &	graph,
		const std::string &	filename,
		bool	directed,
		absl::Span< const int >	num_nodes_with_color )

Writes a graph to the ".g" file format described above. If "directed" is true, all arcs are written to the file. If it is false, the graph is expected to be undirected (i.e. the number of arcs a->b is equal to the number of arcs b->a for all nodes a,b); and only the arcs a->b where a<=b are written. Note however that in this case, the symmetry of the graph is not fully checked (only the parity of the number of non-self arcs is).

"num_nodes_with_color" is optional. If it is not empty, then the color information will be written to the header of the .g file. See ReadGraphFile.

This method is the reverse of ReadGraphFile (with the same value for "directed").

In undirected mode, we must count the self-arcs separately. All other arcs should be duplicated.

Definition at line 102 of file io.h.

Namespaces

Classes

Typedefs

Enumerations

Functions

Detailed Description

Typedef Documentation

◆ DenseIntStableTopologicalSorter

◆ DenseIntTopologicalSorter

◆ Graph

Enumeration Type Documentation

◆ GraphToStringFormat

Function Documentation

◆ AbortedErrorBuilder()

◆ AlreadyExistsErrorBuilder()

◆ BeginEndRange() [1/2]

◆ BeginEndRange() [2/2]

◆ CancelledErrorBuilder()

◆ ComputeOnePossibleReverseArcMapping()

◆ CopyGraph()

◆ DataLossErrorBuilder()

◆ DeadlineExceededErrorBuilder()

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [1/14]

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [2/14]

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [3/14]

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [4/14]

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [5/14]

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [6/14]

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [7/14]

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [8/14]

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [9/14]

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [10/14]

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [11/14]

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [12/14]

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [13/14]

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [14/14]

◆ DenseIntStableTopologicalSort()

◆ DenseIntStableTopologicalSortOrDie()

◆ DenseIntTopologicalSort()

◆ DenseIntTopologicalSortOrDie()

◆ EqualRange() [1/2]

◆ EqualRange() [2/2]

◆ FailedPreconditionErrorBuilder()

◆ FindCycleInDenseIntGraph()

◆ GenerateRandomDirectedSimpleGraph()

◆ GenerateRandomMultiGraph()

◆ GenerateRandomUndirectedSimpleGraph()

◆ GetConnectedComponents()

◆ GetConnectedComponentsTpl()

◆ GetSubgraphOfNodes()

◆ GetWeaklyConnectedComponents()

◆ GraphHasDuplicateArcs()

◆ GraphHasSelfArcs()

◆ GraphIsSymmetric()

◆ GraphIsWeaklyConnected()

◆ GraphToString()

◆ InternalErrorBuilder()

◆ InvalidArgumentErrorBuilder()

◆ IsSubsetOf0N()

◆ IsValidPermutation()

◆ NotFoundErrorBuilder()

◆ OutOfRangeErrorBuilder()

◆ PathHasCycle()

◆ PermissionDeniedErrorBuilder()

◆ Permute() [1/2]

◆ Permute() [2/2]

◆ PermuteWithExplicitElementType()

◆ RemapGraph()

◆ RemoveCyclesFromPath()

◆ RemoveSelfArcsAndDuplicateArcs()

◆ ResourceExhaustedErrorBuilder()

◆ Reverse()

◆ StableTopologicalSort() [1/4]

◆ StableTopologicalSort() [2/4]

◆ StableTopologicalSort() [3/4]

◆ StableTopologicalSort() [4/4]

◆ StableTopologicalSortOrDie()

◆ TopologicalSort() [1/4]

◆ TopologicalSort() [2/4]

◆ TopologicalSort() [3/4]