concepts::Digraph
Declared in lemon/concepts/digraph.h, in the group Graph Structure Concepts; the same class on the Doxygen site.
-
class Digraph
Class describing the concept of directed graphs.
This class describes the common interface of all directed graphs (digraphs).
Like all concept classes, it only provides an interface without any sensible implementation. So any general algorithm for directed graphs should compile with this class, but it will not run properly, of course. An actual digraph implementation like ListDigraph or SmartDigraph may have additional functionality.
See also
Public Functions
-
inline Digraph()
Default constructor.
-
inline LemonRangeWrapper1< NodeIt , Digraph > nodes() const
Gets the collection of the nodes of the digraph.
This function can be used for iterating on the nodes of the digraph. It returns a wrapped NodeIt, which looks like an STL container (by having begin() and end()) which you can use in range-based for loops, STL algorithms, etc. For example you can write:
ListDigraph g; for( auto v : g.nodes() ) doSomething( v ); //Using an STL algorithm: copy( g.nodes().begin() , g.nodes().end() , vect.begin() );
-
inline LemonRangeWrapper2< OutArcIt , Digraph , Node > outArcs( const Node & u ) const
Gets the collection of the outgoing arcs of a certain node of the digraph.
This function can be used for iterating on the outgoing arcs of a certain node of the digraph. It returns a wrapped OutArcIt, which looks like an STL container (by having begin() and end()) which you can use in range-based for loops, STL algorithms, etc. For example if g is a Digraph and u is a node, you can write:
for( auto a : g.outArcs( u ) ) doSomething( a ); //Using an STL algorithm: copy( g.outArcs( u ).begin() , g.outArcs( u ).end() , vect.begin() );
-
inline LemonRangeWrapper2< InArcIt , Digraph , Node > inArcs( const Node & u ) const
Gets the collection of the incoming arcs of a certain node of the digraph.
This function can be used for iterating on the incoming arcs of a certain node of the digraph. It returns a wrapped InArcIt, which looks like an STL container (by having begin() and end()) which you can use in range-based for loops, STL algorithms, etc. For example if g is a Digraph and u is a node, you can write:
for( auto a : g.inArcs( u ) ) doSomething( a ); //Using an STL algorithm: copy( g.inArcs( u ).begin() , g.inArcs( u ).end() , vect.begin() );
-
inline LemonRangeWrapper1< ArcIt , Digraph > arcs() const
Gets the collection of the arcs of the digraph.
This function can be used for iterating on the arcs of the digraph. It returns a wrapped ArcIt, which looks like an STL container (by having begin() and end()) which you can use in range-based for loops, STL algorithms, etc. For example you can write:
ListDigraph g; for( auto a : g.arcs() ) doSomething( a ); //Using an STL algorithm: copy( g.arcs().begin() , g.arcs().end() , vect.begin() );
-
inline Node source(Arc) const
The source node of the arc.
Returns the source node of the given arc.
-
inline Node target(Arc) const
The target node of the arc.
Returns the target node of the given arc.
-
inline Node nodeFromId(int) const
The node with the given ID.
Returns the node with the given ID.
- Pre:
The argument should be a valid node ID in the digraph.
-
inline Arc arcFromId(int) const
The arc with the given ID.
Returns the arc with the given ID.
- Pre:
The argument should be a valid arc ID in the digraph.
-
inline int maxNodeId() const
An upper bound on the node IDs.
Returns an upper bound on the node IDs.
-
inline int maxArcId() const
An upper bound on the arc IDs.
Returns an upper bound on the arc IDs.
-
inline Node oppositeNode(Node, Arc) const
The opposite node on the arc.
Returns the opposite node on the given arc.
-
inline Node baseNode(OutArcIt) const
The base node of the iterator.
Returns the base node of the given outgoing arc iterator (i.e. the source node of the corresponding arc).
-
inline Node runningNode(OutArcIt) const
The running node of the iterator.
Returns the running node of the given outgoing arc iterator (i.e. the target node of the corresponding arc).
-
class Node
The node type of the digraph.
This class identifies a node of the digraph. It also serves as a base class of the node iterators, thus they convert to this type.
Subclassed by Digraph::NodeIt
Public Functions
-
inline Node()
Default constructor.
Warning
It sets the object to an undefined value.
-
inline Node(Invalid)
Invalid constructor & conversion.
Initializes the object to be invalid.
See also
Invalid for more details.
-
inline Node()
-
class NodeIt : public Digraph::Node
Iterator class for the nodes.
This iterator goes through each node of the digraph. Its usage is quite simple, for example, you can count the number of nodes in a digraph
gof typeDigraphlike this:int count = 0; for( Digraph::NodeIt n( g ) ; n != INVALID ; ++n ) ++count;
Public Functions
-
inline NodeIt()
Default constructor.
Warning
It sets the iterator to an undefined value.
-
inline NodeIt(Invalid)
Invalid constructor & conversion.
Initializes the iterator to be invalid.
See also
Invalid for more details.
-
inline explicit NodeIt( const Digraph & )
Sets the iterator to the first node.
Sets the iterator to the first node of the given digraph.
-
inline NodeIt()
-
class Arc
The arc type of the digraph.
This class identifies an arc of the digraph. It also serves as a base class of the arc iterators, thus they will convert to this type.
Subclassed by Digraph::ArcIt, Digraph::InArcIt, Digraph::OutArcIt
Public Functions
-
inline Arc()
Default constructor.
Warning
It sets the object to an undefined value.
-
inline Arc(Invalid)
Invalid constructor & conversion.
Initializes the object to be invalid.
See also
Invalid for more details.
-
inline Arc()
-
class OutArcIt : public Digraph::Arc
Iterator class for the outgoing arcs of a node.
This iterator goes trough the outgoing arcs of a certain node of a digraph. Its usage is quite simple, for example, you can count the number of outgoing arcs of a node
nin a digraphgof typeDigraphas follows.int count = 0; for( Digraph::OutArcIt a( g , n ) ; a != INVALID ; ++a ) ++count;
Public Functions
-
inline OutArcIt()
Default constructor.
Warning
It sets the iterator to an undefined value.
-
inline OutArcIt(Invalid)
Invalid constructor & conversion.
Initializes the iterator to be invalid.
See also
Invalid for more details.
-
inline OutArcIt( const Digraph & , const Node & )
Sets the iterator to the first outgoing arc.
Sets the iterator to the first outgoing arc of the given node.
-
inline OutArcIt()
-
class InArcIt : public Digraph::Arc
Iterator class for the incoming arcs of a node.
This iterator goes trough the incoming arcs of a certain node of a digraph. Its usage is quite simple, for example, you can count the number of incoming arcs of a node
nin a digraphgof typeDigraphas follows.int count = 0; for( Digraph::InArcIt a( g , n ) ; a != INVALID ; ++a ) ++count;
Public Functions
-
inline InArcIt()
Default constructor.
Warning
It sets the iterator to an undefined value.
-
inline InArcIt(Invalid)
Invalid constructor & conversion.
Initializes the iterator to be invalid.
See also
Invalid for more details.
-
inline InArcIt( const Digraph & , const Node & )
Sets the iterator to the first incoming arc.
Sets the iterator to the first incoming arc of the given node.
-
inline InArcIt()
-
class ArcIt : public Digraph::Arc
Iterator class for the arcs.
This iterator goes through each arc of the digraph. Its usage is quite simple, for example, you can count the number of arcs in a digraph
gof typeDigraphas follows:int count = 0; for( Digraph::ArcIt a( g ) ; a != INVALID ; ++a ) ++count;
Public Functions
-
inline ArcIt()
Default constructor.
Warning
It sets the iterator to an undefined value.
-
inline ArcIt(Invalid)
Invalid constructor & conversion.
Initializes the iterator to be invalid.
See also
Invalid for more details.
-
inline explicit ArcIt( const Digraph & g )
Sets the iterator to the first arc.
Sets the iterator to the first arc of the given digraph.
-
inline ArcIt()
-
template< class T >
class NodeMap : public ReferenceMap< Node , T , T& , const T& > Standard graph map type for the nodes. It conforms to the ReferenceMap concept.
Public Functions
-
template< class T >
class ArcMap : public ReferenceMap< Arc , T , T& , const T& > Standard graph map type for the arcs. It conforms to the ReferenceMap concept.
-
inline Digraph()