ClusterGraph.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_CLUSTER_GRAPH_H
#define OGDF_CLUSTER_GRAPH_H

#include <ogdf/basic/NodeArray.h>
#include <ogdf/basic/Stack.h>
#include <ogdf/basic/GraphObserver.h>


namespace ogdf {

class OGDF_EXPORT ClusterGraph;
class OGDF_EXPORT ClusterGraphObserver;


class OGDF_EXPORT ClusterElement : private GraphElement {

    friend class OGDF_EXPORT ClusterGraph;
    friend class GraphList<ClusterElement>;

    int                     m_id;         
    int                     m_depth;      
    List<node>              m_entries;    
    List<ClusterElement*>   m_children;   
    ClusterElement          *m_parent;    
    ClusterElement          *m_pPrev;     
    ClusterElement          *m_pNext;     
    ListIterator<ClusterElement*> m_it;   

    List<adjEntry>          m_adjEntries; 
                                          // Don't use a GraphList ! 
                                          // This messes with the adjacency 
                                          // list of the underlying graph

    #ifdef OGDF_DEBUG
    // we store the graph containing this cluster for debugging purposes
    const ClusterGraph *m_pClusterGraph;
    #endif

    
    void init(List<node> &nodes) {
        while (!nodes.empty())
            m_entries.pushBack(nodes.popFrontRet());
    }

    List<ClusterElement*> &getChildren(){
        return m_children;
    }

    List<node> &getNodes(){
        return m_entries;
    }
    

    void getClusterInducedNodes(List<node> &clusterNodes);
    void getClusterInducedNodes(NodeArray<bool> &clusterNode, int& num);


public:

    #ifdef OGDF_DEBUG
    ClusterElement(const ClusterGraph *pClusterGraph,int id):
        m_id(id),m_depth(0),m_parent(0),m_pPrev(0),m_pNext(0),m_it(0),      
        m_pClusterGraph(pClusterGraph) {};
    #else
    ClusterElement(int id):
        m_id(id), m_depth(0),m_parent(0),m_pPrev(0),m_pNext(0),m_it(0) {};
    #endif


    #ifdef OGDF_DEBUG
    const ClusterGraph *graphOf() const { return m_pClusterGraph; }
    #endif

    
    int index() const { return m_id; }
    int depth() const { return m_depth; }
    int& depth()      { return m_depth; }
    ClusterElement* succ() const { return (ClusterElement*)m_next; }
    ClusterElement* pred() const { return (ClusterElement*)m_prev; }

    ClusterElement* pSucc() const { return m_pNext; }
    ClusterElement* pPred() const { return m_pPrev; }

    // Iteration over tree structures.

    ListConstIterator<ClusterElement*> cBegin() const{ return m_children.begin();}
    ListConstIterator<ClusterElement*> crBegin() const{ return m_children.rbegin();}
    int cCount(){ return m_children.size();}
    ListIterator<node> nBegin(){ return m_entries.begin();}
    ListConstIterator<node> nBegin() const{ return m_entries.begin();}
    int nCount(){ return m_entries.size();}

    ClusterElement* parent(){return m_parent;}


    ListConstIterator<adjEntry> firstAdj() const { return m_adjEntries.begin();  }
    ListIterator<adjEntry> firstAdj() { return m_adjEntries.begin();  }
    ListConstIterator<adjEntry> lastAdj () const { return m_adjEntries.rbegin(); }
    ListIterator<adjEntry> lastAdj () { return m_adjEntries.rbegin(); }


    void getClusterNodes(List<node> &clusterNodes);
    int getClusterNodes(NodeArray<bool> &clusterNode);

    OGDF_NEW_DELETE

};// class ClusterElement




typedef ClusterElement *cluster; 


#define forall_cluster_adj(adj,c)\
for(ogdf::ListIterator<adjEntry> ogdf_loop_var=(c)->firstAdj();\
    ogdf::test_forall_adj_entries_of_cluster(ogdf_loop_var,(adj));\
    ogdf_loop_var=ogdf_loop_var.succ())

#define forall_cluster_rev_adj(adj,c)\
for(ogdf::ListIterator<adjEntry> ogdf_loop_var=(c)->lastAdj();\
    ogdf::test_forall_adj_entries_of_cluster(ogdf_loop_var,(adj));\
    ogdf_loop_var=ogdf_loop_var.pred())

#define forall_cluster_adj_edges(e,c)\
for(ogdf::ListIterator<adjEntry> ogdf_loop_var=(c)->firstAdj();\
    ogdf::test_forall_adj_edges_of_cluster(ogdf_loop_var,(e));\
    ogdf_loop_var=ogdf_loop_var.succ())



inline bool test_forall_adj_entries_of_cluster(ListIterator<adjEntry> &it, adjEntry &adj)
{
    if (it.valid()) { adj = (*it);return true; }
    else return false;
}

inline bool test_forall_adj_edges_of_cluster(ListIterator<adjEntry> &it, edge &e)
{
    adjEntry adj = (*it);
    if (adj) { e = adj->theEdge(); return true; }
    else return false;
}

inline bool test_forall_adj_edges_of_cluster(adjEntry &adj, edge &e)
{
    if (adj) { e = adj->theEdge(); return true; }
    else return false;
}


class ClusterArrayBase;
template<class T>class ClusterArray;

//---------------------------------------------------------
// iteration macros
//---------------------------------------------------------

#define forall_clusters(c,C) for((c)=(C).firstCluster(); (c); (c)=(c)->succ())

#define forall_postOrderClusters(c,C)\
for((c)=(C).firstPostOrderCluster(); (c); (c)=(c)->pSucc())





class OGDF_EXPORT ClusterGraph : public GraphObserver
{
    GraphList<ClusterElement> m_clusters; 

    const Graph *m_pGraph;            

    int     m_nClusters;              
    int     m_clusterIdCount;         
    int     m_clusterArrayTableSize;  
    
    mutable cluster m_postOrderStart; 
    cluster m_rootCluster;            

    bool    m_adjAvailable;       
    bool    m_allowEmptyClusters; 

    NodeArray<cluster> m_nodeMap; 

    NodeArray<ListIterator<node> >  m_itMap;   
    
    mutable ListPure<ClusterArrayBase*> m_regClusterArrays; 
    mutable ListPure<ClusterGraphObserver*> m_regObservers; 

public:

    ClusterGraph();


    ClusterGraph(const Graph &G);

    ClusterGraph(const ClusterGraph &C);


    ClusterGraph(const ClusterGraph &C,Graph &G);


    ClusterGraph(
        const ClusterGraph &C,
        Graph &G,
        ClusterArray<cluster> &originalClusterTable,
        NodeArray<node> &originalNodeTable);


    ClusterGraph(
        const ClusterGraph &C,
        Graph &G,
        ClusterArray<cluster> &originalClusterTable,
        NodeArray<node> &originalNodeTable,
        EdgeArray<edge> &edgeCopy);

    virtual ~ClusterGraph();

    int maxClusterIndex() const { return m_clusterIdCount-1; }

    void clear();

    void semiClear();

    void init(const Graph &G);
    
    operator const Graph &() const { return *m_pGraph; }

    ClusterGraph &operator=(const ClusterGraph &C);

    void clearClusterTree(cluster C);

    //TODO should be named getConstGraph
    const Graph & getGraph() const {return *m_pGraph;}

    cluster newCluster(cluster parent, int id = -1);

    cluster createEmptyCluster(const cluster parent = 0, int clusterId = -1);


    cluster createCluster(SList<node>& nodes, const cluster parent = 0);


    void delCluster(cluster c);

    cluster rootCluster() const {return m_rootCluster;};

    inline cluster clusterOf(node v) const{ 
        OGDF_ASSERT(v->graphOf() == m_pGraph)
        return m_nodeMap[v];
    }

    int numberOfClusters() const { return m_nClusters; }
    int clusterIdCount() const { return m_clusterIdCount;} 

    int clusterArrayTableSize() const { return m_clusterArrayTableSize; }

    void moveCluster(cluster c, cluster newParent);
    

    void reassignNode(node v, cluster c);

    //inserted mainly for use in gmlparser.
    void reInit(Graph& G) 
    {
        reinitGraph(G);
    }

    //---------------------------
    //tree queries / depth issues

    void setUpdateDepth(bool b) const 
    {
        m_updateDepth = b;
        //make sure that depth cant be used anymore
        //(even if it may still be valid a little while)
        if (!b) m_depthUpToDate = false;
    }

    void pullUpSubTree(cluster c);

    //maybe later we should provide a permanent depth member update
    int treeDepth() const
    {
        //initialize depth at first call
        if (m_updateDepth && !m_depthUpToDate)
            computeSubTreeDepth(rootCluster());
        if (!m_updateDepth) OGDF_THROW(AlgorithmFailureException);
        int l_depth = 1;
        cluster c;
        forall_clusters(c, *this)
        {
            if (c->depth() > l_depth) l_depth = c->depth();
        }

        return l_depth;
    }
    void computeSubTreeDepth(cluster c) const;
    //should be called instead of direct c->depth call to assure
    //valid depth
    int& clusterDepth(cluster c) const 
    {
        // updateDepth must be set to true if depth info shall be used
        OGDF_ASSERT(m_updateDepth);

        //initialize depth at first call
        if (!m_depthUpToDate)
            computeSubTreeDepth(rootCluster());
        OGDF_ASSERT(c->depth() != 0)
        return c->depth();
    }

    cluster commonCluster(SList<node>& nodes);


    cluster commonCluster(node v, node w) const;

    cluster commonClusterLastAncestors(
        node v, 
        node w,
        cluster& c1,
        cluster& c2) const;

    cluster commonClusterPath(
        node v,
        node w,
        List<cluster>& eL) const;

    cluster commonClusterAncestorsPath(
        node v, 
        node w,
        cluster& c1,
        cluster& c2,
        List<cluster>& eL) const;

    ListIterator<ClusterArrayBase*> registerArray(ClusterArrayBase *pClusterArray) const;

    void unregisterArray(ListIterator<ClusterArrayBase*> it) const;

    ListIterator<ClusterGraphObserver*> registerObserver(ClusterGraphObserver *pObserver) const;
    
    void unregisterObserver(ListIterator<ClusterGraphObserver*> it) const;
    

    void emptyClusters(SList<cluster>& emptyCluster, SList<cluster>* checkCluster = 0);

    inline bool emptyOnNodeDelete(cluster c) //virtual?
    {
        //if (!c) return false; //Allows easy use in loops
        return (c->nCount() == 1) && (c->cCount() == 0);
    }

    inline bool emptyOnClusterDelete(cluster c) //virtual?
    {
        //if (!c) return false; //Allows easy use in loops
        return (c->nCount() == 0) && (c->cCount() == 1);
    }

    cluster firstCluster() const { return m_clusters.begin (); }
    cluster lastCluster () const { return m_clusters.rbegin(); }
    cluster firstPostOrderCluster() const { 
        if (!m_postOrderStart) postOrder();
        return m_postOrderStart; 
    }

    template<class CLUSTERLIST>
    void allClusters(CLUSTERLIST &clusters) const {
        clusters.clear();
        for (cluster c = m_clusters.begin(); c; c = c->succ())
            clusters.pushBack(c);
    }

    template<class NODELIST>
    void collaps(NODELIST &nodes,Graph &G){
        OGDF_ASSERT(&G == m_pGraph);
        m_adjAvailable = false;

        m_postOrderStart = 0;
        node v = nodes.popFrontRet();
        while (!nodes.empty())
        {
            node w = nodes.popFrontRet();
            adjEntry adj = w->firstAdj();
            while (adj !=0)
            {
                adjEntry succ = adj->succ();
                edge e = adj->theEdge();
                if (e->source() == v || e->target() == v)
                    G.delEdge(e);
                else if (e->source() == w)
                    G.moveSource(e,v);
                else
                    G.moveTarget(e,v);
                adj = succ;
            }
            //because nodes can already be unassigned (they are always
            //unassigned if deleted), we have to check this
            /*
            if (m_nodeMap[w])
            {
                cluster c = m_nodeMap[w];
                c->m_entries.del(m_itMap[w]);
            }
            */
            //removeNodeAssignment(w);
            G.delNode(w);
        }
    }

    template<class EDGELIST>
    void adjEdges(cluster c, EDGELIST &edges) const {
        edges.clear();
        edge e;
        if (m_adjAvailable)
        {
            forall_cluster_adj_edges(e,c)
                edges.pushBack(e);
        }
    }

    template<class ADJLIST>
    void adjEntries(cluster c, ADJLIST &entries) const {
        entries.clear();
        adjEntry adj;
        if (m_adjAvailable)
        {
            forall_cluster_adj(adj,c)
                entries.pushBack(adj);
        }
    }

    template<class LISTITERATOR>
    void makeAdjEntries(cluster c,LISTITERATOR start){
        adjEntry adj;
        c->m_adjEntries.clear();
        LISTITERATOR its;
        for (its = start; its.valid(); its++)
        {
            adj = (*its);
            c->m_adjEntries.pushBack(adj);
        }
    }

    //**************************
    //file output

    void writeGML(const char *fileName);

    void writeGML(ostream &os);


    //**************************
    //file input
    bool readClusterGML(const char* fileName, Graph& G);
    bool readClusterGML(istream& is, Graph& G);

    // read Cluster Graph from OGML file
    //bool readClusterGraphOGML(const char* fileName, ClusterGraph& CG, Graph& G);

    // (for debugging purposes only)
    bool consistencyCheck();

    // (for debugging purposes only)
    bool representsCombEmbedding();

    void adjAvailable(bool val){ m_adjAvailable = val;};

protected:
    cluster doCreateCluster(SList<node>& nodes, 
        const cluster parent, int clusterId = -1);
    cluster doCreateCluster(SList<node>& nodes, 
        SList<cluster>& emptyCluster,
        const cluster parent, int clusterId = -1);

    mutable ClusterArray<int>* m_lcaSearch; 
    mutable int m_lcaNumber;
    mutable ClusterArray<cluster>* m_vAncestor;
    mutable ClusterArray<cluster>* m_wAncestor;

    void copyLCA(const ClusterGraph &C, ClusterArray<cluster>* clusterCopy=0);
    //int m_treeDepth; //should be implemented and updated in operations?

    mutable bool m_updateDepth; 
    mutable bool m_depthUpToDate; 

    //we assume that c is inserted via pushback in newparent->children
    void updatePostOrder(cluster c, cluster oldParent, cluster newParent);

    //0 if c==root 
    cluster postOrderPredecessor(cluster c) const;
    cluster leftMostCluster(cluster c) const;

    //---------------------------------------
    //functions inherited from GraphObserver:
    //define how to cope with graph changes
    
    virtual void nodeDeleted(node v) 
    { 
        bool cRemove = false;
        cluster c = clusterOf(v);
        if (!c) return;
        //never allow totally empty cluster
        //if ((emptyOnNodeDelete(c)) &&
        //  (c != rootCluster()) ) cRemove = true;
        unassignNode(v); 
        if (cRemove && !m_allowEmptyClusters) //parent exists
        {
            cluster nonEmpty = c->parent();
            cluster cRun = nonEmpty;
            delCluster(c);
            while ((cRun != rootCluster()) && (cRun->nCount() + cRun->cCount() == 0))
            {
                nonEmpty = cRun->parent();
                delCluster(cRun);
                cRun = nonEmpty;
            }

        }
    }
    virtual void nodeAdded(node v)   
    {
        assignNode(v, rootCluster());
    };
    virtual void edgeDeleted(edge /* e */) {};
    virtual void edgeAdded(edge /* e */)   {};
    virtual void reInit()            {};
    virtual void cleared()           
    {
        //we don't want a complete clear, as the graph still exists
        //and can be updated from input stream
        semiClear();
    };//Graph cleared

private:
    void assignNode(node v, cluster C);

    void unassignNode(node v);

    void removeNodeAssignment(node v)
    {
        if (m_nodeMap[v]) //iff == 0, itmap == 0 !!?
        {
            cluster C2 = m_nodeMap[v];
            C2->m_entries.del(m_itMap[v]);
            m_nodeMap[v] = 0; 
            m_itMap[v] = 0;   
        }
    }

    void shallowCopy(const ClusterGraph &C);

    void deepCopy(const ClusterGraph &C,Graph &G);
    void deepCopy(const ClusterGraph &C,Graph &G,   
                  ClusterArray<cluster> &originalClusterTable,
                  NodeArray<node> &originalNodeTable);
    void deepCopy(const ClusterGraph &C,Graph &G,   
                  ClusterArray<cluster> &originalClusterTable,
                  NodeArray<node> &originalNodeTable,
                  EdgeArray<edge> &edgeCopy);


    void clearClusterTree(cluster c,List<node> &attached);

    void initGraph(const Graph &G);

    void reinitGraph(const Graph &G);

    cluster newCluster(int id);
    cluster newCluster();

    void postOrder() const;
    void checkPostOrder() const;

    void postOrder(cluster c,SListPure<cluster> &S) const;

    void reinitArrays();


    void writeCluster(ostream &os,
                      NodeArray<int> &nId,
                      ClusterArray<int> & cId,
                      int &nextId,
                      cluster c,
                      String ttt);

    void writeGraphWinCluster(ostream &os,
                      NodeArray<int> &nId,
                      NodeArray<String> &nStr,
                      ClusterArray<int> &cId,
                      ClusterArray<String> &cStr,
                      int &nextId,
                      cluster c,
                      String ttt);

};





ostream &operator<<(ostream &os, ogdf::cluster c);


} // end namespace ogdf

#endif