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
Public Types
-
typedef True UndirectedTag
Undirected graphs should be tagged with
UndirectedTag.This tag helps the
enable_iftechnics 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 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 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 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
trueif 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 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).
-
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(Invalid)
Invalid constructor & conversion.
Initializes the object to be invalid.
See also
Invalid for more details.
-
inline Node()
-
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()
-
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()
-
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
gof typeBpGraphlike 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(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()
-
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
gof typeBpGraphlike 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.
-
inline BlueNodeIt()
-
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
gof typeBpGraphlike 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(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()
-
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(Invalid)
Invalid constructor & conversion.
Initializes the object to be invalid.
See also
Invalid for more details.
-
inline Edge()
-
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
gof typeBpGraphas 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(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()
-
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
nin a graphgof typeBpGraphas 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(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()
-
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(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 Arc()
-
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
gof typeBpGraphas 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(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()
-
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
nin a graphgof typeBpGraphas 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(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()
-
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
nin a graphgof typeBpGraphas 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(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()
-
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.
-
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.
-
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.
-
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.
-
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.
-
typedef True UndirectedTag