Open
Graph Drawing
Framework

#pragma once


#include <ogdf/basic/Graph.h>

#include <ogdf/basic/GraphList.h>


namespace ogdf {


namespace embedder {


template<class T>


class ConnectedSubgraph {

public:

    //constructor

    ConnectedSubgraph() { }


    static void call(const Graph& G, Graph& SG, const node& nG, node& nSG,

            const NodeArray<T>& nodeLengthG, NodeArray<T>& nodeLengthSG) {

        EdgeArray<T> edgeLengthG(G, 1);

        EdgeArray<T> edgeLengthSG;

        call(G, SG, nG, nSG, nodeLengthG, nodeLengthSG, edgeLengthG, edgeLengthSG);

    }


    static void call(const Graph& G, Graph& SG, const node& nG, const NodeArray<T>& nodeLengthG,

            NodeArray<T>& nodeLengthSG, NodeArray<node>& nG_to_nSG) {

        node nSG;

        NodeArray<node> nSG_to_nG;

        EdgeArray<edge> eSG_to_eG;

        EdgeArray<edge> eG_to_eSG;

        EdgeArray<T> edgeLengthG(G, 1);

        EdgeArray<T> edgeLengthSG;

        call(G, SG, nG, nSG, nSG_to_nG, eSG_to_eG, nG_to_nSG, eG_to_eSG, nodeLengthG, nodeLengthSG,

                edgeLengthG, edgeLengthSG);

    }


    static void call(const Graph& G, Graph& SG, const node& nG, node& nSG,

            const NodeArray<T>& nodeLengthG, NodeArray<T>& nodeLengthSG,

            const EdgeArray<T>& edgeLengthG, EdgeArray<T>& edgeLengthSG) {

        NodeArray<node> nSG_to_nG(SG);

        EdgeArray<edge> eSG_to_eG(SG);

        call(G, SG, nG, nSG, nSG_to_nG, eSG_to_eG, nodeLengthG, nodeLengthSG, edgeLengthG,

                edgeLengthSG);

    }


    static void call(const Graph& G, Graph& SG, const node& nG, const NodeArray<T>& nodeLengthG,

            NodeArray<T>& nodeLengthSG) {

        node nSG;

        call(G, SG, nG, nSG, nodeLengthG, nodeLengthSG);

    }


    static void call(const Graph& G, Graph& SG, const node& nG, const NodeArray<T>& nodeLengthG,

            NodeArray<T>& nodeLengthSG, const EdgeArray<T>& edgeLengthG, EdgeArray<T>& edgeLengthSG) {

        node nSG = nullptr;

        call(G, SG, nG, nSG, nodeLengthG, nodeLengthSG, edgeLengthG, edgeLengthSG);

    }


    static void call(const Graph& G, Graph& SG, const node& nG, node& nSG,

            NodeArray<node>& nSG_to_nG, EdgeArray<edge>& eSG_to_eG, const NodeArray<T>& nodeLengthG,

            NodeArray<T>& nodeLengthSG, const EdgeArray<T>& edgeLengthG, EdgeArray<T>& edgeLengthSG) {

        NodeArray<node> nG_to_nSG;

        EdgeArray<edge> eG_to_eSG;

        call(G, SG, nG, nSG, nSG_to_nG, eSG_to_eG, nG_to_nSG, eG_to_eSG, nodeLengthG, nodeLengthSG,

                edgeLengthG, edgeLengthSG);

    }


    static void call(const Graph& G, Graph& SG, const node& nG, node& nSG,

            NodeArray<node>& nSG_to_nG, EdgeArray<edge>& eSG_to_eG, NodeArray<node>& nG_to_nSG,

            EdgeArray<edge>& eG_to_eSG, const NodeArray<T>& nodeLengthG, NodeArray<T>& nodeLengthSG,

            const EdgeArray<T>& edgeLengthG, EdgeArray<T>& edgeLengthSG);


    static void call(const Graph& G, Graph& SG, const node& nG, NodeArray<node>& nSG_to_nG,

            EdgeArray<edge>& eSG_to_eG, NodeArray<node>& nG_to_nSG, EdgeArray<edge>& eG_to_eSG);


    static void call(const Graph& G, Graph& SG, const node& nG, NodeArray<node>& nSG_to_nG) {

        NodeArray<T> nodeLengthG(G, 0);

        NodeArray<T> nodeLengthSG(SG);

        EdgeArray<T> edgeLengthG(G, 0);

        EdgeArray<T> edgeLengthSG(SG);

        node nSG;

        EdgeArray<edge> eSG_to_eG;

        call(G, SG, nG, nSG, nSG_to_nG, eSG_to_eG, nodeLengthG, nodeLengthSG, edgeLengthG,

                edgeLengthSG);

    }


private:

    static void recursion(Graph& SG, NodeArray<bool>& nodeVisited, EdgeArray<bool>& edgeVisited,

            const node& nG, const NodeArray<T>& nodeLengthG, NodeArray<T>& nodeLengthSG,

            const EdgeArray<T>& edgeLengthG, EdgeArray<T>& edgeLengthSG, NodeArray<node>& nSG_to_nG,

            EdgeArray<edge>& eSG_to_eG, NodeArray<node>& nG_to_nSG, EdgeArray<edge>& eG_to_eSG);

};


template<class T>


void ConnectedSubgraph<T>::recursion(Graph& SG, NodeArray<bool>& nodeVisited,

        EdgeArray<bool>& edgeVisited, const node& nG, const NodeArray<T>& nodeLengthG,

        NodeArray<T>& nodeLengthSG, const EdgeArray<T>& edgeLengthG, EdgeArray<T>& edgeLengthSG,

        NodeArray<node>& nSG_to_nG, EdgeArray<edge>& eSG_to_eG, NodeArray<node>& nG_to_nSG,

        EdgeArray<edge>& eG_to_eSG) {

    node nSG = SG.newNode();

    nodeLengthSG[nSG] = nodeLengthG[nG];

    nG_to_nSG[nG] = nSG;

    nSG_to_nG[nSG] = nG;

    nodeVisited[nG] = true;


    for (adjEntry adj : nG->adjEntries) {

        edge eG = adj->theEdge();

        if (!nodeVisited[eG->source()]) {

            recursion(SG, nodeVisited, edgeVisited, eG->source(), nodeLengthG, nodeLengthSG,

                    edgeLengthG, edgeLengthSG, nSG_to_nG, eSG_to_eG, nG_to_nSG, eG_to_eSG);

        } else if (!nodeVisited[eG->target()]) {

            recursion(SG, nodeVisited, edgeVisited, eG->target(), nodeLengthG, nodeLengthSG,

                    edgeLengthG, edgeLengthSG, nSG_to_nG, eSG_to_eG, nG_to_nSG, eG_to_eSG);

        }

        if (!edgeVisited[eG]) {

            edge eSG = SG.newEdge(nG_to_nSG[eG->source()], nG_to_nSG[eG->target()]);

            edgeLengthSG[eSG] = edgeLengthG[eG];

            eG_to_eSG[eG] = eSG;

            eSG_to_eG[eSG] = eG;

            edgeVisited[eG] = true;

        }

    }

}


template<class T>


void ConnectedSubgraph<T>::call(const Graph& G, Graph& SG, const node& nG, node& nSG,

        NodeArray<node>& nSG_to_nG, EdgeArray<edge>& eSG_to_eG, NodeArray<node>& nG_to_nSG,

        EdgeArray<edge>& eG_to_eSG, const NodeArray<T>& nodeLengthG, NodeArray<T>& nodeLengthSG,

        const EdgeArray<T>& edgeLengthG, EdgeArray<T>& edgeLengthSG) {

    SG.clear();


    NodeArray<bool> nodeVisited(G, false);

    EdgeArray<bool> edgeVisited(G, false);


#if 0

    const int n = G.numberOfNodes();

    const int m = G.numberOfEdges();


    bool* nodeVisited = new bool[n];

    bool* edgeVisited = new bool[m];

    for (int i = 0; i < n; i++)

        nodeVisited[i] = false;

    for (int i = 0; i < m; i++)

        edgeVisited[i] = false;

#endif

    nSG_to_nG.init(SG);

    eSG_to_eG.init(SG);

    nodeLengthSG.init(SG);

    edgeLengthSG.init(SG);

    nG_to_nSG.init(G);

    eG_to_eSG.init(G);


    recursion(SG, nodeVisited, edgeVisited, nG, nodeLengthG, nodeLengthSG, edgeLengthG,

            edgeLengthSG, nSG_to_nG, eSG_to_eG, nG_to_nSG, eG_to_eSG);

    nSG = nG_to_nSG[nG];


#if 0

    delete[] nodeVisited;

    delete[] edgeVisited;

#endif

}


template<class T>


void ConnectedSubgraph<T>::call(const Graph& G, Graph& SG, const node& nG, NodeArray<node>& nSG_to_nG,

        EdgeArray<edge>& eSG_to_eG, NodeArray<node>& nG_to_nSG, EdgeArray<edge>& eG_to_eSG) {

    SG.clear();


    NodeArray<bool> nodeVisited(G, false);

    EdgeArray<bool> edgeVisited(G, false);


#if 0

    bool* nodeVisited = new bool[G.numberOfNodes()];

    bool* edgeVisited = new bool[G.numberOfEdges()];

    for (int i = 0; i < G.numberOfNodes(); i++)

        nodeVisited[i] = false;

    for (int i = 0; i < G.numberOfEdges(); i++)

        edgeVisited[i] = false;

#endif

    nSG_to_nG.init(SG);

    eSG_to_eG.init(SG);

    NodeArray<T> nodeLengthG(G, 0);

    NodeArray<T> nodeLengthSG(SG);

    EdgeArray<T> edgeLengthG(G, 1);

    EdgeArray<T> edgeLengthSG(SG);

    nG_to_nSG.init(G);

    eG_to_eSG.init(G);


    recursion(SG, nodeVisited, edgeVisited, nG, nodeLengthG, nodeLengthSG, edgeLengthG,

            edgeLengthSG, nSG_to_nG, eSG_to_eG, nG_to_nSG, eG_to_eSG);


#if 0

    delete[] nodeVisited;

    delete[] edgeVisited;

#endif

}


}


}

Graph.h
Includes declaration of graph class.

GraphList.h
Decralation of GraphElement and GraphList classes.

ogdf::AdjElement
Class for adjacency list elements.
Definition Graph_d.h:143

ogdf::EdgeElement
Class for the representation of edges.
Definition Graph_d.h:364

ogdf::EdgeElement::target
node target() const
Returns the target node of the edge.
Definition Graph_d.h:402

ogdf::EdgeElement::source
node source() const
Returns the source node of the edge.
Definition Graph_d.h:399

ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:866

ogdf::Graph::clear
virtual void clear()
Removes all nodes and all edges from the graph.

ogdf::Graph::newNode
node newNode(int index=-1)
Creates a new node and returns it.
Definition Graph_d.h:1061

ogdf::Graph::newEdge
edge newEdge(node v, node w, int index=-1)
Creates a new edge (v,w) and returns it.
Definition Graph_d.h:1080

ogdf::NodeElement
Class for the representation of nodes.
Definition Graph_d.h:241

ogdf::NodeElement::adjEntries
internal::GraphObjectContainer< AdjElement > adjEntries
The container containing all entries in the adjacency list of this node.
Definition Graph_d.h:272

ogdf::RegisteredArray::init
void init(const Base *base=nullptr)
Reinitializes the array. Associates the array with the matching registry of base.
Definition RegisteredArray.h:910

ogdf::embedder::ConnectedSubgraph
Definition ConnectedSubgraph.h:41

ogdf::embedder::ConnectedSubgraph::call
static void call(const Graph &G, Graph &SG, const node &nG, node &nSG, const NodeArray< T > &nodeLengthG, NodeArray< T > &nodeLengthSG, const EdgeArray< T > &edgeLengthG, EdgeArray< T > &edgeLengthSG)
Computes a connected subgraph SG of G containing node nG.
Definition ConnectedSubgraph.h:94

ogdf::embedder::ConnectedSubgraph::recursion
static void recursion(Graph &SG, NodeArray< bool > &nodeVisited, EdgeArray< bool > &edgeVisited, const node &nG, const NodeArray< T > &nodeLengthG, NodeArray< T > &nodeLengthSG, const EdgeArray< T > &edgeLengthG, EdgeArray< T > &edgeLengthSG, NodeArray< node > &nSG_to_nG, EdgeArray< edge > &eSG_to_eG, NodeArray< node > &nG_to_nSG, EdgeArray< edge > &eG_to_eSG)
Copies to SG node nG and recursively all adjacent edges and nodes.
Definition ConnectedSubgraph.h:233

ogdf::embedder::ConnectedSubgraph::call
static void call(const Graph &G, Graph &SG, const node &nG, const NodeArray< T > &nodeLengthG, NodeArray< T > &nodeLengthSG, const EdgeArray< T > &edgeLengthG, EdgeArray< T > &edgeLengthSG)
Computes a connected subgraph SG of G containing node nG.
Definition ConnectedSubgraph.h:127

ogdf::embedder::ConnectedSubgraph::ConnectedSubgraph
ConnectedSubgraph()
Definition ConnectedSubgraph.h:44

ogdf::embedder::ConnectedSubgraph::call
static void call(const Graph &G, Graph &SG, const node &nG, const NodeArray< T > &nodeLengthG, NodeArray< T > &nodeLengthSG)
Computes a connected subgraph SG of G containing node nG.
Definition ConnectedSubgraph.h:111

ogdf::embedder::ConnectedSubgraph::call
static void call(const Graph &G, Graph &SG, const node &nG, node &nSG, NodeArray< node > &nSG_to_nG, EdgeArray< edge > &eSG_to_eG, const NodeArray< T > &nodeLengthG, NodeArray< T > &nodeLengthSG, const EdgeArray< T > &edgeLengthG, EdgeArray< T > &edgeLengthSG)
Computes a connected subgraph SG of G containing node nG.
Definition ConnectedSubgraph.h:146

ogdf::embedder::ConnectedSubgraph::call
static void call(const Graph &G, Graph &SG, const node &nG, NodeArray< node > &nSG_to_nG)
Computes a connected subgraph SG of G containing node nG.
Definition ConnectedSubgraph.h:195

ogdf::embedder::ConnectedSubgraph::call
static void call(const Graph &G, Graph &SG, const node &nG, const NodeArray< T > &nodeLengthG, NodeArray< T > &nodeLengthSG, NodeArray< node > &nG_to_nSG)
Computes a connected subgraph SG of G containing node nG.
Definition ConnectedSubgraph.h:71

ogdf::embedder::ConnectedSubgraph::call
static void call(const Graph &G, Graph &SG, const node &nG, node &nSG, const NodeArray< T > &nodeLengthG, NodeArray< T > &nodeLengthSG)
Computes a connected subgraph SG of G containing node nG.
Definition ConnectedSubgraph.h:55

ogdf::internal::EdgeArrayBase2
RegisteredArray for edges of a graph, specialized for EdgeArray<edge>.
Definition Graph_d.h:717

ogdf::internal::GraphRegisteredArray
RegisteredArray for nodes, edges and adjEntries of a graph.
Definition Graph_d.h:659

ogdf
The namespace for all OGDF objects.
Definition multilevelmixer.cpp:39