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 DigraphCopy instead. | |

void | operator= (const Graph &) |

Assignment of a graph to another one is not allowed. Use DigraphCopy instead. |

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.

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

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

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.

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.

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

Returns the oppositely directed arc representing the same edge.

Returns the base node of the given incident edge iterator.

Returns the running node of the given incident edge iterator.

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

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

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

Generated on Wed Nov 9 2011 11:44:34 by 1.7.3