util::graph Namespace Reference

Functions
template<class Graph, class NodeIndex = int>
absl::StatusOr< std::vector< NodeIndex > >	GetBFSRootedTree (const Graph &graph, NodeIndex num_nodes, NodeIndex source)
template<class NodeIndex>
absl::StatusOr< std::vector< NodeIndex > >	GetBFSDistances (const std::vector< NodeIndex > &bfs_tree)
template<class NodeIndex>
absl::StatusOr< std::vector< NodeIndex > >	GetBFSShortestPath (const std::vector< NodeIndex > &bfs_tree, NodeIndex target)
template<class AdjacencyLists>
absl::StatusOr< std::vector< typename util::GraphTraits< AdjacencyLists >::NodeIndex > >	FastTopologicalSort (const AdjacencyLists &adj)
template<class AdjacencyLists>
absl::StatusOr< std::vector< typename util::GraphTraits< AdjacencyLists >::NodeIndex > >	FindCycleInGraph (const AdjacencyLists &adj)
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 >	StableTopologicalSortOrDie (const std::vector< T > &nodes, const std::vector< std::pair< T, T > > &arcs)
template<class AdjacencyLists>
absl::StatusOr< std::vector< typename GraphTraits< AdjacencyLists >::NodeIndex > >	FastTopologicalSort (const AdjacencyLists &adj)

Function Documentation

DenseIntStableTopologicalSortOrDie()

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

inline

Definition at line 613 of file topologicalsorter.h.

DenseIntTopologicalSortOrDie()

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

inline

Definition at line 609 of file topologicalsorter.h.

FastTopologicalSort() [1/2]

template<class AdjacencyLists>

absl::StatusOr< std::vector< typename GraphTraits< AdjacencyLists >::NodeIndex > > util::graph::FastTopologicalSort

(

const AdjacencyLists &

adj

)

Definition at line 625 of file topologicalsorter.h.

FastTopologicalSort() [2/2]

template<class AdjacencyLists>

absl::StatusOr< std::vector< typename util::GraphTraits< AdjacencyLists >::NodeIndex > > util::graph::FastTopologicalSort

(

const AdjacencyLists &

adj

)

Definition at line 625 of file topologicalsorter.h.

FindCycleInGraph()

template<class AdjacencyLists>

absl::StatusOr< std::vector< typename util::GraphTraits< AdjacencyLists >::NodeIndex > > util::graph::FindCycleInGraph

(

const AdjacencyLists &

adj

)

Definition at line 667 of file topologicalsorter.h.

GetBFSDistances()

template<class NodeIndex>

absl::StatusOr< std::vector< NodeIndex > > util::graph::GetBFSDistances

(

const std::vector< NodeIndex > &

bfs_tree

)

Definition at line 135 of file bfs.h.

GetBFSRootedTree()

template<class Graph, class NodeIndex = int>

absl::StatusOr< std::vector< NodeIndex > > util::graph::GetBFSRootedTree	(	const Graph &	graph,
		NodeIndex	num_nodes,
		NodeIndex	source )

Definition at line 101 of file bfs.h.

GetBFSShortestPath()

template<class NodeIndex>

absl::StatusOr< std::vector< NodeIndex > > util::graph::GetBFSShortestPath	(	const std::vector< NodeIndex > &	bfs_tree,
		NodeIndex	target )

Definition at line 196 of file bfs.h.

StableTopologicalSortOrDie()

template<typename T>

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

Definition at line 618 of file topologicalsorter.h.