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
Public Types
-
typedef True UndirectedTag
Undirected graphs should be tagged with
UndirectedTag.This tag helps the
enable_iftechnics 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
See also
-
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
See also
-
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 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
trueif 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 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).
-
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(Invalid)
Invalid constructor & conversion.
Initializes the object to be invalid.
See also
Invalid for more details.
-
inline Node()
-
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
gof typeGraphlike 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(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()
-
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(Invalid)
Invalid constructor & conversion.
Initializes the object to be invalid.
See also
Invalid for more details.
-
inline Edge()
-
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
gof typeGraphas 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(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()
-
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
nin a graphgof typeGraphas 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(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()
-
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(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 Arc()
-
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
gof typeGraphas 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(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()
-
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
nin a graphgof typeGraphas 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 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()
-
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
nin a graphgof typeGraphas 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 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()
-
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.
-
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.
-
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.
-
typedef True UndirectedTag