ConnectedSubgraph.h

Go to the documentation of this file.

 
#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
}
 
}
}