All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
List of all members | Classes | Public Types | Public Member Functions | Private Member Functions
Graph Class Reference

Detailed Description

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

#include <lemon/concepts/graph.h>

Classes

class  Arc
 The arc type of the graph. More...
 
class  ArcIt
 Iterator class for the arcs. More...
 
class  ArcMap
 Standard graph map type for the arcs. More...
 
class  Edge
 The edge type of the graph. More...
 
class  EdgeIt
 Iterator class for the edges. More...
 
class  EdgeMap
 Standard graph map type for the edges. More...
 
class  InArcIt
 Iterator class for the incoming arcs of a node. More...
 
class  IncEdgeIt
 Iterator class for the incident edges of a node. More...
 
class  Node
 The node type of the graph. More...
 
class  NodeIt
 Iterator class for the nodes. More...
 
class  NodeMap
 Standard graph map type for the nodes. More...
 
class  OutArcIt
 Iterator class for the outgoing arcs of a node. More...
 

Public Types

typedef True UndirectedTag
 Undirected graphs should be tagged with UndirectedTag.
 

Public Member Functions

 Graph ()
 Default constructor.
 
Node u (Edge) const
 The first node of the edge.
 
Node v (Edge) const
 The second node of the edge.
 
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 (Edge) const
 The ID of the edge.
 
int id (Arc) const
 The ID of the arc.
 
Node nodeFromId (int) const
 The node with the given ID.
 
Edge edgeFromId (int) const
 The edge 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 maxEdgeId () const
 An upper bound on the edge IDs.
 
int maxArcId () const
 An upper bound on the arc IDs.
 
bool direction (Arc) const
 The direction of the arc.
 
Arc direct (Edge, bool) const
 Direct the edge.
 
Arc direct (Edge, Node) const
 Direct the edge.
 
Arc oppositeArc (Arc) const
 The oppositely directed arc.
 
Node oppositeNode (Node, Edge) const
 The opposite node on the edge.
 
Node baseNode (IncEdgeIt) const
 The base node of the iterator.
 
Node runningNode (IncEdgeIt) const
 The running node of the iterator.
 
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

 Graph (const Graph &)
 Graphs are not copy constructible. Use GraphCopy instead.
 
void operator= (const Graph &)
 Assignment of a graph to another one is not allowed. Use GraphCopy instead.
 

Member Typedef Documentation

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.

Member Function Documentation

Node u ( Edge  ) const
inline

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()
direction()
Node v ( Edge  ) const
inline

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()
direction()
Node source ( Arc  ) const
inline

Returns the source node of the given arc.

Node target ( Arc  ) const
inline

Returns the target node of the given arc.

int id ( Node  ) const
inline

Returns the ID of the given node.

int id ( Edge  ) const
inline

Returns the ID of the given edge.

int id ( Arc  ) const
inline

Returns the ID of the given arc.

Node nodeFromId ( int  ) const
inline

Returns the node with the given ID.

Precondition
The argument should be a valid node ID in the graph.
Edge edgeFromId ( int  ) const
inline

Returns the edge with the given ID.

Precondition
The argument should be a valid edge ID in the graph.
Arc arcFromId ( int  ) const
inline

Returns the arc with the given ID.

Precondition
The argument should be a valid arc ID in the graph.
int maxNodeId ( ) const
inline

Returns an upper bound on the node IDs.

int maxEdgeId ( ) const
inline

Returns an upper bound on the edge IDs.

int maxArcId ( ) const
inline

Returns an upper bound on the arc IDs.

bool direction ( Arc  ) const
inline

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

Arc direct ( Edge  ,
bool   
) const
inline

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.

Arc direct ( Edge  ,
Node   
) const
inline

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

Arc oppositeArc ( Arc  ) const
inline

Returns the oppositely directed arc representing the same edge.

Node oppositeNode ( Node  ,
Edge   
) const
inline

Returns the opposite node on the given edge.

Node baseNode ( IncEdgeIt  ) const
inline

Returns the base node of the given incident edge iterator.

Node runningNode ( IncEdgeIt  ) const
inline

Returns the running node of the given incident edge iterator.

Node baseNode ( OutArcIt  ) const
inline

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

Node runningNode ( OutArcIt  ) const
inline

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

Node baseNode ( InArcIt  ) const
inline

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

Node runningNode ( InArcIt  ) const
inline

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