Google OR-Tools: util Namespace Reference

Classes
class	StatusBuilder
class	FlowGraph
class	BaseGraph
class	ArcPropertyIterator
struct	GraphTraits
class	ListGraph
class	StaticGraph
class	ReverseArcListGraph
class	ReverseArcStaticGraph
class	CompleteGraph
class	CompleteBipartiteGraph
class	BeginEndWrapper
class	BeginEndReverseIteratorWrapper
class	IntegerRangeIterator
class	IntegerRange
class	ChasingIterator
class	TopologicalSorter
class	UndirectedAdjacencyListsOfDirectedGraph

Typedefs
template<typename Graph, typename ArcIterator>
using	ArcHeadIterator
template<typename Graph, typename ArcIterator>
using	ArcOppositeArcIterator
typedef ListGraph	Graph
typedef ::util::internal::DenseIntTopologicalSorterTpl< true >	DenseIntStableTopologicalSorter
typedef ::util::internal::DenseIntTopologicalSorterTpl< false >	DenseIntTopologicalSorter

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>
void	Permute (const IntVector &permutation, Array *array_to_permute)
	DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcListGraph, OutgoingOrOppositeIncoming)
	DEFINE_RANGE_BASED_ARC_ITERATION (ReverseArcStaticGraph, OutgoingOrOppositeIncoming)
template<class Graph>
std::string	GraphToString (const Graph &graph, GraphToStringFormat format)
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<class Graph>
std::unique_ptr< Graph >	Create2DGridGraph (int64_t width, int64_t height)
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)
template<typename T>
std::vector< T >	TopologicalSortOrDie (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs)
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)
template<typename T>
std::vector< T >	StableTopologicalSortOrDie (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs)
ABSL_MUST_USE_RESULT 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)
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)
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)
bool	IsSubsetOf0N (absl::Span< const 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, 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>
	UndirectedAdjacencyListsOfDirectedGraph (const Graph &) -> UndirectedAdjacencyListsOfDirectedGraph< Graph >
template<class Graph>
std::vector< int >	GetWeaklyConnectedComponents (const Graph &graph)
bool	IsValidPermutation (absl::Span< const 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, absl::Span< const int > arc_path)
template<class Graph>
std::vector< int >	ComputeOnePossibleReverseArcMapping (const Graph &graph, bool die_if_not_symmetric)

◆ ArcHeadIterator

template<typename Graph, typename ArcIterator>

Initial value:

NodeIndexType Head(ArcIndexType arc) const

Definition at line 381 of file graph.h.

◆ ArcOppositeArcIterator

template<typename Graph, typename ArcIterator>

Initial value:

Definition at line 387 of file graph.h.

◆ DenseIntStableTopologicalSorter

◆ DenseIntTopologicalSorter

◆ Graph

◆ GraphToStringFormat

Enumerator
PRINT_GRAPH_ARCS
PRINT_GRAPH_ADJACENCY_LISTS
PRINT_GRAPH_ADJACENCY_LISTS_SORTED
PRINT_GRAPH_DOT

Definition at line 42 of file graph_io.h.

◆ AbortedErrorBuilder()

◆ AlreadyExistsErrorBuilder()

◆ BeginEndRange() [1/2]

template<typename Iterator>

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

inline

◆ BeginEndRange() [2/2]

template<typename Iterator>

BeginEndWrapper< Iterator > util::BeginEndRange

(

std::pair< Iterator, Iterator >

begin_end

)

inline

◆ CancelledErrorBuilder()

◆ ComputeOnePossibleReverseArcMapping()

template<class Graph>

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

Definition at line 397 of file util.h.

◆ CopyGraph()

template<class Graph>

std::unique_ptr< Graph > util::CopyGraph

(

const Graph &

graph

)

Definition at line 273 of file util.h.

◆ Create2DGridGraph()

template<class Graph>

std::unique_ptr< Graph > util::Create2DGridGraph	(	int64_t	width,
		int64_t	height )

◆ DataLossErrorBuilder()

◆ DeadlineExceededErrorBuilder()

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [1/2]

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [2/2]

◆ DenseIntStableTopologicalSort()

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

inline

◆ DenseIntStableTopologicalSortOrDie()

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

inline

◆ DenseIntTopologicalSort()

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

inline

◆ DenseIntTopologicalSortOrDie()

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

inline

◆ EqualRange() [1/2]

template<typename MultiMap>

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

inline

◆ EqualRange() [2/2]

template<typename MultiMap>

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

inline

◆ FailedPreconditionErrorBuilder()

◆ FindCycleInDenseIntGraph()

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

inline

◆ GenerateRandomDirectedSimpleGraph()

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

◆ GenerateRandomMultiGraph()

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

◆ GenerateRandomUndirectedSimpleGraph()

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

◆ GetConnectedComponents()

template<class UndirectedGraph>

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

◆ GetConnectedComponentsTpl()

template<class UndirectedGraph, class NodeType>

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

◆ GetSubgraphOfNodes()

template<class Graph>

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

Definition at line 305 of file util.h.

◆ GetWeaklyConnectedComponents()

template<class Graph>

std::vector< int > util::GetWeaklyConnectedComponents

(

const Graph &

graph

)

Definition at line 144 of file util.h.

◆ GraphHasDuplicateArcs()

template<class Graph>

bool util::GraphHasDuplicateArcs

(

const Graph &

graph

)

Definition at line 210 of file util.h.

◆ GraphHasSelfArcs()

template<class Graph>

bool util::GraphHasSelfArcs

(

const Graph &

graph

)

Definition at line 202 of file util.h.

◆ GraphIsSymmetric()

template<class Graph>

bool util::GraphIsSymmetric

(

const Graph &

graph

)

Definition at line 228 of file util.h.

◆ GraphIsWeaklyConnected()

template<class Graph>

bool util::GraphIsWeaklyConnected

(

const Graph &

graph

)

Definition at line 257 of file util.h.

◆ GraphToString()

template<class Graph>

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

◆ InternalErrorBuilder()

◆ InvalidArgumentErrorBuilder()

◆ IsSubsetOf0N()

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

Definition at line 22 of file util.cc.

◆ IsValidPermutation()

bool util::IsValidPermutation

(

absl::Span< const int >

)

inline

Definition at line 155 of file util.h.

◆ NotFoundErrorBuilder()

◆ OutOfRangeErrorBuilder()

◆ PathHasCycle()

template<class Graph>

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

Definition at line 386 of file util.h.

◆ PermissionDeniedErrorBuilder()

◆ Permute()

template<class IntVector, class Array>

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

◆ RemapGraph()

template<class Graph>

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

Definition at line 286 of file util.h.

◆ RemoveCyclesFromPath()

template<class Graph>

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

Definition at line 361 of file util.h.

◆ RemoveSelfArcsAndDuplicateArcs()

template<class Graph>

std::unique_ptr< Graph > util::RemoveSelfArcsAndDuplicateArcs

(

const Graph &

graph

)

Definition at line 339 of file util.h.

◆ ResourceExhaustedErrorBuilder()

◆ Reverse()

◆ StableTopologicalSort() [1/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 )

◆ StableTopologicalSort() [2/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 )

◆ StableTopologicalSort() [3/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 )

◆ StableTopologicalSort() [4/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 )

◆ StableTopologicalSortOrDie()

template<typename T>

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

◆ TopologicalSort() [1/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 )

◆ TopologicalSort() [2/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 )

◆ TopologicalSort() [3/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 )

◆ TopologicalSort() [4/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 )

◆ TopologicalSortOrDie()

template<typename T>

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

◆ UnauthenticatedErrorBuilder()

◆ UnavailableErrorBuilder()

◆ UndirectedAdjacencyListsOfDirectedGraph()

template<class Graph>

util::UndirectedAdjacencyListsOfDirectedGraph

(

const Graph &

)

->UndirectedAdjacencyListsOfDirectedGraph< Graph >

◆ UnimplementedErrorBuilder()

◆ UnknownErrorBuilder()

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

Classes

Typedefs

Functions

◆ ArcHeadIterator

◆ ArcOppositeArcIterator

◆ DenseIntStableTopologicalSorter

◆ DenseIntTopologicalSorter

◆ Graph

◆ GraphToStringFormat

◆ AbortedErrorBuilder()

◆ AlreadyExistsErrorBuilder()

◆ BeginEndRange() [1/2]

◆ BeginEndRange() [2/2]

◆ CancelledErrorBuilder()

◆ ComputeOnePossibleReverseArcMapping()

◆ CopyGraph()

◆ Create2DGridGraph()

◆ DataLossErrorBuilder()

◆ DeadlineExceededErrorBuilder()

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [1/2]

◆ DEFINE_RANGE_BASED_ARC_ITERATION() [2/2]

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

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

◆ TopologicalSort() [4/4]

◆ TopologicalSortOrDie()

◆ UnauthenticatedErrorBuilder()

◆ UnavailableErrorBuilder()

◆ UndirectedAdjacencyListsOfDirectedGraph()

◆ UnimplementedErrorBuilder()

◆ UnknownErrorBuilder()

◆ WriteGraphToFile()