Graph_d.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_GRAPH_D_H
#define OGDF_GRAPH_D_H


#include <ogdf/basic/List.h>


namespace ogdf {

//
// in embedded graphs, adjacency lists are given in clockwise order.
//


class OGDF_EXPORT Graph;
class OGDF_EXPORT NodeElement;
class OGDF_EXPORT EdgeElement;
class OGDF_EXPORT AdjElement;
class OGDF_EXPORT FaceElement;
class OGDF_EXPORT GraphListBase;
class OGDF_EXPORT ClusterElement;



class OGDF_EXPORT GraphElement {
    friend class Graph;
    friend class GraphListBase;

protected:
    GraphElement *m_next; 
    GraphElement *m_prev; 

    OGDF_NEW_DELETE
}; // class GraphElement


class OGDF_EXPORT GraphListBase {
protected:
    GraphElement *m_head; 
    GraphElement *m_tail; 

public:
    GraphListBase() { m_head = m_tail = 0; }
    // destruction
    ~GraphListBase() { }

    void pushBack(GraphElement *pX) {
        pX->m_next = 0;
        pX->m_prev = m_tail;
        if (m_head)
            m_tail = m_tail->m_next = pX;
        else
            m_tail = m_head = pX;
    }

    void insertAfter(GraphElement *pX, GraphElement *pY) {
        pX->m_prev = pY;
        GraphElement *pYnext = pX->m_next = pY->m_next;
        pY->m_next = pX;
        if (pYnext) pYnext->m_prev = pX;
        else m_tail = pX;
    }

    void insertBefore(GraphElement *pX, GraphElement *pY) {
        pX->m_next = pY;
        GraphElement *pYprev = pX->m_prev = pY->m_prev;
        pY->m_prev = pX;
        if (pYprev) pYprev->m_next = pX;
        else m_head = pX;
    }

    void del(GraphElement *pX) {
        GraphElement *pxPrev = pX->m_prev, *pxNext = pX->m_next;

        if (pxPrev)
            pxPrev->m_next = pxNext;
        else
            m_head = pxNext;
        if (pxNext)
            pxNext->m_prev = pxPrev;
        else
            m_tail = pxPrev;
    }

    template<class LIST>
    void sort(const LIST &newOrder) {
        GraphElement *pPred = 0;
        typename LIST::const_iterator it = newOrder.begin();
        if (!it.valid()) return;

        m_head = *it;
        for(; it.valid(); ++it) {
            GraphElement *p = *it;
            if ((p->m_prev = pPred) != 0) pPred->m_next = p;
            pPred = p;
        }

        (m_tail = pPred)->m_next = 0;
    }

    void reverse() {
        GraphElement *pX = m_head;
        m_head = m_tail;
        m_tail = pX;
        while(pX) {
            GraphElement *pY = pX->m_next;
            pX->m_next = pX->m_prev;
            pX = pX->m_prev = pY;
        }
    }

    void swap(GraphElement *pX, GraphElement *pY) {
        if (pX->m_next == pY) {
            pX->m_next = pY->m_next;
            pY->m_prev = pX->m_prev;
            pY->m_next = pX;
            pX->m_prev = pY;

        } else if(pY->m_next == pX) {
            pY->m_next = pX->m_next;
            pX->m_prev = pY->m_prev;
            pX->m_next = pY;
            pY->m_prev = pX;

        } else {
            ::swap(pX->m_next,pY->m_next);
            ::swap(pX->m_prev,pY->m_prev);
        }

        if(pX->m_prev)
            pX->m_prev->m_next = pX;
        else
            m_head = pX;
        if(pX->m_next)
            pX->m_next->m_prev = pX;
        else
            m_tail = pX;

        if(pY->m_prev)
            pY->m_prev->m_next = pY;
        else
            m_head = pY;
        if(pY->m_next)
            pY->m_next->m_prev = pY;
        else
            m_tail = pY;

        OGDF_ASSERT(consistencyCheck());
    }


    bool consistencyCheck() {
        if (m_head == 0) {
            return (m_tail == 0);

        } else if (m_tail == 0) {
            return false;

        } else {
            if (m_head->m_prev != 0)
                return false;
            if (m_tail->m_next != 0)
                return false;

            GraphElement *pX = m_head;
            for(; pX; pX = pX->m_next) {
                if (pX->m_prev) {
                    if (pX->m_prev->m_next != pX)
                        return false;
                } else if(pX != m_head)
                    return false;

                if (pX->m_next) {
                    if (pX->m_next->m_prev != pX)
                        return false;
                } else if (pX != m_tail)
                    return false;
            }
        }

        return true;
    }

    OGDF_NEW_DELETE
}; // class GraphListBase



template<class T> class GraphList : protected GraphListBase {
public:
    GraphList() { }
    // destruction (deletes all elements)
    ~GraphList() {
        if (m_head)
            OGDF_ALLOCATOR::deallocateList(sizeof(T), m_head,m_tail);
    }

    T *begin () const { return (T *)m_head; }
    T *rbegin() const { return (T *)m_tail; }

    bool empty() { return m_head; }

    void pushBack(T *pX) {
        GraphListBase::pushBack(pX);
    }

    void insertAfter(T *pX, T *pY) {
        GraphListBase::insertAfter(pX,pY);
    }

    void insertBefore(T *pX, T *pY) {
        GraphListBase::insertBefore(pX,pY);
    }

    void move(T *pX, GraphList<T> &L, T *pY, Direction dir) {
        GraphListBase::del(pX);
        if (dir == after)
            L.insertAfter(pX,pY);
        else
            L.insertBefore(pX,pY);
    }

    void move(T *pX, GraphList<T> &L) {
        GraphListBase::del(pX);
        L.pushBack(pX);
    }

    void moveAfter(T *pX, T *pY){
        GraphListBase::del(pX);
        insertAfter(pX,pY);
    }

    void moveBefore(T *pX, T *pY){
        GraphListBase::del(pX);
        insertBefore(pX,pY);
    }

    void del(T *pX) {
        GraphListBase::del(pX);
        delete pX;
    }

    void delPure(T *pX) {
        GraphListBase::del(pX);
    }

    void clear() {
        if (m_head) {
            OGDF_ALLOCATOR::deallocateList(sizeof(T),m_head,m_tail);
            m_head = m_tail = 0;
        }
    }

    template<class T_LIST>
    void sort(const T_LIST &newOrder) {
        GraphListBase::sort(newOrder);
    }


    void reverse() {
        GraphListBase::reverse();
    }

    void swap(T *pX, T *pY) {
        GraphListBase::swap(pX,pY);
    }


    bool consistencyCheck() {
        return GraphListBase::consistencyCheck();
    }
    
    
    OGDF_NEW_DELETE
}; // class GraphList<T>


typedef NodeElement *node; 
typedef EdgeElement *edge; 
typedef AdjElement *adjEntry; 




class OGDF_EXPORT AdjElement : private GraphElement {
    friend class Graph;
    friend class GraphListBase;
    friend class GraphList<AdjElement>;

    AdjElement *m_twin; 
    edge m_edge; 
    node m_node; 
    int m_id;    

    AdjElement(node v) : m_node(v) { }
    AdjElement(edge e, int id) : m_edge(e), m_id(id) { }

public:
    edge theEdge() const { return m_edge; }
    operator edge() const { return m_edge; }
    node theNode() const { return m_node; }

    adjEntry twin() const { return m_twin; }

    node twinNode() const { return m_twin->m_node; }

    int index() const { return m_id; }

    // traversing faces in clockwise (resp. counter-clockwise) order
    // (if face is an interior face)
    
    adjEntry clockwiseFaceSucc() const { return m_twin->cyclicPred(); }
    adjEntry clockwiseFacePred() const { return cyclicSucc()->m_twin; }
    adjEntry counterClockwiseFaceSucc() const { return m_twin->cyclicSucc(); }
    adjEntry counterClockwiseFacePred() const { return cyclicPred()->m_twin; }

    // default is traversing faces in clockwise order
    adjEntry faceCycleSucc() const { return clockwiseFaceSucc(); }
    adjEntry faceCyclePred() const { return clockwiseFacePred(); }


    adjEntry succ() const { return (adjEntry)m_next; }
    adjEntry pred() const { return (adjEntry)m_prev; }

    adjEntry cyclicSucc() const;
    adjEntry cyclicPred() const;

#ifdef OGDF_DEBUG
    const Graph *graphOf() const;
#endif

    OGDF_NEW_DELETE
}; // class AdjElement


class OGDF_EXPORT NodeElement : private GraphElement {
    friend class Graph;
    friend class GraphList<NodeElement>;

    GraphList<AdjElement> m_adjEdges; 
    int m_indeg;  
    int m_outdeg; 
    int m_id;     

#ifdef OGDF_DEBUG
    // we store the graph containing this node for debugging purposes
    const Graph *m_pGraph; 
#endif


    // construction
#ifdef OGDF_DEBUG


    NodeElement(const Graph *pGraph, int id) :
        m_indeg(0), m_outdeg(0), m_id(id), m_pGraph(pGraph) { }
#else
    NodeElement(int id) : m_indeg(0), m_outdeg(0), m_id(id) { }
#endif


public:
    int index() const { return m_id; }

    int indeg() const { return m_indeg; }
    int outdeg() const { return m_outdeg; }
    int degree() const { return m_indeg + m_outdeg; }

    adjEntry firstAdj() const { return m_adjEdges.begin();  }
    adjEntry lastAdj () const { return m_adjEdges.rbegin(); }

    node succ() const { return (node)m_next; }
    node pred() const { return (node)m_prev; }

#ifdef OGDF_DEBUG

    const Graph *graphOf() const { return m_pGraph; }
#endif

    OGDF_NEW_DELETE
}; // class NodeElement


inline adjEntry AdjElement::cyclicSucc() const
{
    return (m_next) ? (adjEntry)m_next : m_node->firstAdj();
}

inline adjEntry AdjElement::cyclicPred() const
{
    return (m_prev) ? (adjEntry)m_prev : m_node->lastAdj();
}

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



class OGDF_EXPORT EdgeElement : private GraphElement {
    friend class Graph;
    friend class GraphList<EdgeElement>;

    node m_src; 
    node m_tgt; 
    AdjElement *m_adjSrc; 
    AdjElement *m_adjTgt; 
    int m_id; // The (unique) index of the node.


    EdgeElement(node src, node tgt, AdjElement *adjSrc, AdjElement *adjTgt, int id) :
        m_src(src), m_tgt(tgt), m_adjSrc(adjSrc), m_adjTgt(adjTgt), m_id(id) { }
        

    EdgeElement(node src, node tgt, int id) :
        m_src(src), m_tgt(tgt), m_id(id) { }

public:
    int index() const { return m_id; }
    node source() const { return m_src; }
    node target() const { return m_tgt; }

    adjEntry adjSource() const { return m_adjSrc; }
    adjEntry adjTarget() const { return m_adjTgt; }

    node opposite(node v) const { return (v == m_src) ? m_tgt : m_src; }
    // Returns true iff the edge is a self-loop (source node = target node).
    bool isSelfLoop() const { return m_src == m_tgt; }

    edge succ() const { return (edge)m_next; }
    edge pred() const { return (edge)m_prev; }

#ifdef OGDF_DEBUG

    const Graph *graphOf() const { return m_src->graphOf(); }
#endif

    bool isIncident(node v) const { return v == m_src || v == m_tgt; }
    
    node commonNode(edge e) const { return (m_src==e->m_src || m_src==e->m_tgt) ? m_src : ((m_tgt==e->m_src || m_tgt==e->m_tgt) ? m_tgt: 0); }

    OGDF_NEW_DELETE
}; // class EdgeElement


#ifdef OGDF_DEBUG
inline const Graph *AdjElement::graphOf() const {
    return m_node->graphOf();
}
#endif


template<>inline bool doDestruction<node>(const node *) { return false; }
template<>inline bool doDestruction<edge>(const edge *) { return false; }
template<>inline bool doDestruction<adjEntry>(const adjEntry *) { return false; }

class NodeArrayBase;
class EdgeArrayBase;
class AdjEntryArrayBase;
template<class T> class NodeArray;
template<class T> class EdgeArray;
template<class T> class AdjEntryArray;
class OGDF_EXPORT GraphObserver;


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

#define forall_nodes(v,G) for((v)=(G).firstNode(); (v); (v)=(v)->succ())

#define forall_rev_nodes(v,G) for((v)=(G).lastNode(); (v); (v)=(v)->pred())

#define forall_edges(e,G) for((e)=(G).firstEdge(); (e); (e)=(e)->succ())

#define forall_rev_edges(e,G) for((e)=(G).lastEdge(); (e); (e)=(e)->pred())

#define forall_adj(adj,v) for((adj)=(v)->firstAdj(); (adj); (adj)=(adj)->succ())

#define forall_rev_adj(adj,v) for((adj)=(v)->lastAdj(); (adj); (adj)=(adj)->pred())

#define forall_adj_edges(e,v)\
for(ogdf::adjEntry ogdf_loop_var=(v)->firstAdj();\
    ogdf::test_forall_adj_edges(ogdf_loop_var,(e));\
    ogdf_loop_var=ogdf_loop_var->succ())



class OGDF_EXPORT Graph
{
    GraphList<NodeElement> m_nodes; 
    GraphList<EdgeElement> m_edges; 
    int m_nNodes; 
    int m_nEdges; 

    int m_nodeIdCount; 
    int m_edgeIdCount; 

    int m_nodeArrayTableSize; 
    int m_edgeArrayTableSize; 

    mutable ListPure<NodeArrayBase*> m_regNodeArrays; 
    mutable ListPure<EdgeArrayBase*> m_regEdgeArrays; 
    mutable ListPure<AdjEntryArrayBase*> m_regAdjArrays;  
    mutable ListPure<GraphObserver*> m_regStructures; 

    GraphList<EdgeElement> m_hiddenEdges; 

public:
    //
    // enumerations
    //

    enum EdgeType {
        association = 0,
        generalization = 1,
        dependency = 2
    }; // should be more flexible, standard, dissect, expand
    
    enum NodeType {
        vertex,
        dummy,
        generalizationMerger,
        generalizationExpander,
        highDegreeExpander,
        lowDegreeExpander,
        associationClass
    };


    Graph();
    

    Graph(const Graph &G);
    
    // destruction
    virtual ~Graph();



    bool empty() const { return m_nNodes == 0; }

    int numberOfNodes() const { return m_nNodes; }

    int numberOfEdges() const { return m_nEdges; }

    int maxNodeIndex() const { return m_nodeIdCount-1; }
    int maxEdgeIndex() const { return m_edgeIdCount-1; }
    int maxAdjEntryIndex() const { return (m_edgeIdCount<<1)-1; }

    int nodeArrayTableSize() const { return m_nodeArrayTableSize; }
    int edgeArrayTableSize() const { return m_edgeArrayTableSize; }
    int adjEntryArrayTableSize() const { return m_edgeArrayTableSize << 1; }

    node firstNode() const { return m_nodes.begin (); }
    node lastNode () const { return m_nodes.rbegin(); }
    
    edge firstEdge() const { return m_edges.begin (); }
    edge lastEdge () const { return m_edges.rbegin(); }

    node chooseNode() const;
    edge chooseEdge() const;

    template<class NODELIST>
    void allNodes(NODELIST &nodes) const {
        nodes.clear();
        for (node v = m_nodes.begin(); v; v = v->succ())
            nodes.pushBack(v);
    }

    template<class EDGELIST>
    void allEdges(EDGELIST &edges) const {
        edges.clear();
        for (edge e = m_edges.begin(); e; e = e->succ())
            edges.pushBack(e);
    }

    template<class EDGELIST>
    void adjEdges(node v, EDGELIST &edges) const {
        edges.clear();
        edge e;
        forall_adj_edges(e,v)
            edges.pushBack(e);
    }

    template<class ADJLIST>
    void adjEntries(node v, ADJLIST &entries) const {
        entries.clear();
        adjEntry adj;
        forall_adj(adj,v)
            entries.pushBack(adj);
    }

    template<class EDGELIST>
    void inEdges(node v, EDGELIST &edges) const {
        edges.clear();
        edge e;
        forall_adj_edges(e,v)
            if (e->target() == v) edges.pushBack(e);
    }

    template<class EDGELIST>
    void outEdges(node v, EDGELIST &edges) const {
        edges.clear();
        edge e;
        forall_adj_edges(e,v)
            if (e->source() == v) edges.pushBack(e);
    }




    node newNode();


    node newNode(int index);

    edge newEdge(node v, node w);


    edge newEdge(node v, node w, int index);


    edge newEdge(adjEntry adjSrc, adjEntry adjTgt, Direction dir = ogdf::after);
    

    edge newEdge(node v, adjEntry adjTgt);


    edge newEdge(adjEntry adjSrc, node w);




    void delNode(node v);

    void delEdge(edge e);

    void clear();

    



    void hideEdge(edge e);


    void restoreEdge(edge e);

    void restoreAllEdges();


    

    virtual edge split(edge e);


    void unsplit(node u);


    virtual void unsplit(edge eIn, edge eOut);


    node splitNode(adjEntry adjStartLeft, adjEntry adjStartRight);

    node contract(edge e);

    // moves edge e to adjacency list of owner(adjSrc) inserting it before
    // or after adjSrc, and to owner(adjTgt) inserting it before or after
    // adjTgt; e is afterwards an edge from owner(adjSrc) to owner(adjTgt)
    void move(edge e, adjEntry adjSrc, Direction dirSrc,
        adjEntry adjTgt, Direction dirTgt);


    void moveTarget(edge e, node w);


    void moveTarget(edge e, adjEntry adjTgt, Direction dir);


    void moveSource(edge e, node w);


    void moveSource(edge e, adjEntry adjSrc, Direction dir);
    
    //  If no such edge exists, 0 is returned.
    edge searchEdge (node v, node w) const;

    void reverseEdge(edge e);

    void reverseAllEdges();


    template<class NODELIST>
    void collaps(NODELIST &nodes){
        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)
                    delEdge(e);
                else if (e->source() == w)
                    moveSource(e,v);
                else
                    moveTarget(e,v);
                adj = succ;
            }
            delNode(w);
        }
    }


    template<class ADJ_ENTRY_LIST>
    void sort(node v, const ADJ_ENTRY_LIST &newOrder) {
#ifdef OGDF_DEBUG
        typename ADJ_ENTRY_LIST::const_iterator it;
        for(it = newOrder.begin(); it.valid() ; ++it) {
            OGDF_ASSERT((*it)->theNode() == v);
        }
#endif
        v->m_adjEdges.sort(newOrder);
    }

    void reverseAdjEdges(node v) {
        v->m_adjEdges.reverse();
    }


    void moveAdj(adjEntry adjMove, Direction dir, adjEntry adjPos) {
        OGDF_ASSERT(adjMove->graphOf() == this && adjPos->graphOf() == this);
        OGDF_ASSERT(adjMove != 0 && adjPos != 0);
        GraphList<AdjElement> &adjList = adjMove->m_node->m_adjEdges;
        adjList.move(adjMove, adjList, adjPos, dir);
    }


    void moveAdjAfter(adjEntry adjMove, adjEntry adjAfter) {
        OGDF_ASSERT(adjMove->graphOf() == this && adjAfter->graphOf() == this);
        OGDF_ASSERT(adjMove != 0 && adjAfter != 0);
        adjMove->m_node->m_adjEdges.moveAfter(adjMove,adjAfter);
    }


    void moveAdjBefore(adjEntry adjMove, adjEntry adjBefore) {
        OGDF_ASSERT(adjMove->graphOf() == this && adjBefore->graphOf() == this);
        OGDF_ASSERT(adjMove != 0 && adjBefore != 0);
        adjMove->m_node->m_adjEdges.moveBefore(adjMove,adjBefore);
    }

    void reverseAdjEdges();


    void swapAdjEdges(adjEntry adj1, adjEntry adj2) {
        OGDF_ASSERT(adj1->theNode() == adj2->theNode());
        OGDF_ASSERT(adj1->graphOf() == this);

        adj1->theNode()->m_adjEdges.swap(adj1,adj2);
    }




    bool readGML(const char *fileName);

    bool readGML(istream &is);

    void writeGML(const char *fileName) const;

    void writeGML(ostream &os) const;

    bool readLEDAGraph(const char *fileName);

    bool readLEDAGraph(istream &is);





    int genus() const;

    bool representsCombEmbedding() const {
        return (genus() == 0);
    }


    bool consistencyCheck() const;




    ListIterator<NodeArrayBase*> registerArray(NodeArrayBase *pNodeArray) const;
    ListIterator<EdgeArrayBase*> registerArray(EdgeArrayBase *pEdgeArray) const;
    ListIterator<AdjEntryArrayBase*> registerArray(AdjEntryArrayBase *pAdjArray) const;
    ListIterator<GraphObserver*> registerStructure(GraphObserver *pStructure) const;

    void unregisterArray(ListIterator<NodeArrayBase*> it) const;
    void unregisterArray(ListIterator<EdgeArrayBase*> it) const;
    void unregisterArray(ListIterator<AdjEntryArrayBase*> it) const;
    void unregisterStructure(ListIterator<GraphObserver*> it) const;



    void resetEdgeIdCount(int maxId);





    Graph &operator=(const Graph &G);

    OGDF_MALLOC_NEW_DELETE


public:

    static int nextPower2(int start, int idCount);


protected:
    void construct(const Graph &G, NodeArray<node> &mapNode,
        EdgeArray<edge> &mapEdge);

    void assign(const Graph &G, NodeArray<node> &mapNode,
        EdgeArray<edge> &mapEdge);

    void constructInitByNodes(
        const Graph &G,
        const List<node> &nodes,
        NodeArray<node> &mapNode,
        EdgeArray<edge> &mapEdge);

    void constructInitByActiveNodes(
        const List<node> &nodes,
        const NodeArray<bool> &activeNodes,
        NodeArray<node> &mapNode,
        EdgeArray<edge> &mapEdge);

private:
    void copy(const Graph &G, NodeArray<node> &mapNode,
        EdgeArray<edge> &mapEdge);
    void copy(const Graph &G);

    edge createEdgeElement(node v, node w, adjEntry adjSrc, adjEntry adjTgt);
    node pureNewNode();

    // moves adjacency entry to node w
    void moveAdj(adjEntry adj, node w);

    void reinitArrays();
    void reinitStructures();
    void resetAdjEntryIndex(int newIndex, int oldIndex);

    bool readToEndOfLine(istream &is);
}; // class Graph



class OGDF_EXPORT BucketSourceIndex : public BucketFunc<edge> {
public:
    int getBucket(const edge &e) { return e->source()->index(); }
};

class OGDF_EXPORT BucketTargetIndex : public BucketFunc<edge> {
public:
    int getBucket(const edge &e) { return e->target()->index(); }
};


} //namespace 

#endif