BpUGraph Class Reference
[Graph Structure Concepts]

#include <lemon/concept/bpugraph.h>

Inherited by ExtendableBpUGraph.

Inheritance diagram for BpUGraph:

Inheritance graph
[legend]
List of all members.

Detailed Description

This class describes the common interface of all Undirected Bipartite Graphs.

As all concept describing classes it provides only interface without any sensible implementation. So any algorithm for bipartite undirected graph should compile with this class, but it will not run properly, of course.

In LEMON bipartite undirected graphs also fulfill the concept of the undirected graphs (UGraph Concept).

You can assume that all undirected bipartite graph can be handled as an undirected graph and consequently as a static graph.

The bipartite graph stores two types of nodes which are named ANode and BNode. The graph type contains two types ANode and BNode which are inherited from Node type. Moreover they have constructor which converts Node to either ANode or BNode when it is possible. Therefor everywhere the Node type can be used instead of ANode and BNode. So the usage of the ANode and BNode is suggested.

The iteration on the partition can be done with the ANodeIt and BNodeIt classes. The node map can be used to map values to the nodes and similarly we can use to map values for just the ANodes and BNodes the ANodeMap and BNodeMap template classes.


Public Types

typedef True UTag

Public Member Functions

Edge direct (const UEdge &, const Node &) const
 Direct the given undirected edge.
Edge direct (const UEdge &, bool) const
 Direct the given undirected edge.
bool aNode (Node) const
 Returns true when the given node is an ANode.
bool bNode (Node) const
 Returns true when the given node is an BNode.
Node aNode (UEdge) const
 Returns the edge's end node which is in the ANode set.
Node bNode (UEdge) const
 Returns the edge's end node which is in the BNode set.
bool direction (Edge) const
 Returns true if the edge has default orientation.
Edge oppositeEdge (Edge) const
 Returns the opposite directed edge.
Node oppositeNode (Node, UEdge) const
 Opposite node on an edge.
Node source (UEdge) const
 First node of the undirected edge.
Node target (UEdge) 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.
Node baseNode (OutEdgeIt e) const
 Base node of the iterator.
Node runningNode (OutEdgeIt e) const
 Running node of the iterator.
Node baseNode (InEdgeIt e) const
 Base node of the iterator.
Node runningNode (InEdgeIt 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.

Classes

class  ANode
 The base type of anode iterators, or in other words, the trivial anode iterator. More...
class  ANodeIt
 This iterator goes through each ANode. More...
class  ANodeMap
 Read write map of the ANodes to type T. More...
class  BNode
 The base type of bnode iterators, or in other words, the trivial bnode iterator. More...
class  BNodeIt
 This iterator goes through each BNode. More...
class  BNodeMap
 Read write map of the BNodes to type T. More...
class  Edge
 The directed edge type. More...
class  EdgeIt
 This iterator goes through each directed edge. More...
class  EdgeMap
 Read write map of the directed edges to type T. More...
class  IncEdgeIt
 This iterator goes trough the incident undirected edges of a node. More...
class  InEdgeIt
 This iterator goes trough the incoming directed edges 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
 Read write map of the nodes to type T. More...
class  OutEdgeIt
 This iterator goes trough the outgoing directed edges of a node. More...
class  UEdge
 The base type of the undirected edge iterators. More...
class  UEdgeIt
 This iterator goes through each undirected edge. More...
class  UEdgeMap
 Read write map of the undirected edges to type T. More...


Member Typedef Documentation

typedef True UTag
 

Todo:
undocumented


Member Function Documentation

Edge direct const UEdge ,
const Node
const [inline]
 

Direct the given undirected edge. The returned edge source will be the given edge.

Edge direct const UEdge ,
bool 
const [inline]
 

Direct the given undirected edge. The returned edge source will be the source of the undirected edge if the given bool is true.

bool aNode Node   )  const [inline]
 

Returns true when the given node is an ANode.

bool bNode Node   )  const [inline]
 

Returns true when the given node is an BNode.

Node aNode UEdge   )  const [inline]
 

Returns the edge's end node which is in the ANode set.

Node bNode UEdge   )  const [inline]
 

Returns the edge's end node which is in the BNode set.

bool direction Edge   )  const [inline]
 

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

Edge oppositeEdge Edge   )  const [inline]
 

Returns the opposite directed edge.

Node oppositeNode Node  ,
UEdge 
const [inline]
 

Returns:
the opposite of the given Node on the given Edge

Node source UEdge   )  const [inline]
 

Returns:
the first node of the given UEdge.
Naturally uectected 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 "default" direction of the directed versions of the edges.
See also:
direction

Node baseNode OutEdgeIt  e  )  const [inline]
 

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

Node runningNode OutEdgeIt  e  )  const [inline]
 

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

Node baseNode InEdgeIt  e  )  const [inline]
 

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

Node runningNode InEdgeIt  e  )  const [inline]
 

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

Node baseNode IncEdgeIt   )  const [inline]
 

Returns the base node of the iterator

Node runningNode IncEdgeIt   )  const [inline]
 

Returns the running node of the iterator


The documentation for this class was generated from the following file:
Generated on Fri Feb 3 18:43:04 2006 for LEMON by  doxygen 1.4.6