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`. More...

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

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

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

virtual T	value () const override

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

virtual double	call (const Graph &G, const EdgeArray< double > &weights)=0
	Computes the minimum cut of `G` with edge weights `weights`. More...

virtual double	value () const=0
	Returns the value of the last minimum cut computation. More...

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

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

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

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

ArrayBuffer< edge >	m_cutEdges
	Store cut edges if computed. More...

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

T	m_minCut
	Stores the value of the minimum cut. More...

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

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

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 59 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< double >.

Definition at line 61 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.

Definition at line 67 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 161 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< double >.

Definition at line 91 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 139 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 202 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< double >.

Definition at line 113 of file MinimumCutStoerWagner.h.

◆ value()

template<typename T = double>

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

inlineoverridevirtual

Definition at line 115 of file MinimumCutStoerWagner.h.

Member Data Documentation

◆ m_contractedNodes

template<typename T = double>

NodeArray<List<node> > ogdf::MinimumCutStoerWagner< T >::m_contractedNodes

protected

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.

Definition at line 136 of file MinimumCutStoerWagner.h.

◆ m_cutEdges

template<typename T = double>

ArrayBuffer<edge> ogdf::MinimumCutStoerWagner< T >::m_cutEdges

protected

Store cut edges if computed.

Definition at line 131 of file MinimumCutStoerWagner.h.

◆ m_GC

template<typename T = double>

GraphCopy ogdf::MinimumCutStoerWagner< T >::m_GC

protected

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

Definition at line 122 of file MinimumCutStoerWagner.h.

◆ m_minCut

template<typename T = double>

T ogdf::MinimumCutStoerWagner< T >::m_minCut

protected

Stores the value of the minimum cut.

Definition at line 119 of file MinimumCutStoerWagner.h.

◆ m_partition

template<typename T = double>

ArrayBuffer<node> ogdf::MinimumCutStoerWagner< T >::m_partition

protected

Store one side of the computed bipartition.

Definition at line 128 of file MinimumCutStoerWagner.h.

◆ m_w

template<typename T = double>

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

protected

An EdgeArray containing the corresponding edge weights.

Definition at line 125 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

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

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

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