Calculate minimum cut value for a given Graph. More...
#include <ogdf/graphalg/MinimumCutNagamochiIbaraki.h>
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 ¤tNode, 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... | |
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.
ogdf::MinimumCutNagamochiIbaraki::MinimumCutNagamochiIbaraki | ( | bool | p = true , |
bool | preprocessing = false , |
||
Logger::Level | logLevel = Logger::Level::Default |
||
) |
Standard constructor of the class.
p | If true use Padberg Rinaldi heuristics |
preprocessing | If true use preprocessing |
logLevel | Level of debug messages |
|
overridevirtual |
Standard destructor of the class.
|
inlineoverridevirtual |
Computes a minimum cut on graph G
.
Implements ogdf::MinimumCutModule< int >.
Definition at line 90 of file MinimumCutNagamochiIbaraki.h.
|
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.
|
private |
Contracts one clusters.
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 |
|
private |
Contracts all Clusters trough contraction of each cluster using contractClusters.
clusters | Vector containing all clusters to contract |
|
private |
Deletes the node given through placeInL from L.
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) |
|
inlineoverridevirtual |
Returns the edges defining the computed mincut.
Implements ogdf::MinimumCutModule< int >.
Definition at line 107 of file MinimumCutNagamochiIbaraki.h.
|
private |
Refills L, if it's empty but nodes with the same adjacency exists.
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 |
|
inlinestaticprivate |
Returns edge corresponding to adj.
adj | Given adjEntry |
s | Given node incident to edge |
opposite | For saving opposite node to s for the edge |
Definition at line 244 of file MinimumCutNagamochiIbaraki.h.
|
private |
Return first node of L and adjust values of L.
L | Not empty list containing nodes |
|
inline |
Output the number of Nagamochi-Ibaraki rounds (equals to MAO-Computations)
Definition at line 120 of file MinimumCutNagamochiIbaraki.h.
|
inline |
Output the number of Padberg-Rinaldi rounds.
Definition at line 115 of file MinimumCutNagamochiIbaraki.h.
|
private |
Initializes member variables.
Compute a MAO and contract clusters in it.
s | Starting node |
|
private |
Underlying function for minCut computation.
const int& ogdf::MinimumCutNagamochiIbaraki::minCutUnweighted | ( | const Graph & | G | ) |
Compute a minimum cut value for the given unweighted graph.
G | input graph |
|
private |
Compute a minimum cut value for the given weighted graph, assuming that m_GC and edgeCapacity have already been initialized.
const int& ogdf::MinimumCutNagamochiIbaraki::minCutWeighted | ( | const Graph & | G, |
const std::vector< int > & | capacity | ||
) |
Compute a minimum cut value for the given weighted graph.
G | input graph |
capacity | Vector representing the capacity values of edges |
|
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.
|
private |
Tests rule 1 and 2 of Padberg-Rinaldi of all incident edges of lastContracted and contracts on success.
lastContracted | Node to check |
|
inlineprivate |
Test for rule 1 of Padberg-Rinaldi.
eIndex | Index of the edge e to test |
Definition at line 186 of file MinimumCutNagamochiIbaraki.h.
|
inlineprivate |
Test for rule 2 of Padberg-Rinaldi.
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 194 of file MinimumCutNagamochiIbaraki.h.
|
private |
Add new node to an existing cluster of head or create new cluster with head as head.
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 |
|
inlineprivate |
Checks for new upper bound.
nodeDegree | Degree of node to check if lesser than barlambda |
Definition at line 254 of file MinimumCutNagamochiIbaraki.h.
|
inlineoverride |
Output value of last minimum cut computation.
Definition at line 104 of file MinimumCutNagamochiIbaraki.h.
|
private |
Definition at line 280 of file MinimumCutNagamochiIbaraki.h.
|
private |
Definition at line 269 of file MinimumCutNagamochiIbaraki.h.
|
private |
Definition at line 275 of file MinimumCutNagamochiIbaraki.h.
|
private |
Definition at line 274 of file MinimumCutNagamochiIbaraki.h.
|
private |
Definition at line 278 of file MinimumCutNagamochiIbaraki.h.
|
private |
Definition at line 273 of file MinimumCutNagamochiIbaraki.h.
|
private |
Definition at line 284 of file MinimumCutNagamochiIbaraki.h.
|
private |
Definition at line 271 of file MinimumCutNagamochiIbaraki.h.
|
private |
Definition at line 282 of file MinimumCutNagamochiIbaraki.h.
|
private |
Definition at line 260 of file MinimumCutNagamochiIbaraki.h.
|
private |
Definition at line 272 of file MinimumCutNagamochiIbaraki.h.
|
private |
Definition at line 266 of file MinimumCutNagamochiIbaraki.h.
|
private |
Definition at line 262 of file MinimumCutNagamochiIbaraki.h.
|
private |
Definition at line 267 of file MinimumCutNagamochiIbaraki.h.
|
private |
Definition at line 276 of file MinimumCutNagamochiIbaraki.h.
|
private |
Definition at line 264 of file MinimumCutNagamochiIbaraki.h.