simple_graph_alg.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 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);
}


// removes all but one of each bundle of undirected parallel edges
// ((v,w) and (w,v) are considered as the same edge); returns the
// list of remaining edges with parallel edges in the original graph
// including the number of the removed edges that have been parallel 
// to an edge in 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);

//the same as connnectedComponents, but returns the isolated nodes 

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

// Returns true iff \a G contains exactly one sink node (or is empty).
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);


void dfsStrongComponents(const Graph& G,
                        node w,
                        BoundedStack<node>& S,
                        NodeArray<int>& pre,
                        NodeArray<int>& low,
                        int& cnt,
                        int& scnt,
                        NodeArray<int>& component);

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

OGDF_EXPORT bool isFreeForest(const Graph &G);


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


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