simple_graph_alg.h

Go to the documentation of this file.

/*
 * $Revision: 2593 $
 *
 * last checkin:
 *   $Author: gutwenger $
 *   $Date: 2012-07-15 15:33:53 +0200 (So, 15. Jul 2012) $
 ***************************************************************/

#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_SIMPLE_GRAPH_ALG_H
#define OGDF_SIMPLE_GRAPH_ALG_H


#include <ogdf/basic/EdgeArray.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/BoundedStack.h>

namespace ogdf {


//---------------------------------------------------------
// Methods for loops
//---------------------------------------------------------


OGDF_EXPORT bool isLoopFree(const Graph &G);


template<class NODELIST>
void makeLoopFree(Graph &G, NODELIST &L)
{
    L.clear();

    edge e, eNext;
    for (e = G.firstEdge(); e; e = eNext) {
        eNext = e->succ();
        if (e->isSelfLoop()) {
            L.pushBack(e->source());
            G.delEdge(e);
        }
    }
}



OGDF_EXPORT void makeLoopFree(Graph &G);


//---------------------------------------------------------
// Methods for parallel edges
//---------------------------------------------------------


OGDF_EXPORT void parallelFreeSort(const Graph &G, SListPure<edge> &edges);



OGDF_EXPORT bool isParallelFree(const Graph &G);



OGDF_EXPORT int numParallelEdges(const Graph &G);



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 (ePrev->source() == e->source() && ePrev->target() == e->target()) {
            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);



OGDF_EXPORT int numParallelEdgesUndirected(const Graph &G);



template <class EDGELIST>
void makeParallelFreeUndirected(Graph &G, EDGELIST &parallelEdges)
{
    parallelEdges.clear();
    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;
    bool bAppend = true;
    while(it.valid()) {
        e = *it++;
        if (minIndex[ePrev] == minIndex[e] && maxIndex[ePrev] == maxIndex[e]) {
            G.delEdge(e);
            if (bAppend) { parallelEdges.pushBack(ePrev); bAppend = false; }
        } else {
            ePrev = e; bAppend = true;
        }
    }
}



inline void makeParallelFreeUndirected(Graph &G) {
    List<edge> parallelEdges;
    makeParallelFreeUndirected(G,parallelEdges);
}



template <class EDGELIST>
void makeParallelFreeUndirected(
    Graph &G,
    EDGELIST &parallelEdges,
    EdgeArray<int> &cardPositive,
    EdgeArray<int> &cardNegative)
{
    parallelEdges.clear();
    cardPositive.fill(0);
    cardNegative.fill(0);
    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;
    bool bAppend = true;
    int  counter = 0;
    while(it.valid())
    {
        e = *it++;
        if (minIndex[ePrev] == minIndex[e] && maxIndex[ePrev] == maxIndex[e])
        {
            if (ePrev->source() == e->source() && ePrev->target() == e->target())
                cardPositive[ePrev]++;
            else if (ePrev->source() == e->target() && ePrev->target() == e->source())
                cardNegative[ePrev]++;
            G.delEdge(e);
            if (bAppend)
            {
                parallelEdges.pushBack(ePrev);
                bAppend = false;
            }
        }
        else
        {
            ePrev = e; bAppend = true;
        }
    }
}



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


//---------------------------------------------------------
// Methods for simple graphs
//---------------------------------------------------------



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);
}



//---------------------------------------------------------
// Methods for connectivity
//---------------------------------------------------------


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);



OGDF_EXPORT int connectedIsolatedComponents(
    const Graph &G,
    List<node> &isolated,
    NodeArray<int> &component);



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);



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);
}



void triangulate(Graph &G);


//---------------------------------------------------------
// Methods for directed graphs
//---------------------------------------------------------


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);



//---------------------------------------------------------
// Methods for trees and forests
//---------------------------------------------------------


OGDF_EXPORT bool isFreeForest(const Graph &G);



OGDF_EXPORT bool isForest(const Graph& G, List<node> &roots);



inline bool isForest(const Graph &G)
{
    List<node> roots;
    return isForest(G,roots);
}



OGDF_EXPORT bool isTree (const Graph& G, node &root);



inline bool isTree(const Graph &G) {
    node root;
    return isTree(G,root);
}


} // end namespace ogdf

#endif