abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
Loading...
Searching...
No Matches
Digraph Class Reference

Class describing the concept of directed graphs. More...

#include <lemon/concepts/digraph.h>

Classes

class  Node
 The node type of the digraph. More...
class  NodeIt
 Iterator class for the nodes. More...
class  Arc
 The arc type of the digraph. More...
class  OutArcIt
 Iterator class for the outgoing arcs of a node. More...
class  InArcIt
 Iterator class for the incoming arcs of a node. More...
class  ArcIt
 Iterator class for the arcs. More...
class  NodeMap
 Standard graph map type for the nodes. More...
class  ArcMap
 Standard graph map type for the arcs. More...

Public Member Functions

 Digraph ()
 Default constructor.
LemonRangeWrapper1< NodeIt , Digraph > nodes () const
 Gets the collection of the nodes of the digraph.
LemonRangeWrapper2< OutArcIt , Digraph , Node > outArcs (const Node &u) const
 Gets the collection of the outgoing arcs of a certain node of the digraph.
LemonRangeWrapper2< InArcIt , Digraph , Node > inArcs (const Node &u) const
 Gets the collection of the incoming arcs of a certain node of the digraph.
LemonRangeWrapper1< ArcIt , Digraph > arcs () const
 Gets the collection of the arcs of the digraph.
Node source (Arc) const
 The source node of the arc.
Node target (Arc) const
 The target node of the arc.
int id (Node) const
 The ID of the node.
int id (Arc) const
 The ID of the arc.
Node nodeFromId (int) const
 The node with the given ID.
Arc arcFromId (int) const
 The arc with the given ID.
int maxNodeId () const
 An upper bound on the node IDs.
int maxArcId () const
 An upper bound on the arc IDs.
Node oppositeNode (Node, Arc) const
 The opposite node on the arc.
Node baseNode (OutArcIt) const
 The base node of the iterator.
Node runningNode (OutArcIt) const
 The running node of the iterator.
Node baseNode (InArcIt) const
 The base node of the iterator.
Node runningNode (InArcIt) const
 The running node of the iterator.

Private Member Functions

 Digraph (const Digraph &)
 Diraphs are not copy constructible. Use DigraphCopy instead.
void operator= (const Digraph &)
 Assignment of a digraph to another one is not allowed. Use DigraphCopy instead.

Detailed Description

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

Member Function Documentation

◆ nodes()

LemonRangeWrapper1< NodeIt , Digraph > nodes ( ) const
inline

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:

for( auto v : g.nodes() )
doSomething( v );
//Using an STL algorithm:
copy( g.nodes().begin() , g.nodes().end() , vect.begin() );
A general directed graph structure.
Definition list_graph.h:337

◆ outArcs()

LemonRangeWrapper2< OutArcIt , Digraph , Node > outArcs ( const Node & u) const
inline

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() );

◆ inArcs()

LemonRangeWrapper2< InArcIt , Digraph , Node > inArcs ( const Node & u) const
inline

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() );

◆ arcs()

LemonRangeWrapper1< ArcIt , Digraph > arcs ( ) const
inline

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:

for( auto a : g.arcs() )
doSomething( a );
//Using an STL algorithm:
copy( g.arcs().begin() , g.arcs().end() , vect.begin() );

◆ source()

Node source ( Arc ) const
inline

Returns the source node of the given arc.

◆ target()

Node target ( Arc ) const
inline

Returns the target node of the given arc.

◆ id() [1/2]

int id ( Node ) const
inline

Returns the ID of the given node.

◆ id() [2/2]

int id ( Arc ) const
inline

Returns the ID of the given arc.

◆ nodeFromId()

Node nodeFromId ( int ) const
inline

Returns the node with the given ID.

Precondition
The argument should be a valid node ID in the digraph.

◆ arcFromId()

Arc arcFromId ( int ) const
inline

Returns the arc with the given ID.

Precondition
The argument should be a valid arc ID in the digraph.

◆ maxNodeId()

int maxNodeId ( ) const
inline

Returns an upper bound on the node IDs.

◆ maxArcId()

int maxArcId ( ) const
inline

Returns an upper bound on the arc IDs.

◆ oppositeNode()

Node oppositeNode ( Node ,
Arc  ) const
inline

Returns the opposite node on the given arc.

◆ baseNode() [1/2]

Node baseNode ( OutArcIt ) const
inline

Returns the base node of the given outgoing arc iterator (i.e. the source node of the corresponding arc).

◆ runningNode() [1/2]

Node runningNode ( OutArcIt ) const
inline

Returns the running node of the given outgoing arc iterator (i.e. the target node of the corresponding arc).

◆ baseNode() [2/2]

Node baseNode ( InArcIt ) const
inline

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

◆ runningNode() [2/2]

Node runningNode ( InArcIt ) const
inline

Returns the running node of the given incoming arc iterator (i.e. the source node of the corresponding arc).