precondition.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 OREAS_PRECONDITION_H
#define OREAS_PRECONDITION_H


#include <ogdf/orthogonal/EdgeRouter.h>


namespace ogdf {

//descent the hierarchy tree at "sink" v recursively
bool dfsGenTreeRec(
    UMLGraph& UG,
    EdgeArray<bool> &used,
    NodeArray<int> &hierNumber, //number of hierarchy tree
                               //node is visited if number != 0
    int hierNum,
    node v,
    List<edge>& fakedGens, //temporary
    bool fakeTree)
{
    OGDF_ASSERT(hierNumber[v] == 0);
    hierNumber[v] = hierNum;
 
    bool returnValue = true;

    edge e;
    forall_adj_edges(e,v) {
        if (e->source() == v) continue;
        if (!(UG.type(e) == Graph::generalization)) continue;
        if (used[e]) continue; //error ??
        used[e] = true;

        node w = e->opposite(v);

        if (hierNumber[w]) 
            //temporarily fake trees 
            //if (hierNumber[w] == hierNum) //forward search edge
            if (fakeTree)
            {
              //UG.type(e) = Graph::association;
              fakedGens.pushBack(e);
              continue;
            }
            else return false;//reached w over unused edge => no tree

        returnValue = dfsGenTreeRec(UG, used, hierNumber, hierNum, w, fakedGens, fakeTree);
        //shortcut
        if (!returnValue) return false;
    }

    return returnValue;
}

edge firstOutGen(UMLGraph& UG, node v, EdgeArray<bool>& /* used */)
{
    //pruefen: kann es hier bereits ausgehende besuchte Kanten geben???
    edge e;
    forall_adj_edges(e, v)
    {
        if (e->target() == v) continue;
        if (UG.type(e) == Graph::generalization)
        {
            //OGDF_ASSERT(!used[e]);
            return e;
        }
        else continue;
    }//forall
    return 0;
}//firstOutGen

bool dfsGenTree(
    UMLGraph& UG, 
    List<edge>& fakedGens, 
    bool fakeTree)
{
    edge e;
    EdgeArray<bool> used(UG, false);
    //NodeArray<bool> visited(UG,false);
    NodeArray<int>  hierNumber(UG, 0);

    int hierNum = 0; //number of hierarchy tree

    const Graph& G = UG;
    forall_edges(e, G)
    {
        //descent in the hierarchy containing e
        if ((!used[e]) && (UG.type(e) == Graph::generalization))
        {
            hierNum++; //current hierarchy tree
            //first we search for the sink
            node sink = e->target();
            edge sinkPath = firstOutGen(UG, e->target(), used);
            int cycleCounter = 0;
            while (sinkPath)
            {
                sink = sinkPath->target();
                sinkPath = firstOutGen(UG, sinkPath->target(), used);    
                cycleCounter++;
                //if theres no sink, ?throw errGenCycle?, or convert Gens to Ass and draw
                if (cycleCounter > G.numberOfEdges()) 
                {
                    //versuche workaround: eigentlich werden die Typen erst spaeter
                    //gesetzt, damit es nicht zu Fehlern bei der Erkennung kommt, aber
                    //zum Abbruch wird hier bereits eine gesetzt (geht es auch ohne?)
                    UG.type(sinkPath) = Graph::association;
                    fakedGens.pushBack(sinkPath);
                    sink = sinkPath->source();
                    sinkPath = 0;
                    //throw OgdfException(errGenCycle); //vorlaeufig 
                }
            }

            //now sink is the hierarchy sink
              
            //used is set in dfsGenTreeRec
            bool isTree = dfsGenTreeRec(UG, used, hierNumber, hierNum, sink, fakedGens, fakeTree);
            if (!isTree) return false;
        }
      
    }//forall_edges

    return true;    
}

}//end namespace ogdf

#endif