MinimumCut.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_MINIMUM_CUT_H
#define OGDF_MINIMUM_CUT_H

#include <ogdf/basic/EdgeArray.h>
#include <ogdf/basic/NodeArray.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/simple_graph_alg.h>

namespace ogdf {
    

class OGDF_EXPORT MinCut {
    
public:
    //Todo: Shift parameters to the call!
    //m_minCut is only initialized once!!!
    MinCut(Graph &G, EdgeArray<double> &w);
    ~MinCut();
    
    // implements the main loop that computes the minimum cut by invoking function
    // minimumCutPhase() in each iteration. Returns the mincut value.
    double minimumCut();
    
    // returns the edges defining the computed mincut in list \a edges.
    void cutEdges(List<edge> &edges, Graph &G);
    
    // returns list of nodes belonging to one side of the bipartition in list \a nodes.
    void partition(List<node> &nodes);
    
    double const minCutValue() {return m_minCut;}
    
private:

    // stores the value of the minimum cut
    double m_minCut;
    
    // GraphCopy of the corresponding Graph. Used for the computation in order not 
    // to destroy the original Graph.
    GraphCopy m_GC;
    
    // an EdgeArray containing the corresponding edge weights.
    EdgeArray<double> m_w;
    
    // the two node lists corresponding to the node contraction
    List<node> m_contraction1, m_contraction2;
    
    // store one side of the computed bipartition.
    List<node> m_partition;
    
    // the list of edges defining the cut
    List<edge> m_cutEdges;
    
    // each node has a list containing the nodes with which it has been contracted. 
    // Because the GraphCopy \a m_GC is destroyed during the algorithm, this is
    // necessary to be able to determine the original nodes in the end.
    NodeArray<List<node> > m_contractedNodes;
    
    // computes and returns the value of the minimum cut of the current phase (itertion).
    double minimumCutPhase();
    
    // Contracts the nodes \a s and \a t, i.e \a s is collapsed to \a t.
    // The edge (if existing) between \a s and \t s is deleted. Edges incident to \a s are redirected to \t.
    // If parallel edges occur, one of them is deleted and its weight is added to the other one.
    void contraction(node t, node s);
    
};

}// end namespace

#endif