Detailed Description

This class describes the common interface of all undirected bipartite graphs.

Like all concept classes, it only provides an interface without any sensible implementation. So any general algorithm for undirected bipartite graphs should compile with this class, but it will not run properly, of course. An actual graph implementation like ListBpGraph or SmartBpGraph may have additional functionality.

The bipartite graphs also fulfill the concept of undirected graphs. Bipartite graphs provide a bipartition of the node set, namely a red and blue set of the nodes. The nodes can be iterated with the RedNodeIt and BlueNodeIt in the two node sets. With RedNodeMap and BlueNodeMap values can be assigned to the nodes in the two sets.

The edges of the graph cannot connect two nodes of the same set. The edges inherent orientation is from the red nodes to the blue nodes.

See Also: Graph

#include <lemon/concepts/bpgraph.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	BlueNode
	Class to represent blue nodes. More...

class	BlueNodeIt
	Iterator class for the blue nodes. More...

class	BlueNodeMap
	Standard graph map type for the blue nodes. 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...

class	RedNode
	Class to represent red nodes. More...

class	RedNodeIt
	Iterator class for the red nodes. More...

class	RedNodeMap
	Standard graph map type for the red nodes. More...

Public Types
typedef True	UndirectedTag
	Undirected graphs should be tagged with `UndirectedTag`.

Public Member Functions
	BpGraph ()
	Default constructor.

bool	red (const Node &) const

bool	blue (const Node &) const

RedNode	asRedNodeUnsafe (const Node &) const
	Converts the node to red node object.

BlueNode	asBlueNodeUnsafe (const Node &) const
	Converts the node to blue node object.

RedNode	asRedNode (const Node &) const
	Converts the node to red node object.

BlueNode	asBlueNode (const Node &) const
	Converts the node to blue node object.

RedNode	redNode (const Edge &) const

BlueNode	blueNode (const Edge &) const

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 (RedNode) const
	The red ID of the node.

int	id (BlueNode) const
	The blue 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	maxRedId () const
	An upper bound on the red IDs.

int	maxBlueId () const
	An upper bound on the blue 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
	BpGraph (const BpGraph &)
	BpGraphs are not copy constructible. Use bpGraphCopy instead.

void	operator= (const BpGraph &)
	Assignment of a graph to another one is not allowed. Use bpGraphCopy 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

bool red ( const Node & ) const

inline

Gives back true for red nodes.

bool blue ( const Node & ) const

inline

Gives back true for blue nodes.

RedNode asRedNodeUnsafe ( const Node & ) const

inline

This function converts unsafely the node to red node object. It should be called only if the node is from the red partition or INVALID.

BlueNode asBlueNodeUnsafe ( const Node & ) const

inline

This function converts unsafely the node to blue node object. It should be called only if the node is from the red partition or INVALID.

RedNode asRedNode ( const Node & ) const

inline

This function converts safely the node to red node object. If the node is not from the red partition, then it returns INVALID.

BlueNode asBlueNode ( const Node & ) const

inline

This function converts unsafely the node to blue node object. If the node is not from the blue partition, then it returns INVALID.

RedNode redNode ( const Edge & ) const

inline

Gives back the red end node of the edge.

BlueNode blueNode ( const Edge & ) const

inline

Gives back the blue end node of the edge.

Node u ( Edge ) const

inline

It is a synonim for the redNode().

Node v ( Edge ) const

inline

It is a synonim for the blueNode().

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

inline

Returns the red ID of the given node.

int id ( BlueNode ) const

inline

Returns the blue 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 maxRedId ( ) const

inline

Returns an upper bound on the red IDs.

int maxBlueId ( ) const

inline

Returns an upper bound on the blue 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 given arc goes from a red node to a blue node.

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 source of the node will be a red node.

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

Detailed Description

Classes

Public Types

Public Member Functions

Private Member Functions

Member Typedef Documentation

Member Function Documentation