extended_graph_alg.h

Go to the documentation of this file.

/*
 * $Revision: 2027 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2010-09-01 11:55:17 +0200 (Wed, 01 Sep 2010) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_EXTENDED_GRAPH_ALG_H
#define OGDF_EXTENDED_GRAPH_ALG_H


#include <ogdf/cluster/ClusterGraph.h>

namespace ogdf {


//---------------------------------------------------------
// Methods for induced subgraphs
//---------------------------------------------------------

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

    EdgeArray<bool> mark(G,false);

    LISTITERATOR its;
    for (its = start; its.valid(); its++)
    {
        node w = (*its);
        OGDF_ASSERT(w != 0 && w->graphOf() == &G);
        nodeTableOrig2New[w] = subGraph.newNode();

        adjEntry adj = w->firstAdj();
        forall_adj(adj,w)
        {
            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,0);
    edgeTableOrig2New.init(G,0);

    EdgeArray<bool> mark(G,false);

    LISTITERATOR its;
    for (its = start; its.valid(); its++)
    {
        node w = (*its);
        OGDF_ASSERT(w != 0 && w->graphOf() == &G);
        nodeTableOrig2New[w] = subGraph.newNode();

        adjEntry adj = w->firstAdj();
        forall_adj(adj,w)
        {
            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 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);
        adjEntry adj;
        forall_adj(adj,v)
        {
            edge e = adj->theEdge();
            if (mark[e->source()] && mark[e->target()])
                E.pushBack(e);
        }
    }
}


//---------------------------------------------------------
// Methods for clustered graphs
//---------------------------------------------------------


// true <=> C is C-connected
OGDF_EXPORT bool isCConnected(const ClusterGraph &C);

//connect clusters to achieve c-connectivity (probably loosing planarity)
//GG is underlying graph of C, returns inserted edges in addededges
//simple: only connect underlying cluster subgraph without crossing check
OGDF_EXPORT void makeCConnected(
    ClusterGraph& C,
    Graph& GG,
    List<edge>& addedEdges,
    bool simple = true);




//---------------------------------------------------------
// Methods for st-numbering
//---------------------------------------------------------


// Computes an st-Numbering.
// Precondition: G must be biconnected and simple.
// Exception: the Graph is allowed to have isolated nodes.
// The st-numbers are stored in NodeArray. Return value is 
// the number t. It is 0, if the computation was unsuccessful.
// The nodes s and t may be specified. In this case 
// s and t have to be adjacent.
// If s and t are set 0 and parameter randomized is set to true,
// the st edge is chosen to be a random edge in G.
OGDF_EXPORT int stNumber(const Graph &G,
    NodeArray<int> &numbering,
    node s = 0,
    node t = 0,
    bool randomized = false);

// Tests, whether a numbering is an st-numbering
// Precondition: G must be biconnected and simple.
// Exception: the Graph is allowed to have isolated nodes.
OGDF_EXPORT bool testSTnumber(const Graph &G, NodeArray<int> &st_no,int max);


//---------------------------------------------------------
// Methods for minimum spanning tree computation
//---------------------------------------------------------

double computeMinST(const Graph &G, EdgeArray<double> &weight, EdgeArray<bool> &isInTree);

} // end namespace ogdf


#endif