C++ Reference

C++ Reference: Graph

Classes | Public Types | Public Member Functions | Static Public Attributes | Protected Member Functions | List of all members
ReverseArcListGraph< NodeIndexType, ArcIndexType >

Detailed Description

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
class util::ReverseArcListGraph< NodeIndexType, ArcIndexType >

Definition at line 473 of file graph.h.

Classes

class  IncomingArcIterator
 
class  OppositeIncomingArcIterator
 
class  OutgoingArcIterator
 
class  OutgoingHeadIterator
 
class  OutgoingOrOppositeIncomingArcIterator
 

Public Types

typedef int32_t NodeIndex
 
typedef int32_t ArcIndex
 

Public Member Functions

 ReverseArcListGraph ()
 
 ReverseArcListGraph (NodeIndexType num_nodes, ArcIndexType arc_capacity)
 
ArcIndexType OppositeArc (ArcIndexType arc) const
 
ArcIndexType OutDegree (NodeIndexType node) const
 
ArcIndexType InDegree (NodeIndexType node) const
 
BeginEndWrapper< OutgoingArcIterator > OutgoingArcs (NodeIndexType node) const
 
BeginEndWrapper< IncomingArcIterator > IncomingArcs (NodeIndexType node) const
 
BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator > OutgoingOrOppositeIncomingArcs (NodeIndexType node) const
 
BeginEndWrapper< OppositeIncomingArcIterator > OppositeIncomingArcs (NodeIndexType node) const
 
BeginEndWrapper< OutgoingArcIterator > OutgoingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const
 
BeginEndWrapper< IncomingArcIterator > IncomingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const
 
BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator > OutgoingOrOppositeIncomingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const
 
BeginEndWrapper< OppositeIncomingArcIterator > OppositeIncomingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const
 
BeginEndWrapper< OutgoingHeadIterator > operator[] (NodeIndexType node) const
 
NodeIndexType Head (ArcIndexType arc) const
 
NodeIndexType Tail (ArcIndexType arc) const
 
void ReserveNodes (NodeIndexType bound) override
 
void ReserveArcs (ArcIndexType bound) override
 
void AddNode (NodeIndexType node)
 
ArcIndexType AddArc (NodeIndexType tail, NodeIndexType head)
 
void Build ()
 
void Build (std::vector< ArcIndexType > *permutation)
 
bool IsArcValid (ArcIndexType arc) const
 
int32_t num_nodes () const
 
int32_t size () const
 
int32_t num_arcs () const
 
IntegerRange< NodeIndex > AllNodes () const
 
IntegerRange< ArcIndex > AllForwardArcs () const
 
bool IsNodeValid (int32_t node) const
 
bool IsArcValid (int32_t arc) const
 
int32_t node_capacity () const
 
int32_t arc_capacity () const
 
virtual void ReserveNodes (int32_t bound)
 
virtual void ReserveArcs (int32_t bound)
 
void Reserve (int32_t node_capacity, int32_t arc_capacity)
 
void FreezeCapacities ()
 
void GroupForwardArcsByFunctor (const A &a, B *b)
 
int32_t max_end_arc_index () const
 

Static Public Attributes

static const int32_t kNilNode
 
static const int32_t kNilArc
 

Protected Member Functions

void ComputeCumulativeSum (std::vector< int32_t > *v)
 
void BuildStartAndForwardHead (SVector< int32_t > *head, std::vector< int32_t > *start, std::vector< int32_t > *permutation)
 

Member Typedef Documentation

◆ ArcIndex

typedef int32_t ArcIndex
inherited

Definition at line 196 of file graph.h.

◆ NodeIndex

typedef int32_t NodeIndex
inherited

Definition at line 195 of file graph.h.

Constructor & Destructor Documentation

◆ ReverseArcListGraph() [1/2]

ReverseArcListGraph ( )
inline

Definition at line 484 of file graph.h.

◆ ReverseArcListGraph() [2/2]

ReverseArcListGraph ( NodeIndexType  num_nodes,
ArcIndexType  arc_capacity 
)
inline

Definition at line 485 of file graph.h.

Member Function Documentation

◆ AddArc()

ArcIndexType AddArc ( NodeIndexType  tail,
NodeIndexType  head 
)

Definition at line 1544 of file graph.h.

◆ AddNode()

void AddNode ( NodeIndexType  node)

Definition at line 1534 of file graph.h.

◆ AllForwardArcs()

IntegerRange< int32_t > AllForwardArcs
inherited

Definition at line 218 of file graph.h.

◆ AllNodes()

IntegerRange< int32_t > AllNodes
inherited

Definition at line 217 of file graph.h.

◆ arc_capacity()

int32_t arc_capacity
inherited

Definition at line 235 of file graph.h.

◆ Build() [1/2]

void Build ( )
inline

Definition at line 541 of file graph.h.

◆ Build() [2/2]

void Build ( std::vector< ArcIndexType > *  permutation)

Definition at line 1558 of file graph.h.

◆ BuildStartAndForwardHead()

void BuildStartAndForwardHead ( SVector< int32_t > *  head,
std::vector< int32_t > *  start,
std::vector< int32_t > *  permutation 
)
protectedinherited

Definition at line 280 of file graph.h.

◆ ComputeCumulativeSum()

void ComputeCumulativeSum ( std::vector< int32_t > *  v)
protectedinherited

Definition at line 279 of file graph.h.

◆ FreezeCapacities()

void FreezeCapacities
inherited

Definition at line 262 of file graph.h.

◆ GroupForwardArcsByFunctor()

void GroupForwardArcsByFunctor ( const A &  a,
B *  b 
)
inlineinherited

Definition at line 272 of file graph.h.

◆ Head()

NodeIndexType Head ( ArcIndexType  arc) const

Definition at line 1503 of file graph.h.

◆ IncomingArcs()

BeginEndWrapper<IncomingArcIterator> IncomingArcs ( NodeIndexType  node) const

◆ IncomingArcsStartingFrom()

BeginEndWrapper<IncomingArcIterator> IncomingArcsStartingFrom ( NodeIndexType  node,
ArcIndexType  from 
) const

◆ InDegree()

ArcIndexType InDegree ( NodeIndexType  node) const

Definition at line 1488 of file graph.h.

◆ IsArcValid() [1/2]

bool IsArcValid
inline

Definition at line 227 of file graph.h.

◆ IsArcValid() [2/2]

bool IsArcValid ( int32_t  arc) const
inlineinherited

Definition at line 227 of file graph.h.

◆ IsNodeValid()

bool IsNodeValid ( int32_t  node) const
inlineinherited

Definition at line 221 of file graph.h.

◆ max_end_arc_index()

int32_t max_end_arc_index ( ) const
inlineinherited

Definition at line 275 of file graph.h.

◆ node_capacity()

int32_t node_capacity
inherited

Definition at line 232 of file graph.h.

◆ num_arcs()

int32_t num_arcs ( ) const
inlineinherited

Definition at line 212 of file graph.h.

◆ num_nodes()

int32_t num_nodes ( ) const
inlineinherited

Definition at line 208 of file graph.h.

◆ operator[]()

BeginEndWrapper< typename ReverseArcListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator > operator[] ( NodeIndexType  node) const

Definition at line 1472 of file graph.h.

◆ OppositeArc()

ArcIndexType OppositeArc ( ArcIndexType  arc) const

Definition at line 1496 of file graph.h.

◆ OppositeIncomingArcs()

BeginEndWrapper<OppositeIncomingArcIterator> OppositeIncomingArcs ( NodeIndexType  node) const

◆ OppositeIncomingArcsStartingFrom()

BeginEndWrapper<OppositeIncomingArcIterator> OppositeIncomingArcsStartingFrom ( NodeIndexType  node,
ArcIndexType  from 
) const

◆ OutDegree()

ArcIndexType OutDegree ( NodeIndexType  node) const

Definition at line 1480 of file graph.h.

◆ OutgoingArcs()

BeginEndWrapper<OutgoingArcIterator> OutgoingArcs ( NodeIndexType  node) const

◆ OutgoingArcsStartingFrom()

BeginEndWrapper<OutgoingArcIterator> OutgoingArcsStartingFrom ( NodeIndexType  node,
ArcIndexType  from 
) const

◆ OutgoingOrOppositeIncomingArcs()

BeginEndWrapper<OutgoingOrOppositeIncomingArcIterator> OutgoingOrOppositeIncomingArcs ( NodeIndexType  node) const

◆ OutgoingOrOppositeIncomingArcsStartingFrom()

BeginEndWrapper<OutgoingOrOppositeIncomingArcIterator> OutgoingOrOppositeIncomingArcsStartingFrom ( NodeIndexType  node,
ArcIndexType  from 
) const

◆ Reserve()

void Reserve ( int32_t  node_capacity,
int32_t  arc_capacity 
)
inlineinherited

Definition at line 255 of file graph.h.

◆ ReserveArcs() [1/2]

void ReserveArcs ( ArcIndexType  bound)
override

Definition at line 1525 of file graph.h.

◆ ReserveArcs() [2/2]

virtual void ReserveArcs ( int32_t  bound)
inlinevirtualinherited

Definition at line 249 of file graph.h.

◆ ReserveNodes() [1/2]

virtual void ReserveNodes ( int32_t  bound)
inlinevirtualinherited

Definition at line 243 of file graph.h.

◆ ReserveNodes() [2/2]

void ReserveNodes ( NodeIndexType  bound)
override

Definition at line 1516 of file graph.h.

◆ size()

int32_t size ( ) const
inlineinherited

Definition at line 209 of file graph.h.

◆ Tail()

NodeIndexType Tail ( ArcIndexType  arc) const

Definition at line 1510 of file graph.h.

Member Data Documentation

◆ kNilArc

const int32_t kNilArc
staticinherited

Definition at line 267 of file graph.h.

◆ kNilNode

const int32_t kNilNode
staticinherited

Definition at line 266 of file graph.h.

The documentation for this class was generated from the following file: