abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
Loading...
Searching...
No Matches
GomoryHu< GR , CAP >::MinCutNodeIt Class Reference

Iterate on the nodes of a minimum cut. More...

#include <lemon/gomory_hu.h>

Public Member Functions

 MinCutNodeIt (GomoryHu const &gomory, const Node &s, const Node &t, bool side=true)
 Constructor.
 operator typename Graph::Node () const
 Conversion to Node.
MinCutNodeIt & operator++ ()
 Next node.
Graph::Node operator++ (int)
 Postfix incrementation.

Detailed Description

template< typename GR , typename CAP >
class lemon::GomoryHu< GR , CAP >::MinCutNodeIt

This iterator class lists the nodes of a minimum cut found by GomoryHu. Before using it, you must allocate a GomoryHu class and call its run() method.

This example counts the nodes in the minimum cut separating s from t.

GomoryHu< Graph > gom( g , capacities );
gom.run();
int cnt = 0;
for( GomoryHu< Graph >::MinCutNodeIt n( gom , s , t ) ; n != INVALID ;
++n )
++cnt;
Iterate on the nodes of a minimum cut.
Definition gomory_hu.h:394
GomoryHu( const Graph & graph , const Capacity & capacity )
Constructor.
Definition gomory_hu.h:121
const Invalid INVALID
Invalid iterators.
Definition base.cc:33

Constructor & Destructor Documentation

◆ MinCutNodeIt()

template< typename GR , typename CAP >
MinCutNodeIt ( GomoryHu const & gomory,
const Node & s,
const Node & t,
bool side = true )
inline

Constructor.

Parameters
gomoryThe GomoryHu class. You must call its run() method before initializing this iterator.
sThe base node.
tThe node you want to separate from node s.
sideIf it is true (default) then the iterator lists the nodes of the component containing s, otherwise it lists the other component.
Note
As the minimum cut is not always unique,
MinCutNodeIt( gomory , s , t , true );
MinCutNodeIt( GomoryHu const & gomory , const Node & s , const Node & t , bool side=true )
Constructor.
Definition gomory_hu.h:404
and
MinCutNodeIt( gomory , t , s , false );
does not necessarily give the same set of nodes. However, it is ensured that
MinCutNodeIt( gomory , s , t , true );
and
MinCutNodeIt( gomory , s , t , false );
together list each node exactly once.

Member Function Documentation

◆ operator typename Graph::Node()

template< typename GR , typename CAP >
operator typename Graph::Node ( ) const
inline

Conversion to Node.

◆ operator++() [1/2]

template< typename GR , typename CAP >
MinCutNodeIt & operator++ ( )
inline

Next node.

◆ operator++() [2/2]

template< typename GR , typename CAP >
Graph::Node operator++ ( int )
inline

Postfix incrementation.

Warning
This incrementation returns a Node, not a MinCutNodeIt, as one may expect.