C++ Reference

C++ Reference: Graph

Classes | Typedefs | Enumerations | Functions
util Namespace Reference

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  SVector
 
class  UndirectedAdjacencyListsOfDirectedGraph
 

Typedefs

typedef ListGraph Graph
 

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)
 
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 IsSubsetOf0N (const std::vector< int > &v, int n)
 
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

◆ 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 util.h.

◆ CopyGraph()

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

Definition at line 262 of file 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)   
)

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

◆ GetConnectedComponents()

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

Definition at line 287 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 util.h.

◆ GetWeaklyConnectedComponents()

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

Definition at line 133 of file util.h.

◆ GraphHasDuplicateArcs()

bool GraphHasDuplicateArcs ( const Graph &  graph)

Definition at line 199 of file util.h.

◆ GraphHasSelfArcs()

bool GraphHasSelfArcs ( const Graph &  graph)

Definition at line 191 of file util.h.

◆ GraphIsSymmetric()

bool GraphIsSymmetric ( const Graph &  graph)

Definition at line 217 of file util.h.

◆ GraphIsWeaklyConnected()

bool GraphIsWeaklyConnected ( const Graph &  graph)

Definition at line 246 of file util.h.

◆ GraphToString()

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

Definition at line 107 of file io.h.

◆ IsSubsetOf0N()

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

◆ IsValidPermutation()

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

Definition at line 144 of file util.h.

◆ PathHasCycle()

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

Definition at line 375 of file 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 util.h.

◆ RemoveCyclesFromPath()

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

Definition at line 350 of file util.h.

◆ RemoveSelfArcsAndDuplicateArcs()

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

Definition at line 328 of file util.h.

◆ Reverse()

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

Definition at line 98 of file iterators.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 224 of file io.h.