Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::MinimumCutNagamochiIbaraki Class Reference

Calculate minimum cut value for a given Graph. More...

#include <ogdf/graphalg/MinimumCutNagamochiIbaraki.h>

+ Inheritance diagram for ogdf::MinimumCutNagamochiIbaraki:

Classes

struct  adjInfo
 
struct  BoundedList
 
struct  clusterstruct
 

Public Member Functions

 MinimumCutNagamochiIbaraki (bool p=true, bool preprocessing=false, Logger::Level logLevel=Logger::Level::Default)
 Standard constructor of the class. More...
 
virtual ~MinimumCutNagamochiIbaraki () override
 Standard destructor of the class. More...
 
virtual int call (const Graph &G) override
 Computes a minimum cut on graph G. More...
 
virtual int call (const Graph &G, const EdgeArray< int > &weights) override
 Computes a minimum cut on graph G with non-negative weights on edges. More...
 
virtual const ArrayBuffer< edge > & edges () override
 Returns the edges defining the computed mincut. More...
 
const unsigned int & getNIRounds () const
 Output the number of Nagamochi-Ibaraki rounds (equals to MAO-Computations) More...
 
const unsigned int & getPrRounds () const
 Output the number of Padberg-Rinaldi rounds. More...
 
const int & minCutUnweighted (const Graph &G)
 Compute a minimum cut value for the given unweighted graph. More...
 
const int & minCutWeighted (const Graph &G, const std::vector< int > &capacity)
 Compute a minimum cut value for the given weighted graph. More...
 
virtual const ArrayBuffer< node > & nodes () override
 Returns a list of nodes belonging to one side of the bipartition. More...
 
int value () const override
 Output value of last minimum cut computation. More...
 
- Public Member Functions inherited from ogdf::Logger
 Logger ()
 creates a new Logger-object with LogMode::Global and local log-level equal globalLogLevel More...
 
 Logger (Level level)
 creates a new Logger-object with LogMode::Log and given local log-level More...
 
 Logger (LogMode m)
 creates a new Logger-object with given log-mode and local log-level equal globalLogLevel More...
 
 Logger (LogMode m, Level level)
 creates a new Logger-object with given log-mode and given local log-level More...
 
bool is_lout (Level level=Level::Default) const
 returns true if such an lout command will result in text being printed More...
 
std::ostream & lout (Level level=Level::Default, bool indent=true) const
 stream for logging-output (local) More...
 
std::ostream & sout () const
 stream for statistic-output (local) More...
 
std::ostream & fout () const
 stream for forced output (local) More...
 
Level localLogLevel () const
 gives the local log-level More...
 
void localLogLevel (Level level)
 sets the local log-level More...
 
LogMode localLogMode () const
 gives the local log-mode More...
 
void localLogMode (LogMode m)
 sets the local log-mode More...
 
void indent (int by=1)
 
void dedent (int by=1)
 
int getIndent () const
 
void setIndent (int indent)
 
Level effectiveLogLevel () const
 obtain the effective log-level for the Logger-object (i.e., resolve the dependencies on the global settings) More...
 
bool effectiveStatisticMode () const
 returns true if the Logger-object is effectively in statistic-mode (as this might be depending on the global settings) More...
 
- Public Member Functions inherited from ogdf::MinimumCutModule< int >
virtual ~MinimumCutModule ()
 Do nothing on destruction. More...
 
virtual int value () const=0
 Returns the value of the last minimum cut computation. More...
 

Private Member Functions

void contract (const node &s, const ListPure< node > &toContract, const int &clusterlevel, const std::vector< clusterstruct > &clusters)
 Contracts one clusters. More...
 
void contractClusters (const std::vector< clusterstruct > &clusters)
 Contracts all Clusters trough contraction of each cluster using contractClusters. More...
 
void deleteFromL (BoundedList &L, ListIterator< node > &placeInL)
 Deletes the node given through placeInL from L. More...
 
void fillL (const int &maxAdj, ListPure< node > &unviewed, BoundedList &L, std::vector< adjInfo > &adjToViewed)
 Refills L, if it's empty but nodes with the same adjacency exists. More...
 
node getFirstNode (BoundedList &L)
 Return first node of L and adjust values of L. More...
 
void init (const Graph &G)
 Initializes member variables. More...
 
node MAOComputation (const node &s)
 Compute a MAO and contract clusters in it. More...
 
void minCut ()
 Underlying function for minCut computation. More...
 
const int & minCutWeighted ()
 Compute a minimum cut value for the given weighted graph, assuming that m_GC and edgeCapacity have already been initialized. More...
 
void PRPass1_2 (const node &lastContracted)
 Tests rule 1 and 2 of Padberg-Rinaldi of all incident edges of lastContracted and contracts on success. More...
 
bool PRTest1 (const unsigned int &eIndex)
 Test for rule 1 of Padberg-Rinaldi. More...
 
bool PRTest2 (const unsigned int &eIndex, const unsigned int &uIndex, const unsigned int &vIndex)
 Test for rule 2 of Padberg-Rinaldi. More...
 
void updateClusters (const node &head, const node &currentNode, std::vector< clusterstruct > &clusters, int &level)
 Add new node to an existing cluster of head or create new cluster with head as head. More...
 
void updateLambda (const int nodeDegree)
 Checks for new upper bound. More...
 

Static Private Member Functions

static edge getAdjEdge (const adjEntry &adj, const node &s, node &opposite)
 Returns edge corresponding to adj. More...
 

Private Attributes

std::unordered_set< nodeallNodes
 
int barLambda = 0
 
std::vector< int > degree
 
std::vector< int > edgeCapacity
 
Graph::HiddenEdgeSethiddenEdges
 
int M
 
ArrayBuffer< edgem_cutEdges
 
GraphCopy m_GC
 
ArrayBuffer< nodem_partition
 
bool m_preprocess
 
int N
 
unsigned int NIRounds = 0
 
bool pr
 
unsigned int prRounds = 0
 
std::vector< int > setid
 
int size
 

Additional Inherited Members

- Public Types inherited from ogdf::Logger
enum  Level { Level::Minor, Level::Medium, Level::Default, Level::High, Level::Alarm, Level::Force }
 supported log-levels from lowest to highest importance More...
 
enum  LogMode { LogMode::Global, LogMode::GlobalLog, LogMode::Log, LogMode::Statistic }
 Local log-modes. More...
 
- Static Public Member Functions inherited from ogdf::Logger
static bool is_slout (Level level=Level::Default)
 returns true if such an slout command will result in text being printed More...
 
static std::ostream & slout (Level level=Level::Default)
 stream for logging-output (global) More...
 
static std::ostream & ssout ()
 stream for statistic-output (global) More...
 
static std::ostream & sfout ()
 stream for forced output (global) More...
 
static bool is_ilout (Level level=Level::Default)
 stream for logging-output (global; used by internal libraries, e.g. Abacus) returns true if such an ilout command will result in text being printed More...
 
static std::ostream & ilout (Level level=Level::Default)
 
static std::ostream & ifout ()
 stream for forced output (global; used by internal libraries, e.g. Abacus) More...
 
static Level globalLogLevel ()
 gives the global log-level More...
 
static void globalLogLevel (Level level)
 sets the global log-level More...
 
static Level globalInternalLibraryLogLevel ()
 gives the internal-library log-level More...
 
static void globalInternalLibraryLogLevel (Level level)
 sets the internal-library log-level More...
 
static Level globalMinimumLogLevel ()
 gives the globally minimally required log-level More...
 
static void globalMinimumLogLevel (Level level)
 sets the globally minimally required log-level More...
 
static bool globalStatisticMode ()
 returns true if we are globally in statistic mode More...
 
static void globalStatisticMode (bool s)
 sets whether we are globally in statistic mode More...
 
static void setWorldStream (std::ostream &o)
 change the stream to which allowed output is written (by default: std::cout) More...
 

Detailed Description

Calculate minimum cut value for a given Graph.

This class implements a version of Nagamochi-Ibaraki with Padberg-Rinaldi heuristics. Implemented to be faster than the standard mincut algorithm.

Definition at line 60 of file MinimumCutNagamochiIbaraki.h.

Constructor & Destructor Documentation

◆ MinimumCutNagamochiIbaraki()

ogdf::MinimumCutNagamochiIbaraki::MinimumCutNagamochiIbaraki ( bool  p = true,
bool  preprocessing = false,
Logger::Level  logLevel = Logger::Level::Default 
)

Standard constructor of the class.

Parameters
pIf true use Padberg Rinaldi heuristics
preprocessingIf true use preprocessing
logLevelLevel of debug messages

◆ ~MinimumCutNagamochiIbaraki()

virtual ogdf::MinimumCutNagamochiIbaraki::~MinimumCutNagamochiIbaraki ( )
overridevirtual

Standard destructor of the class.

Member Function Documentation

◆ call() [1/2]

virtual int ogdf::MinimumCutNagamochiIbaraki::call ( const Graph G)
inlineoverridevirtual

Computes a minimum cut on graph G.

Implements ogdf::MinimumCutModule< int >.

Definition at line 90 of file MinimumCutNagamochiIbaraki.h.

◆ call() [2/2]

virtual int ogdf::MinimumCutNagamochiIbaraki::call ( const Graph G,
const EdgeArray< int > &  weights 
)
inlineoverridevirtual

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

Implements ogdf::MinimumCutModule< int >.

Definition at line 93 of file MinimumCutNagamochiIbaraki.h.

◆ contract()

void ogdf::MinimumCutNagamochiIbaraki::contract ( const node s,
const ListPure< node > &  toContract,
const int &  clusterlevel,
const std::vector< clusterstruct > &  clusters 
)
private

Contracts one clusters.

Parameters
sClusterhead of the current cluster
toContractNodes of the current cluster
clusterlevelInteger representing the cluster in setid
clustersVector containing all clusters to contract

◆ contractClusters()

void ogdf::MinimumCutNagamochiIbaraki::contractClusters ( const std::vector< clusterstruct > &  clusters)
private

Contracts all Clusters trough contraction of each cluster using contractClusters.

Parameters
clustersVector containing all clusters to contract

◆ deleteFromL()

void ogdf::MinimumCutNagamochiIbaraki::deleteFromL ( BoundedList L,
ListIterator< node > &  placeInL 
)
private

Deletes the node given through placeInL from L.

Parameters
LList which could contain node (only possible if node was added to list )
placeInLInformation of node (If null, the node wasn't added to the list)

◆ edges()

virtual const ArrayBuffer<edge>& ogdf::MinimumCutNagamochiIbaraki::edges ( )
inlineoverridevirtual

Returns the edges defining the computed mincut.

Implements ogdf::MinimumCutModule< int >.

Definition at line 107 of file MinimumCutNagamochiIbaraki.h.

◆ fillL()

void ogdf::MinimumCutNagamochiIbaraki::fillL ( const int &  maxAdj,
ListPure< node > &  unviewed,
BoundedList L,
std::vector< adjInfo > &  adjToViewed 
)
private

Refills L, if it's empty but nodes with the same adjacency exists.

Parameters
maxAdjNodes with adjacency maxAdj are added to L
unviewedRemaining nodes which are candidates to add to L
LList to add nodes to
adjToViewedAdjacency values of nodes

◆ getAdjEdge()

static edge ogdf::MinimumCutNagamochiIbaraki::getAdjEdge ( const adjEntry adj,
const node s,
node opposite 
)
inlinestaticprivate

Returns edge corresponding to adj.

Parameters
adjGiven adjEntry
sGiven node incident to edge
oppositeFor saving opposite node to s for the edge

Definition at line 244 of file MinimumCutNagamochiIbaraki.h.

◆ getFirstNode()

node ogdf::MinimumCutNagamochiIbaraki::getFirstNode ( BoundedList L)
private

Return first node of L and adjust values of L.

Parameters
LNot empty list containing nodes

◆ getNIRounds()

const unsigned int& ogdf::MinimumCutNagamochiIbaraki::getNIRounds ( ) const
inline

Output the number of Nagamochi-Ibaraki rounds (equals to MAO-Computations)

Definition at line 120 of file MinimumCutNagamochiIbaraki.h.

◆ getPrRounds()

const unsigned int& ogdf::MinimumCutNagamochiIbaraki::getPrRounds ( ) const
inline

Output the number of Padberg-Rinaldi rounds.

Definition at line 115 of file MinimumCutNagamochiIbaraki.h.

◆ init()

void ogdf::MinimumCutNagamochiIbaraki::init ( const Graph G)
private

Initializes member variables.

◆ MAOComputation()

node ogdf::MinimumCutNagamochiIbaraki::MAOComputation ( const node s)
private

Compute a MAO and contract clusters in it.

Parameters
sStarting node

◆ minCut()

void ogdf::MinimumCutNagamochiIbaraki::minCut ( )
private

Underlying function for minCut computation.

◆ minCutUnweighted()

const int& ogdf::MinimumCutNagamochiIbaraki::minCutUnweighted ( const Graph G)

Compute a minimum cut value for the given unweighted graph.

Parameters
Ginput graph

◆ minCutWeighted() [1/2]

const int& ogdf::MinimumCutNagamochiIbaraki::minCutWeighted ( )
private

Compute a minimum cut value for the given weighted graph, assuming that m_GC and edgeCapacity have already been initialized.

◆ minCutWeighted() [2/2]

const int& ogdf::MinimumCutNagamochiIbaraki::minCutWeighted ( const Graph G,
const std::vector< int > &  capacity 
)

Compute a minimum cut value for the given weighted graph.

Parameters
Ginput graph
capacityVector representing the capacity values of edges

◆ nodes()

virtual const ArrayBuffer<node>& ogdf::MinimumCutNagamochiIbaraki::nodes ( )
inlineoverridevirtual

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

Implements ogdf::MinimumCutModule< int >.

Definition at line 110 of file MinimumCutNagamochiIbaraki.h.

◆ PRPass1_2()

void ogdf::MinimumCutNagamochiIbaraki::PRPass1_2 ( const node lastContracted)
private

Tests rule 1 and 2 of Padberg-Rinaldi of all incident edges of lastContracted and contracts on success.

Parameters
lastContractedNode to check

◆ PRTest1()

bool ogdf::MinimumCutNagamochiIbaraki::PRTest1 ( const unsigned int &  eIndex)
inlineprivate

Test for rule 1 of Padberg-Rinaldi.

Parameters
eIndexIndex of the edge e to test

Definition at line 186 of file MinimumCutNagamochiIbaraki.h.

◆ PRTest2()

bool ogdf::MinimumCutNagamochiIbaraki::PRTest2 ( const unsigned int &  eIndex,
const unsigned int &  uIndex,
const unsigned int &  vIndex 
)
inlineprivate

Test for rule 2 of Padberg-Rinaldi.

Parameters
eIndexIndex of the edge e to test
uIndexIndex of node incident to e
vIndexIndex of node incident to e (uIndex != vIndex)

Definition at line 194 of file MinimumCutNagamochiIbaraki.h.

◆ updateClusters()

void ogdf::MinimumCutNagamochiIbaraki::updateClusters ( const node head,
const node currentNode,
std::vector< clusterstruct > &  clusters,
int &  level 
)
private

Add new node to an existing cluster of head or create new cluster with head as head.

Parameters
headAdjacent node with adjacency of currentNode >= barlambda
currentNodeNode to add to Cluster
clustersNeeded for adding node to or adding new cluster
levelSetid for the next new cluster

◆ updateLambda()

void ogdf::MinimumCutNagamochiIbaraki::updateLambda ( const int  nodeDegree)
inlineprivate

Checks for new upper bound.

Parameters
nodeDegreeDegree of node to check if lesser than barlambda

Definition at line 254 of file MinimumCutNagamochiIbaraki.h.

◆ value()

int ogdf::MinimumCutNagamochiIbaraki::value ( ) const
inlineoverride

Output value of last minimum cut computation.

Definition at line 104 of file MinimumCutNagamochiIbaraki.h.

Member Data Documentation

◆ allNodes

std::unordered_set<node> ogdf::MinimumCutNagamochiIbaraki::allNodes
private

Definition at line 280 of file MinimumCutNagamochiIbaraki.h.

◆ barLambda

int ogdf::MinimumCutNagamochiIbaraki::barLambda = 0
private

Definition at line 269 of file MinimumCutNagamochiIbaraki.h.

◆ degree

std::vector<int> ogdf::MinimumCutNagamochiIbaraki::degree
private

Definition at line 275 of file MinimumCutNagamochiIbaraki.h.

◆ edgeCapacity

std::vector<int> ogdf::MinimumCutNagamochiIbaraki::edgeCapacity
private

Definition at line 274 of file MinimumCutNagamochiIbaraki.h.

◆ hiddenEdges

Graph::HiddenEdgeSet* ogdf::MinimumCutNagamochiIbaraki::hiddenEdges
private

Definition at line 278 of file MinimumCutNagamochiIbaraki.h.

◆ M

int ogdf::MinimumCutNagamochiIbaraki::M
private

Definition at line 273 of file MinimumCutNagamochiIbaraki.h.

◆ m_cutEdges

ArrayBuffer<edge> ogdf::MinimumCutNagamochiIbaraki::m_cutEdges
private

Definition at line 284 of file MinimumCutNagamochiIbaraki.h.

◆ m_GC

GraphCopy ogdf::MinimumCutNagamochiIbaraki::m_GC
private

Definition at line 271 of file MinimumCutNagamochiIbaraki.h.

◆ m_partition

ArrayBuffer<node> ogdf::MinimumCutNagamochiIbaraki::m_partition
private

Definition at line 282 of file MinimumCutNagamochiIbaraki.h.

◆ m_preprocess

bool ogdf::MinimumCutNagamochiIbaraki::m_preprocess
private

Definition at line 260 of file MinimumCutNagamochiIbaraki.h.

◆ N

int ogdf::MinimumCutNagamochiIbaraki::N
private

Definition at line 272 of file MinimumCutNagamochiIbaraki.h.

◆ NIRounds

unsigned int ogdf::MinimumCutNagamochiIbaraki::NIRounds = 0
private

Definition at line 266 of file MinimumCutNagamochiIbaraki.h.

◆ pr

bool ogdf::MinimumCutNagamochiIbaraki::pr
private

Definition at line 262 of file MinimumCutNagamochiIbaraki.h.

◆ prRounds

unsigned int ogdf::MinimumCutNagamochiIbaraki::prRounds = 0
private

Definition at line 267 of file MinimumCutNagamochiIbaraki.h.

◆ setid

std::vector<int> ogdf::MinimumCutNagamochiIbaraki::setid
private

Definition at line 276 of file MinimumCutNagamochiIbaraki.h.

◆ size

int ogdf::MinimumCutNagamochiIbaraki::size
private

Definition at line 264 of file MinimumCutNagamochiIbaraki.h.


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