extended_graph_alg.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/DisjointSets.h>
#include <ogdf/basic/PriorityQueue.h>
#include <ogdf/cluster/ClusterGraph.h>
#include <ogdf/planarity/BoyerMyrvold.h>
 
namespace ogdf {
 
 
 
template<class LISTITERATOR>
void inducedSubGraph(const Graph& G, LISTITERATOR start, Graph& subGraph) {
    NodeArray<node> nodeTableOrig2New;
    inducedSubGraph(G, start, subGraph, nodeTableOrig2New);
}
 
 
template<class LISTITERATOR>
void inducedSubGraph(const Graph& G, LISTITERATOR start, Graph& subGraph,
        NodeArray<node>& nodeTableOrig2New) {
    subGraph.clear();
    nodeTableOrig2New.init(G, nullptr);
 
    EdgeArray<bool> mark(G, false);
 
    LISTITERATOR its;
    for (its = start; its.valid(); its++) {
        node w = (*its);
        OGDF_ASSERT(w != nullptr);
        OGDF_ASSERT(w->graphOf() == &G);
        nodeTableOrig2New[w] = subGraph.newNode();
 
        for (adjEntry adj : w->adjEntries) {
            edge e = adj->theEdge();
            if (nodeTableOrig2New[e->source()] && nodeTableOrig2New[e->target()] && !mark[e]) {
                subGraph.newEdge(nodeTableOrig2New[e->source()], nodeTableOrig2New[e->target()]);
                mark[e] = true;
            }
        }
    }
}
 
 
template<class LISTITERATOR>
void inducedSubGraph(const Graph& G, LISTITERATOR start, Graph& subGraph,
        NodeArray<node>& nodeTableOrig2New, EdgeArray<edge>& edgeTableOrig2New) {
    subGraph.clear();
    nodeTableOrig2New.init(G, nullptr);
    edgeTableOrig2New.init(G, nullptr);
 
    EdgeArray<bool> mark(G, false);
 
    LISTITERATOR its;
    for (its = start; its.valid(); its++) {
        node w = (*its);
        OGDF_ASSERT(w != nullptr);
        OGDF_ASSERT(w->graphOf() == &G);
        nodeTableOrig2New[w] = subGraph.newNode();
 
        for (adjEntry adj : w->adjEntries) {
            edge e = adj->theEdge();
            if (nodeTableOrig2New[e->source()] && nodeTableOrig2New[e->target()] && !mark[e]) {
                edgeTableOrig2New[e] = subGraph.newEdge(nodeTableOrig2New[e->source()],
                        nodeTableOrig2New[e->target()]);
                mark[e] = true;
            }
        }
    }
}
 
 
template<class LISTITERATOR>
void inducedSubGraph(const Graph& G, LISTITERATOR start, GraphCopySimple& subGraph) {
    subGraph.clear();
    subGraph.createEmpty(G);
    EdgeArray<bool> mark(G, false);
 
    LISTITERATOR its;
    for (its = start; its.valid(); its++) {
        node w = (*its);
        OGDF_ASSERT(w != nullptr);
        OGDF_ASSERT(w->graphOf() == &G);
        subGraph.newNode(w);
 
        for (adjEntry adj : w->adjEntries) {
            edge e = adj->theEdge();
            if (subGraph.copy(e->source()) && subGraph.copy(e->target()) && !subGraph.copy(e)) {
                subGraph.newEdge(e);
            }
        }
    }
}
 
 
template<class NODELISTITERATOR, class EDGELIST>
void inducedSubgraph(Graph& G, NODELISTITERATOR& it, EDGELIST& E) {
    NODELISTITERATOR itBegin = it;
    NodeArray<bool> mark(G, false);
 
    for (; it.valid(); it++) {
        mark[*it] = true;
    }
    it = itBegin;
    for (; it.valid(); it++) {
        node v = (*it);
        for (adjEntry adj : v->adjEntries) {
            edge e = adj->theEdge();
            if (mark[e->source()] && mark[e->target()]) {
                E.pushBack(e);
            }
        }
    }
}
 
 
 
OGDF_EXPORT bool isCConnected(const ClusterGraph& C);
 
 
OGDF_EXPORT void makeCConnected(ClusterGraph& C, Graph& G, List<edge>& addedEdges,
        bool simple = true);
 
 
 
template<typename T>
inline T computeMinST(const Graph& G, const EdgeArray<T>& weight, EdgeArray<bool>& isInTree) {
    NodeArray<edge> pred(G, nullptr);
    return computeMinST(G.firstNode(), G, weight, pred, isInTree);
}
 
 
template<typename T>
inline T computeMinST(const Graph& G, const EdgeArray<T>& weight, NodeArray<edge>& pred,
        EdgeArray<bool>& isInTree) {
    return computeMinST(G.firstNode(), G, weight, pred, isInTree);
}
 
 
template<typename T>
inline void computeMinST(const Graph& G, const EdgeArray<T>& weight, NodeArray<edge>& pred) {
    computeMinST(G.firstNode(), G, weight, pred);
}
 
 
template<typename T>
void computeMinST(node s, const Graph& G, const EdgeArray<T>& weight, NodeArray<edge>& pred) {
    PrioritizedMapQueue<node, T> pq(G); // priority queue of front vertices
 
    // insert start node
    T tmp(0);
    pq.push(s, tmp);
 
    // extract the nodes again along a minimum ST
    NodeArray<bool> processed(G, false);
    pred.init(G, nullptr);
 
    while (!pq.empty()) {
        const node v = pq.topElement();
        pq.pop();
        processed[v] = true;
        for (adjEntry adj = v->firstAdj(); adj; adj = adj->succ()) {
            const node w = adj->twinNode();
            const edge e = adj->theEdge();
            if (pred[w] == nullptr && w != s) {
                tmp = weight[e];
                pq.push(w, tmp);
                pred[w] = e;
            } else if (!processed[w] && weight[e] < pq.priority(w)) {
                pq.decrease(w, weight[e]);
                pred[w] = e;
            }
        }
    }
}
 
 
template<typename T>
T computeMinST(node s, const Graph& G, const EdgeArray<T>& weight, NodeArray<edge>& pred,
        EdgeArray<bool>& isInTree) {
    computeMinST(s, G, weight, pred);
 
    // now just compute isInTree and total weight
#ifdef OGDF_DEBUG
    int rootcount = 0;
#endif
    T treeWeight = 0;
    isInTree.init(G, false);
    for (node v = G.firstNode(); v; v = v->succ()) {
        if (pred[v]) {
            isInTree[pred[v]] = true;
            treeWeight += weight[pred[v]];
        }
#ifdef OGDF_DEBUG
        else {
            ++rootcount;
        }
#endif
    }
    OGDF_ASSERT(rootcount == 1); // is connected
 
    return treeWeight;
}
 
 
template<typename T>
T makeMinimumSpanningTree(Graph& G, const EdgeArray<T>& weight) {
    T total(0);
    Array<Prioritized<edge, T>> sortEdges(G.numberOfEdges());
    int i = 0;
    for (edge e : G.edges) {
        sortEdges[i++] = Prioritized<edge, T>(e, weight[e]);
    }
    sortEdges.quicksort();
 
    // now let's do Kruskal's algorithm
    NodeArray<int> setID(G);
    DisjointSets<> uf(G.numberOfNodes());
    for (node v : G.nodes) {
        setID[v] = uf.makeSet();
    }
 
    for (auto prioEdge : sortEdges) {
        const edge e = prioEdge.item();
        const int v = setID[e->source()];
        const int w = setID[e->target()];
        if (uf.find(v) != uf.find(w)) {
            uf.link(uf.find(v), uf.find(w));
            total += weight[e];
        } else {
            G.delEdge(e);
        }
    }
    return total;
}
 
 
 
inline bool isPlanar(const Graph& G) { return BoyerMyrvold().isPlanar(G); }
 
inline bool isSTPlanar(const Graph& graph, const node s, const node t) {
    OGDF_ASSERT(s != nullptr);
    OGDF_ASSERT(t != nullptr);
    OGDF_ASSERT(s->graphOf() == &graph);
    OGDF_ASSERT(t->graphOf() == &graph);
 
    GraphCopy copy(graph);
    copy.newEdge(copy.copy(s), copy.copy(t));
 
    return isPlanar(copy);
}
 
 
inline bool planarEmbed(Graph& G) { return BoyerMyrvold().planarEmbed(G); }
 
inline bool planarSTEmbed(Graph& graph, node s, node t) {
    edge e = graph.newEdge(s, t);
    bool result = planarEmbed(graph);
    graph.delEdge(e);
 
    return result;
}
 
 
inline bool planarEmbedPlanarGraph(Graph& G) { return BoyerMyrvold().planarEmbedPlanarGraph(G); }
 
}