concepts::Graph

Declared in lemon/concepts/graph.h, in the group Graph Structure Concepts; the same class on the Doxygen site.

class Graph

Class describing the concept of undirected graphs.

This class describes the common interface of all undirected graphs.

Like all concept classes, it only provides an interface without any sensible implementation. So any general algorithm for undirected graphs should compile with this class, but it will not run properly, of course. An actual graph implementation like ListGraph or SmartGraph may have additional functionality.

The undirected graphs also fulfill the concept of directed graphs, since each edge can also be regarded as two oppositely directed arcs. Undirected graphs provide an Edge type for the undirected edges and an Arc type for the directed arcs. The Arc type is convertible to Edge or inherited from it, i.e. the corresponding edge can be obtained from an arc. EdgeIt and EdgeMap classes can be used for the edges, while ArcIt and ArcMap classes can be used for the arcs (just like in digraphs). Both InArcIt and OutArcIt iterates on the same edges but with opposite direction. IncEdgeIt also iterates on the same edges as OutArcIt and InArcIt, but it is not convertible to Arc, only to Edge.

In LEMON, each undirected edge has an inherent orientation. Thus it can defined if an arc is forward or backward oriented in an undirected graph with respect to this default oriantation of the represented edge. With the direction() and direct() functions the direction of an arc can be obtained and set, respectively.

Only nodes and edges can be added to or removed from an undirected graph and the corresponding arcs are added or removed automatically.

See also

Digraph

Public Types

typedef True UndirectedTag

Undirected graphs should be tagged with UndirectedTag.

This tag helps the enable_if technics to make compile time specializations for undirected graphs.

Public Functions

inline Graph()

Default constructor.

inline LemonRangeWrapper1< NodeIt , Graph > nodes() const

Gets the collection of the nodes of the graph.

This function can be used for iterating on the nodes of the graph. 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:

ListGraph g;
for( auto v : g.nodes() )
 doSomething( v );

//Using an STL algorithm:
copy( g.nodes().begin() , g.nodes().end() , vect.begin() );

inline LemonRangeWrapper1< EdgeIt , Graph > edges() const

Gets the collection of the edges of the graph.

This function can be used for iterating on the edges of the graph. It returns a wrapped EdgeIt, 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:

ListGraph g;
for( auto e : g.edges() )
 doSomething( e );

//Using an STL algorithm:
copy( g.edges().begin() , g.edges().end() , vect.begin() );

inline LemonRangeWrapper2< IncEdgeIt , Graph , Node > incEdges( const Node & u ) const

Gets the collection of the incident undirected edges of a certain node of the graph.

This function can be used for iterating on the incident undirected edges of a certain node of the graph. It returns a wrapped IncEdgeIt, 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 Graph and u is a Node, you can write:

for( auto e : g.incEdges( u ) )
 doSomething( e );

//Using an STL algorithm:
copy( g.incEdges( u ).begin() , g.incEdges( u ).end() , vect.begin() );

inline LemonRangeWrapper1< ArcIt , Graph > arcs() const

Gets the collection of the directed arcs of the graph.

This function can be used for iterating on the arcs of the graph. 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:

ListGraph g;
for( auto a : g.arcs() )
 doSomething( a );

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

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

Gets the collection of the outgoing directed arcs of a certain node of the graph.

This function can be used for iterating on the outgoing arcs of a certain node of the graph. 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 Graph 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 , Graph , Node > inArcs( const Node & u ) const

Gets the collection of the incoming directed arcs of a certain node of the graph.

This function can be used for iterating on the incoming directed arcs of a certain node of the graph. 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 Graph 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 Node u(Edge) const

The first node of the edge.

Returns the first node of the given edge.

Edges don’t have source and target nodes, however, methods u() and v() are used to query the two end-nodes of an edge. The orientation of an edge that arises this way is called the inherent direction, it is used to define the default direction for the corresponding arcs.

See also

v()

See also

direction()

inline Node v(Edge) const

The second node of the edge.

Returns the second node of the given edge.

Edges don’t have source and target nodes, however, methods u() and v() are used to query the two end-nodes of an edge. The orientation of an edge that arises this way is called the inherent direction, it is used to define the default direction for the corresponding arcs.

See also

u()

See also

direction()

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(Edge) const

The ID of the edge.

Returns the ID of the given edge.

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

inline Edge edgeFromId(int) const

The edge with the given ID.

Returns the edge with the given ID.

Pre:

The argument should be a valid edge ID in the graph.

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

inline int maxNodeId() const

An upper bound on the node IDs.

Returns an upper bound on the node IDs.

inline int maxEdgeId() const

An upper bound on the edge IDs.

Returns an upper bound on the edge IDs.

inline int maxArcId() const

An upper bound on the arc IDs.

Returns an upper bound on the arc IDs.

inline bool direction(Arc) const

The direction of the arc.

Returns true if the direction of the given arc is the same as the inherent orientation of the represented edge.

inline Arc direct(Edge, bool) const

Direct the edge.

Direct the given edge. The returned arc represents the given edge and its direction comes from the bool parameter. If it is true, then the direction of the arc is the same as the inherent orientation of the edge.

inline Arc direct(Edge, Node) const

Direct the edge.

Direct the given edge. The returned arc represents the given edge and its source node is the given node.

inline Arc oppositeArc(Arc) const

The oppositely directed arc.

Returns the oppositely directed arc representing the same edge.

inline Node oppositeNode(Node, Edge) const

The opposite node on the edge.

Returns the opposite node on the given edge.

inline void first(Node&) const
inline void next(Node&) const
inline void first(Edge&) const
inline void next(Edge&) const
inline void first(Arc&) const
inline void next(Arc&) const
inline void firstOut(Arc&, Node) const
inline void nextOut(Arc&) const
inline void firstIn(Arc&, Node) const
inline void nextIn(Arc&) const
inline void firstInc( Edge & , bool & , const Node & ) const
inline void nextInc(Edge&, bool&) const
inline Node fromId(int, Node) const
inline Edge fromId(int, Edge) const
inline Arc fromId(int, Arc) const
inline int maxId(Node) const
inline int maxId(Edge) const
inline int maxId(Arc) const
inline Node baseNode(IncEdgeIt) const

The base node of the iterator.

Returns the base node of the given incident edge iterator.

inline Node runningNode(IncEdgeIt) const

The running node of the iterator.

Returns the running node of the given incident edge iterator.

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

This class identifies a node of the graph. It also serves as a base class of the node iterators, thus they convert to this type.

Subclassed by Graph::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 items; this order has nothing to do with the iteration ordering of the items.

class NodeIt : public Graph::Node

Iterator class for the nodes.

This iterator goes through each node of the graph. Its usage is quite simple, for example, you can count the number of nodes in a graph g of type Graph like this:

int count = 0;
for( Graph::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 Graph & )

Sets the iterator to the first node.

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

inline NodeIt( const Graph & , 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 Edge

The edge type of the graph.

This class identifies an edge of the graph. It also serves as a base class of the edge iterators, thus they will convert to this type.

Subclassed by Graph::EdgeIt, Graph::IncEdgeIt

Public Functions

inline Edge()

Default constructor.

Warning

It sets the object to an undefined value.

inline Edge( const Edge & )

Copy constructor.

inline const Edge & operator=( const Edge & )

Assignment operator.

inline Edge(Invalid)

Invalid constructor & conversion.

Initializes the object to be invalid.

See also

Invalid for more details.

inline bool operator==(Edge) const

Equality operator.

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

inline bool operator!=(Edge) const

Inequality operator.

inline bool operator<(Edge) const

Artificial ordering operator.

Note

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

class EdgeIt : public Graph::Edge

Iterator class for the edges.

This iterator goes through each edge of the graph. Its usage is quite simple, for example, you can count the number of edges in a graph g of type Graph as follows:

int count = 0;
for( Graph::EdgeIt e( g ) ; e != INVALID ; ++e )
 ++count;

Public Functions

inline EdgeIt()

Default constructor.

Warning

It sets the iterator to an undefined value.

inline EdgeIt( const EdgeIt & e )

Copy constructor.

inline const EdgeIt & operator=( const EdgeIt & )

Assignment operator.

inline EdgeIt(Invalid)

Invalid constructor & conversion.

Initializes the iterator to be invalid.

See also

Invalid for more details.

inline explicit EdgeIt( const Graph & )

Sets the iterator to the first edge.

Sets the iterator to the first edge of the given graph.

inline EdgeIt( const Graph & , const Edge & )

Sets the iterator to the given edge.

Sets the iterator to the given edge of the given graph.

inline EdgeIt & operator++()

Next edge.

Assign the iterator to the next edge.

class IncEdgeIt : public Graph::Edge

Iterator class for the incident edges of a node.

This iterator goes trough the incident undirected edges of a certain node of a graph. Its usage is quite simple, for example, you can compute the degree (i.e. the number of incident edges) of a node n in a graph g of type Graph as follows.

int count = 0;
for( Graph::IncEdgeIt e( g , n ) ; e != INVALID ; ++e )
 ++count;

Warning

Loop edges will be iterated twice.

Public Functions

inline IncEdgeIt()

Default constructor.

Warning

It sets the iterator to an undefined value.

inline IncEdgeIt( const IncEdgeIt & e )

Copy constructor.

inline const IncEdgeIt & operator=( const IncEdgeIt & )

Assignment operator.

inline IncEdgeIt(Invalid)

Invalid constructor & conversion.

Initializes the iterator to be invalid.

See also

Invalid for more details.

inline IncEdgeIt( const Graph & , const Node & )

Sets the iterator to the first incident edge.

Sets the iterator to the first incident edge of the given node.

inline IncEdgeIt( const Graph & , const Edge & )

Sets the iterator to the given edge.

Sets the iterator to the given edge of the given graph.

inline IncEdgeIt & operator++()

Next incident edge.

Assign the iterator to the next incident edge of the corresponding node.

class Arc

The arc type of the graph.

This class identifies a directed arc of the graph. It also serves as a base class of the arc iterators, thus they will convert to this type.

Subclassed by Graph::ArcIt, Graph::InArcIt, Graph::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.

inline operator Edge() const

Converison to Edge.

class ArcIt : public Graph::Arc

Iterator class for the arcs.

This iterator goes through each directed arc of the graph. Its usage is quite simple, for example, you can count the number of arcs in a graph g of type Graph as follows:

int count = 0;
for( Graph::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 Graph & g )

Sets the iterator to the first arc.

Sets the iterator to the first arc of the given graph.

inline ArcIt( const Graph & , const Arc & )

Sets the iterator to the given arc.

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

inline ArcIt & operator++()

Next arc.

Assign the iterator to the next arc.

class OutArcIt : public Graph::Arc

Iterator class for the outgoing arcs of a node.

This iterator goes trough the outgoing directed arcs of a certain node of a graph. Its usage is quite simple, for example, you can count the number of outgoing arcs of a node n in a graph g of type Graph 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 Graph & n , const Node & g )

Sets the iterator to the first outgoing arc.

Sets the iterator to the first outgoing arc of the given node.

inline OutArcIt( const Graph & , const Arc & )

Sets the iterator to the given arc.

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

inline OutArcIt & operator++()

Next outgoing arc.

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

class InArcIt : public Graph::Arc

Iterator class for the incoming arcs of a node.

This iterator goes trough the incoming directed arcs of a certain node of a graph. Its usage is quite simple, for example, you can count the number of incoming arcs of a node n in a graph g of type Graph 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 Graph & g , const Node & n )

Sets the iterator to the first incoming arc.

Sets the iterator to the first incoming arc of the given node.

inline InArcIt( const Graph & , const Arc & )

Sets the iterator to the given arc.

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

inline InArcIt & operator++()

Next incoming arc.

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

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 Graph & )

Constructor.

inline NodeMap( const Graph & , T )

Constructor with given initial value.

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 Graph & )

Constructor.

inline ArcMap( const Graph & , T )

Constructor with given initial value.

template< class T >
class EdgeMap : public ReferenceMap< Edge , T , T& , const T& >

Standard graph map type for the edges. It conforms to the ReferenceMap concept.

Public Functions

inline explicit EdgeMap( const Graph & )

Constructor.

inline EdgeMap( const Graph & , T )

Constructor with given initial value.

template< typename _Graph >
struct Constraints

Public Functions

inline void constraints()