Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::MinSTCutMaxFlow< TCost > Class Template Reference

Min-st-cut algorithm, that calculates the cut via maxflow. More...

#include <ogdf/graphalg/MinSTCutMaxFlow.h>

+ Inheritance diagram for ogdf::MinSTCutMaxFlow< TCost >:

Public Types

enum  cutType { cutType::FRONT_CUT, cutType::BACK_CUT, cutType::NO_CUT }
 The three types of cuts. More...
 

Public Member Functions

 MinSTCutMaxFlow (bool treatAsUndirected=true, MaxFlowModule< TCost > *mfModule=new MaxFlowGoldbergTarjan< TCost >(), bool primaryCut=true, bool calculateOtherCut=true, EpsilonTest *epsilonTest=new EpsilonTest())
 Constructor. More...
 
virtual bool call (const Graph &graph, const EdgeArray< TCost > &weight, node s, node t, List< edge > &edgeList, edge e_st=nullptr) override
 The actual algorithm call. More...
 
void call (const Graph &graph, const EdgeArray< TCost > &weights, const EdgeArray< TCost > &flow, const node source, const node target)
 Partitions the nodes to front- and backcut. More...
 
virtual bool call (const Graph &graph, node s, node t, List< edge > &edgeList, edge e_st=nullptr) override
 The actual algorithm call. More...
 
bool frontCutIsComplementOfBackCut () const
 Returns whether the front cut is the complement of the backcut. More...
 
bool isBackCutEdge (const edge e) const
 Returns whether this edge is entering the back cut. More...
 
bool isFrontCutEdge (const edge e) const
 Returns whether this edge is leaving the front cut. More...
 
bool isInBackCut (const node v) const
 Returns whether this node is part of the back cut. More...
 
bool isInFrontCut (const node v) const
 Returns whether this node is part of the front cut. More...
 
bool isOfType (const node v, cutType type) const
 Return whether this node is of the specified type. More...
 
void setEpsilonTest (EpsilonTest *et)
 Assigns a new epsilon test. More...
 
- Public Member Functions inherited from ogdf::MinSTCutModule< TCost >
 MinSTCutModule ()
 default constructor (empty) More...
 
virtual ~MinSTCutModule ()
 
virtual bool direction (edge e)
 Returns the direction of e in the cut. More...
 

Private Member Functions

void computeCut (const Graph &graph, std::function< edge(edge)> origEdge, std::function< node(node)> origNode, const node source, const node target, List< edge > &edgeList)
 Partitions the nodes to front and back cut. More...
 
void markCut (node startNode, bool frontCut, std::function< node(node)> origNode)
 Mark the all nodes which are in the same cut partition as the startNode. More...
 

Private Attributes

int m_backCutCount
 
bool m_calculateOtherCut = true
 iff true, the other (near to s for primaryCut == false, near to t for primaryCut == true) cut should also be calculated. More...
 
std::unique_ptr< EpsilonTestm_et
 
EdgeArray< TCost > m_flow
 
int m_frontCutCount
 
std::unique_ptr< MaxFlowModule< TCost > > m_mfModule
 the module used for calculating the maxflow More...
 
NodeArray< cutTypem_nodeSet
 
bool m_primaryCut = true
 true if the algorithm should search for the mincut nearest to s, false if it should be near to t. More...
 
int m_totalCount
 
bool m_treatAsUndirected = false
 states whether or not edges are considered undirected while calculating the maxflow More...
 
EdgeArray< TCost > m_weight
 

Additional Inherited Members

- Protected Member Functions inherited from ogdf::MinSTCutModule< TCost >
bool preprocessingDual (const Graph &graph, GraphCopy &gc, CombinatorialEmbedding &CE, node source, node target, edge e_st)
 This method preprocesses gc for minstcut calculations, by adding an st-edge if needed and embedding gc. More...
 
- Protected Attributes inherited from ogdf::MinSTCutModule< TCost >
EdgeArray< int > m_direction
 
GraphCopym_gc = nullptr
 

Detailed Description

template<typename TCost>
class ogdf::MinSTCutMaxFlow< TCost >

Min-st-cut algorithm, that calculates the cut via maxflow.

Template Parameters
TCostThe type in which the weight of the edges is given.

Definition at line 48 of file MinSTCutMaxFlow.h.

Member Enumeration Documentation

◆ cutType

template<typename TCost >
enum ogdf::MinSTCutMaxFlow::cutType
strong

The three types of cuts.

Enumerator
FRONT_CUT 

node is in front cut

BACK_CUT 

node is in back cut

NO_CUT 

node is not part of any cut

Definition at line 101 of file MinSTCutMaxFlow.h.

Constructor & Destructor Documentation

◆ MinSTCutMaxFlow()

template<typename TCost >
ogdf::MinSTCutMaxFlow< TCost >::MinSTCutMaxFlow ( bool  treatAsUndirected = true,
MaxFlowModule< TCost > *  mfModule = new MaxFlowGoldbergTarjan<TCost>(),
bool  primaryCut = true,
bool  calculateOtherCut = true,
EpsilonTest epsilonTest = new EpsilonTest() 
)
inlineexplicit

Constructor.

Parameters
treatAsUndirectedStates whether or not
mfModuleThe MaxFlowModule that is used to calculate a flow. The module will be deleted, when the lifetime of this object is over.
primaryCuttrue if the algorithm should search for the mincut nearest to s, false if it should be near to t.
calculateOtherCutif true, the other cut (primaryCut == false : front cut, primaryCut == true : back cut) should also be calculated. Setting this to false will speed up the algorithm a bit, but some functions might not work correctly or at all.
epsilonTestThe module used for epsilon tests. The module will be deleted, when the lifetime of this object is over.

Definition at line 66 of file MinSTCutMaxFlow.h.

Member Function Documentation

◆ call() [1/3]

template<typename TCost >
bool ogdf::MinSTCutMaxFlow< TCost >::call ( const Graph graph,
const EdgeArray< TCost > &  weight,
node  s,
node  t,
List< edge > &  edgeList,
edge  e_st = nullptr 
)
overridevirtual

The actual algorithm call.

Parameters
graphThe graph on which the min-st-cut is to be calculated.
weightProvides a weight for every edge.
sThe source node.
tThe target node.
edgeListThis list is filled with the edges which are part of the mincut. If the graph is st-planarly embedded, this list is correctly ordered along the cut.
e_stAn edge between s and t which is used to determine where the cut should start, nullptr elsewise.
Returns
Indicates success.

Implements ogdf::MinSTCutModule< TCost >.

Definition at line 316 of file MinSTCutMaxFlow.h.

◆ call() [2/3]

template<typename TCost >
void ogdf::MinSTCutMaxFlow< TCost >::call ( const Graph graph,
const EdgeArray< TCost > &  weights,
const EdgeArray< TCost > &  flow,
const node  source,
const node  target 
)

Partitions the nodes to front- and backcut.

Parameters
graphThe underlying graph
weightsThe weights (aka capacity) of the edges
flowThe precomputed flow of each edge
sourceThe source of the min cut
targetthe target (aka sink) of the minimum cut

Definition at line 360 of file MinSTCutMaxFlow.h.

◆ call() [3/3]

template<typename TCost >
virtual bool ogdf::MinSTCutMaxFlow< TCost >::call ( const Graph graph,
node  s,
node  t,
List< edge > &  edgeList,
edge  e_st = nullptr 
)
inlineoverridevirtual

The actual algorithm call.

Parameters
graphThe graph on which the min-st-cut is to be calculated.
sThe source node.
tThe target node.
edgeListThis list is filled with the edges which are part of the mincut. If the graph is st-planarly embedded, this list is correctly ordered along the cut.
e_stAn edge between s and t which is used to determine where the cut should start, nullptr elsewise.
Returns
Indicates success.

Implements ogdf::MinSTCutModule< TCost >.

Definition at line 82 of file MinSTCutMaxFlow.h.

◆ computeCut()

template<typename TCost >
void ogdf::MinSTCutMaxFlow< TCost >::computeCut ( const Graph graph,
std::function< edge(edge)>  origEdge,
std::function< node(node)>  origNode,
const node  source,
const node  target,
List< edge > &  edgeList 
)
inlineprivate

Partitions the nodes to front and back cut.

Parameters
graphThe input graph
origEdgeMaps internal edges to edges of the the input graph.
origNodeMaps internal nodes to nodes from the input graph.
sourceThe source node.
targetThe target node.
edgeListA list in which the edges of the cut are stored in.

Definition at line 249 of file MinSTCutMaxFlow.h.

◆ frontCutIsComplementOfBackCut()

template<typename TCost >
bool ogdf::MinSTCutMaxFlow< TCost >::frontCutIsComplementOfBackCut ( ) const
inline

Returns whether the front cut is the complement of the backcut.

i.e. there are no nodes not assigned to one of both cut types.

Precondition
calculateOtherCut has to be set to true in the constructor

Definition at line 121 of file MinSTCutMaxFlow.h.

◆ isBackCutEdge()

template<typename TCost >
bool ogdf::MinSTCutMaxFlow< TCost >::isBackCutEdge ( const edge  e) const
inline

Returns whether this edge is entering the back cut.

Definition at line 140 of file MinSTCutMaxFlow.h.

◆ isFrontCutEdge()

template<typename TCost >
bool ogdf::MinSTCutMaxFlow< TCost >::isFrontCutEdge ( const edge  e) const
inline

Returns whether this edge is leaving the front cut.

Definition at line 130 of file MinSTCutMaxFlow.h.

◆ isInBackCut()

template<typename TCost >
bool ogdf::MinSTCutMaxFlow< TCost >::isInBackCut ( const node  v) const
inline

Returns whether this node is part of the back cut.

Meaning it is located in the same set as the target.

Parameters
vThe node in question.

Definition at line 163 of file MinSTCutMaxFlow.h.

◆ isInFrontCut()

template<typename TCost >
bool ogdf::MinSTCutMaxFlow< TCost >::isInFrontCut ( const node  v) const
inline

Returns whether this node is part of the front cut.

Meaning it is located in the same set as the source.

Definition at line 151 of file MinSTCutMaxFlow.h.

◆ isOfType()

template<typename TCost >
bool ogdf::MinSTCutMaxFlow< TCost >::isOfType ( const node  v,
cutType  type 
) const
inline

Return whether this node is of the specified type.

Parameters
vthe node to be tested
typethe cut type to test for (see MinSTCut::CutType)
Returns
true if the node is contained in the specified cut

Definition at line 180 of file MinSTCutMaxFlow.h.

◆ markCut()

template<typename TCost >
void ogdf::MinSTCutMaxFlow< TCost >::markCut ( node  startNode,
bool  frontCut,
std::function< node(node)>  origNode 
)
inlineprivate

Mark the all nodes which are in the same cut partition as the startNode.

Parameters
startNodeOnly works if this is either s or t.
frontCutShould be set to true, iff startNode is s.
origNodeA function which maps the internal nodes to the nodes of the input graph.

Definition at line 215 of file MinSTCutMaxFlow.h.

◆ setEpsilonTest()

template<typename TCost >
void ogdf::MinSTCutMaxFlow< TCost >::setEpsilonTest ( EpsilonTest et)
inline

Assigns a new epsilon test.

Definition at line 110 of file MinSTCutMaxFlow.h.

Member Data Documentation

◆ m_backCutCount

template<typename TCost >
int ogdf::MinSTCutMaxFlow< TCost >::m_backCutCount
private
  • the number of nodes in the back cut

Definition at line 205 of file MinSTCutMaxFlow.h.

◆ m_calculateOtherCut

template<typename TCost >
bool ogdf::MinSTCutMaxFlow< TCost >::m_calculateOtherCut = true
private

iff true, the other (near to s for primaryCut == false, near to t for primaryCut == true) cut should also be calculated.

Setting this to false will speed up the algorithm a bit, but all functions but call might not work correctly or at all.

Definition at line 197 of file MinSTCutMaxFlow.h.

◆ m_et

template<typename TCost >
std::unique_ptr<EpsilonTest> ogdf::MinSTCutMaxFlow< TCost >::m_et
private
  • the module used for epsilon tests

Definition at line 200 of file MinSTCutMaxFlow.h.

◆ m_flow

template<typename TCost >
EdgeArray<TCost> ogdf::MinSTCutMaxFlow< TCost >::m_flow
private

Definition at line 202 of file MinSTCutMaxFlow.h.

◆ m_frontCutCount

template<typename TCost >
int ogdf::MinSTCutMaxFlow< TCost >::m_frontCutCount
private
  • the number of nodes in the front cut

Definition at line 204 of file MinSTCutMaxFlow.h.

◆ m_mfModule

template<typename TCost >
std::unique_ptr<MaxFlowModule<TCost> > ogdf::MinSTCutMaxFlow< TCost >::m_mfModule
private

the module used for calculating the maxflow

Definition at line 187 of file MinSTCutMaxFlow.h.

◆ m_nodeSet

template<typename TCost >
NodeArray<cutType> ogdf::MinSTCutMaxFlow< TCost >::m_nodeSet
private
  • holds the partition type for each node

Definition at line 201 of file MinSTCutMaxFlow.h.

◆ m_primaryCut

template<typename TCost >
bool ogdf::MinSTCutMaxFlow< TCost >::m_primaryCut = true
private

true if the algorithm should search for the mincut nearest to s, false if it should be near to t.

Definition at line 191 of file MinSTCutMaxFlow.h.

◆ m_totalCount

template<typename TCost >
int ogdf::MinSTCutMaxFlow< TCost >::m_totalCount
private
  • the total number of nodes in the graph

Definition at line 206 of file MinSTCutMaxFlow.h.

◆ m_treatAsUndirected

template<typename TCost >
bool ogdf::MinSTCutMaxFlow< TCost >::m_treatAsUndirected = false
private

states whether or not edges are considered undirected while calculating the maxflow

Definition at line 189 of file MinSTCutMaxFlow.h.

◆ m_weight

template<typename TCost >
EdgeArray<TCost> ogdf::MinSTCutMaxFlow< TCost >::m_weight
private

Definition at line 203 of file MinSTCutMaxFlow.h.


The documentation for this class was generated from the following file: