CliqueFinder.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_CLIQUEFINDER_H
#define OGDF_CLIQUEFINDER_H


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

namespace ogdf{



class OGDF_EXPORT CliqueFinder {

public:
    //constructor
    CliqueFinder(const Graph &G);
    ~CliqueFinder();
    
    //Calls
    //We first make G biconnected, this keeps the triconnected 
    //components. then the triconnected components are computed
    //within these components, we search for cliques
    

    void call(NodeArray<int> &cliqueNumber);

    void call(List< List<node> > &cliqueLists);

    void setMinSize(int i) { m_minDegree = max(2, i-1);}
    enum postProcess {ppNone, ppSimple};


    void setDensity(int density)
    {
        if (density < 0) m_density = 0;
        else if (density > 100) m_density = 100;
        else m_density = density;
    }

protected:
    void doCall(int minDegree = 2);

    //------------------------------------------------------
    //sets the results of doCall depending on call signature

    //clique nodes get numbers from >=0, all other nodes -1
    void setResults(NodeArray<int> &cliqueNumber);
    void setResults(List< List<node> > &cliqueLists);
    void setResults(List< List<node>* > &cliqueLists);

    //work on the result of the first phase (heuristic), e.g.
    //by dropping, splitting or joining some of the found subgraphs
    void postProcessCliques(List< List<node>* > &cliqueList,
        EdgeArray<bool> &usableEdge);

    //check if node v is adjacent to all nodes in node list
    bool allAdjacent(node v, List<node>* vList);
    void writeGraph(Graph &G, NodeArray<int> &cliqueNumber,
        const String &fileName);

    //does a heuristic evaluation of node v (in m_pCopy)
    //concerning its qualification as a cluster start node
    //the higher the return value, the better the node
    //uses only edges with usableEdge == true
    int evaluate(node v, EdgeArray<bool> &usableEdge);
    void checkCliques(List< List<node>* > &cliqueList, bool sizeCheck = true);
    bool cliqueOK(List<node> *clique);
    void findClique(node v, List<node> &neighbours,
                        int numRandom = 0);

private:
    const Graph* m_pGraph;
    GraphCopy* m_pCopy;
    NodeArray<int> m_copyCliqueNumber;
    NodeArray<bool> m_usedNode; //node is assigned to clique
    //List< List<node>* > m_cliqueList;
    int m_minDegree;
    int m_numberOfCliques; //stores the number of found cliques
    postProcess m_postProcess;
    bool m_callByList; //stores information on type of call for result setting
    List< List<node> > *m_pList; //stores pointer on list given as call parameter

    int m_density; //an abstract value from 0..100 definin how dense the
                   //subgraphs need to be, is not directly related to any
                   //measure (degree, ...) but translated into a constraint
                   //based on the heuristical search of the subgraphs
};//CliqueFinder

}//end namespace ogdf

#endif