# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
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 class  cutType { FRONT_CUT , BACK_CUT , 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.

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.

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.

virtual bool call (const Graph &graph, node s, node t, List< edge > &edgeList, edge e_st=nullptr) override
The actual algorithm call.

bool frontCutIsComplementOfBackCut () const
Returns whether the front cut is the complement of the backcut.

bool isBackCutEdge (const edge e) const
Returns whether this edge is entering the back cut.

bool isFrontCutEdge (const edge e) const
Returns whether this edge is leaving the front cut.

bool isInBackCut (const node v) const
Returns whether this node is part of the back cut.

bool isInFrontCut (const node v) const
Returns whether this node is part of the front cut.

bool isOfType (const node v, cutType type) const
Return whether this node is of the specified type.

void setEpsilonTest (EpsilonTest *et)
Assigns a new epsilon test.

Public Member Functions inherited from ogdf::MinSTCutModule< TCost >
MinSTCutModule ()
default constructor (empty)

virtual ~MinSTCutModule ()

virtual bool direction (edge e)
Returns the direction of e in the cut.

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

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.

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

std::unique_ptr< EpsilonTestm_et

EdgeArray< TCostm_flow

int m_frontCutCount

std::unique_ptr< MaxFlowModule< TCost > > m_mfModule
the module used for calculating the maxflow

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.

int m_totalCount

bool m_treatAsUndirected = false
states whether or not edges are considered undirected while calculating the maxflow

EdgeArray< TCostm_weight

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.

Protected Attributes inherited from ogdf::MinSTCutModule< TCost >
EdgeArray< intm_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
 TCost The type in which the weight of the edges is given.

Definition at line 49 of file MinSTCutMaxFlow.h.

## ◆ cutType

template<typename TCost >
 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 108 of file MinSTCutMaxFlow.h.

## ◆ MinSTCutMaxFlow()

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

Constructor.

Parameters
 treatAsUndirected States whether or not mfModule The MaxFlowModule that is used to calculate a flow. The module will be deleted, when the lifetime of this object is over. primaryCut true if the algorithm should search for the mincut nearest to s, false if it should be near to t. calculateOtherCut if 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. epsilonTest The module used for epsilon tests. The module will be deleted, when the lifetime of this object is over.

Definition at line 68 of file MinSTCutMaxFlow.h.

## ◆ 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
 graph The graph on which the min-st-cut is to be calculated. weight Provides a weight for every edge. s The source node. t The target node. edgeList This 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_st An 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 310 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
 graph The underlying graph weights The weights (aka capacity) of the edges flow The precomputed flow of each edge source The source of the min cut target the target (aka sink) of the minimum cut

Definition at line 354 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
 graph The graph on which the min-st-cut is to be calculated. s The source node. t The target node. edgeList This 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_st An 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 87 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
 graph The input graph origEdge Maps internal edges to edges of the the input graph. origNode Maps internal nodes to nodes from the input graph. source The source node. target The target node. edgeList A list in which the edges of the cut are stored in.

Definition at line 245 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 125 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 142 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 133 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
 v The 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 152 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
 v the node to be tested type the cut type to test for (see MinSTCut::CutType)
Returns
true if the node is contained in the specified cut

Definition at line 179 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
 startNode Only works if this is either s or t. frontCut Should be set to true, iff startNode is s. origNode A function which maps the internal nodes to the nodes of the input graph.

Definition at line 211 of file MinSTCutMaxFlow.h.

## ◆ setEpsilonTest()

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

Assigns a new epsilon test.

Definition at line 117 of file MinSTCutMaxFlow.h.

## ◆ m_backCutCount

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

Definition at line 201 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 193 of file MinSTCutMaxFlow.h.

## ◆ m_et

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

Definition at line 196 of file MinSTCutMaxFlow.h.

## ◆ m_flow

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

Definition at line 198 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 200 of file MinSTCutMaxFlow.h.

## ◆ m_mfModule

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

the module used for calculating the maxflow

Definition at line 183 of file MinSTCutMaxFlow.h.

## ◆ m_nodeSet

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

Definition at line 197 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 187 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 202 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 185 of file MinSTCutMaxFlow.h.

## ◆ m_weight

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

Definition at line 199 of file MinSTCutMaxFlow.h.

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