Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

UndirGraph Class Reference
[Graph Structure Concepts]

#include <lemon/concept/undir_graph.h>

List of all members.


Detailed Description

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 couse.

In LEMON undirected graphs also fulfill the concept of directed graphs (Graph Concept). For explanation of this and more see also the page Undirected graph structures, a tutorial about undirected graphs.

Definition at line 234 of file undir_graph.h.

Public Types

typedef GraphNode Node
 Type describing a node in the graph.
typedef GraphItem<'u'> UndirEdge
 Type describing an undirected edge.
typedef UndirGraphEdge Edge
 Type describing an UndirEdge with direction.
typedef GraphIterator NodeIt
 Iterator type which iterates over all nodes.
typedef GraphIterator UndirEdgeIt
 Iterator type which iterates over all undirected edges.
typedef GraphIterator EdgeIt
 Iterator type which iterates over all directed edges.
typedef GraphIncIterator IncEdgeIt
 Iterator of undirected edges incident to a node.
typedef GraphIncIterator InEdgeIt
 Iterator of edges incoming to a node.
typedef GraphIncIterator OutEdgeIt
 Iterator of edges outgoing from a node.
typedef GraphMap NodeMap<T>
 NodeMap template.
typedef GraphMap UndirEdgeMap<T>
 UndirEdgeMap template.
typedef GraphMap EdgeMap<T>
 EdgeMap template.

Public Member Functions

bool forward (Edge) const
 Is the Edge oriented "forward"?
Node oppositeNode (Node, UndirEdge) const
 Opposite node on an edge.
Node source (UndirEdge) const
 First node of the undirected edge.
Node target (UndirEdge) const
 Second node of the undirected edge.
Node source (Edge) const
 Source node of the directed edge.
Node target (Edge) const
 Target node of the directed edge.
void first (Node &) const
 First node of the graph.
void next (Node &) const
 Next node of the graph.
void first (UndirEdge &) const
 First undirected edge of the graph.
void next (UndirEdge &) const
 Next undirected edge of the graph.
void first (Edge &) const
 First directed edge of the graph.
void next (Edge &) const
 Next directed edge of the graph.
void firstOut (Edge &, Node) const
 First outgoing edge from a given node.
void nextOut (Edge &) const
 Next outgoing edge to a node.
void firstIn (Edge &, Node) const
 First incoming edge to a given node.
void nextIn (Edge &) const
 Next incoming edge to a node.
Node baseNode (OutEdgeIt e) const
Node runningNode (OutEdgeIt e) const
Node baseNode (InEdgeIt e) const
Node runningNode (InEdgeIt e) const
Node baseNode (IncEdgeIt e) const
Node runningNode (IncEdgeIt e) const


Member Typedef Documentation

typedef GraphIterator EdgeIt
 

Iterator type which iterates over all edges (each undirected edge occurs twice with both directions.

Definition at line 271 of file undir_graph.h.


Member Function Documentation

bool forward Edge   )  const [inline]
 

Returns whether the given directed edge is same orientation as the corresponding undirected edge.

Todo:
"What does the direction of an undirected edge mean?"

Definition at line 344 of file undir_graph.h.

Node oppositeNode Node  ,
UndirEdge 
const [inline]
 

Returns:
the opposite of the given Node on the given Edge
Todo:
What should we do if given Node and Edge are not incident?

Definition at line 351 of file undir_graph.h.

Node source UndirEdge   )  const [inline]
 

Returns:
the first node of the given UndirEdge.
Naturally undirectected edges don't have direction and thus don't have source and target node. But we use these two methods to query the two endnodes of the edge. The direction of the edge which arises this way is called the inherent direction of the undirected edge, and is used to define the "forward" direction of the directed versions of the edges.
See also:
forward

Definition at line 364 of file undir_graph.h.

void first Node  )  const [inline]
 

Note:
This method is part of so called Developpers' interface, so it shouldn't be used in an end-user program.

Definition at line 380 of file undir_graph.h.

void next Node  )  const [inline]
 

Note:
This method is part of so called Developpers' interface, so it shouldn't be used in an end-user program.

Definition at line 386 of file undir_graph.h.

void first UndirEdge  )  const [inline]
 

Note:
This method is part of so called Developpers' interface, so it shouldn't be used in an end-user program.

Definition at line 393 of file undir_graph.h.

void next UndirEdge  )  const [inline]
 

Note:
This method is part of so called Developpers' interface, so it shouldn't be used in an end-user program.

Definition at line 399 of file undir_graph.h.

void first Edge  )  const [inline]
 

Note:
This method is part of so called Developpers' interface, so it shouldn't be used in an end-user program.

Definition at line 406 of file undir_graph.h.

void next Edge  )  const [inline]
 

Note:
This method is part of so called Developpers' interface, so it shouldn't be used in an end-user program.

Definition at line 412 of file undir_graph.h.

void firstOut Edge ,
Node 
const [inline]
 

Note:
This method is part of so called Developpers' interface, so it shouldn't be used in an end-user program.

Definition at line 419 of file undir_graph.h.

void nextOut Edge  )  const [inline]
 

Note:
This method is part of so called Developpers' interface, so it shouldn't be used in an end-user program.

Definition at line 425 of file undir_graph.h.

void firstIn Edge ,
Node 
const [inline]
 

Note:
This method is part of so called Developpers' interface, so it shouldn't be used in an end-user program.

Definition at line 432 of file undir_graph.h.

void nextIn Edge  )  const [inline]
 

Note:
This method is part of so called Developpers' interface, so it shouldn't be used in an end-user program.

Definition at line 438 of file undir_graph.h.

Node baseNode OutEdgeIt  e  )  const [inline]
 

Base node of the iterator

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

Definition at line 444 of file undir_graph.h.

Here is the call graph for this function:

Node runningNode OutEdgeIt  e  )  const [inline]
 

Running node of the iterator

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

Definition at line 451 of file undir_graph.h.

Here is the call graph for this function:

Node baseNode InEdgeIt  e  )  const [inline]
 

Base node of the iterator

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

Definition at line 458 of file undir_graph.h.

Here is the call graph for this function:

Node runningNode InEdgeIt  e  )  const [inline]
 

Running node of the iterator

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

Definition at line 465 of file undir_graph.h.

Here is the call graph for this function:

Node baseNode IncEdgeIt  e  )  const [inline]
 

Base node of the iterator

Returns the base node of the iterator

Definition at line 472 of file undir_graph.h.

Node runningNode IncEdgeIt  e  )  const [inline]
 

Running node of the iterator

Returns the running node of the iterator

Definition at line 478 of file undir_graph.h.


The documentation for this class was generated from the following file:
Generated on Mon Feb 21 15:02:44 2005 for LEMON by  doxygen 1.4.1