ogdf::MinSTCutDijkstra< TCost > Class Template Reference

Min-st-cut algorithm, that calculates the cut by calculating the shortest path between the faces adjacent to an edge between s and t, via the algorithm by Dijkstra on the dual graph. More...

#include <ogdf/graphalg/MinSTCutDijkstra.h>

Inheritance diagram for ogdf::MinSTCutDijkstra< TCost >:

Public Member Functions
	MinSTCutDijkstra ()
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.
virtual bool	call (const Graph &graph, node s, node t, List< edge > &edgeList, edge e_st=nullptr) override
	The actual algorithm call.
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.

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::MinSTCutDijkstra< TCost >

Min-st-cut algorithm, that calculates the cut by calculating the shortest path between the faces adjacent to an edge between s and t, via the algorithm by Dijkstra on the dual graph.

Precondition

The input graph is st-planar.

Template Parameters

TCost

The type in which the weight of the edges is given.

Definition at line 55 of file MinSTCutDijkstra.h.

Constructor & Destructor Documentation

MinSTCutDijkstra()

template<typename TCost >

ogdf::MinSTCutDijkstra< TCost >::MinSTCutDijkstra ( )

inline

Definition at line 57 of file MinSTCutDijkstra.h.

Member Function Documentation

call() [1/2]

template<typename TCost >

bool ogdf::MinSTCutDijkstra< 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 78 of file MinSTCutDijkstra.h.

call() [2/2]

template<typename TCost >

virtual bool ogdf::MinSTCutDijkstra< 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 68 of file MinSTCutDijkstra.h.

---

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

• include/ogdf/graphalg/MinSTCutDijkstra.h