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 (Digraph Concept"). 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.
| bool direction | ( | Arc | ) | const [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.
| Node nodeFromId | ( | int | ) | const [inline] |
| Edge edgeFromId | ( | int | ) | const [inline] |
| Arc arcFromId | ( | int | ) | const [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
1.7.3
