MinimumCutNagamochiIbaraki.h

Go to the documentation of this file.

 
#pragma once
 
#define OGDF_MINCUTNI_MAXLISTSIZE 100
#define OGDF_MINCUTNI_PRTHR 100
#define OGDF_MINCUTNI_CLUSTERSIZE 10
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/Graph_d.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/Logger.h>
#include <ogdf/basic/Math.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/simple_graph_alg.h>
#include <ogdf/graphalg/MinimumCutModule.h>
 
#include <queue>
#include <unordered_map>
#include <unordered_set>
 
namespace ogdf {
 
class OGDF_EXPORT MinimumCutNagamochiIbaraki : public Logger, public MinimumCutModule<int> {
public:
    MinimumCutNagamochiIbaraki(bool p = true, bool preprocessing = false,
            Logger::Level logLevel = Logger::Level::Default);
 
    virtual ~MinimumCutNagamochiIbaraki() override;
 
    const int& minCutWeighted(const Graph& G, const std::vector<int>& capacity);
 
    const int& minCutUnweighted(const Graph& G);
 
    virtual inline int call(const Graph& G) override { return minCutUnweighted(G); }
 
    virtual int call(const Graph& G, const EdgeArray<int>& weights) override {
        init(G);
        for (edge e : G.edges) {
            edgeCapacity[m_GC.copy(e)->index()] = weights[e];
        }
        const int& value {minCutWeighted()};
        delete hiddenEdges;
        return value;
    }
 
    int value() const override { return barLambda; };
 
    // @warning Currently this algorithm does not support returning the cut edges.
    virtual const ArrayBuffer<edge>& edges() override { return m_cutEdges; };
 
    // @warning Currently this algorithm does not support returning a min cut partition.
    virtual const ArrayBuffer<node>& nodes() override { return m_partition; };
 
    const unsigned int& getPrRounds() const { return prRounds; };
 
    const unsigned int& getNIRounds() const { return NIRounds; };
 
private:
    struct BoundedList {
        explicit BoundedList(ListPure<node> l_init = ListPure<node>(), int nodesInList_init = 0,
                int size_init = 0) {
            list = l_init;
            nodesInList = nodesInList_init;
            size = size_init;
        }
 
        ListPure<node> list;
        int nodesInList;
        int size;
    };
 
    struct adjInfo {
        int adj = 0;
        ListIterator<node> placeInL = nullptr;
    };
 
    struct clusterstruct {
        ListPure<node> clusterNodes;
        node clusterhead;
    };
 
    void init(const Graph& G);
 
    const int& minCutWeighted();
 
    void minCut();
 
    void contractClusters(const std::vector<clusterstruct>& clusters);
 
    void contract(const node& s, const ListPure<node>& toContract, const int& clusterlevel,
            const std::vector<clusterstruct>& clusters);
 
    void PRPass1_2(const node& lastContracted);
 
    inline bool PRTest1(const unsigned int& eIndex) { return (edgeCapacity[eIndex] >= barLambda); };
 
    inline bool PRTest2(const unsigned int& eIndex, const unsigned int& uIndex,
            const unsigned int& vIndex) {
        return 2 * edgeCapacity[eIndex] >= min(degree[uIndex], degree[vIndex]);
    };
 
    void updateClusters(const node& head, const node& currentNode,
            std::vector<clusterstruct>& clusters, int& level);
 
    node MAOComputation(const node& s);
 
    void deleteFromL(BoundedList& L, ListIterator<node>& placeInL);
 
    void fillL(const int& maxAdj, ListPure<node>& unviewed, BoundedList& L,
            std::vector<adjInfo>& adjToViewed);
 
    node getFirstNode(BoundedList& L);
 
    static edge getAdjEdge(const adjEntry& adj, const node& s, node& opposite) {
        auto e = adj->theEdge();
        opposite = e->opposite(s);
        return e;
    }
 
    inline void updateLambda(const int nodeDegree) {
        if (nodeDegree < barLambda && size >= 2) {
            barLambda = nodeDegree;
        }
    }
 
    bool m_preprocess; //if preprocessing should be used
 
    bool pr; //if pr should be used
 
    int size; //G.numberOfNodes()
 
    unsigned int NIRounds = 0;
    unsigned int prRounds = 0; //successful rounds of PR1_2
    //unsigned int pr3Rounds = 0;
    int barLambda = 0; //mincut value
 
    GraphCopy m_GC; //Copy of the Graph for changing nodes and edges
    int N; //original size
    int M; //original |E|
    std::vector<int> edgeCapacity; //capacity in graphcopy
    std::vector<int> degree;
    std::vector<int> setid;
 
    Graph::HiddenEdgeSet* hiddenEdges;
 
    std::unordered_set<node> allNodes;
 
    ArrayBuffer<node> m_partition;
 
    ArrayBuffer<edge> m_cutEdges;
};
}