Namespaces
	graph

	internal

Classes
class	BaseGraph

class	BeginEndReverseIteratorWrapper

class	BeginEndWrapper

class	CompleteBipartiteGraph

class	CompleteGraph

class	IntegerRange

class	IntegerRangeIterator

class	ListGraph

struct	MutableVectorIteration

class	ReverseArcListGraph

class	ReverseArcMixedGraph

class	ReverseArcStaticGraph

class	StaticGraph

class	StatusBuilder

class	SVector

class	TopologicalSorter

class	UndirectedAdjacencyListsOfDirectedGraph

Typedefs
typedef ListGraph	Graph

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 }

Functions
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)

	DEFINE_RANGE_BASED_ARC_ITERATION (StaticGraph, Outgoing, DirectArcLimit(node))

	DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcListGraph, Outgoing, Base::kNilArc)

	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))

	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))

	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)

template<class Graph >
absl::StatusOr< Graph * >	ReadGraphFile (const std::string &filename, bool directed, std::vector< int > *num_nodes_with_color_or_null)

template<class Graph >
absl::Status	WriteGraphToFile (const Graph &graph, const std::string &filename, bool directed, const std::vector< 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::vector< int >	FindCycleInDenseIntGraph (int num_nodes, const std::vector< std::pair< int, int >> &arcs)

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

ABSL_MUST_USE_RESULT bool	DenseIntStableTopologicalSort (int num_nodes, const std::vector< std::pair< int, int >> &arcs, std::vector< int > *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)

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< int >	DenseIntTopologicalSortOrDie (int num_nodes, const std::vector< std::pair< int, int >> &arcs)

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

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

template<typename T >
std::vector< T >	StableTopologicalSortOrDie (const std::vector< T > &nodes, const std::vector< std::pair< T, T >> &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	StableTopologicalSort (const std::vector< T > &nodes, const std::vector< std::pair< T, T >> &arcs, std::vector< T > *topological_order)

bool	IsSubsetOf0N (const std::vector< int > &v, int n)

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

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)

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

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

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

bool	IsValidPermutation (const std::vector< int > &v)

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

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

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

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

Typedef Documentation

◆ DenseIntStableTopologicalSorter

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

Definition at line 232 of file topologicalsorter.h.

◆ DenseIntTopologicalSorter

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

Definition at line 241 of file topologicalsorter.h.

◆ Graph

typedef ListGraph Graph

Definition at line 2354 of file graph.h.

Enumeration Type Documentation

◆ GraphToStringFormat

enum GraphToStringFormat

Enumerator
PRINT_GRAPH_ARCS
PRINT_GRAPH_ADJACENCY_LISTS
PRINT_GRAPH_ADJACENCY_LISTS_SORTED

Definition at line 38 of file io.h.

Function Documentation

◆ BeginEndRange() [1/2]

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

inline

Definition at line 58 of file iterators.h.

◆ BeginEndRange() [2/2]

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

inline

Definition at line 62 of file iterators.h.

◆ ComputeOnePossibleReverseArcMapping()

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

Definition at line 386 of file graph/util.h.

◆ CopyGraph()

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

Definition at line 262 of file graph/util.h.

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [1/14]

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

◆ 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
	)

◆ 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)
	)

◆ 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)
	)

◆ 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 DenseIntStableTopologicalSort	(	int	num_nodes,
		const std::vector< std::pair< int, int >> &	arcs,
		std::vector< int > *	topological_order
	)

inline

Definition at line 459 of file topologicalsorter.h.

◆ DenseIntStableTopologicalSortOrDie()

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

inline

Definition at line 486 of file topologicalsorter.h.

◆ DenseIntTopologicalSort()

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

inline

Definition at line 452 of file topologicalsorter.h.

◆ DenseIntTopologicalSortOrDie()

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

inline

Definition at line 481 of file topologicalsorter.h.

◆ EqualRange() [1/2]

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

inline

Definition at line 76 of file iterators.h.

◆ EqualRange() [2/2]

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

inline

Definition at line 71 of file iterators.h.

◆ FindCycleInDenseIntGraph()

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

Definition at line 288 of file topologicalsorter.cc.

◆ GetConnectedComponents()

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

Definition at line 296 of file connected_components.h.

◆ GetSubgraphOfNodes()

std::unique_ptr< Graph > GetSubgraphOfNodes	(	const Graph &	graph,
		const std::vector< int > &	nodes
	)

Definition at line 294 of file graph/util.h.

◆ GetWeaklyConnectedComponents()

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

Definition at line 133 of file graph/util.h.

◆ GraphHasDuplicateArcs()

bool GraphHasDuplicateArcs ( const Graph & graph )

Definition at line 199 of file graph/util.h.

◆ GraphHasSelfArcs()

bool GraphHasSelfArcs ( const Graph & graph )

Definition at line 191 of file graph/util.h.

◆ GraphIsSymmetric()

bool GraphIsSymmetric ( const Graph & graph )

Definition at line 217 of file graph/util.h.

◆ GraphIsWeaklyConnected()

bool GraphIsWeaklyConnected ( const Graph & graph )

Definition at line 246 of file graph/util.h.

◆ GraphToString()

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

Definition at line 107 of file io.h.

◆ IsSubsetOf0N()

bool IsSubsetOf0N	(	const std::vector< int > &	v,
		int	n
	)

Definition at line 18 of file graph/util.cc.

◆ IsValidPermutation()

bool util::IsValidPermutation ( const std::vector< int > & v )

inline

Definition at line 144 of file graph/util.h.

◆ PathHasCycle()

bool PathHasCycle	(	const Graph &	graph,
		const std::vector< int > &	arc_path
	)

Definition at line 375 of file graph/util.h.

◆ Permute() [1/2]

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

Definition at line 737 of file graph.h.

◆ Permute() [2/2]

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

Definition at line 748 of file graph.h.

◆ PermuteWithExplicitElementType()

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

Definition at line 724 of file graph.h.

◆ ReadGraphFile()

absl::StatusOr< Graph * > ReadGraphFile	(	const std::string &	filename,
		bool	directed,
		std::vector< int > *	num_nodes_with_color_or_null
	)

Definition at line 132 of file io.h.

◆ RemapGraph()

std::unique_ptr< Graph > RemapGraph	(	const Graph &	graph,
		const std::vector< int > &	new_node_index
	)

Definition at line 275 of file graph/util.h.

◆ RemoveCyclesFromPath()

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

Definition at line 350 of file graph/util.h.

◆ RemoveSelfArcsAndDuplicateArcs()

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

Definition at line 328 of file graph/util.h.

◆ Reverse()

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

Definition at line 98 of file iterators.h.

◆ StableTopologicalSort() [1/2]

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
	)

Definition at line 475 of file topologicalsorter.h.

◆ StableTopologicalSort() [2/2]

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

Definition at line 475 of file topologicalsorter.h.

◆ StableTopologicalSortOrDie()

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

Definition at line 498 of file topologicalsorter.h.

◆ TopologicalSort() [1/2]

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
	)

Definition at line 467 of file topologicalsorter.h.

◆ TopologicalSort() [2/2]

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

Definition at line 467 of file topologicalsorter.h.

◆ TopologicalSortOrDie()

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

Definition at line 492 of file topologicalsorter.h.

◆ WriteGraphToFile()

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

Definition at line 225 of file io.h.

Namespaces

Classes

Typedefs

Enumerations

Functions

Typedef Documentation

◆ DenseIntStableTopologicalSorter

◆ DenseIntTopologicalSorter

◆ Graph

Enumeration Type Documentation

◆ GraphToStringFormat

Function Documentation

◆ BeginEndRange() [1/2]

◆ BeginEndRange() [2/2]

◆ ComputeOnePossibleReverseArcMapping()

◆ CopyGraph()

◆ 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]

◆ FindCycleInDenseIntGraph()

◆ GetConnectedComponents()

◆ GetSubgraphOfNodes()

◆ GetWeaklyConnectedComponents()

◆ GraphHasDuplicateArcs()

◆ GraphHasSelfArcs()

◆ GraphIsSymmetric()

◆ GraphIsWeaklyConnected()

◆ GraphToString()

◆ IsSubsetOf0N()

◆ IsValidPermutation()

◆ PathHasCycle()

◆ Permute() [1/2]

◆ Permute() [2/2]

◆ PermuteWithExplicitElementType()

◆ ReadGraphFile()

◆ RemapGraph()

◆ RemoveCyclesFromPath()

◆ RemoveSelfArcsAndDuplicateArcs()

◆ Reverse()

◆ StableTopologicalSort() [1/2]

◆ StableTopologicalSort() [2/2]

◆ StableTopologicalSortOrDie()

◆ TopologicalSort() [1/2]

◆ TopologicalSort() [2/2]

◆ TopologicalSortOrDie()

◆ WriteGraphToFile()