simple_graph_alg.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/NodeArray.h>
#include <ogdf/basic/EdgeArray.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/tuples.h>
 
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);
 
 
 
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();
    });
}
 
}