Computes a minimum cut in a graph. More...

#include <ogdf/graphalg/MinimumCutStoerWagner.h>

Inheritance diagram for ogdf::MinimumCutStoerWagner< T >:

Public Member Functions
virtual T	call (const Graph &G) override
	Computes a minimum cut on graph `G`.

virtual T	call (const Graph &G, const EdgeArray< T > &weights) override
	Computes a minimum cut on graph `G` with non-negative `weights` on edges.

virtual const ArrayBuffer< edge > &	edges () override
	Computes the edges defining the computed mincut and returns them.

virtual const ArrayBuffer< node > &	nodes () override
	Returns a const-reference to the list of nodes belonging to one side of the bipartition.

virtual T	value () const override
	Returns the value of the last minimum cut computation.

Public Member Functions inherited from ogdf::MinimumCutModule< T >
virtual	~MinimumCutModule ()
	Do nothing on destruction.

Protected Member Functions
void	contraction (node t, node s)
	Contracts the nodes `s` and `t`, i.e., `s` is collapsed to `t`. The edge (if existing) between `s` and `t` is deleted. Edges incident to `s` are redirected to `t`. If parallel edges occur, one of them is deleted and its weight is added to the other one.

void	mainLoop ()
	Computes minimum cut by invoking minimumCutPhase() O(\|V\|) times.

T	minimumCutPhase ()
	Computes and returns the value of the minimum cut of the current phase (iteration).

Protected Attributes
NodeArray< List< node > >	m_contractedNodes
	Each node has a list containing the nodes with which it has been contracted. Because the GraphCopy m_GC is destroyed during the algorithm, this is necessary to be able to determine the original nodes in the end.

ArrayBuffer< edge >	m_cutEdges
	Store cut edges if computed.

GraphCopy	m_GC
	The modifiable version of the input graph (used for contractions)

T	m_minCut
	Stores the value of the minimum cut.

ArrayBuffer< node >	m_partition
	Store one side of the computed bipartition.

EdgeArray< T >	m_w
	An EdgeArray containing the corresponding edge weights.

Detailed Description

template<typename T = double>
struct ogdf::MinimumCutStoerWagner< T >

Computes a minimum cut in a graph.

The minimum-cut algorithm according to an approach of Stoer and Wagner 1997 is used.

Definition at line 50 of file MinimumCutStoerWagner.h.

Member Function Documentation

◆ call() [1/2]

template<typename T = double>

virtual T ogdf::MinimumCutStoerWagner< T >::call ( const Graph & G )

inlineoverridevirtual

Computes a minimum cut on graph G.

Implements ogdf::MinimumCutModule< T >.

Definition at line 52 of file MinimumCutStoerWagner.h.

◆ call() [2/2]

template<typename T = double>

virtual T ogdf::MinimumCutStoerWagner< T >::call	(	const Graph &	G,
		const EdgeArray< T > &	weights
	)

inlineoverridevirtual

Computes a minimum cut on graph G with non-negative weights on edges.

Implements ogdf::MinimumCutModule< T >.

Definition at line 58 of file MinimumCutStoerWagner.h.

◆ contraction()

template<typename T >

void ogdf::MinimumCutStoerWagner< T >::contraction	(	node	t,
		node	s
	)

protected

Contracts the nodes s and t, i.e., s is collapsed to t. The edge (if existing) between s and t is deleted. Edges incident to s are redirected to t. If parallel edges occur, one of them is deleted and its weight is added to the other one.

Definition at line 152 of file MinimumCutStoerWagner.h.

◆ edges()

template<typename T = double>

virtual const ArrayBuffer< edge > & ogdf::MinimumCutStoerWagner< T >::edges ( )

inlineoverridevirtual

Computes the edges defining the computed mincut and returns them.

When calling this method multiple times, the cut edges are only recomputed if the main min cut algorithm has been called in between.

Implements ogdf::MinimumCutModule< T >.

Definition at line 82 of file MinimumCutStoerWagner.h.

◆ mainLoop()

template<typename T = double>

void ogdf::MinimumCutStoerWagner< T >::mainLoop ( )

inlineprotected

Computes minimum cut by invoking minimumCutPhase() O(|V|) times.

Definition at line 130 of file MinimumCutStoerWagner.h.

◆ minimumCutPhase()

template<typename T >

T ogdf::MinimumCutStoerWagner< T >::minimumCutPhase ( )

protected

Computes and returns the value of the minimum cut of the current phase (iteration).

Definition at line 193 of file MinimumCutStoerWagner.h.

◆ nodes()

template<typename T = double>

virtual const ArrayBuffer< node > & ogdf::MinimumCutStoerWagner< T >::nodes ( )

inlineoverridevirtual

Returns a const-reference to the list of nodes belonging to one side of the bipartition.

Implements ogdf::MinimumCutModule< T >.

Definition at line 104 of file MinimumCutStoerWagner.h.

◆ value()

template<typename T = double>

virtual T ogdf::MinimumCutStoerWagner< T >::value ( ) const

template<typename T = double>

EdgeArray<T> ogdf::MinimumCutStoerWagner< T >::m_w

protected

An EdgeArray containing the corresponding edge weights.

Definition at line 116 of file MinimumCutStoerWagner.h.

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

include/ogdf/graphalg/MinimumCutStoerWagner.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Function Documentation

◆ call() [1/2]

◆ call() [2/2]

◆ contraction()

◆ edges()

◆ mainLoop()

◆ minimumCutPhase()

◆ nodes()

◆ value()

Member Data Documentation

◆ m_contractedNodes

◆ m_cutEdges

◆ m_GC

◆ m_minCut

◆ m_partition

◆ m_w

Open
Graph Drawing
Framework