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< node >	allNodes

int	barLambda = 0

std::vector< int >	degree

std::vector< int >	edgeCapacity

Graph::HiddenEdgeSet *	hiddenEdges

int	M

ArrayBuffer< edge >	m_cutEdges

GraphCopy	m_GC

ArrayBuffer< node >	m_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 59 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

p	If true use Padberg Rinaldi heuristics
preprocessing	If true use preprocessing
logLevel	Level 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 89 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 92 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

s	Clusterhead of the current cluster
toContract	Nodes of the current cluster
clusterlevel	Integer representing the cluster in setid
clusters	Vector 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

clusters Vector 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

L	List which could contain node (only possible if node was added to list )
placeInL	Information 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 106 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

maxAdj	Nodes with adjacency maxAdj are added to L
unviewed	Remaining nodes which are candidates to add to L
L	List to add nodes to
adjToViewed	Adjacency values of nodes

◆ getAdjEdge()

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

inlinestaticprivate

Returns edge corresponding to adj.

Parameters

adj	Given adjEntry
s	Given node incident to edge
opposite	For saving opposite node to s for the edge

Definition at line 243 of file MinimumCutNagamochiIbaraki.h.

◆ getFirstNode()

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

private

Return first node of L and adjust values of L.

Parameters

L	Not 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 119 of file MinimumCutNagamochiIbaraki.h.

◆ getPrRounds()

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

inline

Output the number of Padberg-Rinaldi rounds.

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

s	Starting 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

G	input 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

G	input graph
capacity	Vector 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 109 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

lastContracted Node to check

◆ PRTest1()

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

inlineprivate

Test for rule 1 of Padberg-Rinaldi.

Parameters

eIndex Index of the edge e to test

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

eIndex	Index of the edge e to test
uIndex	Index of node incident to e
vIndex	Index of node incident to e (uIndex != vIndex)

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

head	Adjacent node with adjacency of currentNode >= barlambda
currentNode	Node to add to Cluster
clusters	Needed for adding node to or adding new cluster
level	Setid for the next new cluster