concepts::BpGraph

Declared in lemon/concepts/bpgraph.h, in the group Graph Structure Concepts; the same class on the Doxygen site.

class BpGraph

Class describing the concept of undirected bipartite graphs.

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

Public Types

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.

Public Functions

inline BpGraph()

Default constructor.

inline LemonRangeWrapper1< RedNodeIt , BpGraph > redNodes() const

Gets the collection of the red nodes of the graph.

This function can be used for iterating on the red nodes of the graph. It returns a wrapped RedNodeIt, which looks like an STL container (by having begin() and end()) which you can use in range-based for loops, stl algorithms, etc. For example if g is a BpGraph, you can write:

for( auto v : g.redNodes() )
 doSomething( v );

inline LemonRangeWrapper1< BlueNodeIt , BpGraph > blueNodes() const

Gets the collection of the blue nodes of the graph.

This function can be used for iterating on the blue nodes of the graph. It returns a wrapped BlueNodeIt, which looks like an STL container (by having begin() and end()) which you can use in range-based for loops, stl algorithms, etc. For example if g is a BpGraph, you can write:

for( auto v : g.blueNodes() )
 doSomething( v );

inline LemonRangeWrapper1< NodeIt , BpGraph > nodes() const

Gets the collection of the nodes of the graph.

This function can be used for iterating on the nodes of the graph. It returns a wrapped NodeIt, which looks like an STL container (by having begin() and end()) which you can use in range-based for loops, stl algorithms, etc. For example if g is a BpGraph, you can write:

for( auto v : g.nodes() )
 doSomething( v );

inline LemonRangeWrapper1< EdgeIt , BpGraph > edges() const

Gets the collection of the edges of the graph.

This function can be used for iterating on the edges of the graph. It returns a wrapped EdgeIt, which looks like an STL container (by having begin() and end()) which you can use in range-based for loops, stl algorithms, etc. For example if g is a BpGraph, you can write:

for( auto e : g.edges() )
 doSomething( e );

inline LemonRangeWrapper2< IncEdgeIt , BpGraph , Node > incEdges( const Node & u ) const

Gets the collection of the incident edges of a certain node of the graph.

This function can be used for iterating on the incident undirected edges of a certain node of the graph. It returns a wrapped IncEdgeIt, which looks like an STL container (by having begin() and end()) which you can use in range-based for loops, stl algorithms, etc. For example if g is a BpGraph and u is a Node, you can write:

for( auto e : g.incEdges( u ) )
 doSomething( e );

inline LemonRangeWrapper1< ArcIt , BpGraph > arcs() const

Gets the collection of the directed arcs of the graph.

This function can be used for iterating on the arcs of the graph. It returns a wrapped ArcIt, which looks like an STL container (by having begin() and end()) which you can use in range-based for loops, stl algorithms, etc. For example if g is a BpGraph you can write:

for( auto a : g.arcs() )
 doSomething( a );

inline LemonRangeWrapper2< OutArcIt , BpGraph , Node > outArcs( const Node & u ) const

Gets the collection of the outgoing directed arcs of a certain node of the graph.

This function can be used for iterating on the outgoing arcs of a certain node of the graph. It returns a wrapped OutArcIt, which looks like an STL container (by having begin() and end()) which you can use in range-based for loops, stl algorithms, etc. For example if g is a BpGraph and u is a Node, you can write:

for( auto a : g.outArcs( u ) )
 doSomething( a );

inline LemonRangeWrapper2< InArcIt , BpGraph , Node > inArcs( const Node & u ) const

Gets the collection of the incoming directed arcs of a certain node of the graph.

This function can be used for iterating on the incoming arcs of a certain node of the graph. It returns a wrapped InArcIt, which looks like an STL container (by having begin() and end()) which you can use in range-based for loops, stl algorithms, etc. For example if g is a BpGraph and u is a Node, you can write:

for( auto a : g.inArcs( u ) )
 doSomething( a );

inline bool red( const Node & ) const

Gives back true for red nodes.

inline bool blue( const Node & ) const

Gives back true for blue nodes.

inline RedNode asRedNodeUnsafe( const Node & ) const

Converts the node to red node object.

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.

inline BlueNode asBlueNodeUnsafe( const Node & ) const

Converts the node to blue node object.

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.

inline RedNode asRedNode( const Node & ) const

Converts the node to red node object.

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

inline BlueNode asBlueNode( const Node & ) const

Converts the node to blue node object.

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

inline RedNode redNode( const Edge & ) const

Gives back the red end node of the edge.

inline BlueNode blueNode( const Edge & ) const

Gives back the blue end node of the edge.

inline Node u(Edge) const

The first node of the edge.

It is a synonim for the redNode().

inline Node v(Edge) const

The second node of the edge.

It is a synonim for the blueNode().

inline Node source(Arc) const

The source node of the arc.

Returns the source node of the given arc.

inline Node target(Arc) const

The target node of the arc.

Returns the target node of the given arc.

inline int id(Node) const

The ID of the node.

Returns the ID of the given node.

inline int id(RedNode) const

The red ID of the node.

Returns the red ID of the given node.

inline int id(BlueNode) const

The blue ID of the node.

Returns the blue ID of the given node.

inline int id(Edge) const

The ID of the edge.

Returns the ID of the given edge.

inline int id(Arc) const

The ID of the arc.

Returns the ID of the given arc.

inline Node nodeFromId(int) const

The node with the given ID.

Returns the node with the given ID.

Pre:

The argument should be a valid node ID in the graph.

inline Edge edgeFromId(int) const

The edge with the given ID.

Returns the edge with the given ID.

Pre:

The argument should be a valid edge ID in the graph.

inline Arc arcFromId(int) const

The arc with the given ID.

Returns the arc with the given ID.

Pre:

The argument should be a valid arc ID in the graph.

inline int maxNodeId() const

An upper bound on the node IDs.

Returns an upper bound on the node IDs.

inline int maxRedId() const

An upper bound on the red IDs.

Returns an upper bound on the red IDs.

inline int maxBlueId() const

An upper bound on the blue IDs.

Returns an upper bound on the blue IDs.

inline int maxEdgeId() const

An upper bound on the edge IDs.

Returns an upper bound on the edge IDs.

inline int maxArcId() const

An upper bound on the arc IDs.

Returns an upper bound on the arc IDs.

inline bool direction(Arc) const

The direction of the arc.

Returns true if the given arc goes from a red node to a blue node.

inline Arc direct(Edge, bool) const

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

inline Arc direct(Edge, Node) const

Direct the edge.

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

inline Arc oppositeArc(Arc) const

The oppositely directed arc.

Returns the oppositely directed arc representing the same edge.

inline Node oppositeNode(Node, Edge) const

The opposite node on the edge.

Returns the opposite node on the given edge.

inline void first(Node&) const
inline void next(Node&) const
inline void firstRed(RedNode&) const
inline void nextRed(RedNode&) const
inline void firstBlue(BlueNode&) const
inline void nextBlue(BlueNode&) const
inline void first(Edge&) const
inline void next(Edge&) const
inline void first(Arc&) const
inline void next(Arc&) const
inline void firstOut(Arc&, Node) const
inline void nextOut(Arc&) const
inline void firstIn(Arc&, Node) const
inline void nextIn(Arc&) const
inline void firstInc( Edge & , bool & , const Node & ) const
inline void nextInc(Edge&, bool&) const
inline Node fromId(int, Node) const
inline Edge fromId(int, Edge) const
inline Arc fromId(int, Arc) const
inline int maxId(Node) const
inline int maxId(RedNode) const
inline int maxId(BlueNode) const
inline int maxId(Edge) const
inline int maxId(Arc) const
inline Node baseNode(IncEdgeIt) const

The base node of the iterator.

Returns the base node of the given incident edge iterator.

inline Node runningNode(IncEdgeIt) const

The running node of the iterator.

Returns the running node of the given incident edge iterator.

inline Node baseNode(OutArcIt) const

The base node of the iterator.

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

inline Node runningNode(OutArcIt) const

The running node of the iterator.

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

inline Node baseNode(InArcIt) const

The base node of the iterator.

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

inline Node runningNode(InArcIt) const

The running node of the iterator.

Returns the running node of the given incoming arc iterator (i.e. the source node of the corresponding arc).

class Node

The node type of the graph.

This class identifies a node of the graph. It also serves as a base class of the node iterators, thus they convert to this type.

Subclassed by BpGraph::BlueNode, BpGraph::NodeIt, BpGraph::RedNode

Public Functions

inline Node()

Default constructor.

Warning

It sets the object to an undefined value.

inline Node( const Node & )

Copy constructor.

inline const Node & operator=( const Node & )

Assignment operator.

inline Node(Invalid)

Invalid constructor & conversion.

Initializes the object to be invalid.

See also

Invalid for more details.

inline bool operator==(Node) const

Equality operator.

Two iterators are equal if and only if they point to the same object or both are INVALID.

inline bool operator!=(Node) const

Inequality operator.

inline bool operator<(Node) const

Artificial ordering operator.

Note

This operator only has to define some strict ordering of the items; this order has nothing to do with the iteration ordering of the items.

class RedNode : public BpGraph::Node

Class to represent red nodes.

This class represents the red nodes of the graph. It does not supposed to be used directly, because the nodes can be represented as Node instances. This class can be used as template parameter for special map classes.

Subclassed by BpGraph::RedNodeIt

Public Functions

inline RedNode()

Default constructor.

Warning

It sets the object to an undefined value.

inline RedNode( const RedNode & )

Copy constructor.

inline const RedNode & operator=( const RedNode & )

Assignment operator.

inline RedNode(Invalid)

Invalid constructor & conversion.

Initializes the object to be invalid.

See also

Invalid for more details.

class BlueNode : public BpGraph::Node

Class to represent blue nodes.

This class represents the blue nodes of the graph. It does not supposed to be used directly, because the nodes can be represented as Node instances. This class can be used as template parameter for special map classes.

Subclassed by BpGraph::BlueNodeIt

Public Functions

inline BlueNode()

Default constructor.

Warning

It sets the object to an undefined value.

inline BlueNode( const BlueNode & )

Copy constructor.

inline const BlueNode & operator=( const BlueNode & )

Assignment operator.

inline BlueNode(Invalid)

Invalid constructor & conversion.

Initializes the object to be invalid.

See also

Invalid for more details.

class RedNodeIt : public BpGraph::RedNode

Iterator class for the red nodes.

This iterator goes through each red node of the graph. Its usage is quite simple, for example, you can count the number of red nodes in a graph g of type BpGraph like this:

int count = 0;
for( BpGraph::RedNodeIt n( g ) ; n != INVALID ; ++n )
 ++count;

Public Functions

inline RedNodeIt()

Default constructor.

Warning

It sets the iterator to an undefined value.

inline RedNodeIt( const RedNodeIt & n )

Copy constructor.

inline const RedNodeIt & operator=( const RedNodeIt & )

Assignment operator.

inline RedNodeIt(Invalid)

Invalid constructor & conversion.

Initializes the iterator to be invalid.

See also

Invalid for more details.

inline explicit RedNodeIt( const BpGraph & )

Sets the iterator to the first red node.

Sets the iterator to the first red node of the given digraph.

inline RedNodeIt( const BpGraph & , const RedNode & )

Sets the iterator to the given red node.

Sets the iterator to the given red node of the given digraph.

inline RedNodeIt & operator++()

Next node.

Assign the iterator to the next red node.

class BlueNodeIt : public BpGraph::BlueNode

Iterator class for the blue nodes.

This iterator goes through each blue node of the graph. Its usage is quite simple, for example, you can count the number of blue nodes in a graph g of type BpGraph like this:

int count = 0;
for( BpGraph::BlueNodeIt n( g ) ; n != INVALID ; ++n )
 ++count;

Public Functions

inline BlueNodeIt()

Default constructor.

Warning

It sets the iterator to an undefined value.

inline BlueNodeIt( const BlueNodeIt & n )

Copy constructor.

inline const BlueNodeIt & operator=( const BlueNodeIt & )

Assignment operator.

inline BlueNodeIt(Invalid)

Invalid constructor & conversion.

Initializes the iterator to be invalid.

See also

Invalid for more details.

inline explicit BlueNodeIt( const BpGraph & )

Sets the iterator to the first blue node.

Sets the iterator to the first blue node of the given digraph.

inline BlueNodeIt( const BpGraph & , const BlueNode & )

Sets the iterator to the given blue node.

Sets the iterator to the given blue node of the given digraph.

inline BlueNodeIt & operator++()

Next node.

Assign the iterator to the next blue node.

class NodeIt : public BpGraph::Node

Iterator class for the nodes.

This iterator goes through each node of the graph. Its usage is quite simple, for example, you can count the number of nodes in a graph g of type BpGraph like this:

int count = 0;
for( BpGraph::NodeIt n( g ) ; n != INVALID ; ++n )
 ++count;

Public Functions

inline NodeIt()

Default constructor.

Warning

It sets the iterator to an undefined value.

inline NodeIt( const NodeIt & n )

Copy constructor.

inline const NodeIt & operator=( const NodeIt & )

Assignment operator.

inline NodeIt(Invalid)

Invalid constructor & conversion.

Initializes the iterator to be invalid.

See also

Invalid for more details.

inline explicit NodeIt( const BpGraph & )

Sets the iterator to the first node.

Sets the iterator to the first node of the given digraph.

inline NodeIt( const BpGraph & , const Node & )

Sets the iterator to the given node.

Sets the iterator to the given node of the given digraph.

inline NodeIt & operator++()

Next node.

Assign the iterator to the next node.

class Edge

The edge type of the graph.

This class identifies an edge of the graph. It also serves as a base class of the edge iterators, thus they will convert to this type.

Subclassed by BpGraph::EdgeIt, BpGraph::IncEdgeIt

Public Functions

inline Edge()

Default constructor.

Warning

It sets the object to an undefined value.

inline Edge( const Edge & )

Copy constructor.

inline const Edge & operator=( const Edge & )

Assignment operator.

inline Edge(Invalid)

Invalid constructor & conversion.

Initializes the object to be invalid.

See also

Invalid for more details.

inline bool operator==(Edge) const

Equality operator.

Two iterators are equal if and only if they point to the same object or both are INVALID.

inline bool operator!=(Edge) const

Inequality operator.

inline bool operator<(Edge) const

Artificial ordering operator.

Note

This operator only has to define some strict ordering of the edges; this order has nothing to do with the iteration ordering of the edges.

class EdgeIt : public BpGraph::Edge

Iterator class for the edges.

This iterator goes through each edge of the graph. Its usage is quite simple, for example, you can count the number of edges in a graph g of type BpGraph as follows:

int count = 0;
for( BpGraph::EdgeIt e( g ) ; e != INVALID ; ++e )
 ++count;

Public Functions

inline EdgeIt()

Default constructor.

Warning

It sets the iterator to an undefined value.

inline EdgeIt( const EdgeIt & e )

Copy constructor.

inline const EdgeIt & operator=( const EdgeIt & )

Assignment operator.

inline EdgeIt(Invalid)

Invalid constructor & conversion.

Initializes the iterator to be invalid.

See also

Invalid for more details.

inline explicit EdgeIt( const BpGraph & )

Sets the iterator to the first edge.

Sets the iterator to the first edge of the given graph.

inline EdgeIt( const BpGraph & , const Edge & )

Sets the iterator to the given edge.

Sets the iterator to the given edge of the given graph.

inline EdgeIt & operator++()

Next edge.

Assign the iterator to the next edge.

class IncEdgeIt : public BpGraph::Edge

Iterator class for the incident edges of a node.

This iterator goes trough the incident undirected edges of a certain node of a graph. Its usage is quite simple, for example, you can compute the degree (i.e. the number of incident edges) of a node n in a graph g of type BpGraph as follows.

int count = 0;
for( BpGraph::IncEdgeIt e( g , n ) ; e != INVALID ; ++e )
 ++count;

Warning

Loop edges will be iterated twice.

Public Functions

inline IncEdgeIt()

Default constructor.

Warning

It sets the iterator to an undefined value.

inline IncEdgeIt( const IncEdgeIt & e )

Copy constructor.

inline const IncEdgeIt & operator=( const IncEdgeIt & )

Assignment operator.

inline IncEdgeIt(Invalid)

Invalid constructor & conversion.

Initializes the iterator to be invalid.

See also

Invalid for more details.

inline IncEdgeIt( const BpGraph & , const Node & )

Sets the iterator to the first incident edge.

Sets the iterator to the first incident edge of the given node.

inline IncEdgeIt( const BpGraph & , const Edge & )

Sets the iterator to the given edge.

Sets the iterator to the given edge of the given graph.

inline IncEdgeIt & operator++()

Next incident edge.

Assign the iterator to the next incident edge of the corresponding node.

class Arc

The arc type of the graph.

This class identifies a directed arc of the graph. It also serves as a base class of the arc iterators, thus they will convert to this type.

Subclassed by BpGraph::ArcIt, BpGraph::InArcIt, BpGraph::OutArcIt

Public Functions

inline Arc()

Default constructor.

Warning

It sets the object to an undefined value.

inline Arc( const Arc & )

Copy constructor.

inline const Arc & operator=( const Arc & )

Assignment operator.

inline Arc(Invalid)

Invalid constructor & conversion.

Initializes the object to be invalid.

See also

Invalid for more details.

inline bool operator==(Arc) const

Equality operator.

Two iterators are equal if and only if they point to the same object or both are INVALID.

inline bool operator!=(Arc) const

Inequality operator.

inline bool operator<(Arc) const

Artificial ordering operator.

Note

This operator only has to define some strict ordering of the arcs; this order has nothing to do with the iteration ordering of the arcs.

inline operator Edge() const

Converison to Edge.

class ArcIt : public BpGraph::Arc

Iterator class for the arcs.

This iterator goes through each directed arc of the graph. Its usage is quite simple, for example, you can count the number of arcs in a graph g of type BpGraph as follows:

int count = 0;
for( BpGraph::ArcIt a( g ) ; a != INVALID ; ++a )
 ++count;

Public Functions

inline ArcIt()

Default constructor.

Warning

It sets the iterator to an undefined value.

inline ArcIt( const ArcIt & e )

Copy constructor.

inline const ArcIt & operator=( const ArcIt & )

Assignment operator.

inline ArcIt(Invalid)

Invalid constructor & conversion.

Initializes the iterator to be invalid.

See also

Invalid for more details.

inline explicit ArcIt( const BpGraph & g )

Sets the iterator to the first arc.

Sets the iterator to the first arc of the given graph.

inline ArcIt( const BpGraph & , const Arc & )

Sets the iterator to the given arc.

Sets the iterator to the given arc of the given graph.

inline ArcIt & operator++()

Next arc.

Assign the iterator to the next arc.

class OutArcIt : public BpGraph::Arc

Iterator class for the outgoing arcs of a node.

This iterator goes trough the outgoing directed arcs of a certain node of a graph. Its usage is quite simple, for example, you can count the number of outgoing arcs of a node n in a graph g of type BpGraph as follows.

int count = 0;
for( Digraph::OutArcIt a( g , n ) ; a != INVALID ; ++a )
 ++count;

Public Functions

inline OutArcIt()

Default constructor.

Warning

It sets the iterator to an undefined value.

inline OutArcIt( const OutArcIt & e )

Copy constructor.

inline const OutArcIt & operator=( const OutArcIt & )

Assignment operator.

inline OutArcIt(Invalid)

Invalid constructor & conversion.

Initializes the iterator to be invalid.

See also

Invalid for more details.

inline OutArcIt( const BpGraph & n , const Node & g )

Sets the iterator to the first outgoing arc.

Sets the iterator to the first outgoing arc of the given node.

inline OutArcIt( const BpGraph & , const Arc & )

Sets the iterator to the given arc.

Sets the iterator to the given arc of the given graph.

inline OutArcIt & operator++()

Next outgoing arc.

Assign the iterator to the next outgoing arc of the corresponding node.

class InArcIt : public BpGraph::Arc

Iterator class for the incoming arcs of a node.

This iterator goes trough the incoming directed arcs of a certain node of a graph. Its usage is quite simple, for example, you can count the number of incoming arcs of a node n in a graph g of type BpGraph as follows.

int count = 0;
for( Digraph::InArcIt a( g , n ) ; a != INVALID ; ++a )
 ++count;

Public Functions

inline InArcIt()

Default constructor.

Warning

It sets the iterator to an undefined value.

inline InArcIt( const InArcIt & e )

Copy constructor.

inline const InArcIt & operator=( const InArcIt & )

Assignment operator.

inline InArcIt(Invalid)

Invalid constructor & conversion.

Initializes the iterator to be invalid.

See also

Invalid for more details.

inline InArcIt( const BpGraph & g , const Node & n )

Sets the iterator to the first incoming arc.

Sets the iterator to the first incoming arc of the given node.

inline InArcIt( const BpGraph & , const Arc & )

Sets the iterator to the given arc.

Sets the iterator to the given arc of the given graph.

inline InArcIt & operator++()

Next incoming arc.

Assign the iterator to the next incoming arc of the corresponding node.

template< class T >
class NodeMap : public ReferenceMap< Node , T , T& , const T& >

Standard graph map type for the nodes. It conforms to the ReferenceMap concept.

Public Functions

inline explicit NodeMap( const BpGraph & )

Constructor.

inline NodeMap( const BpGraph & , T )

Constructor with given initial value.

template< class T >
class RedNodeMap : public ReferenceMap< Node , T , T& , const T& >

Standard graph map type for the red nodes. It conforms to the ReferenceMap concept.

Public Functions

inline explicit RedNodeMap( const BpGraph & )

Constructor.

inline RedNodeMap( const BpGraph & , T )

Constructor with given initial value.

template< class T >
class BlueNodeMap : public ReferenceMap< Node , T , T& , const T& >

Standard graph map type for the blue nodes. It conforms to the ReferenceMap concept.

Public Functions

inline explicit BlueNodeMap( const BpGraph & )

Constructor.

inline BlueNodeMap( const BpGraph & , T )

Constructor with given initial value.

template< class T >
class ArcMap : public ReferenceMap< Arc , T , T& , const T& >

Standard graph map type for the arcs. It conforms to the ReferenceMap concept.

Public Functions

inline explicit ArcMap( const BpGraph & )

Constructor.

inline ArcMap( const BpGraph & , T )

Constructor with given initial value.

template< class T >
class EdgeMap : public ReferenceMap< Edge , T , T& , const T& >

Standard graph map type for the edges. It conforms to the ReferenceMap concept.

Public Functions

inline explicit EdgeMap( const BpGraph & )

Constructor.

inline EdgeMap( const BpGraph & , T )

Constructor with given initial value.

template< typename _BpGraph >
struct Constraints

Public Functions

inline void constraints()