simple_graph_alg.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/ArrayBuffer.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/internal/graph_iterators.h>
#include <ogdf/basic/internal/list_templates.h>
#include <ogdf/basic/tuples.h>
 
#include <functional>
 
namespace ogdf {
 
 
OGDF_EXPORT void removeSelfLoops(Graph& graph, node v);
 
 
OGDF_EXPORT bool isLoopFree(const Graph& G);
 
 
template<class NODELIST>
void makeLoopFree(Graph& G, NODELIST& L) {
    L.clear();
 
    safeForEach(G.edges, [&](edge e) {
        if (e->isSelfLoop()) {
            L.pushBack(e->source());
            G.delEdge(e);
        }
    });
}
 
OGDF_EXPORT bool hasNonSelfLoopEdges(const Graph& G);
 
 
OGDF_EXPORT void makeLoopFree(Graph& G);
 
 
 
 
OGDF_EXPORT void parallelFreeSort(const Graph& G, SListPure<edge>& edges);
 
 
 
OGDF_EXPORT bool isParallelFree(const Graph& G);
 
 
template<bool ONLY_ONCE = false>
int numParallelEdges(const Graph& G) {
    if (G.numberOfEdges() <= 1) {
        return 0;
    }
 
    SListPure<edge> edges;
    parallelFreeSort(G, edges);
 
    int num = 0;
    SListConstIterator<edge> it = edges.begin();
    edge ePrev = *it, e;
    for (it = ++it; it.valid(); ++it, ePrev = e) {
        e = *it;
        if (ePrev->isParallelDirected(e)) {
            ++num;
            if (ONLY_ONCE) {
                return num;
            }
        }
    }
 
    return num;
}
 
 
template<class EDGELIST>
void makeParallelFree(Graph& G, EDGELIST& parallelEdges) {
    parallelEdges.clear();
    if (G.numberOfEdges() <= 1) {
        return;
    }
 
    SListPure<edge> edges;
    parallelFreeSort(G, edges);
 
    SListConstIterator<edge> it = edges.begin();
    edge ePrev = *it++, e;
    bool bAppend = true;
    while (it.valid()) {
        e = *it++;
        if (e->isParallelDirected(ePrev)) {
            G.delEdge(e);
            if (bAppend) {
                parallelEdges.pushBack(ePrev);
                bAppend = false;
            }
        } else {
            ePrev = e;
            bAppend = true;
        }
    }
}
 
 
inline void makeParallelFree(Graph& G) {
    List<edge> parallelEdges;
    makeParallelFree(G, parallelEdges);
}
 
 
OGDF_EXPORT void parallelFreeSortUndirected(const Graph& G, SListPure<edge>& edges,
        EdgeArray<int>& minIndex, EdgeArray<int>& maxIndex);
 
 
 
OGDF_EXPORT bool isParallelFreeUndirected(const Graph& G);
 
 
template<bool ONLY_ONCE = false>
int numParallelEdgesUndirected(const Graph& G) {
    if (G.numberOfEdges() <= 1) {
        return 0;
    }
 
    SListPure<edge> edges;
    EdgeArray<int> minIndex(G), maxIndex(G);
    parallelFreeSortUndirected(G, edges, minIndex, maxIndex);
 
    int num = 0;
    SListConstIterator<edge> it = edges.begin();
    edge ePrev = *it, e;
    for (it = ++it; it.valid(); ++it, ePrev = e) {
        e = *it;
        if (minIndex[ePrev] == minIndex[e] && maxIndex[ePrev] == maxIndex[e]) {
            ++num;
            if (ONLY_ONCE) {
                return num;
            }
        }
    }
 
    return num;
}
 
 
template<class EDGELIST>
void getParallelFreeUndirected(const Graph& G, EdgeArray<EDGELIST>& parallelEdges) {
    if (G.numberOfEdges() <= 1) {
        return;
    }
 
    SListPure<edge> edges;
    EdgeArray<int> minIndex(G), maxIndex(G);
    parallelFreeSortUndirected(G, edges, minIndex, maxIndex);
 
    SListConstIterator<edge> it = edges.begin();
    edge ePrev = *it++, e;
    while (it.valid()) {
        e = *it++;
        if (minIndex[ePrev] == minIndex[e] && maxIndex[ePrev] == maxIndex[e]) {
            parallelEdges[ePrev].pushBack(e);
        } else {
            ePrev = e;
        }
    }
}
 
 
template<class EDGELIST = SListPure<edge>>
void makeParallelFreeUndirected(Graph& G, EDGELIST* parallelEdges = nullptr,
        EdgeArray<int>* cardPositive = nullptr, EdgeArray<int>* cardNegative = nullptr) {
    if (parallelEdges != nullptr) {
        parallelEdges->clear();
    }
    if (cardPositive != nullptr) {
        cardPositive->fill(0);
    }
    if (cardNegative != nullptr) {
        cardNegative->fill(0);
    }
 
    if (G.numberOfEdges() <= 1) {
        return;
    }
 
    EdgeArray<SListPure<edge>> parEdges(G);
    getParallelFreeUndirected(G, parEdges);
 
    for (edge e : G.edges) {
        for (edge parEdge : parEdges(e)) {
            if (cardPositive != nullptr && e->source() == parEdge->source()) {
                (*cardPositive)[e]++;
            }
            if (cardNegative != nullptr && e->source() == parEdge->target()) {
                (*cardNegative)[e]++;
            }
            G.delEdge(parEdge);
            if (parallelEdges != nullptr) {
                parallelEdges->pushBack(e);
            }
        }
    }
}
 
template<class EDGELIST>
OGDF_DEPRECATED("The pointer-based makeParallelFreeUndirected() should be used instead.")
void makeParallelFreeUndirected(Graph& G, EDGELIST& parallelEdges) {
    makeParallelFreeUndirected(G, &parallelEdges);
}
 
template<class EDGELIST>
OGDF_DEPRECATED("The pointer-based makeParallelFreeUndirected() should be used instead.")
void makeParallelFreeUndirected(Graph& G, EDGELIST& parallelEdges, EdgeArray<int>& cardPositive,
        EdgeArray<int>& cardNegative) {
    makeParallelFreeUndirected(G, &parallelEdges, &cardPositive, &cardNegative);
}
 
 
 
inline bool isSimple(const Graph& G) { return isLoopFree(G) && isParallelFree(G); }
 
 
inline void makeSimple(Graph& G) {
    makeLoopFree(G);
    makeParallelFree(G);
}
 
 
inline bool isSimpleUndirected(const Graph& G) {
    return isLoopFree(G) && isParallelFreeUndirected(G);
}
 
 
inline void makeSimpleUndirected(Graph& G) {
    makeLoopFree(G);
    makeParallelFreeUndirected(G);
}
 
 
 
OGDF_EXPORT bool isConnected(const Graph& G);
 
 
 
OGDF_EXPORT void makeConnected(Graph& G, List<edge>& added);
 
 
inline void makeConnected(Graph& G) {
    List<edge> added;
    makeConnected(G, added);
}
 
 
OGDF_EXPORT int connectedComponents(const Graph& G, NodeArray<int>& component,
        List<node>* isolated = nullptr, ArrayBuffer<node>* reprs = nullptr);
 
 
inline int connectedComponents(const Graph& G) {
    NodeArray<int> component(G);
    return connectedComponents(G, component);
}
 
 
OGDF_DEPRECATED("connectedComponents() should be used instead.")
 
 
inline int connectedIsolatedComponents(const Graph& G, List<node>& isolated,
        NodeArray<int>& component) {
    return connectedComponents(G, component, &isolated);
}
 
OGDF_EXPORT bool findCutVertices(const Graph& G, ArrayBuffer<node>& cutVertices,
        ArrayBuffer<Tuple2<node, node>>& addEdges, bool onlyOne = false);
 
 
inline bool findCutVertices(const Graph& G, ArrayBuffer<node>& cutVertices, bool onlyOne = false) {
    ArrayBuffer<Tuple2<node, node>> addEdges;
    return findCutVertices(G, cutVertices, addEdges, onlyOne);
}
 
 
OGDF_EXPORT bool isBiconnected(const Graph& G, node& cutVertex);
 
 
inline bool isBiconnected(const Graph& G) {
    node cutVertex;
    return isBiconnected(G, cutVertex);
}
 
 
OGDF_EXPORT void makeBiconnected(Graph& G, List<edge>& added);
 
 
inline void makeBiconnected(Graph& G) {
    List<edge> added;
    makeBiconnected(G, added);
}
 
OGDF_EXPORT int biconnectedComponents(const Graph& G, EdgeArray<int>& component,
        int& nonEmptyComponents);
 
 
inline int biconnectedComponents(const Graph& G, EdgeArray<int>& component) {
    int doNotNeedTheValue;
    return biconnectedComponents(G, component, doNotNeedTheValue);
}
 
OGDF_EXPORT bool isTwoEdgeConnected(const Graph& graph, edge& bridge);
 
inline bool isTwoEdgeConnected(const Graph& graph) {
    edge bridge;
    return isTwoEdgeConnected(graph, bridge);
}
 
 
OGDF_EXPORT bool isTriconnected(const Graph& G, node& s1, node& s2);
 
 
inline bool isTriconnected(const Graph& G) {
    node s1, s2;
    return isTriconnected(G, s1, s2);
}
 
 
OGDF_EXPORT bool isTriconnectedPrimitive(const Graph& G, node& s1, node& s2);
 
 
inline bool isTriconnectedPrimitive(const Graph& G) {
    node s1, s2;
    return isTriconnectedPrimitive(G, s1, s2);
}
 
 
OGDF_EXPORT void triangulate(Graph& G);
 
 
 
 
OGDF_EXPORT bool isAcyclic(const Graph& G, List<edge>& backedges);
 
 
inline bool isAcyclic(const Graph& G) {
    List<edge> backedges;
    return isAcyclic(G, backedges);
}
 
 
OGDF_EXPORT bool isAcyclicUndirected(const Graph& G, List<edge>& backedges);
 
 
inline bool isAcyclicUndirected(const Graph& G) {
    List<edge> backedges;
    return isAcyclicUndirected(G, backedges);
}
 
 
OGDF_EXPORT void makeAcyclic(Graph& G);
 
 
 
OGDF_EXPORT void makeAcyclicByReverse(Graph& G);
 
 
 
OGDF_EXPORT bool hasSingleSource(const Graph& G, node& source);
 
 
inline bool hasSingleSource(const Graph& G) {
    node source;
    return hasSingleSource(G, source);
}
 
 
OGDF_EXPORT bool hasSingleSink(const Graph& G, node& sink);
 
 
inline bool hasSingleSink(const Graph& G) {
    node sink;
    return hasSingleSink(G, sink);
}
 
 
OGDF_EXPORT bool isStGraph(const Graph& G, node& s, node& t, edge& st);
 
 
inline bool isStGraph(const Graph& G) {
    node s, t;
    edge st;
    return isStGraph(G, s, t, st);
}
 
 
OGDF_EXPORT void topologicalNumbering(const Graph& G, NodeArray<int>& num);
 
 
 
OGDF_EXPORT int strongComponents(const Graph& G, NodeArray<int>& component);
 
 
 
OGDF_EXPORT void makeBimodal(Graph& G, List<edge>& newEdges);
 
 
inline void makeBimodal(Graph& G) {
    List<edge> dummy;
    makeBimodal(G, dummy);
}
 
 
 
OGDF_DEPRECATED("isAcyclicUndirected() should be used instead.")
 
 
inline bool isFreeForest(const Graph& G) { return isAcyclicUndirected(G); }
 
 
inline bool isTree(const Graph& G) {
    return G.empty() || ((G.numberOfNodes() == G.numberOfEdges() + 1) && isConnected(G));
}
 
 
OGDF_EXPORT bool isArborescenceForest(const Graph& G, List<node>& roots);
 
 
inline bool isArborescenceForest(const Graph& G) {
    List<node> roots;
    return isArborescenceForest(G, roots);
}
 
 
OGDF_DEPRECATED("isArborescenceForest() should be used instead.")
 
 
inline bool isForest(const Graph& G, List<node>& roots) { return isArborescenceForest(G, roots); }
 
 
OGDF_DEPRECATED("isArborescenceForest() should be used instead.")
 
 
inline bool isForest(const Graph& G) { return isArborescenceForest(G); }
 
 
OGDF_EXPORT bool isArborescence(const Graph& G, node& root);
 
 
inline bool isArborescence(const Graph& G) {
    node root;
    return isArborescence(G, root);
}
 
 
 
OGDF_EXPORT bool isRegular(const Graph& G);
 
 
 
OGDF_EXPORT bool isRegular(const Graph& G, int d);
 
 
 
OGDF_EXPORT bool isBipartite(const Graph& G, NodeArray<bool>& color);
 
 
inline bool isBipartite(const Graph& G) {
    NodeArray<bool> color(G);
    return isBipartite(G, color);
}
 
OGDF_EXPORT void nodeDistribution(const Graph& G, Array<int>& degdist, std::function<int(node)> func);
 
inline void degreeDistribution(const Graph& G, Array<int>& degdist) {
    nodeDistribution(G, degdist, [](node v) { return v->degree(); });
}
 
}