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< EpsilonTest >	m_et

EdgeArray< TCost >	m_flow

int	m_frontCutCount

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

NodeArray< cutType >	m_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< 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`.

Protected Attributes inherited from ogdf::MinSTCutModule< TCost >
EdgeArray< int >	m_direction

GraphCopy *	m_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.

Member Enumeration Documentation

◆ cutType

template<typename TCost >

enum class 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 108 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

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.

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

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.

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 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<EpsilonTest> 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<TCost> 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<MaxFlowModule<TCost> > 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<cutType> 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<TCost> 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:

include/ogdf/graphalg/MinSTCutMaxFlow.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

◆ cutType

Constructor & Destructor Documentation

◆ MinSTCutMaxFlow()

Member Function Documentation

◆ call() [1/3]

◆ call() [2/3]

◆ call() [3/3]

◆ computeCut()

◆ frontCutIsComplementOfBackCut()

◆ isBackCutEdge()

◆ isFrontCutEdge()

◆ isInBackCut()

◆ isInFrontCut()

◆ isOfType()

◆ markCut()

◆ setEpsilonTest()

Member Data Documentation

◆ m_backCutCount

◆ m_calculateOtherCut

◆ m_et

◆ m_flow

◆ m_frontCutCount

◆ m_mfModule

◆ m_nodeSet

◆ m_primaryCut

◆ m_totalCount

◆ m_treatAsUndirected

◆ m_weight

Open
Graph Drawing
Framework