Logo Search packages:      
Sourcecode: ddd version File versions  Download package

layout.C

// $Id$ -*- C++ -*-
// Graph layout functions

// Copyright (C) 1995 Technische Universitaet Braunschweig, Germany.
// Written by Christian Lindig <lindig@ips.cs.tu-bs.de>.
// 
// This file is part of DDD.
// 
// DDD is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public
// License as published by the Free Software Foundation; either
// version 2 of the License, or (at your option) any later version.
// 
// DDD is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
// See the GNU General Public License for more details.
// 
// You should have received a copy of the GNU General Public
// License along with DDD -- see the file COPYING.
// If not, write to the Free Software Foundation, Inc.,
// 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
// 
// DDD is the data display debugger.
// For details, see the DDD World-Wide-Web page, 
// `http://www.gnu.org/software/ddd/',
// or send a mail to the DDD developers <ddd@gnu.org>.

char layout_rcsid[] = 
    "$Id$";

#include "layout.h"
#include "assert.h"
#include "casts.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <X11/StringDefs.h>


// This is an implementation of the Sugiyama/Misue graph layout
// algorithm.  For details, see
// 
// @Article{sugiyama/misue/visualization,
//   author =       "Kozo Sugiyama and Kazuo Misue",
//   title =        "Visualization of Structural Information: Automatic
//                  Drawing of Compound Digraphs",
//   journal =      "IEEE Transactions on Systems, Man, and Cybernetics",
//   year =         "1991",
//   volume =       "SMC-21",
//   number =       "4",
//   pages =        "876--892",
//   month =        "July/August",
// }



const int MINXDIST    = 20;
const int MINYDIST    = 20;
const int XITERATIONS = 6;
const bool REVERSE    = false;

/*
 * PULLUP
 * if TRUE each node will be placed on the highest level possible. 
 * Otherwise each node will be placed on the level determined 
 * by a topological sort.
 */
const bool PULLUP    = false;

const int HINTPRIO   = 100;

const int NOLEVEL    = -1;
const int NOPOSITION = -1;

/*
 * definitions for return values
 */

const int MEMORY_ERROR  = 1;
const int NOT_MEMBER    = 3;
const int NODE_TYPE     = 8;
const int LEVEL_ERROR   = 9;
const int NO_EDGE       = 10;
const int INTERNAL      = 11;
const int NOT_REGULAR   = 12;


/*****************************************************************************
    Interface layer
*****************************************************************************/

void (*Layout::node_callback)(const char *, int, int) = 0;
void (*Layout::hint_callback)(const char *, const char *, int, int) = 0;
int  (*Layout::compare_callback)(const char *, const char *) = 0;

#define UP 0
#define DOWN 1

#define WARN_IF_ALREADY_PRESENT 0

// GRAPHTAB Layout::tab;
static GRAPHTAB tab;

/*
 * add_graph
 * define a new graph
 * TODO: this is a dummy - we don't distinct between different graphs yet.
 */

void Layout::add_graph (const char *g)

{
    GRAPH *graph;
    graph = graphGet (&tab,g);
    if (graph) {
#if WARN_IF_ALREADY_PRESENT
      fprintf (stderr,"add-graph warning: ");
      fprintf (stderr,"graph %s exists - not added!\n", g);
#endif /* WARN_IF_ALREADY_PRESENT */
      return;
    } else {
      graphNew (&tab,g);
    }
}

/* 
 * add_node
 * N is added to G, with all node attributes set to default values.  G
 * must exist. If there is already a node called N, this action has no
 * effect.
 */

void Layout::add_node (const char *g, const char *node)
{ 
    NODE *nd;
    GRAPH *graph;
    ID id;

    graph = graphGet (&tab,g);
    if (!graph) {
      fprintf (stderr,"add-node warning: graph %s unknown\n",g);
      return ;
    }
    id.label = node;
    /*
     * check for dublicates
     */
    nd = graphGetNode (graph,&id,Regular);
    if (nd) {
#if WARN_IF_ALREADY_PRESENT
      fprintf (stderr,"add_node: Warning - node already");
      fprintf (stderr,"member of the graph - not added\n");
#endif /* WARN_IF_ALREADY_PRESENT */
      return ;
    }
    /*
     * enter node with default width and height
     */
    nd  = graphEnterNode (graph, &id, Regular);
    nd->attr.node.w = 10 * strlen (node);
    nd->attr.node.h = 30 ;
}
      
/* 
 * add_edge
 * The edge leading from N1 to N2 is added to the graph G, with all edge
 * attributes set to default values.  G, N1 and N2 must exist.  If there
 * is already an edge (N1, N2), this action has no effect.
 * TODO: check, if edge allready exists.
 */ 

void Layout::add_edge (const char *g, const char *node1, const char *node2)
{
    NODE *source;
    NODE *target;
    GRAPH *graph;
    ID id1;
    ID id2;

    id1.label = node1;
    id2.label = node2;

    graph = graphGet (&tab,g);
    if (!graph) {
      fprintf (stderr,"add-edge warning: graph %s unknown\n",g);
      return ;
    }
    source = graphGetNode (graph, &id1, Regular);
    if (!source) {
      fprintf (stderr,"add_edge: unknown node %s\n",node1);
      exit (NOT_MEMBER);
    }
    target = graphGetNode (graph, &id2, Regular);
    if (!target) {
      fprintf (stderr,"add_edge: unknown node %s\n",node2);
      exit (NOT_MEMBER);
    }
    if (source == target) {
      /*
       * LOOP ! Mark the node
       */
      source->loop = 1;
    } else {
      graphInsertEdge (graph, source,target);
    }
}


/*
 * set_node_width
 * The width of N is set to W.  G and N must exist.  The old width is
 * overwritten.
 */

void Layout::set_node_width (const char *g, const char *node, int width)
{
    NODE *nd;
    GRAPH *graph;
    ID id;

    graph = graphGet (&tab,g);
    if (!graph) {
      fprintf (stderr,"set-node-width warning: ");
      fprintf (stderr,"graph %s unknown\n",g);
      return ;
    }
    id.label = node;
    nd = graphGetNode (graph, &id, Regular);
    if (!nd) {
      fprintf (stderr,"set_node_width: node %s unknown to %s\n",
             node, g);
      return ;
    }
    nd->attr.node.w = width;
}
      

/*
 * set_node_height
 * The height of N is set to H.  G and N must exist.  The old width is
 * overwritten.
 */

void Layout::set_node_height (const char *g, const char *node, int height)
{
    NODE *nd;
    GRAPH *graph;
    ID id;

    graph = graphGet (&tab,g);
    if (!graph) {
      fprintf (stderr,"set-node warning: graph %s unknown\n",g);
      return ;
    }
    id.label = node;
    nd = graphGetNode (graph, &id, Regular);
    if (!nd) {
      fprintf (stderr,"set_node_width: node %s unknown to %s\n",
             node, g);
      return ;
    }
    nd->attr.node.h = height;
}
      
/*
 * set_node_position
 * The position of N is set to (X, Y).  G and N must exist.  The old
 * position is overwritten.
 */

void Layout::set_node_position (const char *g, const char *node, int x, int y)
{
    NODE *nd;
    GRAPH *graph;
    ID id;

    graph = graphGet (&tab,g);
    if (!graph) {
      fprintf (stderr,"set-node-position warning: ");
      fprintf (stderr,"graph %s unknown\n",g);
      return ;
    }
    id.label = node;
    nd = graphGetNode (graph, &id, Regular);
    if (!nd) {
      fprintf (stderr,"set_node_position: node %s unknown to %s\n",
             node, g);
      return ;
    }
    nd->oldx = x;
    nd->oldy = y;
}

/*
 * add_edge_hint
 * The hint (X, Y) is added to the edge (N1, N2).  This means that the
 * edge is supposed to touch this position.  If there is already a hint
 * (X, Y), this has no effect.
 */

void Layout::add_edge_hint (const char *, const char *, const char *, int, int)
{
}

/* 
 * remove_edge_hint The hint (X, Y) is remove from the edge (N1, N2).
 * If there is no such hint, this action has no effect.  
 */

void Layout::remove_edge_hint (const char *, const char *, const char *, int, int)
{
}

/* 
 * remove_edge 
 * The edge (N1, N2) is removed from G.  If there is no
 * such edge, this action has no effect.  
 */

void Layout::remove_edge (const char *g, const char *node1, const char *node2)
{
    GRAPH *graph;
    NODE *source;
    NODE *target;
    NODE *hint;
    NODE *tmp;
    EDGE *toTarget;
    EDGE *toSource;
    ID id1, id2, tmpid;
    int direction;            /* UP or DOWN */

    id1.label = node1;
    id2.label = node2;

    graph = graphGet (&tab,g);
    if (!graph) {
      fprintf (stderr,"remove-edge warning: graph %s unknown\n",g);
      return ;
    }

    source = graphGetNode (graph, &id1, Regular);
    if (!source) {
      fprintf (stderr,"remove_edge: unknown node %s\n",node1);
      return;
    }
    target = graphGetNode (graph, &id2, Regular);
    if (!target) {
      fprintf (stderr,"remove_edge: unknown node %s\n",node2);
      return;
    }

    /*
     * try to find the edge between the two nodes
     */

    toTarget = graphFindEdgeAtSource (source,target);
    if (!toTarget) {
      fprintf (stderr,"remove_edge: can't find edge from");
      fprintf (stderr," %s to %s \n", node1, node2);
      return ;
    }
    toSource = graphFindEdgeAtTarget (source,target);
    if (!toSource) {
      fprintf (stderr,"remove_edge: can't find edge from");
      fprintf (stderr," %s to %s \n", node1, node2);
      return;
    }

    /*
     * remove all hints
     * start at the source node and move to the target node
     * removing all hints on that way. We have to determine
     * if we have to go UP ord DOWN at each hint we find, because
     * the edge may be inverted!
     */

    hint = toTarget->node;
    if (hint->type == Hint && hint->attr.hint.up == source) {
      direction = DOWN;
    } else {
      direction = UP;
    }
    while (hint != target) {
      if (hint->level != NOLEVEL) {
          /*
           * remove hint form its level
           */
          levelsRemoveNode (graph, hint, hint->level);
      }
      tmp = ( direction == DOWN ? 
            hint->attr.hint.down : hint->attr.hint.up );
      tmpid.id = hint->attr.hint.id;
      graphRemoveNode (graph, &tmpid, Hint);
      hint = tmp;
    }

    /*
     * remove edges
     */
      
    listRemoveEdge (&source->attr.node.down, toTarget);
    listRemoveEdge (&target->attr.node.up, toSource); 
}

/* 
 * remove_node
 * The node N is removed from G. All edges coming
 * from or leading to N are also removed. If there is no such node,
 * this action has no effect.
 */

void Layout::remove_node (const char *g, const char *label)
{
    GRAPH *graph;
    NODE *node;
    EDGE *edge;
    ID id;

    graph = graphGet (&tab,g);
    if (!graph) {
      fprintf (stderr,"remove-edge warning: graph %s unknown\n",g);
      return ;
    }
    id.label = label;
    node = graphGetNode (graph, &id, Regular);
    if (!node ) {
      fprintf (stderr,"remove_node: unknown node %s\n", label);
      exit (NOT_MEMBER);
    }
    if (node->level != NOLEVEL) {
      levelsRemoveNode (graph, node, node->level);
    }
    /* 
     * remove all edges leading down ...
     */

    edge = node->attr.node.down.head ;
    while (edge) {
      remove_edge (g,label, edge->target->attr.node.label);
      edge = edge->next;
    }
      
    /* 
     * remove all edges leading up  ...
     */

    edge = node->attr.node.up.head ;
    while (edge) {
      remove_edge (g,edge->target->attr.node.label, label);
      edge = edge->next;
    }
    /*
     * remove node by itself
     */
    graphRemoveNode (graph, &id, Regular);
}

/* 
 * remove_graph
 * The graph G is removed, including all its edges and
 * nodes.  If there is no such graph, this action has no effect.
 */

void Layout::remove_graph (const char *g)
{
    graphRemove (&tab,g);
}

/* 
 * layout
 * A layout for all nodes in G is computed.  Changing node
 * positions are echoed on the standard output in the form
 * !^node-position(G, N, X, Y)  for each old (now invalid) node
 * position (X, Y) and !node-position(G, N, X, Y) for each new node
 * position (X, Y). Changing edge hints are echoed on the stan- dard
 * output in the form ^!edge-hint(G, N1, N2, X, Y) for each old (now
 * invalid) edge hint (X, Y) and !edge-hint(G, N1, N2, X, Y) for each
 * new edge hint (X, Y).
 */

void Layout::layout (const char *g)
{
    GRAPH *graph;
      
    graph = graphGet (&tab,g);
    if (!graph) {
      fprintf (stderr,"layout warning: graph %s unknown\n",g);
      return ;
    }

    if (graph->layouted) {
      inc_layout(graph);
    } else {
      new_layout(graph);
    }
    dddOutput (graph);

}

/*
 * debug
 */
void Layout::dddDebug (const char *g)
{
    GRAPH *graph;
      
    graph = graphGet (&tab,g);
    if (!graph) {
      fprintf (stderr,"debug warning: graph %s unknown\n",g);
      return ;
    }

    if (graph->layouted) {
      inc_layout (graph);
    } else {
      new_layout (graph);
    }
    debugGraphXFig (graph);
}


/*
 * inc_layout
 * perform an incremental layout
 */

void Layout::inc_layout (GRAPH *graph)
{
    int i;

    levelsEnterNodes (graph,graph->pullup);
    sortInsertHints (graph);

    sortGraphUpperBary (graph);
    sortGraphLowerBary (graph);
    sortInitX (graph);

    /*
     * there are two ways for finetunig the x-coordinates.
     * graph.xiterations tells the number of iterations.
     */
    if (graph->reverseflag) {
      for (i=0;i < graph->xiterations/2;i++) {
          sortGraphDownX (graph);
          sortGraphUpX (graph);
      }
      if (graph->xiterations % 2) {
          sortGraphUpX (graph);
      }
    } else {
      
      for (i=0;i<graph->xiterations/2;i++) {
          sortGraphUpX (graph);
          sortGraphDownX (graph);
      }
      if (graph->xiterations % 2) {
          sortGraphUpX (graph);
      }
    }

    sortGraphVertical (graph);
}


/*
 * new_layout
 * create a new layout
 */

void Layout::new_layout (GRAPH *graph)
{
    int i;

    graph->layouted = true;

    levelsEnterNodes (graph,graph->pullup);
    sortInsertHints (graph);

    /*
     * there are two ways for finetunig the x-coordinates.
     * graph->xiterations tells the number of iterations.
     */
    if (graph->reverseflag) {

      sortGraphLowerBary (graph);
      sortGraphUpperBary (graph);
      sortGraphLowerBary (graph);   
      sortGraphUpperBary (graph);
      if (graph->xiterations % 2) {
          sortGraphLowerBary (graph);
      }

      sortInitX (graph);


      for (i=0;i < graph->xiterations/2;i++) {
          sortGraphDownX (graph);
          sortGraphUpX (graph);
      }
      if (graph->xiterations % 2) {
          sortGraphDownX (graph);
      }
    } else {
      sortGraphUpperBary (graph);
      sortGraphLowerBary (graph);
      sortGraphUpperBary (graph);
      sortGraphLowerBary (graph);   
      if (graph->xiterations % 2) {
          sortGraphUpperBary (graph);
      }

      sortInitX (graph);

      for (i=0;i<graph->xiterations/2;i++) {
          sortGraphUpX (graph);
          sortGraphDownX (graph);
      }
      if (graph->xiterations % 2) {
          sortGraphUpX (graph);
      }
    }

    sortGraphVertical (graph);
}

/*
 * dddOutput
 * echo the changes to stdout. For each node its new position will
 * be written out. 
 */

void Layout::dddOutput (GRAPH *graph)
{
    int i;
    NODE *node;
    
    for (i = 0; i < PRIME; i++) {
      node = graph->hashtab[i];
      while (node) {
          dddNodeOut (graph->label, node);
          node = node->hashnext;
      }
    }
}

/*
 * dddNodeOut
 * write out the node position 
 */

void Layout::dddNodeOut (const char *, NODE *node)
{
    if (node->x == node->oldx && node->y == node->oldy) {
      return;     /* no changes */
    }

    if (node->type == Regular) {
      node_callback(node->attr.node.label,
                       node->x,
                       node->y);
    } else {
      hint_callback(node->attr.hint.source->attr.node.label,
                       node->attr.hint.target->attr.node.label,
                       node->x,
                       node->y);
    }
    node->oldx = node->x;
    node->oldy = node->y;
    node->layouted = true;
}


/*****************************************************************************
    Debugging functions
*****************************************************************************/

#define XFIGHEADER "#FIG 2.1\n80 2\n"
#define BOXHEADER  "2 2 0 1 -1 0 0 0 0.000 0 0 0\n\t"
#define TEXTHEADER "4 1 0 12 0 -1 0 0.000 0 0 0 "
#define FWDLINE "2 1 0 1 -1 0 0 0 0.000 0 1 0\n\t0 0 1.000 4.000 8.000\n\t"
#define BKWDLINE "2 1 0 1 -1 0 0 0 0.000 0 0 1\n\t0 0 1.000 4.000 8.000\n\t"
#define LINE "2 1 0 1 -1 0 0 0 0.000 0 0 0\n\t"

/*
 * debugNode
 * print a node
 */

void Layout::debugNode (NODE *node)
{
    EDGE *tmp;

    printf ("level=%i center=%i x=%i ",node->level, node->center,
          node->x);
    if (node->type == Regular) {
      printf ("regular label=%s\n",node->attr.node.label);
      printf ("down: ");
      tmp = node->attr.node.down.head ;
      while (tmp) {
          if (tmp->node->type == Regular) {
            printf ("%s ",tmp->node->attr.node.label);
          } else {
            printf ("%i ",tmp->node->attr.hint.id);
          }
          tmp=tmp->next;
      }
      printf ("\n");
      printf ("up: ");
      tmp = node->attr.node.up.head ;
      while (tmp) {
          if (tmp->node->type == Regular) {
            printf ("%s ",tmp->node->attr.node.label);
          } else {
            printf ("%i ",tmp->node->attr.hint.id);
          }
          tmp=tmp->next;
      }
      printf ("\n");
    } else {
      printf ("hint %i\n",node->attr.hint.id);
      printf ("down: ");
      if (node->attr.hint.down) {
          if (node->attr.hint.down->type == Regular) {
            printf ("%s ",node->attr.hint.down
                  ->attr.node.label);
          } else {
            printf ("%i ",node->attr.hint.down
                  ->attr.hint.id);
          }
      }
      printf ("\n");
      printf ("up: ");
      if (node->attr.hint.up) {
          if (node->attr.hint.up->type == Regular) {
            printf ("%s ",node->attr.hint.up
                  ->attr.node.label);
          } else {
            printf ("%i ",node->attr.hint.up
                  ->attr.hint.id);
          }
      }
      printf ("\n");
    }
}

/*
 * debugLevel
 * print all nodes of a level
 */

void Layout::debugLevel (GRAPH *graph, int n)
{
    NODE **level = graph->level+n;
    NODE *node;

    node = *level ;
    while (node) {
      debugNode (node);
      node = node->right;
    }
}

/*
 * debugAllLevels
 * print the nodes of all levels
 */

void Layout::debugAllLevel (GRAPH *graph)
{
    int i;

    for ( i = 0 ; i < graph->levels; i++) {
      printf ("*** level %i ***\n",i);
      debugLevel (graph,i);
    }
}     
      
/*
 * debugAllNodes
 * write out all nodes
 */

void Layout::debugAllNodes (GRAPH *graph)
{
    int i;
    NODE *node;

    for (i=0;i<PRIME;i++) {
      if (graph->hashtab[i] ) {
          node = graph->hashtab[i] ;
          while (node) {
            debugNode (node);
            node = node->hashnext;
          }
      }
    }
}


/*
 * debugNodeXFig
 * write a xfig-representation for the given node to stdout. The function
 * will display a rectangle for the node and lines to all descants.
 */

void Layout::debugNodeXFig (NODE *nd)
{
    EDGE *edge;
    Arrow arrow;
    int w,h;

    if (nd->type == Regular) {

      w = nd->attr.node.w/2;
      h = nd->attr.node.h/2;

      printf ( BOXHEADER );
      printf ("%i %i ",nd->x - w , nd->y - h);
      printf ("%i %i ",nd->x + w , nd->y - h);
      printf ("%i %i ",nd->x + w , nd->y + h);
      printf ("%i %i ",nd->x - w , nd->y + h);
      printf ("%i %i ",nd->x - w , nd->y - h);
      printf (" 9999 9999\n");
      printf ( TEXTHEADER );
      printf ("%i %i %s\x01\n", nd->x, nd->y, nd->attr.node.label);

      /*
       * draw the lines to all descendants
       */

      edge = nd->attr.node.down.head;
      while (edge) {
          arrow = ( edge->arrow == Here ? HERE : OTHER);
          if (arrow == HERE) {
            debugEdgeXFig (nd, edge->node, HERE) ;
          } else {
            if (edge->node->type == Regular) {
                debugEdgeXFig (nd, edge->node, OTHER);
            } else {
                debugEdgeXFig (nd, edge->node,NOTHING);
            }
          }
          edge = edge->next;
      }

    } else if (nd->attr.hint.down) {
      /*
       * draw the line 
       */
      if (nd->attr.hint.down->type == Regular) {
          if (nd->attr.hint.target == nd->attr.hint.down) {
            debugEdgeXFig (nd, nd->attr.hint.down, OTHER);
          } else {
            debugEdgeXFig (nd, nd->attr.hint.down,NOTHING);
          }
      } else {
      }

      if (nd->attr.hint.down->type == Hint) {
          debugEdgeXFig (nd, nd->attr.hint.down, NOTHING);
      } else {
          if (nd->attr.hint.target == nd->attr.hint.down) {
            debugEdgeXFig (nd, nd->attr.hint.down, OTHER);
          } else {
            debugEdgeXFig (nd, nd->attr.hint.down,NOTHING);
          }
      }
                  
    }
}

/*
 * debugEdgeXFig
 * write a xfig-representation for a line between to nodes to stdout
 */

void Layout::debugEdgeXFig (NODE *source, NODE *target, Arrow arrow)
{
    int x1,y1,x2,y2;

    x1 = source->x ;
    y1 = source->y ;
    if (source->type == Regular ) {
      y1 += source->attr.node.h/2;
    }
    x2 = target->x ;
    y2 = target->y ;
    if (target->type == Regular ) {
      y2 -= target->attr.node.h/2;
    }
    switch (arrow) {
    case OTHER:
      printf (FWDLINE);
      break;
    case HERE:
      printf (BKWDLINE);
      break;
    case NOTHING:
    default:
      printf (LINE);
      break;
    }
    printf ("%i %i %i %i 9999 9999\n",x1,y1,x2,y2);
}

/*
 * debugGraphXFig
 */

void Layout::debugGraphXFig (GRAPH *graph)
{
    NODE *node;
    int i;

    printf (XFIGHEADER);
    for ( i = 0 ; i < PRIME; i++) {
      node = graph->hashtab[i];
      while (node) {
          debugNodeXFig (node);
          node = node->hashnext;
      }
    }
      
}


/*****************************************************************************
    Edgelist functions
*****************************************************************************/

/*
 * listInit
 * initialize a list of edges
 */

void Layout::listInit (EDGELIST *list)
{
    list->head = (EDGE*) 0;
    list->tail = (EDGE*) 0;
    list->length = 0;
}

/*
 * listInsertEdge
 * insert a new edge to a list
 */

EDGE *Layout::listInsertEdge (EDGELIST *list, NODE *node)
{
    EDGE *edge;
    EDGE *tail;

    /*
     * create a new edge
     */
    edge = (EDGE*) malloc (sizeof (EDGE));
    if (!edge) {
      fprintf (stderr,"listInsertEdge: out of memory\n");
      exit (MEMORY_ERROR);
    }
    /*
     * link the edge to the list
     */
    edge->next = (EDGE*) 0;
    edge->prev = (EDGE*) 0;

    tail = list->head;
    list->head = edge;
    edge->next = tail;
    if (!tail) {
      list->tail = edge;
    } else {
      tail->prev = edge;
    }
      
    /*
     * enter the node to the edge
     */
    edge->node = node;

    list->length++;

    return edge;
}
      
/*
 * listRemoveEdge
 * remove one edge form a list of edges
 */

void Layout::listRemoveEdge (EDGELIST *list, EDGE *edge)
{
    if (edge->prev && edge->next) {
      /* edge neither head nor tail of list */
      edge->next->prev = edge->prev ;
      edge->prev->next = edge->next ;
    } else {
      if (!edge->next) {
          /* last entry of list */
          list->tail = edge->prev;
          if (edge->prev) {
            edge->prev->next = (EDGE*) 0;
          }
      }
      if (!edge->prev) {
          /* first entry of list */
          list->head = edge->next ;
          if (edge->next) {
            edge->next->prev = (EDGE*) 0;
          }
      }
    }
    free ((char *)edge);
    /*
     * correct number of entries 
     */
    list->length-- ;

}

/*
 * listFindNode
 * find an edge to a specified node
 */

EDGE *Layout::listFindNode (EDGELIST *list, NODE *node)
{
    EDGE *edge;
      
    edge = list->head;
    while (edge && edge->node != node) {
      edge = edge->next;
    }
    if (!edge) {
      fprintf (stderr,"listFindEntry: can't find entry\n");
      exit (NOT_MEMBER);
    }
      
    return edge;
}

/*
 * listFindTarget
 * find an edge to a specified target
 */

EDGE *Layout::listFindTarget (EDGELIST *list, NODE *target)
{
    EDGE *edge;
      
    edge = list->head;
    while (edge && edge->target != target) {
      edge = edge->next;
    }
    if (!edge) {
      fprintf (stderr,"listFindEntry: can't find entry\n");
      edge = (EDGE*) 0;
    }
      
    return edge;
}

/*
 * listRemove
 * remove all edges from a list
 * this function is just for cleaning up
 */

void Layout::listRemove (EDGELIST *list)
{
    EDGE *edge;
    EDGE *tmp;
      
    edge = list->head;
    while (edge) {
      tmp = edge->next;
      free ((char *) edge);
      edge = tmp;
    }
    list->head = (EDGE*) 0;
    list->tail = (EDGE*) 0;
}


/*****************************************************************************
    Node functions
*****************************************************************************/

/*
 * nodeInit
 * initialize a node
 */

void Layout::nodeInit (NODE* node, const ID *id , NODETYPE type)
{
    node->x = 0;
    node->y = 0;
    node->oldx = NOPOSITION;
    node->oldy = NOPOSITION;
    node->layouted = false;
    node->level = NOLEVEL;
    node->center = 0;
    node->index = 0 ;
    node->loop = 0;
    node->mark = (NODE*) 0;
      
    node->left = (NODE*) 0;
    node->right = (NODE*) 0;

    node->hashnext = (NODE*) 0;
    node->hashprev = (NODE*) 0;
      
    node->type = type;

    if ( type == Regular ) {
      node->attr.node.label = (char *) malloc (strlen(id->label)+5);
      if (!node->attr.node.label) {
          fprintf (stderr,"nodeInit: out of memory!\n");
          exit (MEMORY_ERROR);
      }
      strcpy (node->attr.node.label, id->label);

      node->attr.node.w = 0;
      node->attr.node.h = 0;
      listInit (&node->attr.node.up);
      listInit (&node->attr.node.down);
    } else {
      node->attr.hint.id = id->id ;
      node->attr.hint.up = (NODE*) 0;
      node->attr.hint.down = (NODE*) 0;
      node->attr.hint.source = (NODE*) 0;
      node->attr.hint.target = (NODE*) 0;
    }
            
}           

/*
 * nodeRemove
 * remove a node.
 * remember to free the label and and the lists of adjacent nodes.
 */

void Layout::nodeRemove (NODE *node) 
{
    if (node->type == Regular) {
      free (node->attr.node.label);
      listRemove (&node->attr.node.up);
      listRemove (&node->attr.node.down);
    }
      
    free ((char *)node);
}

/*****************************************************************************
    Graph functions
*****************************************************************************/

/*
 * graphInit
 * initialize a graph
 */

void Layout::graphInit (GRAPH *graph, const char *label)
{
    int i;
      
    graph->label = (char *)malloc (strlen(label)+1);
    if (!graph->label) {
      fprintf (stderr,"graphInit: out of memory!\n");
    }
    strcpy (graph->label, label);
    graph->hashnext = (GRAPH*) 0;
    graph->hashprev = (GRAPH*) 0;

    graph->minxdist    = MINXDIST ;
    graph->minydist    = MINYDIST;
    graph->xiterations = XITERATIONS;
    graph->reverseflag = REVERSE ;
    graph->pullup      = PULLUP;

    graph->levels = 0;
    graph->level = (NODE**) 0;

    graph->layouted = false;  /* the graph was never layouted */

    for ( i = 0; i < PRIME; i++) {
      graph->hashtab[i] = (NODE*) 0;
    }
}

/*
 * graphEnterNode
 * enter a new node to the graph and return a pointer to the
 * new node
 */

NODE *Layout::graphEnterNode (GRAPH *graph, const ID *id, NODETYPE type)
{
    NODE *node;
    NODE *tail;
    int pos;

    node = (NODE*) malloc (sizeof(NODE)) ;
    if (!node) {
      fprintf (stderr, "graphEnterNode: out of memory\n");
      exit (MEMORY_ERROR);
    }
    nodeInit (node,id,type);

    /*
     * insert the new node to the hashing table
     * TODO: check for dublicates of the given nodeID
     */
      
    if (type == Regular) {
      pos = graphHashStr (node->attr.node.label, PRIME);
    } else {
      pos =  node->attr.hint.id % PRIME;
    }
    tail = graph->hashtab[pos] ;
    graph->hashtab[pos] = node;
    node->hashnext = tail ;
    node->hashprev = (NODE*) 0;
    if (node->hashnext) {
      node->hashnext->hashprev = node;
    }
      
    return node;
}

/*
 * graphGetNode
 * get a pointer to a node described by its ID
 */

NODE *Layout::graphGetNode (GRAPH *graph, const ID *id, NODETYPE type)
{
    int pos;
    bool found = false;
    NODE *node;

    /*
     * calculate the hash-entry
     */
    if (type == Regular) {
      pos = graphHashStr (id->label, PRIME);
      node = graph->hashtab[pos];

      /*
       * search for entry 
       */
      while (node && !found) {
          if (node->type != Regular 
            ||  strcmp(node->attr.node.label,id->label)) {
            node = node->hashnext;
          } else {
            found = true;
          }
      } 

    } else {
      pos =  id->id % PRIME;
      node = graph->hashtab[pos];

      /*
       * search for entry 
       */

      while (node && !found) {
          if (node->type != Hint 
            ||  node->attr.hint.id != id->id) {
            node = node->hashnext;
          } else {
            found = true;
          }
      } 
    }

    /*
     * node == 0 if not found
     */
    return node;
}

/*
 * graphRemoveNode
 * delete a node from the hashtab of a graph. 
 * ATTENTION: You have to delete all edges connected to the node
 * and remove the node from its level by yourself!
 */

void Layout::graphRemoveNode (GRAPH *graph, const ID *id, NODETYPE type)
{
    int pos;
    NODE *node;

    /*
     * calculate the hash-entry
     */
    if (type == Regular) {
      pos = graphHashStr (id->label, PRIME);
      node = graph->hashtab[pos];

      /*
       * search for entry 
       */
      while (node && strcmp(node->attr.node.label,id->label)) {
          node = node->hashnext;
      }

    } else {
      pos =  id->id % PRIME;
      node = graph->hashtab[pos];

      /*
       * search for entry 
       */
      while (node && node->attr.hint.id != id->id) {
          node = node->hashnext;
      }
    }

    /*
     * node == 0 if not found
     */

    if (!node) {
      fprintf (stderr,"graphRemoveNode: can't find entry!\n");
      exit (NOT_MEMBER);
    }

    /*
     * remove the node from the double linked list
     */

    if (node->hashprev && node->hashprev) {
      node->hashprev->hashnext = node->hashnext;
      node->hashnext->hashprev = node->hashprev;
    } else {
      if (!node->hashprev) {
          graph->hashtab[pos] = node->hashnext;
          if (node->hashnext) {
            node->hashnext->hashprev = (NODE*) 0;
          }
      }
      if (!node->hashnext && node->hashprev) {
          node->hashprev->hashnext = (NODE*) 0;
      }
    }
    nodeRemove (node);
}
      
/* 
 * graphCreateLevels
 * create a number of Levels for a graph and initialize it
 */

void Layout::graphCreateLevels (GRAPH *graph, int n)
{
    NODE **nodeptr;
    int i;

    graph->levels = n;
    graph->level = (NODE **) malloc (sizeof (NODE*) * n);
    if (!graph->level) {
      fprintf (stderr,"graphCreateLevels: out of memory!\n");
      exit (MEMORY_ERROR);
    }
      
    /*
     * initialize it
     */

    nodeptr = graph->level ;
    for ( i = 0 ; i < n ; i++ ) {
      *(nodeptr++) = (NODE*) 0;
    }
}

/*
 * graphRemoveLevels
 * remove the level references.
 * ATTENTION: only the references will be deleted, not the nodes
 * contained by the levels!
 */

void Layout::graphRemoveLevels (GRAPH *graph)
{
    free ( (char *) graph->level);
    graph->level = (NODE**) 0;
    graph->levels = 0;
}

/*
 * graphAddLevels
 * enlarge the table of levels by 'n'. The new levels will all be 
 * empty.
 */

void Layout::graphAddLevels (GRAPH *graph, int n)
{
    NODE **newtab;
    int i;
      

    /*
     * create a larger table
     */
    newtab = (NODE**) malloc (sizeof(NODE*) * (graph->levels + n));
    if (!newtab) {
      fprintf (stderr,"graphAddLevels: out of memory!\n");
      exit (MEMORY_ERROR);
    }
    /*
     * fill the table ..
     */
    for (i=0 ; i < graph->levels; i++) {
      *(newtab+i) = *(graph->level);
    }
    /*
     * clear the new levels
     */
    for (i=graph->levels; i < graph->levels+n; i++) {
      *(newtab+i) = (NODE*) 0;
    }
    /*
     * make the new table to the actual table
     */
    graph->levels += n;
    free ((char *) graph->level);
    graph->level = newtab;
}

/*
 * graphInsertEdge
 * insert an edge of a specified type between two regular nodes of the graph
 * TODO: check for dublicates and loops
 */

void Layout::graphInsertEdge (GRAPH *, NODE *source, NODE *target)
{
    EDGE *from;
    EDGE *to;

    if (source->type != Regular) {
      fprintf (stderr,"graphInsertEdge: wrong node type\n");
      exit (NODE_TYPE);
    }
    if (target->type != Regular) {
      fprintf (stderr,"graphInsertEdge: wrong node type\n");
      exit (NODE_TYPE);
    }
      
    to = graphFindEdgeAtSource (source,target) ;
    if (to) {
      fprintf (stderr,"graphInsertEdge: warning - edge exists\n");
      return;
    }

    from = listInsertEdge (&source->attr.node.down, target);
    from->arrow = Other;
    from->target = target;
    from->node = target;

    to = listInsertEdge (&target->attr.node.up, source);
    to->arrow = Here;
    to->target = source;
    to->node = source;

}

/*
 * graphInvertEdge
 * invert the internal represation of an edge.
 */

void Layout::graphInvertEdge (NODE *source, NODE *target)
{
    EDGE *to, *from;
    EDGEARROW srcarrow;


    if (source->type != Regular || target->type != Regular) {
      fprintf (stderr,"graphInvertEdge: node not regular!\n");
      exit (INTERNAL);
    }
    fprintf (stderr,"graphInvertEdge: inverting Edge %s -> %s\n", 
           source->attr.node.label, target->attr.node.label);
    to = listFindTarget (&source->attr.node.down,target);
    from = listFindTarget (&target->attr.node.up,source);
    if (!to || !from) {
      fprintf (stderr,"graphInvertEdge: can't find edge!\n");
      exit (NO_EDGE);
    }
    srcarrow = to->arrow;

    /*
     * remove the edge
     */
    listRemoveEdge (&source->attr.node.down, to);
    listRemoveEdge (&target->attr.node.up,from);
    /*
     * create inverted edge
     */
    to = listInsertEdge (&source->attr.node.up, target);
    to->target = target;
    to->arrow = srcarrow;
    from = listInsertEdge (&target->attr.node.down, source);
    from->target = source;
    from->arrow = ( srcarrow == Here ? Other : Here );
}

/*
 * graphNewNodeID
 * return a new nodeID
 */

int Layout::graphNewNodeID()
{
    static int counter = 1000 ;

    return counter++ ;
}

/*
 * graphInsertHint
 * insert a hint node by splitting an edge between two nodes.
 * A pointer to the new created hint node will be returned
 */

NODE *Layout::graphInsertHint (GRAPH *graph, NODE *source, NODE* target)
{
    ID id;
    NODE *hint = 0;
    EDGE *toTarget = 0;
    EDGE *toSource = 0;

    /*
     * there must be an edge between source and target 
     */

    id.id = graphNewNodeID();
    hint = graphEnterNode (graph,&id, Hint);
    if (source->type == Regular) {
      /*
       * find edge to target
       */
      toTarget = listFindNode (&source->attr.node.down, target);
      toTarget->node = hint;
    } else {
      source->attr.hint.down = hint;
    }

    if (target->type == Regular) {
      /*
       * find edge to source
       */
      toSource = listFindNode (&target->attr.node.up, source);
      toSource->node = hint;
    } else {
      target->attr.hint.up = hint;
    }

    hint->attr.hint.up = source;
    hint->attr.hint.down = target;

    /*
     * enter the information, to which edge this hint belongs
     */
      
    if (source->type == Hint) {
      hint->attr.hint.source = source->attr.hint.source;
      hint->attr.hint.target = source->attr.hint.target;
    } else if (target->type == Hint) {
      hint->attr.hint.source = target->attr.hint.source;
      hint->attr.hint.target = target->attr.hint.target;
    } else if (toTarget->arrow == Other){
      hint->attr.hint.source = source;
      hint->attr.hint.target = target;
    } else {
      hint->attr.hint.source = target;
      hint->attr.hint.target = source;
    }

    return hint;
}

/*
 * graphFindEdgeAtSource 
 * return the edge leading from source to target. Source and target
 * must be regular!
 */

EDGE *Layout::graphFindEdgeAtSource (NODE *source, NODE *target)
{
    EDGE *edge;
      
    edge = source->attr.node.down.head ;
    while (edge && !(edge->target == target && edge->arrow == Other)){
      edge = edge->next;
    }
    if (!edge) {
      edge = source->attr.node.up.head ;
      while (edge && !(edge->target == target && 
                   edge->arrow == Other )) {
          edge = edge->next;
      }
    }
    return edge;
}


/*
 * graphFindEdgeAtTarget
 * return the edge (at target) leading from source to target. Source and target
 * must be regular!
 */

EDGE *Layout::graphFindEdgeAtTarget (NODE *source, NODE *target)
{
    EDGE *edge;
      
    edge = target->attr.node.up.head ;
    while (edge && !(edge->target == source && edge->arrow == Here)){
      edge = edge->next;
    }
    if (!edge) {
      edge = target->attr.node.down.head ;
      while (edge && !(edge->target == source && 
                   edge->arrow == Here )) {
          edge = edge->next;
      }
    }
    return edge;
}


/*
 * graphResetLevels
 * set the level of all nodes to NOLEVEL. The entries of 'left' and 'right'
 * will be set to 0.
 * ATTENTION: You first have to clear the Levels by calling
 * 'graphRemoveLevels' before you call this function!
 */

void Layout::graphResetLevels (GRAPH *graph) 
{
    int i;
    NODE *node;

    for (i = 0 ; i < PRIME; i++) {
      node = graph->hashtab[i];
      while (node) {
          node->level = NOLEVEL;
          node->left = (NODE*) 0;
          node->right = (NODE*) 0;

          node = node->hashnext;
      }
    }
}
      
      
/*
 * graphHashStr
 * calculate a hash-value for a given string and return it. The 
 * hash-value will belong to [0..PRIME]
 * original by P.J. Weinberger
 */

int Layout::graphHashStr (const char *str, int prime) 
{
    const char *p;
    unsigned h = 0, g;
      
    for (p=str; *p != '\0'; p++ ) {
      h = ( h << 4) + (*p);
      if ((g = h & 0xf0000000)) {
          h = h ^ (g >> 24);
          h = h ^ g;
      }
    }
    return h % prime;
}

/*
 * functions for maintaining multiple graphs
 */

/*
 * graphGet
 * return a pointer to a specified graph. Return 0, if no such
 * graph exists.
 * 'hashtab' contains SMALLPRIME pointers to GRAPHs.
 */

GRAPH *Layout::graphGet (GRAPHTAB *tab, const char *label)
{
    int pos;
    GRAPH *graph;

    pos = graphHashStr (label, SMALLPRIME);
    /*
     * try to find graph
     */
    graph = (*tab)[pos];
    while (graph && strcmp(graph->label, label)) {
      graph = graph->hashnext;
    }
    return graph;
}
      
      
/*
 * graphNew
 * create a new graph, initialize it and return a pointer to it
 * if a graph with the specified label allready exists a warning
 * is printed and no new graph is created (0 returned).
 */

GRAPH *Layout::graphNew (GRAPHTAB *tab, const char *label)
{
    GRAPH *graph;
    GRAPH *tail;
    int pos;

    /*
     * check for dublicate
     */
    graph = graphGet (tab, label);
    if (graph) {
      fprintf (stderr,"graphNew: %s already there!\n",label);
      return (GRAPH*) 0;
    }
            
    graph = (GRAPH*) malloc (sizeof(GRAPH));
    if (!graph) {
      fprintf (stderr,"graphNew: out of memory\n");
      exit (MEMORY_ERROR);
    }
    graphInit (graph,label);
      
    /*
     * enter graph to tab
     */
    pos = graphHashStr (label, SMALLPRIME);

    if ((*tab)[pos]) {
      tail = ((*tab)[pos])->hashnext;
    } else {
      tail = (GRAPH*) 0;
    }
    (*tab)[pos] = graph;
    graph->hashnext = tail;
    graph->hashprev = (GRAPH*) 0;
    if (graph->hashnext) {
      graph->hashnext->hashprev = graph;
    }
      
    return graph;
}
                  
/*
 * graphRemove
 * remove a graph from a GRAPHTAB
 */

void Layout::graphRemove (GRAPHTAB *tab, const char *label)
{
    int pos;
    int i;
    GRAPH *graph;
    NODE *nextnode;
    NODE *node;

    pos = graphHashStr (label, SMALLPRIME);
    /*
     * try to find graph
     */
    graph = (*tab)[pos];
    while (graph && strcmp(graph->label, label)) {
      graph = graph->hashnext;
    }
    if (!graph) {
      /*
       * not found
       */
      fprintf (stderr,"graphRemove: %s not found!\n",label);
      return;
    }
    /*
     * remove the graph
     */
    if (graph->hashprev && graph->hashprev) {
      graph->hashprev->hashnext = graph->hashnext;
      graph->hashnext->hashprev = graph->hashprev;
    } else {
      if (!graph->hashprev) {
          (*tab)[pos] = graph->hashnext;
          if (graph->hashnext) {
            graph->hashnext->hashprev = (GRAPH*) 0;
          }
      }
      if (!graph->hashnext && graph->hashprev) {
          graph->hashprev->hashnext = (GRAPH*) 0;
      }
    }

    graphRemoveLevels (graph); /* remove Levels */
    for (i=0; i < PRIME; i++) {
      node = graph->hashtab[i];
      while (node) {
          nextnode = node->hashnext;
          nodeRemove (node);
          node = nextnode;
      }
    }
    free (graph->label);
    free ((char *) graph);
}

/*
 * graphTabInit
 * initalize a GRAPHTAB
 */

void Layout::graphTabInit (GRAPHTAB *tab)
{
    int i;
      
    for (i=0 ; i < SMALLPRIME; i++) {
      (*tab)[i] = (GRAPH*) 0;
    }
}


/*****************************************************************************
    Level functions
*****************************************************************************/

/*
 * levelsInsertNode
 * insert a node to a specified level. The node wil only be
 * inserted if its components 'left' and 'right' are 0. Otherwise
 * the function assumes, that the node is allready member of
 * a level. These differences are made to allow incremental
 * layout of the graph.
 */

void Layout::levelsInsertNode (GRAPH *graph, NODE *node, int n)
{
    NODE **level;

    if (n > graph->levels || !graph->level) {
      fprintf (stderr,"levelsInsertNode: wrong Level!\n");
      exit (LEVEL_ERROR);
    }

    if (!node->right && !node->left) {

      /*
       * insert Node at head of level
       */
      
      level = graph->level+n ;
      node->right = *level;
      node->left = (NODE*) 0;
      if (*level) {
          (*level)->left = node;
      }
      *level = node;
      node->level = n;
    }

    /*
     * else do nothing, assuming the node is member of a level
     */
}

/*
 * levelsRemoveNode
 * remove a node from a level
 * The node won't be deleted - it's just not referenced by the
 * specified level any more.
 */

void Layout::levelsRemoveNode (GRAPH *graph, NODE *node, int n)
{
    NODE **level = graph->level+n;

    if (!node->left) {
      *level = node->right;
    } else {
      node->left->right = node->right;
    }

    if (node->right) {
      node->right->left = node->left;
    }
    node->level = NOLEVEL ;
}


      
/*
 * levelsEnterNodes
 * enter all nodes to their level
 */

void Layout::levelsEnterNodes (GRAPH *graph, bool pullup)
{
    int levels;
    int i;
    NODE *node;

    levels = sortApplyLevel (graph);      /* apply levels */

    /*
     * check for levels allready there
     */
    if (!levels) {
      fprintf (stderr," levelsEnterNodes: internal Error\n");
      exit (INTERNAL);
    }
    if (!graph->level) {
      /*
       * create levels
       */
      graphCreateLevels (graph, levels);
    } else {
      /*
       * maybee we have to add some levels
       */
      if (levels > graph->levels) {
          graphAddLevels (graph, levels - graph->levels);
      }
    }
    for ( i = 0 ; i < PRIME ; i++ ) {
      node = graph->hashtab[i] ;
      while (node) {
          /*
           * add only new nodes ..
           */
          if (!node->layouted) {
            /* 
             * node was previously not
             * layouted -- add it
             */
            levelsInsertNode (graph,node, node->level);
          }
          node = node->hashnext;
                  
      }
    }
    if (pullup) {
      sortPullupNodes (graph);            /* optimize */
    }
}
      
/*
 * levelsIndex
 * apply an index to a level: the first node of a level will get
 * index=1, the second index=2, ....
 */

void Layout::levelsIndex (NODE **level)
{
    int i = 1;
    NODE *node;

    node = *level ;
    while (node) {
      node->index = i;
      i++;
      node = node->right;
    }
}

/*
 * levelsLength
 * return the number of elements of a given level
 */

int Layout::levelsLength (NODE **level) 
{
    NODE *node;
    int len = 0;

    node = *level;
    while (node) {
      len++;
      node = node->right;
    }
    return len;
}


/*****************************************************************************
    Sorting functions
*****************************************************************************/

// arnaud.desitter@nag.co.uk says `extern "C"' is required to fix
// warnings on Sun CC 5.x, which enforces a standard C++ rule where
// pointer to function are extern "C" or extern "C++" (see Sun C++
// migration guide).
extern "C"{
    static int _sortCmpCenters(const void* k1, const void* k2)
    {
      NODE **_n1 = (NODE **)k1;
      NODE **_n2 = (NODE **)k2;
      return Layout::sortCmpCenters(_n1,_n2);
    }

    static int _sortCmpUpperPrio(const void* k1, const void* k2)
    {
      NODE **_n1 = (NODE **)k1;
      NODE **_n2 = (NODE **)k2;
      return Layout::sortCmpUpperPrio(_n1,_n2);
    }

    static int _sortCmpLowerPrio(const void* k1, const void* k2)
    {
      NODE **_n1 = (NODE **)k1;
      NODE **_n2 = (NODE **)k2;
      return Layout::sortCmpLowerPrio(_n1,_n2);
    }
}



/*
 * sortApplyLevel
 * apply a level to each node of the graph and return the number of
 * levels inside the graph
 */

int Layout::sortApplyLevel (GRAPH *graph)
{
    int level ;
    int maxlevel = 0;
    NODE *node;
    int i;

    for (i=0; i < PRIME; i++) {
      node = graph->hashtab[i];
      while (node) {
          if (node->level == NOLEVEL) {
            level = distance (node,node);
          } else {
            level = node->level;
          }
          maxlevel = ( level > maxlevel ? level : maxlevel );
          node = node->hashnext;
      }
    }
    return ++maxlevel;
}

/*
 * sortPullupNodes
 * each node should reside one level below the minimum of the levels
 * of its anchestors.
 * This function improves the assigned levels in the way mentioned
 * above. This works only for graph with no hints inside !
 */

void Layout::sortPullupNodes (GRAPH *graph)
{
    NODE **level;
    NODE *node;
    NODE *rightnode;
    int newlevel ;
      
    if (graph->levels < 2) {
      return ;
    }
    level = graph->level+(graph->levels-1);
    do {
      level--;
      node = *level;
            
      while (node) {
          newlevel = minimumLevel (node) - 1;
          rightnode = node->right;
          if (newlevel != node->level) {
            /*
             * pull it up
             */
            levelsRemoveNode (graph, node, node->level);
            node->left = (NODE*) 0;
            node->right = (NODE*) 0;
            levelsInsertNode (graph, node, newlevel);
          }
          node = rightnode;
      }
            
    } while ( level != graph->level);
}


/*
 * minimumLevel
 * return the minimum level of the anchestors of a given regular node.
 */

int Layout::minimumLevel (NODE *node)
{
    EDGE *edge;
    int min = 1000 ;
    int tmp;

    if (node->type != Regular) {
      fprintf (stderr,"minimumLevel: not a regular Node!\n");
      exit (NOT_REGULAR);
    }
      
    edge = node->attr.node.up.head ;
    if (edge) {
      while (edge) {
          tmp = edge->target->level;
          min = ( tmp < min ? tmp : min);
          edge = edge->next;
      }
      return min;
    } else {
      return node->level + 1;
    }
}
            

/*
 * distance
 * determine the max. number of descendants of a given node. Enter this
 * value to the 'level' component and return it. 
 */

int Layout::distance (NODE *node, NODE *origin)
{
    int dist = 0;
    int maxdist = 0;
    EDGE *edge;
    EDGE *tmpedge;

    node->mark = origin;
    /*
     * have a look at the type of the node ...
     */
    if (node->type == Regular) {
      edge = node->attr.node.down.head ;
      while (edge) {
          if (edge->node->level != NOLEVEL) {
            dist = 1 + edge->node->level;
            edge = edge->next;
          } else if ( edge->node->mark == origin ) {
            /*
             * cycle detected ...
             * there is a cycle (following the
             * down-references) which is 
             * closed by the path from node to
             * edge->node
             * The cycle can be brocken up by 
             * inverting the edge between
             * node and edge->node.
             */
            dist = 0;
            tmpedge = edge->next;
            graphInvertEdge (node,edge->node);
            edge = tmpedge;
          } else {
            tmpedge = edge->next;
            dist = 1 + distance (edge->node, origin);
            edge = tmpedge;
          }
          maxdist = (dist > maxdist ? dist : maxdist);
      }
    }
    else {
      fprintf (stderr,"distance: unleveled Hint!\n");
      exit (INTERNAL);
    }
    /*
     * enter the distance to the node and return maxdist
     */
    node->level = maxdist;
    return maxdist;
}

/*
 * sortInsertHints
 * check the descendants of each node. If a descendant is more than one
 * level apart insert hints on the level inbetween.
 */

void Layout::sortInsertHints (GRAPH *graph) 
{
    NODE *node;
    NODE **level;
    int i;

    level = graph->level+(graph->levels-1);
    for ( i = 0 ; i < graph->levels ; i++ ) {
      node = *level;
      while (node) {
          sortCheckNode (graph,node);
          node = node->right;
      }
      level--;
    }
}

/*
 * sortCheckNode
 * check the descaendants of a node: if a descandant is more than
 * one level away insert a hint node.
 */

void Layout::sortCheckNode (GRAPH *graph, NODE *node)
{
    EDGE *edge;
    NODE *des;
    NODE *hint;

    if (node->type == Regular) {
      edge = node->attr.node.down.head ;
      while (edge) {
          des = edge->node;
          if (des->level < node->level-1) {
            /* 
             * insert hint
             */
            hint = graphInsertHint (graph,node, des);
            levelsInsertNode (graph, hint, node->level-1);
          }
          edge = edge->next;
      }
    } else {
      if ( node->attr.hint.down
           && node->attr.hint.down->level < node->level-1 ) {
          /*
           * insert hint
           */
          hint = graphInsertHint (graph,node, 
                            node->attr.hint.down);
          levelsInsertNode (graph, hint, node->level-1);
      }
    }
}


/*
 * sortNodeUpperBary
 * calculate the bary center of a node according to its ancestors.
 * ATTENTION: the 'index'-components of the anchestors must be valid!
 */
      

int Layout::sortNodeUpperBary (NODE *node)
{
    int sum = 0;
    int count = 0;
    EDGE *upnode;

    if (node->type == Hint) {
      if (node->attr.hint.up) {
          return (node->attr.hint.up->index * 10);
      } else {
          return 0;
      }
    } else {
      if (node->attr.node.up.length == 0) {
          return 0;
      } else {
          upnode = node->attr.node.up.head;
          while (upnode) {
            sum += upnode->node->index;
            count++;
            upnode=upnode->next;
          }
          return ( (sum * 10) / count );
      }
    }
}
                  

/*
 * sortNodeLowerBary
 * calculate the bary center og a node according to its descendants.
 * ATTENTION: the 'index'-components of the descendabts must be valid!
 */
      
int Layout::sortNodeLowerBary (NODE *node)
{
    int sum = 0;
    int count = 0;
    EDGE *downnode;

    if (node->type == Hint) {
      if (node->attr.hint.down) {
          return (node->attr.hint.down->index * 10);
      } else {
          return 0;
      }
    } else {
      if (node->attr.node.down.length == 0) {
          return 0;
      } else {
          downnode = node->attr.node.down.head;
          while (downnode) {
            sum += downnode->node->index;
            count++;
            downnode=downnode->next;
          }
          return ( (sum * 10) / count );
      }
    }
}
                  
/*
 * sortGraphUpperBary
 * assign to every node of every level its bary center according to its
 * anchestors and sort each level by the centers. The algorithm will
 * start with the top levels and will move down. If the flag is set,
 * the determined center will not be written to 'center' but 'upcenter' 
 * and the level won't be sorted. This will be done later by the 
 * sortAvrgCenter-function.
 */

void Layout::sortGraphUpperBary (GRAPH *graph)
{
    NODE **uplevel;
    NODE **level;
    NODE *node;

    if (graph->levels < 2) {
      /* only one level - nothing to do */
      return;
    }

    uplevel = graph->level+(graph->levels-1) ;
    level = uplevel;

    do {
      level--;
      levelsIndex (uplevel);
      node = *level;
      while (node) {
          node->center = sortNodeUpperBary (node);
          node = node->right;
      }
      sortByCenter (level);
      uplevel--;
            
    } while (level != graph->level);

}

/*
 * sortGraphLowerBary
 * assign to every node of every level its bary center according to its
 * descendants and sort each level by the centers. The algorithm will
 * start with the lowest levels and will move up.
 * If the flag is set,
 * the determined center will not be written to 'center' but 'downcenter' 
 * and the level won't be sorted. This will be done later by the 
 * sortAvrgCenter-function.
 */

void Layout::sortGraphLowerBary (GRAPH *graph)
{
    NODE **downlevel;
    NODE **toplevel;
    NODE **level;
    NODE *node;

    if (graph->levels < 2) {
      /* only one level - nothing to do */
      return;
    }

    toplevel = graph->level+(graph->levels-1);
    downlevel = graph->level ;
    level = downlevel;

    do {
      level++;
      levelsIndex (downlevel);
      node = *level;
      while (node) {
          node->center = sortNodeLowerBary (node);
          node = node->right;
      }
      sortByCenter (level);
      downlevel++;
            
    } while (level != toplevel);
}

/*
 * sortByCenter
 * sort a level by the bary centers of its nodes. The function will 
 * first calculate the order and then rebuild the level (i.e. its
 * list. 
 */

void Layout::sortByCenter (NODE **level) 
{
    NODE **index;
    NODE **tmp;
    NODE *node;
    int len = levelsLength (level);
    int i;
      
    if (len < 2) {
      return;
    }
      
    index = (NODE**) malloc (sizeof (NODE*) * len);
    if (!index) {
      fprintf (stderr,"sortByCenter: out of memory!\n");
      exit (MEMORY_ERROR);
    }

    /* fill the index */
      
    tmp = index;
    node = *level;
    while (node) {
      *(tmp++) = node;
      node = node->right;
    }

    /* sort the index */

    qsort ( (char *) index , len, sizeof (NODE*), _sortCmpCenters );

    /*
     * build up a new list according to the sorted index
     */

    tmp = index;
    *level = *tmp;
    (*level)->left = (NODE*) 0;

    for (i=1 ; i < len ; i++) {
      (*tmp)->right = *(tmp+1);
      (*(tmp+1))->left = *tmp;
      tmp++;
    }
    (*tmp)->right = (NODE*) 0;

    free ( (char *) index);
}

#if 0
/*
 * sortAvrgCenter
 * calculate the average bary center for each node by its upper and 
 * lower bary center. This value will be stored in 'center' of each
 * node. Each level will be sorted by the average bary center.
 */

void Layout::sortAvrgCenter (GRAPH *graph)
{
    NODE **level;
    NODE *node;
    int i;
      
    level = graph->level;
    for (i=0; i < graph->levels; i++) {
      node = *level;
      while (node) {
          node->center = (node->upcenter + node->downcenter) / 2;
          node = node->right;
      }
      sortByCenter (level);
      level++;
    }
}
            
#endif

/*
 * sortCmpCenters
 * compare the centers of two nodes
 */

int Layout::sortCmpCenters (NODE **_n1, NODE **_n2) 
{     
    NODE *n1 = *_n1;
    NODE *n2 = *_n2;

    // Compare by center
    int ret = n1->center - n2->center;
    if (ret != 0 || compare_callback == 0)
      return ret;

    // Compare by target name
    while (n1 && n1->type == Hint)
      n1 = n1->attr.hint.target;
    while (n2 && n2->type == Hint)
      n2 = n2->attr.hint.target;

    assert (n1 != 0);
    assert (n1->type == Regular);
    assert (n2 != 0);
    assert (n2->type == Regular);

    const char *label1 = n1->attr.node.label;
    const char *label2 = n2->attr.node.label;

    return compare_callback(label1, label2);
}

                        
                         
/*
 * sortInitX
 * assign initial x-ccordinates to all nodes. Nodes of the same level 
 * will have at least the minimum distance.
 * The x- and y-ccordinates of a node represent its center!
 */

void Layout::sortInitX (GRAPH *graph) 
{
    NODE **level = graph->level;
    NODE *node;
    int x;
    int nodex;
    int i;
      
    for (i=0; i < graph->levels; i++) {
      node = *level;
      x = 0;
      while (node) {
          if (node->type == Regular) {
            nodex = x + node->attr.node.w / 2;
          } else {
            nodex = x ;
          }
          node->x = nodex;
          x += graph->minxdist ;
          if (node->type == Regular) {
            x +=  node->attr.node.w ;
          } 
          node = node->right;
      }
      level++;
    }
}

/*
 * sortGraphUpX
 * assign a x-coordinate to each node of the graph. Each x-coordinate
 * is determined by the anchestors of each node. The function starts
 * with the highest level and moves down.
 */

void Layout::sortGraphUpX (GRAPH *graph)
{
    NODE **level;

    if (graph->levels < 2) {
      /* only one level - nothing to do */
      return;
    }

    level = graph->level+(graph->levels-1) ;

    do {
      level--;
      sortLevelUpX (level, graph->minxdist);
            
    } while (level != graph->level);
      
}

/*
 * sortGraphDownX
 * assign a x-coordinate to each node of the graph. Each x-coordinate
 * is determined by the descendants of each node. The function starts
 * with the lowest level and moves up.
 */

void Layout::sortGraphDownX (GRAPH *graph)
{
    NODE **level;
    NODE **toplevel = graph->level+(graph->levels-1);

    if (graph->levels < 2) {
      /* only one level - nothing to do */
      return;
    }

    level = graph->level;

    do {
      level++;
      sortLevelDownX (level, graph->minxdist);
    } while (level != toplevel);
}

/*
 * sortLevelUpX
 * assign x-ccordinates to each node of a level. The preferred x-position 
 * of a nodes is the average x-position of its anchestors. For resolving
 * conflicts each node gets a priority depending on its number of
 * anchestors. Nodes with high priority will be placed on its preferred
 * position with a higher probability.
 */

void Layout::sortLevelUpX (NODE **level, int dist)
{
    NODE **index;
    NODE **tmp;
    NODE *node;

    int len = levelsLength (level);
    int newx;

    index = (NODE**) malloc (sizeof (NODE*) * (len+1));
    if (!index) {
      fprintf (stderr,"sortByCenter: out of memory!\n");
      exit (MEMORY_ERROR);
    }

    /* fill the index */
      
    tmp = index;
    node = *level;
    while (node) {
      *(tmp++) = node;
      node = node->right;
    }
    *tmp = (NODE*) 0;

    /* 
     * sort the index by node priority (from low to high)
     */

    qsort ( (char *)index, len, sizeof (NODE*), _sortCmpUpperPrio);

    tmp = index;
    while (*tmp) {
      newx = sortAvrgUpperX (*tmp) ;
      sortMove (*tmp, newx, dist);
      tmp++;
    }

    free ( (char *) index);
}

/*
 * sortLevelDownX
 * assign x-ccordinates to each node of a level. The preferred x-position 
 * of a nodes is the average x-position of its descendants. For resolving
 * conflicts each node gets a priority depending on its number of
 * descendants. Nodes with high priority will be placed on its preferred
 * position with a higher probability.
 */

void Layout::sortLevelDownX (NODE **level, int dist)
{
    NODE **index;
    NODE **tmp;
    NODE *node;

    int len = levelsLength (level);
    int newx;

    index = (NODE**) malloc (sizeof (NODE*) * (len+1));
    if (!index) {
      fprintf (stderr,"sortLevelDownX: out of memory!\n");
      exit (MEMORY_ERROR);
    }

    /* fill the index */
      
    tmp = index;
    node = *level;
    while (node) {
      *(tmp++) = node;
      node = node->right;
    }
    *tmp = (NODE*) 0;

    /* 
     * sort the index by node priority (from low to high)
     */

    qsort ( (char *)index, len, sizeof (NODE*), _sortCmpLowerPrio);

    tmp = index;
    while (*tmp) {
      newx = sortAvrgLowerX (*tmp) ;
      sortMove (*tmp, newx, dist);
      tmp++;
    }

    free ( (char *) index);
}

/*
 * sortLeftSpace
 * return the free space to the left of a node. The free space is the 
 * ammount of space you can push all nodes to the left without falling
 * below the minimum distance between two nodes.
 */

int Layout::sortLeftSpace (NODE *node, int dist) 
{
    int space = 0;
    NODE *left;
      
    left = node->left;
    while (left) {
      space += node->x - left->x - dist;
      if (node->type == Regular) {
          space -= node->attr.node.w / 2;
      }
      if (left->type == Regular) {
          space -= left->attr.node.w / 2;
      }
      node = left;
      left = left->left;
    }
    space += node->x ;
    if (node->type == Regular) {
      space -= node->attr.node.w / 2;
    }
    return space;
}

/*
 * sortMoveLeft
 * move a given node to the left. All nodes to the left of the node
 * will be moved to the left if required but the minimum distance between 
 * two nodes won't be influenced. The function assumes, that there is at least
 * enough space to the left of the node!
 */

void Layout::sortMoveLeft (NODE *node, int newx, int dist)
{
    int maxleftx = 0;
    int ready    = 0;

    do {
      node->x = newx;
      if (node->left) {
          maxleftx = newx - dist;
          if (node->type == Regular) {
            maxleftx -= node->attr.node.w / 2;
          }
          if (node->left->type == Regular) {
            maxleftx -= node->left->attr.node.w / 2;
          }
          ready = ( node->left->x < maxleftx );
                  
      }
      node = node->left;                  
      newx = maxleftx;

    } while (node && !ready) ;
      
}

/*
 * sortMoveRight
 * move a given node to the right. All nodes to the right of the node
 * will be moved to the right if required but the minimum distance between 
 * two nodes won't be influenced. 
 */

void Layout::sortMoveRight (NODE *node, int newx, int mindist)
{
    int minrightx = 0;
    int ready     = 0;

    do {
      node->x = newx;

      if (node->right) {
          minrightx = newx + mindist ;
          if (node->type == Regular) {
            minrightx += node->attr.node.w /2;
          }
          if (node->right->type == Regular) {
            minrightx += node->right->attr.node.w /2;
          }
      }
      ready =  !(node->right) ||  (node->right->x > minrightx );

      node = node->right;
      newx = minrightx;

    } while (!ready) ;
}

/*
 * sortMove
 * move a node to a new x-ccordinate. All other nodes of the same level
 * will be moved, too if required. The minimum distance between two 
 * node won't be influenced.
 */ 

void Layout::sortMove (NODE *node, int newx, int mindist)
{
    int leftspace;
    int oldx;
    int move;

    oldx = node->x;
    if (newx < oldx) {
      move = oldx - newx;
      leftspace = sortLeftSpace (node, mindist);
      if ( move > leftspace ) {
          newx = oldx - leftspace;
      }
      sortMoveLeft (node,newx,mindist);
    } else if (newx > oldx) {
      sortMoveRight (node,newx,mindist);
    }
}
      
/*
 * sortAvrgUpperX
 * determine the average x-position of a nodes anchestors.
 */

int Layout::sortAvrgUpperX (NODE *node)
{
    EDGE *edge;
    int sumx = 0;
    int count = 0;

    if (node->type == Regular) {
      edge = node->attr.node.up.head ;
      while (edge) {
          sumx += edge->node->x;
          count++;
          edge = edge->next;
      }
    } else if (node->attr.hint.up) {
      sumx = node->attr.hint.up->x;
      count = 1;
    }
      
    if (count) {
      return (sumx / count);
    } else {
      return ((node->x * 3) / 4);
    }
}
/*
 * sortAvrgLowerX
 * determine the average x-position of a nodes descendants.
 */

int Layout::sortAvrgLowerX (NODE *node)
{
    EDGE *edge;
    int sumx = 0;
    int count = 0;

    if (node->type == Regular) {
      edge = node->attr.node.down.head ;
      while (edge) {
          sumx += edge->node->x;
          count++;
          edge = edge->next;
      }
    } else if (node->attr.hint.down) {
      sumx = node->attr.hint.down->x;
      count = 1;
    }
      
    if (count) {
      return (sumx / count);
    } else {
      return ((node->x * 3) / 4);
    }
}

/*
 * sortCmpUpperPrio
 * compare two nodes by its x-layout-priority: hint nodes will have
 * the highest priority, other nodes will have a priority equal to
 * their number of anchestors.
 */

int Layout::sortCmpUpperPrio (NODE **fst, NODE **snd)
{
    int fstprio, sndprio;

    if ( (*fst)->type == Hint ) {
      fstprio = HINTPRIO;
    } else {
      fstprio = (*fst)->attr.node.up.length ;
    }
    if ( (*snd)->type == Hint ) {
      sndprio = HINTPRIO;
    } else {
      sndprio = (*snd)->attr.node.up.length ;
    }

    return (fstprio - sndprio);
}

/*
 * sortCmpLowerPrio
 * compare two nodes by its x-layout-priority: hint nodes will have
 * the highest priority, other nodes will have a priority equal to
 * their number of descendants.
 */

int Layout::sortCmpLowerPrio (NODE **fst, NODE **snd)
{
    int fstprio, sndprio;

    if ( (*fst)->type == Hint ) {
      fstprio = HINTPRIO;
    } else {
      fstprio = (*fst)->attr.node.down.length ;
    }
    if ( (*snd)->type == Hint ) {
      sndprio = HINTPRIO;
    } else {
      sndprio = (*snd)->attr.node.down.length ;
    }

    return (fstprio - sndprio);
}

/*
 * sortLevelVertical
 * apply y-coordinates to all nodes of a level. Attention: the coordinates 
 * of a node represent its center! The function will return the highest
 * y-coordinate covered by the level. 
 */

int Layout::sortLevelVertical (NODE **level, int miny, int minydist)
{
    int length = 0 ;
    int maxheight = 0;
    int newy;
    NODE *node;

    /* 
     * calculate the max. height of the nodes at this level
     */

    node = *level;
    while (node) {
      if (node->type == Regular && 
          node->attr.node.h > maxheight) {
          maxheight = node->attr.node.h;
      }
      length++;
      node = node->right;
    }
    /*
     * the distance to the previous level will be 'minydist'
     * and some additional dynamic space.
     */
      
    newy = miny + minydist + maxheight / 2 + (length * maxheight) / 5;

    node = *level;
    while (node) {
      node->y = newy;
      node = node->right;
    }

    return newy + maxheight / 2;
}
      
/*
 * sortGraphVertical
 * apply a y-coordinate to each node.
 */

void Layout::sortGraphVertical (GRAPH *graph)
{
    int y = (- graph->minydist) + 1; /* for top level  */
    NODE **level;
    int i;
      
    if (!graph->levels) {
      /* nothing to do */
      return;
    }

    level = graph->level+(graph->levels-1);
    for (i = 0; i < graph->levels; i++) {
      y = sortLevelVertical (level,y, graph->minydist);
      level-- ;
    } 
}

Generated by  Doxygen 1.6.0   Back to index