This class describes the common interface of all Undirected Graphs.
As all concept describing classes it provides only interface without any sensible implementation. So any algorithm for undirected graph should compile with this class, but it will not run properly, of course.
The LEMON undirected graphs also fulfill the concept of directed graphs (DigraphConcept"). Each edges can be seen as two opposite directed arc and consequently the undirected graph can be seen as the direceted graph of these directed arcs. The Graph has the Edge inner class for the edges and the Arc type for the directed arcs. The Arc type is convertible to Edge or inherited from it so from a directed arc we can get the represented edge.
In the sense of the LEMON each edge has a default direction (it should be in every computer implementation, because the order of edge's nodes defines an orientation). With the default orientation we can define that the directed arc is forward or backward directed. With the direction()
and direct()
function we can get the direction of the directed arc and we can direct an edge.
The EdgeIt is an iterator for the edges. We can use the EdgeMap to map values for the edges. The InArcIt and OutArcIt iterates on the same edges but with opposite direction. The IncEdgeIt iterates also on the same edges as the OutArcIt and InArcIt but it is not convertible to Arc just to Edge.
#include <lemon/concepts/graph.h>
Classes  
class  Arc 
The directed arc type. More...  
class  ArcIt 
This iterator goes through each directed arc. More...  
class  ArcMap 
class  Edge 
class  EdgeIt 
This iterator goes through each edge. More...  
class  EdgeMap 
class  InArcIt 
This iterator goes trough the incoming directed arcs of a node. More...  
class  IncEdgeIt 
This iterator goes trough the incident undirected arcs of a node. More...  
class  Node 
The base type of node iterators, or in other words, the trivial node iterator. More...  
class  NodeIt 
This iterator goes through each node. More...  
class  NodeMap 
class  OutArcIt 
This iterator goes trough the outgoing directed arcs of a node. More...  
Public Types  
typedef True  UndirectedTag 
The undirected graph should be tagged by the UndirectedTag.  
Public Member Functions  
Arc  direct (const Edge &, const Node &) const 
Direct the given edge.  
Arc  direct (const Edge &, bool) const 
Direct the given edge.  
bool  direction (Arc) const 
Returns true if the arc has default orientation.  
Arc  oppositeArc (Arc) const 
Node  oppositeNode (Node, Edge) const 
Opposite node on an arc.  
Node  u (Edge) const 
First node of the edge.  
Node  v (Edge) const 
Second node of the edge.  
Node  source (Arc) const 
Source node of the directed arc.  
Node  target (Arc) const 
Target node of the directed arc.  
int  id (Node) const 
Returns the id of the node.  
int  id (Edge) const 
Returns the id of the edge.  
int  id (Arc) const 
Returns the id of the arc.  
Node  nodeFromId (int) const 
Returns the node with the given id.  
Edge  edgeFromId (int) const 
Returns the edge with the given id.  
Arc  arcFromId (int) const 
Returns the arc with the given id.  
int  maxNodeId () const 
Returns an upper bound on the node IDs.  
int  maxEdgeId () const 
Returns an upper bound on the edge IDs.  
int  maxArcId () const 
Returns an upper bound on the arc IDs.  
Node  baseNode (OutArcIt e) const 
Base node of the iterator.  
Node  runningNode (OutArcIt e) const 
Running node of the iterator.  
Node  baseNode (InArcIt e) const 
Base node of the iterator.  
Node  runningNode (InArcIt e) const 
Running node of the iterator.  
Node  baseNode (IncEdgeIt) const 
Base node of the iterator.  
Node  runningNode (IncEdgeIt) const 
Running node of the iterator.  
typedef True UndirectedTag 
The undirected graph should be tagged by the UndirectedTag. This tag helps the enable_if technics to make compile time specializations for undirected graphs.
Direct the given edge. The returned arc source will be the given node.
Direct the given edge. The returned arc represents the given edge and the direction comes from the bool parameter. The source of the edge and the directed arc is the same when the given bool is true.

inline 
Returns whether the given directed arc is same orientation as the corresponding edge's default orientation.
Naturally edges don't have direction and thus don't have source and target node. However we use u()
and v()
methods to query the two nodes of the arc. The direction of the arc which arises this way is called the inherent direction of the edge, and is used to define the "default" direction of the directed versions of the arcs.
Naturally edges don't have direction and thus don't have source and target node. However we use u()
and v()
methods to query the two nodes of the arc. The direction of the arc which arises this way is called the inherent direction of the edge, and is used to define the "default" direction of the directed versions of the arcs.

inline 

inline 

inline 
Returns the base node (the source in this case) of the iterator
Returns the running node (the target in this case) of the iterator
Returns the base node (the target in this case) of the iterator
Returns the running node (the source in this case) of the iterator