Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::MinCut Class Reference

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

#include <ogdf/graphalg/MinimumCut.h>

Public Member Functions

 MinCut (Graph &G, EdgeArray< double > &w)
 
 ~MinCut ()
 
void cutEdges (List< edge > &edges, Graph &G)
 
double minCutValue () const
 
double minimumCut ()
 
void partition (List< node > &nodes)
 

Private Member Functions

void contraction (node t, node s)
 
double minimumCutPhase ()
 

Private Attributes

NodeArray< List< node > > m_contractedNodes
 
List< nodem_contraction1
 
List< nodem_contraction2
 
List< edgem_cutEdges
 
GraphCopy m_GC
 
double m_minCut
 
List< nodem_partition
 
EdgeArray< double > m_w
 

Detailed Description

Computes a minimum cut in a graph.

Definition at line 49 of file MinimumCut.h.

Constructor & Destructor Documentation

◆ MinCut()

ogdf::MinCut::MinCut ( Graph G,
EdgeArray< double > &  w 
)

◆ ~MinCut()

ogdf::MinCut::~MinCut ( )

Member Function Documentation

◆ contraction()

void ogdf::MinCut::contraction ( node  t,
node  s 
)
private

◆ cutEdges()

void ogdf::MinCut::cutEdges ( List< edge > &  edges,
Graph G 
)

◆ minCutValue()

double ogdf::MinCut::minCutValue ( ) const
inline

Definition at line 67 of file MinimumCut.h.

◆ minimumCut()

double ogdf::MinCut::minimumCut ( )

◆ minimumCutPhase()

double ogdf::MinCut::minimumCutPhase ( )
private

◆ partition()

void ogdf::MinCut::partition ( List< node > &  nodes)

Member Data Documentation

◆ m_contractedNodes

NodeArray<List<node> > ogdf::MinCut::m_contractedNodes
private

Definition at line 93 of file MinimumCut.h.

◆ m_contraction1

List<node> ogdf::MinCut::m_contraction1
private

Definition at line 82 of file MinimumCut.h.

◆ m_contraction2

List<node> ogdf::MinCut::m_contraction2
private

Definition at line 82 of file MinimumCut.h.

◆ m_cutEdges

List<edge> ogdf::MinCut::m_cutEdges
private

Definition at line 88 of file MinimumCut.h.

◆ m_GC

GraphCopy ogdf::MinCut::m_GC
private

Definition at line 76 of file MinimumCut.h.

◆ m_minCut

double ogdf::MinCut::m_minCut
private

Definition at line 72 of file MinimumCut.h.

◆ m_partition

List<node> ogdf::MinCut::m_partition
private

Definition at line 85 of file MinimumCut.h.

◆ m_w

EdgeArray<double> ogdf::MinCut::m_w
private

Definition at line 79 of file MinimumCut.h.


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