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

Graph

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 int id(Node) const

The ID of the node.

Returns the ID of the given node.

inline int id(Arc) const

The ID of the arc.

Returns the ID 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 void first(Node&) const
inline void next(Node&) const
inline void first(Arc&) const
inline void next(Arc&) const
inline void firstIn( Arc & , const Node & ) const
inline void nextIn(Arc&) const
inline void firstOut( Arc & , const Node & ) const
inline void nextOut(Arc&) const
inline Node fromId(int, Node) const
inline Arc fromId(int, Arc) const
inline int maxId(Node) const
inline int maxId(Arc) const
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).

inline Node baseNode(InArcIt) const

The base node of the iterator.

Returns the base node of the given incoming arc iterator (i.e. the target node of the corresponding arc).

inline Node runningNode(InArcIt) const

The running node of the iterator.

Returns the running node of the given incoming arc iterator (i.e. the source 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( const Node & )

Copy constructor.

inline const Node & operator=( const Node & )

Assignment operator.

inline Node(Invalid)

Invalid constructor & conversion.

Initializes the object to be invalid.

See also

Invalid for more details.

inline bool operator==(Node) const

Equality operator.

Two iterators are equal if and only if they point to the same object or both are INVALID.

inline bool operator!=(Node) const

Inequality operator.

inline bool operator<(Node) const

Artificial ordering operator.

Note

This operator only has to define some strict ordering of the nodes; this order has nothing to do with the iteration ordering of the nodes.

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 g of type Digraph like 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( const NodeIt & n )

Copy constructor.

inline const NodeIt & operator=( const NodeIt & )

Assignment operator.

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( const Digraph & , const Node & )

Sets the iterator to the given node.

Sets the iterator to the given node of the given digraph.

inline NodeIt & operator++()

Next node.

Assign the iterator to the next node.

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( const Arc & )

Copy constructor.

inline const Arc & operator=( const Arc & )

Assignment operator.

inline Arc(Invalid)

Invalid constructor & conversion.

Initializes the object to be invalid.

See also

Invalid for more details.

inline bool operator==(Arc) const

Equality operator.

Two iterators are equal if and only if they point to the same object or both are INVALID.

inline bool operator!=(Arc) const

Inequality operator.

inline bool operator<(Arc) const

Artificial ordering operator.

Note

This operator only has to define some strict ordering of the arcs; this order has nothing to do with the iteration ordering of the arcs.

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 n in a digraph g of type Digraph as 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( const OutArcIt & e )

Copy constructor.

inline const OutArcIt & operator=( const OutArcIt & )

Assignment operator.

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( const Digraph & , const Arc & )

Sets the iterator to the given arc.

Sets the iterator to the given arc of the given digraph.

inline OutArcIt & operator++()

Next outgoing arc.

Assign the iterator to the next outgoing arc of the corresponding node.

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 n in a digraph g of type Digraph as 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( const InArcIt & e )

Copy constructor.

inline const InArcIt & operator=( const InArcIt & )

Assignment operator.

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( const Digraph & , const Arc & )

Sets the iterator to the given arc.

Sets the iterator to the given arc of the given digraph.

inline InArcIt & operator++()

Next incoming arc.

Assign the iterator to the next incoming arc of the corresponding node.

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 g of type Digraph as 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( const ArcIt & e )

Copy constructor.

inline const ArcIt & operator=( const ArcIt & )

Assignment operator.

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( const Digraph & , const Arc & )

Sets the iterator to the given arc.

Sets the iterator to the given arc of the given digraph.

inline ArcIt & operator++()

Next arc.

Assign the iterator to the next arc.

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

inline explicit NodeMap( const Digraph & )

Constructor.

inline NodeMap( const Digraph & , T )

Constructor with given initial value.

inline NodeMap & operator=( const NodeMap & )

Assignment operator.

template< typename CMap >
inline NodeMap & operator=( const CMap & )

Template Assignment operator.

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.

Public Functions

inline explicit ArcMap( const Digraph & )

Constructor.

inline ArcMap( const Digraph & , T )

Constructor with given initial value.

template< typename _Digraph >
struct Constraints

Public Functions

inline void constraints()