home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1999 March / PCWK3A99.iso / Linux / DDD331 / DDD-3_1_.000 / DDD-3_1_ / ddd-3.1.1 / ddd / layout.C < prev    next >
Encoding:
C/C++ Source or Header  |  1998-03-25  |  60.9 KB  |  2,984 lines
  1. // $Id: layout.C,v 1.13 1998/03/25 12:46:06 zeller Exp $ -*- C++ -*-
  2. // Graph layout functions
  3.  
  4. // Copyright (C) 1995 Technische Universitaet Braunschweig, Germany.
  5. // Written by Christian Lindig <lindig@ips.cs.tu-bs.de>.
  6. // 
  7. // This file is part of DDD.
  8. // 
  9. // DDD is free software; you can redistribute it and/or
  10. // modify it under the terms of the GNU General Public
  11. // License as published by the Free Software Foundation; either
  12. // version 2 of the License, or (at your option) any later version.
  13. // 
  14. // DDD is distributed in the hope that it will be useful,
  15. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  16. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  17. // See the GNU General Public License for more details.
  18. // 
  19. // You should have received a copy of the GNU General Public
  20. // License along with DDD -- see the file COPYING.
  21. // If not, write to the Free Software Foundation, Inc.,
  22. // 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  23. // 
  24. // DDD is the data display debugger.
  25. // For details, see the DDD World-Wide-Web page, 
  26. // `http://www.cs.tu-bs.de/softech/ddd/',
  27. // or send a mail to the DDD developers <ddd@ips.cs.tu-bs.de>.
  28.  
  29. char layout_rcsid[] = 
  30.     "$Id: layout.C,v 1.13 1998/03/25 12:46:06 zeller Exp $";
  31.  
  32. #ifdef __GNUG__
  33. #pragma implementation
  34. #endif
  35.  
  36. #include "layout.h"
  37. #include "assert.h"
  38.  
  39. #include <stdio.h>
  40. #include <stdlib.h>
  41. #include <string.h>
  42. #include <X11/StringDefs.h>
  43.  
  44.  
  45. // This is an implementation of the Sugiyama/Misue graph layout
  46. // algorithm.  For details, see
  47. // 
  48. // @Article{sugiyama/misue/visualization,
  49. //   author =       "Kozo Sugiyama and Kazuo Misue",
  50. //   title =        "Visualization of Structural Information: Automatic
  51. //                  Drawing of Compound Digraphs",
  52. //   journal =      "IEEE Transactions on Systems, Man, and Cybernetics",
  53. //   year =         "1991",
  54. //   volume =       "SMC-21",
  55. //   number =       "4",
  56. //   pages =        "876--892",
  57. //   month =        "July/August",
  58. // }
  59.  
  60.  
  61.  
  62. const int MINXDIST    = 20;
  63. const int MINYDIST    = 20;
  64. const int XITERATIONS = 6;
  65. const int REVERSE     = FALSE;
  66.  
  67. /*
  68.  * PULLUP
  69.  * if TRUE each node will be placed on the highest level possible. 
  70.  * Otherwise each node will be placed on the level determined 
  71.  * by a topological sort.
  72.  */
  73. const int PULLUP     = FALSE;
  74.  
  75. const int HINTPRIO   = 100;
  76.  
  77. const int NOLEVEL    = -1;
  78. const int NOPOSITION = -1;
  79.  
  80. /*
  81.  * definitions for return values
  82.  */
  83.  
  84. const int MEMORY_ERROR  = 1;
  85. const int NOT_MEMBER    = 3;
  86. const int NODE_TYPE     = 8;
  87. const int LEVEL_ERROR   = 9;
  88. const int NO_EDGE       = 10;
  89. const int INTERNAL      = 11;
  90. const int NOT_REGULAR   = 12;
  91.  
  92.  
  93. /*****************************************************************************
  94.     Interface layer
  95. *****************************************************************************/
  96.  
  97. void (*Layout::node_callback)(char *, int, int) = 0;
  98. void (*Layout::hint_callback)(char *, char *, int, int) = 0;
  99. int  (*Layout::compare_callback)(char *, char *) = 0;
  100.  
  101. #define UP 0
  102. #define DOWN 1
  103.  
  104. #define WARN_IF_ALREADY_PRESENT 0
  105.  
  106. // GRAPHTAB Layout::tab;
  107. static GRAPHTAB tab;
  108.  
  109. /*
  110.  * add_graph
  111.  * define a new graph
  112.  * TODO: this is a dummy - we don't distinct between different graphs yet.
  113.  */
  114.  
  115. void Layout::add_graph (char *g)
  116.  
  117. {
  118.     GRAPH *graph;
  119.     graph = graphGet (&tab,g);
  120.     if (graph) {
  121. #if WARN_IF_ALREADY_PRESENT
  122.     fprintf (stderr,"add-graph warning: ");
  123.     fprintf (stderr,"graph %s exists - not added!\n", g);
  124. #endif /* WARN_IF_ALREADY_PRESENT */
  125.     return;
  126.     } else {
  127.     graphNew (&tab,g);
  128.     }
  129. }
  130.  
  131. /* 
  132.  * add_node
  133.  * N is added to G, with all node attributes set to default values.  G
  134.  * must exist. If there is already a node called N, this action has no
  135.  * effect.
  136.  */
  137.  
  138. void Layout::add_node (char *g, char *node)
  139. { 
  140.     NODE *nd;
  141.     GRAPH *graph;
  142.     ID id;
  143.  
  144.     graph = graphGet (&tab,g);
  145.     if (!graph) {
  146.     fprintf (stderr,"add-node warning: graph %s unknown\n",g);
  147.     return ;
  148.     }
  149.     id.label = node;
  150.     /*
  151.      * check for dublicates
  152.      */
  153.     nd = graphGetNode (graph,&id,Regular);
  154.     if (nd) {
  155. #if WARN_IF_ALREADY_PRESENT
  156.     fprintf (stderr,"add_node: Warning - node already");
  157.     fprintf (stderr,"member of the graph - not added\n");
  158. #endif /* WARN_IF_ALREADY_PRESENT */
  159.     return ;
  160.     }
  161.     /*
  162.      * enter node with default width and height
  163.      */
  164.     nd  = graphEnterNode (graph, &id, Regular);
  165.     nd->attr.node.w = 10 * strlen (node);
  166.     nd->attr.node.h = 30 ;
  167. }
  168.     
  169. /* 
  170.  * add_edge
  171.  * The edge leading from N1 to N2 is added to the graph G, with all edge
  172.  * attributes set to default values.  G, N1 and N2 must exist.  If there
  173.  * is already an edge (N1, N2), this action has no effect.
  174.  * TODO: check, if edge allready exists.
  175.  */ 
  176.  
  177. void Layout::add_edge (char *g, char *node1, char *node2)
  178. {
  179.     NODE *source;
  180.     NODE *target;
  181.     GRAPH *graph;
  182.     ID id1;
  183.     ID id2;
  184.  
  185.     id1.label = node1;
  186.     id2.label = node2;
  187.  
  188.     graph = graphGet (&tab,g);
  189.     if (!graph) {
  190.     fprintf (stderr,"add-edge warning: graph %s unknown\n",g);
  191.     return ;
  192.     }
  193.     source = graphGetNode (graph, &id1, Regular);
  194.     if (!source) {
  195.     fprintf (stderr,"add_edge: unknown node %s\n",node1);
  196.     exit (NOT_MEMBER);
  197.     }
  198.     target = graphGetNode (graph, &id2, Regular);
  199.     if (!target) {
  200.     fprintf (stderr,"add_edge: unknown node %s\n",node2);
  201.     exit (NOT_MEMBER);
  202.     }
  203.     if (source == target) {
  204.     /*
  205.      * LOOP ! Mark the node
  206.      */
  207.     source->loop = 1;
  208.     } else {
  209.     graphInsertEdge (graph, source,target);
  210.     }
  211. }
  212.  
  213.  
  214. /*
  215.  * set_node_width
  216.  * The width of N is set to W.  G and N must exist.  The old width is
  217.  * overwritten.
  218.  */
  219.  
  220. void Layout::set_node_width (char *g, char *node, int width)
  221. {
  222.     NODE *nd;
  223.     GRAPH *graph;
  224.     ID id;
  225.  
  226.     graph = graphGet (&tab,g);
  227.     if (!graph) {
  228.     fprintf (stderr,"set-node-width warning: ");
  229.     fprintf (stderr,"graph %s unknown\n",g);
  230.     return ;
  231.     }
  232.     id.label = node;
  233.     nd = graphGetNode (graph, &id, Regular);
  234.     if (!nd) {
  235.     fprintf (stderr,"set_node_width: node %s unknown to %s\n",
  236.          node, g);
  237.     return ;
  238.     }
  239.     nd->attr.node.w = width;
  240. }
  241.     
  242.  
  243. /*
  244.  * set_node_height
  245.  * The height of N is set to H.  G and N must exist.  The old width is
  246.  * overwritten.
  247.  */
  248.  
  249. void Layout::set_node_height (char *g, char *node, int height)
  250. {
  251.     NODE *nd;
  252.     GRAPH *graph;
  253.     ID id;
  254.  
  255.     graph = graphGet (&tab,g);
  256.     if (!graph) {
  257.     fprintf (stderr,"set-node warning: graph %s unknown\n",g);
  258.     return ;
  259.     }
  260.     id.label = node;
  261.     nd = graphGetNode (graph, &id, Regular);
  262.     if (!nd) {
  263.     fprintf (stderr,"set_node_width: node %s unknown to %s\n",
  264.          node, g);
  265.     return ;
  266.     }
  267.     nd->attr.node.h = height;
  268. }
  269.     
  270. /*
  271.  * set_node_position
  272.  * The position of N is set to (X, Y).  G and N must exist.  The old
  273.  * position is overwritten.
  274.  */
  275.  
  276. void Layout::set_node_position (char *g, char *node, int x, int y)
  277. {
  278.     NODE *nd;
  279.     GRAPH *graph;
  280.     ID id;
  281.  
  282.     graph = graphGet (&tab,g);
  283.     if (!graph) {
  284.     fprintf (stderr,"set-node-position warning: ");
  285.     fprintf (stderr,"graph %s unknown\n",g);
  286.     return ;
  287.     }
  288.     id.label = node;
  289.     nd = graphGetNode (graph, &id, Regular);
  290.     if (!nd) {
  291.     fprintf (stderr,"set_node_position: node %s unknown to %s\n",
  292.          node, g);
  293.     return ;
  294.     }
  295.     nd->oldx = x;
  296.     nd->oldy = y;
  297. }
  298.  
  299. /*
  300.  * add_edge_hint
  301.  * The hint (X, Y) is added to the edge (N1, N2).  This means that the
  302.  * edge is supposed to touch this position.  If there is already a hint
  303.  * (X, Y), this has no effect.
  304.  */
  305.  
  306. void Layout::add_edge_hint (char *, char *, char *, int, int)
  307. {
  308. }
  309.  
  310. /* 
  311.  * remove_edge_hint The hint (X, Y) is remove from the edge (N1, N2).
  312.  * If there is no such hint, this action has no effect.  
  313.  */
  314.  
  315. void Layout::remove_edge_hint (char *, char *, char *, int, int)
  316. {
  317. }
  318.  
  319. /* 
  320.  * remove_edge 
  321.  * The edge (N1, N2) is removed from G.  If there is no
  322.  * such edge, this action has no effect.  
  323.  */
  324.  
  325. void Layout::remove_edge (char *g, char *node1, char *node2)
  326. {
  327.     GRAPH *graph;
  328.     NODE *source;
  329.     NODE *target;
  330.     NODE *hint;
  331.     NODE *tmp;
  332.     EDGE *toTarget;
  333.     EDGE *toSource;
  334.     ID id1, id2, tmpid;
  335.     int direction;        /* UP or DOWN */
  336.  
  337.     id1.label = node1;
  338.     id2.label = node2;
  339.  
  340.     graph = graphGet (&tab,g);
  341.     if (!graph) {
  342.     fprintf (stderr,"remove-edge warning: graph %s unknown\n",g);
  343.     return ;
  344.     }
  345.  
  346.     source = graphGetNode (graph, &id1, Regular);
  347.     if (!source) {
  348.     fprintf (stderr,"remove_edge: unknown node %s\n",node1);
  349.     return;
  350.     }
  351.     target = graphGetNode (graph, &id2, Regular);
  352.     if (!target) {
  353.     fprintf (stderr,"remove_edge: unknown node %s\n",node2);
  354.     return;
  355.     }
  356.  
  357.     /*
  358.      * try to find the edge between the two nodes
  359.      */
  360.  
  361.     toTarget = graphFindEdgeAtSource (source,target);
  362.     if (!toTarget) {
  363.     fprintf (stderr,"remove_edge: can't find edge from");
  364.     fprintf (stderr," %s to %s \n", node1, node2);
  365.     return ;
  366.     }
  367.     toSource = graphFindEdgeAtTarget (source,target);
  368.     if (!toSource) {
  369.     fprintf (stderr,"remove_edge: can't find edge from");
  370.     fprintf (stderr," %s to %s \n", node1, node2);
  371.     return;
  372.     }
  373.  
  374.     /*
  375.      * remove all hints
  376.      * start at the source node and move to the target node
  377.      * removing all hints on that way. We have to determine
  378.      * if we have to go UP ord DOWN at each hint we find, because
  379.      * the edge may be inverted!
  380.      */
  381.  
  382.     hint = toTarget->node;
  383.     if (hint->type == Hint && hint->attr.hint.up == source) {
  384.     direction = DOWN;
  385.     } else {
  386.     direction = UP;
  387.     }
  388.     while (hint != target) {
  389.     if (hint->level != NOLEVEL) {
  390.         /*
  391.          * remove hint form its level
  392.          */
  393.         levelsRemoveNode (graph, hint, hint->level);
  394.     }
  395.     tmp = ( direction == DOWN ? 
  396.         hint->attr.hint.down : hint->attr.hint.up );
  397.     tmpid.id = hint->attr.hint.id;
  398.     graphRemoveNode (graph, &tmpid, Hint);
  399.     hint = tmp;
  400.     }
  401.  
  402.     /*
  403.      * remove edges
  404.      */
  405.     
  406.     listRemoveEdge (&source->attr.node.down, toTarget);
  407.     listRemoveEdge (&target->attr.node.up, toSource);    
  408. }
  409.  
  410. /* 
  411.  * remove_node
  412.  * The node N is removed from G. All edges coming
  413.  * from or leading to N are also removed. If there is no such node,
  414.  * this action has no effect.
  415.  */
  416.  
  417. void Layout::remove_node (char *g, char *label)
  418. {
  419.     GRAPH *graph;
  420.     NODE *node;
  421.     EDGE *edge;
  422.     ID id;
  423.  
  424.     graph = graphGet (&tab,g);
  425.     if (!graph) {
  426.     fprintf (stderr,"remove-edge warning: graph %s unknown\n",g);
  427.     return ;
  428.     }
  429.     id.label = label;
  430.     node = graphGetNode (graph, &id, Regular);
  431.     if (!node ) {
  432.     fprintf (stderr,"remove_node: unknown node %s\n", label);
  433.     exit (NOT_MEMBER);
  434.     }
  435.     if (node->level != NOLEVEL) {
  436.     levelsRemoveNode (graph, node, node->level);
  437.     }
  438.     /* 
  439.      * remove all edges leading down ...
  440.      */
  441.  
  442.     edge = node->attr.node.down.head ;
  443.     while (edge) {
  444.     remove_edge (g,label, edge->target->attr.node.label);
  445.     edge = edge->next;
  446.     }
  447.     
  448.     /* 
  449.      * remove all edges leading up  ...
  450.      */
  451.  
  452.     edge = node->attr.node.up.head ;
  453.     while (edge) {
  454.     remove_edge (g,edge->target->attr.node.label, label);
  455.     edge = edge->next;
  456.     }
  457.     /*
  458.      * remove node by itself
  459.      */
  460.     graphRemoveNode (graph, &id, Regular);
  461. }
  462.  
  463. /* 
  464.  * remove_graph
  465.  * The graph G is removed, including all its edges and
  466.  * nodes.  If there is no such graph, this action has no effect.
  467.  */
  468.  
  469. void Layout::remove_graph (char *g)
  470. {
  471.     graphRemove (&tab,g);
  472. }
  473.  
  474. /* 
  475.  * layout
  476.  * A layout for all nodes in G is computed.  Changing node
  477.  * positions are echoed on the standard output in the form
  478.  * !^node-position(G, N, X, Y)  for each old (now invalid) node
  479.  * position (X, Y) and !node-position(G, N, X, Y) for each new node
  480.  * position (X, Y). Changing edge hints are echoed on the stan- dard
  481.  * output in the form ^!edge-hint(G, N1, N2, X, Y) for each old (now
  482.  * invalid) edge hint (X, Y) and !edge-hint(G, N1, N2, X, Y) for each
  483.  * new edge hint (X, Y).
  484.  */
  485.  
  486. void Layout::layout (char *g)
  487. {
  488.     GRAPH *graph;
  489.     
  490.     graph = graphGet (&tab,g);
  491.     if (!graph) {
  492.     fprintf (stderr,"layout warning: graph %s unknown\n",g);
  493.     return ;
  494.     }
  495.  
  496.     if (graph->layouted) {
  497.     inc_layout(graph);
  498.     } else {
  499.     new_layout(graph);
  500.     }
  501.     dddOutput (graph);
  502.  
  503. }
  504.  
  505. /*
  506.  * debug
  507.  */
  508. void Layout::dddDebug (char *g)
  509. {
  510.     GRAPH *graph;
  511.     
  512.     graph = graphGet (&tab,g);
  513.     if (!graph) {
  514.     fprintf (stderr,"debug warning: graph %s unknown\n",g);
  515.     return ;
  516.     }
  517.  
  518.     if (graph->layouted) {
  519.     inc_layout (graph);
  520.     } else {
  521.     new_layout (graph);
  522.     }
  523.     debugGraphXFig (graph);
  524. }
  525.  
  526.  
  527. /*
  528.  * inc_layout
  529.  * perform an incremental layout
  530.  */
  531.  
  532. void Layout::inc_layout (GRAPH *graph)
  533. {
  534.     int i;
  535.  
  536.     levelsEnterNodes (graph,graph->pullup);
  537.     sortInsertHints (graph);
  538.  
  539.     sortGraphUpperBary (graph);
  540.     sortGraphLowerBary (graph);
  541.     sortInitX (graph);
  542.  
  543.     /*
  544.      * there are two ways for finetunig the x-coordinates.
  545.      * graph.xiterations tells the number of iterations.
  546.      */
  547.     if (graph->reverseflag) {
  548.     for (i=0;i < graph->xiterations/2;i++) {
  549.         sortGraphDownX (graph);
  550.         sortGraphUpX (graph);
  551.     }
  552.     if (graph->xiterations % 2) {
  553.         sortGraphUpX (graph);
  554.     }
  555.     } else {
  556.     
  557.     for (i=0;i<graph->xiterations/2;i++) {
  558.         sortGraphUpX (graph);
  559.         sortGraphDownX (graph);
  560.     }
  561.     if (graph->xiterations % 2) {
  562.         sortGraphUpX (graph);
  563.     }
  564.     }
  565.  
  566.     sortGraphVertical (graph);
  567. }
  568.  
  569.  
  570. /*
  571.  * new_layout
  572.  * create a new layout
  573.  */
  574.  
  575. void Layout::new_layout (GRAPH *graph)
  576. {
  577.     int i;
  578.  
  579.     graph->layouted = TRUE;
  580.  
  581.     levelsEnterNodes (graph,graph->pullup);
  582.     sortInsertHints (graph);
  583.  
  584.     /*
  585.      * there are two ways for finetunig the x-coordinates.
  586.      * graph->xiterations tells the number of iterations.
  587.      */
  588.     if (graph->reverseflag) {
  589.  
  590.     sortGraphLowerBary (graph);
  591.     sortGraphUpperBary (graph);
  592.     sortGraphLowerBary (graph);    
  593.     sortGraphUpperBary (graph);
  594.     if (graph->xiterations % 2) {
  595.         sortGraphLowerBary (graph);
  596.     }
  597.  
  598.     sortInitX (graph);
  599.  
  600.  
  601.     for (i=0;i < graph->xiterations/2;i++) {
  602.         sortGraphDownX (graph);
  603.         sortGraphUpX (graph);
  604.     }
  605.     if (graph->xiterations % 2) {
  606.         sortGraphDownX (graph);
  607.     }
  608.     } else {
  609.     sortGraphUpperBary (graph);
  610.     sortGraphLowerBary (graph);
  611.     sortGraphUpperBary (graph);
  612.     sortGraphLowerBary (graph);    
  613.     if (graph->xiterations % 2) {
  614.         sortGraphUpperBary (graph);
  615.     }
  616.  
  617.     sortInitX (graph);
  618.  
  619.     for (i=0;i<graph->xiterations/2;i++) {
  620.         sortGraphUpX (graph);
  621.         sortGraphDownX (graph);
  622.     }
  623.     if (graph->xiterations % 2) {
  624.         sortGraphUpX (graph);
  625.     }
  626.     }
  627.  
  628.     sortGraphVertical (graph);
  629. }
  630.  
  631. /*
  632.  * dddOutput
  633.  * echo the changes to stdout. For each node its new position will
  634.  * be written out. 
  635.  */
  636.  
  637. void Layout::dddOutput (GRAPH *graph)
  638. {
  639.     int i;
  640.     NODE *node;
  641.     
  642.     for (i = 0; i < PRIME; i++) {
  643.     node = graph->hashtab[i];
  644.     while (node) {
  645.         dddNodeOut (graph->label, node);
  646.         node = node->hashnext;
  647.     }
  648.     }
  649. }
  650.  
  651. /*
  652.  * dddNodeOut
  653.  * write out the node position 
  654.  */
  655.  
  656. void Layout::dddNodeOut (char *, NODE *node)
  657. {
  658.     if (node->x == node->oldx && node->y == node->oldy) {
  659.     return;    /* no changes */
  660.     }
  661.  
  662.     if (node->type == Regular) {
  663.     node_callback(node->attr.node.label,
  664.                  node->x,
  665.                  node->y);
  666.     } else {
  667.     hint_callback(node->attr.hint.source->attr.node.label,
  668.                  node->attr.hint.target->attr.node.label,
  669.                  node->x,
  670.                  node->y);
  671.     }
  672.     node->oldx = node->x;
  673.     node->oldy = node->y;
  674.     node->layouted = TRUE;
  675. }
  676.  
  677.  
  678. /*****************************************************************************
  679.     Debugging functions
  680. *****************************************************************************/
  681.  
  682. #define XFIGHEADER "#FIG 2.1\n80 2\n"
  683. #define BOXHEADER  "2 2 0 1 -1 0 0 0 0.000 0 0 0\n\t"
  684. #define TEXTHEADER "4 1 0 12 0 -1 0 0.000 0 0 0 "
  685. #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"
  686. #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"
  687. #define LINE "2 1 0 1 -1 0 0 0 0.000 0 0 0\n\t"
  688.  
  689. #define HERE 0
  690. #define OTHER 1
  691. #define NOTHING 3
  692.  
  693. /*
  694.  * debugNode
  695.  * print a node
  696.  */
  697.  
  698. void Layout::debugNode (NODE *node)
  699. {
  700.     EDGE *tmp;
  701.  
  702.     printf ("level=%i center=%i x=%i ",node->level, node->center,
  703.         node->x);
  704.     if (node->type == Regular) {
  705.     printf ("regular label=%s\n",node->attr.node.label);
  706.     printf ("down: ");
  707.     tmp = node->attr.node.down.head ;
  708.     while (tmp) {
  709.         if (tmp->node->type == Regular) {
  710.         printf ("%s ",tmp->node->attr.node.label);
  711.         } else {
  712.         printf ("%i ",tmp->node->attr.hint.id);
  713.         }
  714.         tmp=tmp->next;
  715.     }
  716.     printf ("\n");
  717.     printf ("up: ");
  718.     tmp = node->attr.node.up.head ;
  719.     while (tmp) {
  720.         if (tmp->node->type == Regular) {
  721.         printf ("%s ",tmp->node->attr.node.label);
  722.         } else {
  723.         printf ("%i ",tmp->node->attr.hint.id);
  724.         }
  725.         tmp=tmp->next;
  726.     }
  727.     printf ("\n");
  728.     } else {
  729.     printf ("hint %i\n",node->attr.hint.id);
  730.     printf ("down: ");
  731.     if (node->attr.hint.down) {
  732.         if (node->attr.hint.down->type == Regular) {
  733.         printf ("%s ",node->attr.hint.down
  734.             ->attr.node.label);
  735.         } else {
  736.         printf ("%i ",node->attr.hint.down
  737.             ->attr.hint.id);
  738.         }
  739.     }
  740.     printf ("\n");
  741.     printf ("up: ");
  742.     if (node->attr.hint.up) {
  743.         if (node->attr.hint.up->type == Regular) {
  744.         printf ("%s ",node->attr.hint.up
  745.             ->attr.node.label);
  746.         } else {
  747.         printf ("%i ",node->attr.hint.up
  748.             ->attr.hint.id);
  749.         }
  750.     }
  751.     printf ("\n");
  752.     }
  753. }
  754.  
  755. /*
  756.  * debugLevel
  757.  * print all nodes of a level
  758.  */
  759.  
  760. void Layout::debugLevel (GRAPH *graph, int n)
  761. {
  762.     NODE **level = graph->level+n;
  763.     NODE *node;
  764.  
  765.     node = *level ;
  766.     while (node) {
  767.     debugNode (node);
  768.     node = node->right;
  769.     }
  770. }
  771.  
  772. /*
  773.  * debugAllLevels
  774.  * print the nodes of all levels
  775.  */
  776.  
  777. void Layout::debugAllLevel (GRAPH *graph)
  778. {
  779.     int i;
  780.  
  781.     for ( i = 0 ; i < graph->levels; i++) {
  782.     printf ("*** level %i ***\n",i);
  783.     debugLevel (graph,i);
  784.     }
  785. }    
  786.     
  787. /*
  788.  * debugAllNodes
  789.  * write out all nodes
  790.  */
  791.  
  792. void Layout::debugAllNodes (GRAPH *graph)
  793. {
  794.     int i;
  795.     NODE *node;
  796.  
  797.     for (i=0;i<PRIME;i++) {
  798.     if (graph->hashtab[i] ) {
  799.         node = graph->hashtab[i] ;
  800.         while (node) {
  801.         debugNode (node);
  802.         node = node->hashnext;
  803.         }
  804.     }
  805.     }
  806. }
  807.  
  808.  
  809. /*
  810.  * debugNodeXFig
  811.  * write a xfig-representation for the given node to stdout. The function
  812.  * will display a rectangle for the node and lines to all descants.
  813.  */
  814.  
  815. void Layout::debugNodeXFig (NODE *nd)
  816. {
  817.     EDGE *edge;
  818.     int arrow;
  819.     int w,h;
  820.  
  821.     if (nd->type == Regular) {
  822.  
  823.     w = nd->attr.node.w/2;
  824.     h = nd->attr.node.h/2;
  825.  
  826.     printf ( BOXHEADER );
  827.     printf ("%i %i ",nd->x - w , nd->y - h);
  828.     printf ("%i %i ",nd->x + w , nd->y - h);
  829.     printf ("%i %i ",nd->x + w , nd->y + h);
  830.     printf ("%i %i ",nd->x - w , nd->y + h);
  831.     printf ("%i %i ",nd->x - w , nd->y - h);
  832.     printf (" 9999 9999\n");
  833.     printf ( TEXTHEADER );
  834.     printf ("%i %i %s\x01\n", nd->x, nd->y, nd->attr.node.label);
  835.  
  836.     /*
  837.      * draw the lines to all descendants
  838.      */
  839.  
  840.     edge = nd->attr.node.down.head;
  841.     while (edge) {
  842.         arrow = ( edge->arrow == Here ? HERE : OTHER);
  843.         if (arrow == HERE) {
  844.         debugEdgeXFig (nd, edge->node, HERE) ;
  845.         } else {
  846.         if (edge->node->type == Regular) {
  847.             debugEdgeXFig (nd, edge->node, OTHER);
  848.         } else {
  849.             debugEdgeXFig (nd, edge->node,NOTHING);
  850.         }
  851.         }
  852.         edge = edge->next;
  853.     }
  854.  
  855.     } else if (nd->attr.hint.down) {
  856.     /*
  857.      * draw the line 
  858.      */
  859.     if (nd->attr.hint.down->type == Regular) {
  860.         if (nd->attr.hint.target == nd->attr.hint.down) {
  861.         debugEdgeXFig (nd, nd->attr.hint.down, OTHER);
  862.         } else {
  863.         debugEdgeXFig (nd, nd->attr.hint.down,NOTHING);
  864.         }
  865.     } else {
  866.     }
  867.  
  868.     if (nd->attr.hint.down->type == Hint) {
  869.         debugEdgeXFig (nd, nd->attr.hint.down, NOTHING);
  870.     } else {
  871.         if (nd->attr.hint.target == nd->attr.hint.down) {
  872.         debugEdgeXFig (nd, nd->attr.hint.down, OTHER);
  873.         } else {
  874.         debugEdgeXFig (nd, nd->attr.hint.down,NOTHING);
  875.         }
  876.     }
  877.             
  878.     }
  879. }
  880.  
  881. /*
  882.  * debugEdgeXFig
  883.  * write a xfig-representation for a line between to nodes to stdout
  884.  */
  885.  
  886. void Layout::debugEdgeXFig (NODE *source, NODE *target, int arrow)
  887. {
  888.     int x1,y1,x2,y2;
  889.  
  890.     x1 = source->x ;
  891.     y1 = source->y ;
  892.     if (source->type == Regular ) {
  893.     y1 += source->attr.node.h/2;
  894.     }
  895.     x2 = target->x ;
  896.     y2 = target->y ;
  897.     if (target->type == Regular ) {
  898.     y2 -= target->attr.node.h/2;
  899.     }
  900.     switch (arrow) {
  901.     case OTHER:
  902.     printf (FWDLINE);
  903.     break;
  904.     case HERE:
  905.     printf (BKWDLINE);
  906.     break;
  907.     case NOTHING:
  908.     default:
  909.     printf (LINE);
  910.     break;
  911.     }
  912.     printf ("%i %i %i %i 9999 9999\n",x1,y1,x2,y2);
  913. }
  914.  
  915. /*
  916.  * debugGraphXFig
  917.  */
  918.  
  919. void Layout::debugGraphXFig (GRAPH *graph)
  920. {
  921.     NODE *node;
  922.     int i;
  923.  
  924.     printf (XFIGHEADER);
  925.     for ( i = 0 ; i < PRIME; i++) {
  926.     node = graph->hashtab[i];
  927.     while (node) {
  928.         debugNodeXFig (node);
  929.         node = node->hashnext;
  930.     }
  931.     }
  932.     
  933. }
  934.  
  935.  
  936. /*****************************************************************************
  937.     Edgelist functions
  938. *****************************************************************************/
  939.  
  940. /*
  941.  * listInit
  942.  * initialize a list of edges
  943.  */
  944.  
  945. void Layout::listInit (EDGELIST *list)
  946. {
  947.     list->head = (EDGE*) NULL;
  948.     list->tail = (EDGE*) NULL;
  949.     list->length = 0;
  950. }
  951.  
  952. /*
  953.  * listInsertEdge
  954.  * insert a new edge to a list
  955.  */
  956.  
  957. EDGE *Layout::listInsertEdge (EDGELIST *list, NODE *node)
  958. {
  959.     EDGE *edge;
  960.     EDGE *tail;
  961.  
  962.     /*
  963.      * create a new edge
  964.      */
  965.     edge = (EDGE*) malloc (sizeof (EDGE));
  966.     if (!edge) {
  967.     fprintf (stderr,"listInsertEdge: out of memory\n");
  968.     exit (MEMORY_ERROR);
  969.     }
  970.     /*
  971.      * link the edge to the list
  972.      */
  973.     edge->next = (EDGE*) NULL;
  974.     edge->prev = (EDGE*) NULL;
  975.  
  976.     tail = list->head;
  977.     list->head = edge;
  978.     edge->next = tail;
  979.     if (!tail) {
  980.     list->tail = edge;
  981.     } else {
  982.     tail->prev = edge;
  983.     }
  984.     
  985.     /*
  986.      * enter the node to the edge
  987.      */
  988.     edge->node = node;
  989.  
  990.     list->length++;
  991.  
  992.     return edge;
  993. }
  994.     
  995. /*
  996.  * listRemoveEdge
  997.  * remove one edge form a list of edges
  998.  */
  999.  
  1000. void Layout::listRemoveEdge (EDGELIST *list, EDGE *edge)
  1001. {
  1002.     if (edge->prev && edge->next) {
  1003.     /* edge neither head nor tail of list */
  1004.     edge->next->prev = edge->prev ;
  1005.     edge->prev->next = edge->next ;
  1006.     } else {
  1007.     if (!edge->next) {
  1008.         /* last entry of list */
  1009.         list->tail = edge->prev;
  1010.         if (edge->prev) {
  1011.         edge->prev->next = (EDGE*) NULL;
  1012.         }
  1013.     }
  1014.     if (!edge->prev) {
  1015.         /* first entry of list */
  1016.         list->head = edge->next ;
  1017.         if (edge->next) {
  1018.         edge->next->prev = (EDGE*) NULL;
  1019.         }
  1020.     }
  1021.     }
  1022.     free ((char*)edge);
  1023.     /*
  1024.      * correct number of entries 
  1025.      */
  1026.     list->length-- ;
  1027.  
  1028. }
  1029.  
  1030. /*
  1031.  * listFindNode
  1032.  * find an edge to a specified node
  1033.  */
  1034.  
  1035. EDGE *Layout::listFindNode (EDGELIST *list, NODE *node)
  1036. {
  1037.     EDGE *edge;
  1038.     
  1039.     edge = list->head;
  1040.     while (edge && edge->node != node) {
  1041.     edge = edge->next;
  1042.     }
  1043.     if (!edge) {
  1044.     fprintf (stderr,"listFindEntry: can't find entry\n");
  1045.     exit (NOT_MEMBER);
  1046.     }
  1047.     
  1048.     return edge;
  1049. }
  1050.  
  1051. /*
  1052.  * listFindTarget
  1053.  * find an edge to a specified target
  1054.  */
  1055.  
  1056. EDGE *Layout::listFindTarget (EDGELIST *list, NODE *target)
  1057. {
  1058.     EDGE *edge;
  1059.     
  1060.     edge = list->head;
  1061.     while (edge && edge->target != target) {
  1062.     edge = edge->next;
  1063.     }
  1064.     if (!edge) {
  1065.     fprintf (stderr,"listFindEntry: can't find entry\n");
  1066.     edge = (EDGE*) NULL;
  1067.     }
  1068.     
  1069.     return edge;
  1070. }
  1071.  
  1072. /*
  1073.  * listRemove
  1074.  * remove all edges from a list
  1075.  * this function is just for cleaning up
  1076.  */
  1077.  
  1078. void Layout::listRemove (EDGELIST *list)
  1079. {
  1080.     EDGE *edge;
  1081.     EDGE *tmp;
  1082.     
  1083.     edge = list->head;
  1084.     while (edge) {
  1085.     tmp = edge->next;
  1086.     free ((char*) edge);
  1087.     edge = tmp;
  1088.     }
  1089.     list->head = (EDGE*) NULL;
  1090.     list->tail = (EDGE*) NULL;
  1091. }
  1092.  
  1093.  
  1094. /*****************************************************************************
  1095.     Node functions
  1096. *****************************************************************************/
  1097.  
  1098. /*
  1099.  * nodeInit
  1100.  * initialize a node
  1101.  */
  1102.  
  1103. void Layout::nodeInit (NODE* node, ID *id , NODETYPE type)
  1104. {
  1105.     node->x = 0;
  1106.     node->y = 0;
  1107.     node->oldx = NOPOSITION;
  1108.     node->oldy = NOPOSITION;
  1109.     node->layouted = FALSE;
  1110.     node->level = NOLEVEL;
  1111.     node->center = 0;
  1112.     node->index = 0 ;
  1113.     node->loop = 0;
  1114.     node->mark = (NODE*) NULL;
  1115.     
  1116.     node->left = (NODE*) NULL;
  1117.     node->right = (NODE*) NULL;
  1118.  
  1119.     node->hashnext = (NODE*) NULL;
  1120.     node->hashprev = (NODE*) NULL;
  1121.     
  1122.     node->type = type;
  1123.  
  1124.     if ( type == Regular ) {
  1125.     node->attr.node.label = (char*) malloc (strlen(id->label)+5);
  1126.     if (!node->attr.node.label) {
  1127.         fprintf (stderr,"nodeInit: out of memory!\n");
  1128.         exit (MEMORY_ERROR);
  1129.     }
  1130.     strcpy (node->attr.node.label, id->label);
  1131.  
  1132.     node->attr.node.w = 0;
  1133.     node->attr.node.h = 0;
  1134.     listInit (&node->attr.node.up);
  1135.     listInit (&node->attr.node.down);
  1136.     } else {
  1137.     node->attr.hint.id = id->id ;
  1138.     node->attr.hint.up = (NODE*) NULL;
  1139.     node->attr.hint.down = (NODE*) NULL;
  1140.     node->attr.hint.source = (NODE*) NULL;
  1141.     node->attr.hint.target = (NODE*) NULL;
  1142.     }
  1143.         
  1144. }        
  1145.  
  1146. /*
  1147.  * nodeRemove
  1148.  * remove a node.
  1149.  * remember to free the label and and the lists of adjacent nodes.
  1150.  */
  1151.  
  1152. void Layout::nodeRemove (NODE *node) 
  1153. {
  1154.     if (node->type == Regular) {
  1155.     free (node->attr.node.label);
  1156.     listRemove (&node->attr.node.up);
  1157.     listRemove (&node->attr.node.down);
  1158.     }
  1159.     
  1160.     free ((char*)node);
  1161. }
  1162.  
  1163. /*****************************************************************************
  1164.     Graph functions
  1165. *****************************************************************************/
  1166.  
  1167. /*
  1168.  * graphInit
  1169.  * initialize a graph
  1170.  */
  1171.  
  1172. void Layout::graphInit (GRAPH *graph, char *label)
  1173. {
  1174.     int i;
  1175.     
  1176.     graph->label = (char *)malloc (strlen(label)+1);
  1177.     if (!graph->label) {
  1178.     fprintf (stderr,"graphInit: out of memory!\n");
  1179.     }
  1180.     strcpy (graph->label, label);
  1181.     graph->hashnext = (GRAPH*) NULL;
  1182.     graph->hashprev = (GRAPH*) NULL;
  1183.  
  1184.     graph->minxdist    = MINXDIST ;
  1185.     graph->minydist    = MINYDIST;
  1186.     graph->xiterations = XITERATIONS;
  1187.     graph->reverseflag = REVERSE ;
  1188.     graph->pullup      = PULLUP;
  1189.  
  1190.     graph->levels = 0;
  1191.     graph->level = (NODE**) NULL;
  1192.  
  1193.     graph->layouted = FALSE ;     /* the graph was never layouted */
  1194.  
  1195.     for ( i = 0; i < PRIME; i++) {
  1196.     graph->hashtab[i] = (NODE*) NULL;
  1197.     }
  1198. }
  1199.  
  1200. /*
  1201.  * graphEnterNode
  1202.  * enter a new node to the graph and return a pointer to the
  1203.  * new node
  1204.  */
  1205.  
  1206. NODE *Layout::graphEnterNode (GRAPH *graph, ID *id, NODETYPE type)
  1207. {
  1208.     NODE *node;
  1209.     NODE *tail;
  1210.     int pos;
  1211.  
  1212.     node = (NODE*) malloc (sizeof(NODE)) ;
  1213.     if (!node) {
  1214.     fprintf (stderr, "graphEnterNode: out of memory\n");
  1215.     exit (MEMORY_ERROR);
  1216.     }
  1217.     nodeInit (node,id,type);
  1218.  
  1219.     /*
  1220.      * insert the new node to the hashing table
  1221.      * TODO: check for dublicates of the given nodeID
  1222.      */
  1223.     
  1224.     if (type == Regular) {
  1225.     pos = graphHashStr (node->attr.node.label, PRIME);
  1226.     } else {
  1227.     pos =  node->attr.hint.id % PRIME;
  1228.     }
  1229.     tail = graph->hashtab[pos] ;
  1230.     graph->hashtab[pos] = node;
  1231.     node->hashnext = tail ;
  1232.     node->hashprev = (NODE*) NULL;
  1233.     if (node->hashnext) {
  1234.     node->hashnext->hashprev = node;
  1235.     }
  1236.     
  1237.     return node;
  1238. }
  1239.  
  1240. /*
  1241.  * graphGetNode
  1242.  * get a pointer to a node described by its ID
  1243.  */
  1244.  
  1245. NODE *Layout::graphGetNode (GRAPH *graph, ID *id, NODETYPE type)
  1246. {
  1247.     int pos;
  1248.     int found = FALSE ;
  1249.     NODE *node;
  1250.  
  1251.     /*
  1252.      * calculate the hash-entry
  1253.      */
  1254.     if (type == Regular) {
  1255.     pos = graphHashStr (id->label, PRIME);
  1256.     node = graph->hashtab[pos];
  1257.  
  1258.     /*
  1259.      * search for entry 
  1260.      */
  1261.     while (node && !found) {
  1262.         if (node->type != Regular 
  1263.         ||  strcmp(node->attr.node.label,id->label)) {
  1264.         node = node->hashnext;
  1265.         } else {
  1266.         found = TRUE;
  1267.         }
  1268.     } 
  1269.  
  1270.     } else {
  1271.     pos =  id->id % PRIME;
  1272.     node = graph->hashtab[pos];
  1273.  
  1274.     /*
  1275.      * search for entry 
  1276.      */
  1277.  
  1278.     while (node && !found) {
  1279.         if (node->type != Hint 
  1280.         ||  node->attr.hint.id != id->id) {
  1281.         node = node->hashnext;
  1282.         } else {
  1283.         found = TRUE;
  1284.         }
  1285.     } 
  1286.     }
  1287.  
  1288.     /*
  1289.      * node == NULL if not found
  1290.      */
  1291.     return node;
  1292. }
  1293.  
  1294. /*
  1295.  * graphRemoveNode
  1296.  * delete a node from the hashtab of a graph. 
  1297.  * ATTENTION: You have to delete all edges connected to the node
  1298.  * and remove the node from its level by yourself!
  1299.  */
  1300.  
  1301. void Layout::graphRemoveNode (GRAPH *graph, ID *id, NODETYPE type)
  1302. {
  1303.     int pos;
  1304.     NODE *node;
  1305.  
  1306.     /*
  1307.      * calculate the hash-entry
  1308.      */
  1309.     if (type == Regular) {
  1310.     pos = graphHashStr (id->label, PRIME);
  1311.     node = graph->hashtab[pos];
  1312.  
  1313.     /*
  1314.      * search for entry 
  1315.      */
  1316.     while (node && strcmp(node->attr.node.label,id->label)) {
  1317.         node = node->hashnext;
  1318.     }
  1319.  
  1320.     } else {
  1321.     pos =  id->id % PRIME;
  1322.     node = graph->hashtab[pos];
  1323.  
  1324.     /*
  1325.      * search for entry 
  1326.      */
  1327.     while (node && node->attr.hint.id != id->id) {
  1328.         node = node->hashnext;
  1329.     }
  1330.     }
  1331.  
  1332.     /*
  1333.      * node == NULL if not found
  1334.      */
  1335.  
  1336.     if (!node) {
  1337.     fprintf (stderr,"graphRemoveNode: can't find entry!\n");
  1338.     exit (NOT_MEMBER);
  1339.     }
  1340.  
  1341.     /*
  1342.      * remove the node from the double linked list
  1343.      */
  1344.  
  1345.     if (node->hashprev && node->hashprev) {
  1346.     node->hashprev->hashnext = node->hashnext;
  1347.     node->hashnext->hashprev = node->hashprev;
  1348.     } else {
  1349.     if (!node->hashprev) {
  1350.         graph->hashtab[pos] = node->hashnext;
  1351.         if (node->hashnext) {
  1352.         node->hashnext->hashprev = (NODE*) NULL;
  1353.         }
  1354.     }
  1355.     if (!node->hashnext && node->hashprev) {
  1356.         node->hashprev->hashnext = (NODE*) NULL;
  1357.     }
  1358.     }
  1359.     nodeRemove (node);
  1360. }
  1361.     
  1362. /* 
  1363.  * graphCreateLevels
  1364.  * create a number of Levels for a graph and initialize it
  1365.  */
  1366.  
  1367. void Layout::graphCreateLevels (GRAPH *graph, int n)
  1368. {
  1369.     NODE **nodeptr;
  1370.     int i;
  1371.  
  1372.     graph->levels = n;
  1373.     graph->level = (NODE **) malloc (sizeof (NODE*) * n);
  1374.     if (!graph->level) {
  1375.     fprintf (stderr,"graphCreateLevels: out of memory!\n");
  1376.     exit (MEMORY_ERROR);
  1377.     }
  1378.     
  1379.     /*
  1380.      * initialize it
  1381.      */
  1382.  
  1383.     nodeptr = graph->level ;
  1384.     for ( i = 0 ; i < n ; i++ ) {
  1385.     *(nodeptr++) = (NODE*) NULL;
  1386.     }
  1387. }
  1388.  
  1389. /*
  1390.  * graphRemoveLevels
  1391.  * remove the level references.
  1392.  * ATTENTION: only the references will be deleted, not the nodes
  1393.  * contained by the levels!
  1394.  */
  1395.  
  1396. void Layout::graphRemoveLevels (GRAPH *graph)
  1397. {
  1398.     free ( (char*) graph->level);
  1399.     graph->level = (NODE**) NULL;
  1400.     graph->levels = 0;
  1401. }
  1402.  
  1403. /*
  1404.  * graphAddLevels
  1405.  * enlarge the table of levels by 'n'. The new levels will all be 
  1406.  * empty.
  1407.  */
  1408.  
  1409. void Layout::graphAddLevels (GRAPH *graph, int n)
  1410. {
  1411.     NODE **newtab;
  1412.     int i;
  1413.     
  1414.  
  1415.     /*
  1416.      * create a larger table
  1417.      */
  1418.     newtab = (NODE**) malloc (sizeof(NODE*) * (graph->levels + n));
  1419.     if (!newtab) {
  1420.     fprintf (stderr,"graphAddLevels: out of memory!\n");
  1421.     exit (MEMORY_ERROR);
  1422.     }
  1423.     /*
  1424.      * fill the table ..
  1425.      */
  1426.     for (i=0 ; i < graph->levels; i++) {
  1427.     *(newtab+i) = *(graph->level);
  1428.     }
  1429.     /*
  1430.      * clear the new levels
  1431.      */
  1432.     for (i=graph->levels; i < graph->levels+n; i++) {
  1433.     *(newtab+i) = (NODE*) NULL;
  1434.     }
  1435.     /*
  1436.      * make the new table to the actual table
  1437.      */
  1438.     graph->levels += n;
  1439.     free ((char*) graph->level);
  1440.     graph->level = newtab;
  1441. }
  1442.  
  1443. /*
  1444.  * graphInsertEdge
  1445.  * insert an edge of a specified type between two regular nodes of the graph
  1446.  * TODO: check for dublicates and loops
  1447.  */
  1448.  
  1449. void Layout::graphInsertEdge (GRAPH *, NODE *source, NODE *target)
  1450. {
  1451.     EDGE *from;
  1452.     EDGE *to;
  1453.  
  1454.     if (source->type != Regular) {
  1455.     fprintf (stderr,"graphInsertEdge: wrong node type\n");
  1456.     exit (NODE_TYPE);
  1457.     }
  1458.     if (target->type != Regular) {
  1459.     fprintf (stderr,"graphInsertEdge: wrong node type\n");
  1460.     exit (NODE_TYPE);
  1461.     }
  1462.     
  1463.     to = graphFindEdgeAtSource (source,target) ;
  1464.     if (to) {
  1465.     fprintf (stderr,"graphInsertEdge: warning - edge exists\n");
  1466.     return;
  1467.     }
  1468.  
  1469.     from = listInsertEdge (&source->attr.node.down, target);
  1470.     from->arrow = Other;
  1471.     from->target = target;
  1472.     from->node = target;
  1473.  
  1474.     to = listInsertEdge (&target->attr.node.up, source);
  1475.     to->arrow = Here;
  1476.     to->target = source;
  1477.     to->node = source;
  1478.  
  1479. }
  1480.  
  1481. /*
  1482.  * graphInvertEdge
  1483.  * invert the internal represation of an edge.
  1484.  */
  1485.  
  1486. void Layout::graphInvertEdge (NODE *source, NODE *target)
  1487. {
  1488.     EDGE *to, *from;
  1489.     EDGEARROW srcarrow;
  1490.  
  1491.  
  1492.     if (source->type != Regular || target->type != Regular) {
  1493.     fprintf (stderr,"graphInvertEdge: node not regular!\n");
  1494.     exit (INTERNAL);
  1495.     }
  1496.     fprintf (stderr,"graphInvertEdge: inverting Edge %s -> %s\n", 
  1497.          source->attr.node.label, target->attr.node.label);
  1498.     to = listFindTarget (&source->attr.node.down,target);
  1499.     from = listFindTarget (&target->attr.node.up,source);
  1500.     if (!to || !from) {
  1501.     fprintf (stderr,"graphInvertEdge: can't find edge!\n");
  1502.     exit (NO_EDGE);
  1503.     }
  1504.     srcarrow = to->arrow;
  1505.  
  1506.     /*
  1507.      * remove the edge
  1508.      */
  1509.     listRemoveEdge (&source->attr.node.down, to);
  1510.     listRemoveEdge (&target->attr.node.up,from);
  1511.     /*
  1512.      * create inverted edge
  1513.      */
  1514.     to = listInsertEdge (&source->attr.node.up, target);
  1515.     to->target = target;
  1516.     to->arrow = srcarrow;
  1517.     from = listInsertEdge (&target->attr.node.down, source);
  1518.     from->target = source;
  1519.     from->arrow = ( srcarrow == Here ? Other : Here );
  1520. }
  1521.  
  1522. /*
  1523.  * graphNewNodeID
  1524.  * return a new nodeID
  1525.  */
  1526.  
  1527. int Layout::graphNewNodeID()
  1528. {
  1529.     int counter = 1000 ;
  1530.  
  1531.     return counter++ ;
  1532. }
  1533.  
  1534. /*
  1535.  * graphInsertHint
  1536.  * insert a hint node by splitting an edge between two nodes.
  1537.  * A pointer to the new created hint node will be returned
  1538.  */
  1539.  
  1540. NODE *Layout::graphInsertHint (GRAPH *graph, NODE *source, NODE* target)
  1541. {
  1542.     ID id;
  1543.     NODE *hint = 0;
  1544.     EDGE *toTarget = 0;
  1545.     EDGE *toSource = 0;
  1546.  
  1547.     /*
  1548.      * there must be an edge between source and target 
  1549.      */
  1550.  
  1551.     id.id = graphNewNodeID();
  1552.     hint = graphEnterNode (graph,&id, Hint);
  1553.     if (source->type == Regular) {
  1554.     /*
  1555.      * find edge to target
  1556.      */
  1557.     toTarget = listFindNode (&source->attr.node.down, target);
  1558.     toTarget->node = hint;
  1559.     } else {
  1560.     source->attr.hint.down = hint;
  1561.     }
  1562.  
  1563.     if (target->type == Regular) {
  1564.     /*
  1565.      * find edge to source
  1566.      */
  1567.     toSource = listFindNode (&target->attr.node.up, source);
  1568.     toSource->node = hint;
  1569.     } else {
  1570.     target->attr.hint.up = hint;
  1571.     }
  1572.  
  1573.     hint->attr.hint.up = source;
  1574.     hint->attr.hint.down = target;
  1575.  
  1576.     /*
  1577.      * enter the information, to which edge this hint belongs
  1578.      */
  1579.     
  1580.     if (source->type == Hint) {
  1581.     hint->attr.hint.source = source->attr.hint.source;
  1582.     hint->attr.hint.target = source->attr.hint.target;
  1583.     } else if (target->type == Hint) {
  1584.     hint->attr.hint.source = target->attr.hint.source;
  1585.     hint->attr.hint.target = target->attr.hint.target;
  1586.     } else if (toTarget->arrow == Other){
  1587.     hint->attr.hint.source = source;
  1588.     hint->attr.hint.target = target;
  1589.     } else {
  1590.     hint->attr.hint.source = target;
  1591.     hint->attr.hint.target = source;
  1592.     }
  1593.  
  1594.     return hint;
  1595. }
  1596.  
  1597. /*
  1598.  * graphFindEdgeAtSource 
  1599.  * return the edge leading from source to target. Source and target
  1600.  * must be regular!
  1601.  */
  1602.  
  1603. EDGE *Layout::graphFindEdgeAtSource (NODE *source, NODE *target)
  1604. {
  1605.     EDGE *edge;
  1606.     
  1607.     edge = source->attr.node.down.head ;
  1608.     while (edge && !(edge->target == target && edge->arrow == Other)){
  1609.     edge = edge->next;
  1610.     }
  1611.     if (!edge) {
  1612.     edge = source->attr.node.up.head ;
  1613.     while (edge && !(edge->target == target && 
  1614.              edge->arrow == Other )) {
  1615.         edge = edge->next;
  1616.     }
  1617.     }
  1618.     return edge;
  1619. }
  1620.  
  1621.  
  1622. /*
  1623.  * graphFindEdgeAtTarget
  1624.  * return the edge (at target) leading from source to target. Source and target
  1625.  * must be regular!
  1626.  */
  1627.  
  1628. EDGE *Layout::graphFindEdgeAtTarget (NODE *source, NODE *target)
  1629. {
  1630.     EDGE *edge;
  1631.     
  1632.     edge = target->attr.node.up.head ;
  1633.     while (edge && !(edge->target == source && edge->arrow == Here)){
  1634.     edge = edge->next;
  1635.     }
  1636.     if (!edge) {
  1637.     edge = target->attr.node.down.head ;
  1638.     while (edge && !(edge->target == source && 
  1639.              edge->arrow == Here )) {
  1640.         edge = edge->next;
  1641.     }
  1642.     }
  1643.     return edge;
  1644. }
  1645.  
  1646.  
  1647. /*
  1648.  * graphResetLevels
  1649.  * set the level of all nodes to NOLEVEL. The entries of 'left' and 'right'
  1650.  * will be set to NULL.
  1651.  * ATTENTION: You first have to clear the Levels by calling
  1652.  * 'graphRemoveLevels' before you call this function!
  1653.  */
  1654.  
  1655. void Layout::graphResetLevels (GRAPH *graph) 
  1656. {
  1657.     int i;
  1658.     NODE *node;
  1659.  
  1660.     for (i = 0 ; i < PRIME; i++) {
  1661.     node = graph->hashtab[i];
  1662.     while (node) {
  1663.         node->level = NOLEVEL;
  1664.         node->left = (NODE*) NULL;
  1665.         node->right = (NODE*) NULL;
  1666.  
  1667.         node = node->hashnext;
  1668.     }
  1669.     }
  1670. }
  1671.     
  1672.     
  1673. /*
  1674.  * graphHashStr
  1675.  * calculate a hash-value for a given string and return it. The 
  1676.  * hash-value will belong to [0..PRIME]
  1677.  * original by P.J. Weinberger
  1678.  */
  1679.  
  1680. int Layout::graphHashStr (char *str, int prime) 
  1681. {
  1682.     char *p;
  1683.     unsigned h = 0, g;
  1684.     
  1685.     for (p=str; *p != '\0'; p++ ) {
  1686.     h = ( h << 4) + (*p);
  1687.     if ((g = h & 0xf0000000)) {
  1688.         h = h ^ (g >> 24);
  1689.         h = h ^ g;
  1690.     }
  1691.     }
  1692.     return h % prime;
  1693. }
  1694.  
  1695. /*
  1696.  * functions for maintaining multiple graphs
  1697.  */
  1698.  
  1699. /*
  1700.  * graphGet
  1701.  * return a pointer to a specified graph. Return NULL, if no such
  1702.  * graph exists.
  1703.  * 'hashtab' contains SMALLPRIME pointers to GRAPHs.
  1704.  */
  1705.  
  1706. GRAPH *Layout::graphGet (GRAPHTAB *tab, char *label)
  1707. {
  1708.     int pos;
  1709.     GRAPH *graph;
  1710.  
  1711.     pos = graphHashStr (label, SMALLPRIME);
  1712.     /*
  1713.      * try to find graph
  1714.      */
  1715.     graph = (*tab)[pos];
  1716.     while (graph && strcmp(graph->label, label)) {
  1717.     graph = graph->hashnext;
  1718.     }
  1719.     return graph;
  1720. }
  1721.     
  1722.     
  1723. /*
  1724.  * graphNew
  1725.  * create a new graph, initialize it and return a pointer to it
  1726.  * if a graph with the specified label allready exists a warning
  1727.  * is printed and no new graph is created (NULL returned).
  1728.  */
  1729.  
  1730. GRAPH *Layout::graphNew (GRAPHTAB *tab,char *label)
  1731. {
  1732.     GRAPH *graph;
  1733.     GRAPH *tail;
  1734.     int pos;
  1735.  
  1736.     /*
  1737.      * check for dublicate
  1738.      */
  1739.     graph = graphGet (tab, label);
  1740.     if (graph) {
  1741.     fprintf (stderr,"graphNew: %s already there!\n",label);
  1742.     return (GRAPH*) NULL;
  1743.     }
  1744.         
  1745.     graph = (GRAPH*) malloc (sizeof(GRAPH));
  1746.     if (!graph) {
  1747.     fprintf (stderr,"graphNew: out of memory\n");
  1748.     exit (MEMORY_ERROR);
  1749.     }
  1750.     graphInit (graph,label);
  1751.     
  1752.     /*
  1753.      * enter graph to tab
  1754.      */
  1755.     pos = graphHashStr (label, SMALLPRIME);
  1756.  
  1757.     if ((*tab)[pos]) {
  1758.     tail = ((*tab)[pos])->hashnext;
  1759.     } else {
  1760.     tail = (GRAPH*) NULL;
  1761.     }
  1762.     (*tab)[pos] = graph;
  1763.     graph->hashnext = tail;
  1764.     graph->hashprev = (GRAPH*) NULL;
  1765.     if (graph->hashnext) {
  1766.     graph->hashnext->hashprev = graph;
  1767.     }
  1768.     
  1769.     return graph;
  1770. }
  1771.             
  1772. /*
  1773.  * graphRemove
  1774.  * remove a graph from a GRAPHTAB
  1775.  */
  1776.  
  1777. void Layout::graphRemove (GRAPHTAB *tab, char *label)
  1778. {
  1779.     int pos;
  1780.     int i;
  1781.     GRAPH *graph;
  1782.     NODE *nextnode;
  1783.     NODE *node;
  1784.  
  1785.     pos = graphHashStr (label, SMALLPRIME);
  1786.     /*
  1787.      * try to find graph
  1788.      */
  1789.     graph = (*tab)[pos];
  1790.     while (graph && strcmp(graph->label, label)) {
  1791.     graph = graph->hashnext;
  1792.     }
  1793.     if (!graph) {
  1794.     /*
  1795.      * not found
  1796.      */
  1797.     fprintf (stderr,"graphRemove: %s not found!\n",label);
  1798.     return;
  1799.     }
  1800.     /*
  1801.      * remove the graph
  1802.      */
  1803.     if (graph->hashprev && graph->hashprev) {
  1804.     graph->hashprev->hashnext = graph->hashnext;
  1805.     graph->hashnext->hashprev = graph->hashprev;
  1806.     } else {
  1807.     if (!graph->hashprev) {
  1808.         (*tab)[pos] = graph->hashnext;
  1809.         if (graph->hashnext) {
  1810.         graph->hashnext->hashprev = (GRAPH*) NULL;
  1811.         }
  1812.     }
  1813.     if (!graph->hashnext && graph->hashprev) {
  1814.         graph->hashprev->hashnext = (GRAPH*) NULL;
  1815.     }
  1816.     }
  1817.  
  1818.     graphRemoveLevels (graph); /* remove Levels */
  1819.     for (i=0; i < PRIME; i++) {
  1820.     node = graph->hashtab[i];
  1821.     while (node) {
  1822.         nextnode = node->hashnext;
  1823.         nodeRemove (node);
  1824.         node = nextnode;
  1825.     }
  1826.     }
  1827.     free (graph->label);
  1828.     free ((char*) graph);
  1829. }
  1830.  
  1831. /*
  1832.  * graphTabInit
  1833.  * initalize a GRAPHTAB
  1834.  */
  1835.  
  1836. void Layout::graphTabInit (GRAPHTAB *tab)
  1837. {
  1838.     int i;
  1839.     
  1840.     for (i=0 ; i < SMALLPRIME; i++) {
  1841.     (*tab)[i] = (GRAPH*) NULL;
  1842.     }
  1843. }
  1844.  
  1845.  
  1846. /*****************************************************************************
  1847.     Level functions
  1848. *****************************************************************************/
  1849.  
  1850. /*
  1851.  * levelsInsertNode
  1852.  * insert a node to a specified level. The node wil only be
  1853.  * inserted if its components 'left' and 'right' are NULL. Otherwise
  1854.  * the function assumes, that the node is allready member of
  1855.  * a level. These differences are made to allow incremental
  1856.  * layout of the graph.
  1857.  */
  1858.  
  1859. void Layout::levelsInsertNode (GRAPH *graph, NODE *node, int n)
  1860. {
  1861.     NODE **level;
  1862.  
  1863.     if (n > graph->levels || !graph->level) {
  1864.     fprintf (stderr,"levelsInsertNode: wrong Level!\n");
  1865.     exit (LEVEL_ERROR);
  1866.     }
  1867.  
  1868.     if (!node->right && !node->left) {
  1869.  
  1870.     /*
  1871.      * insert Node at head of level
  1872.      */
  1873.     
  1874.     level = graph->level+n ;
  1875.     node->right = *level;
  1876.     node->left = (NODE*) NULL;
  1877.     if (*level) {
  1878.         (*level)->left = node;
  1879.     }
  1880.     *level = node;
  1881.     node->level = n;
  1882.     }
  1883.  
  1884.     /*
  1885.      * else do nothing, assuming the node is member of a level
  1886.      */
  1887. }
  1888.  
  1889. /*
  1890.  * levelsRemoveNode
  1891.  * remove a node from a level
  1892.  * The node won't be deleted - it's just not referenced by the
  1893.  * specified level any more.
  1894.  */
  1895.  
  1896. void Layout::levelsRemoveNode (GRAPH *graph, NODE *node, int n)
  1897. {
  1898.     NODE **level = graph->level+n;
  1899.  
  1900.     if (!node->left) {
  1901.     *level = node->right;
  1902.     } else {
  1903.     node->left->right = node->right;
  1904.     }
  1905.  
  1906.     if (node->right) {
  1907.     node->right->left = node->left;
  1908.     }
  1909.     node->level = NOLEVEL ;
  1910. }
  1911.  
  1912.  
  1913.     
  1914. /*
  1915.  * levelsEnterNodes
  1916.  * enter all nodes to their level
  1917.  */
  1918.  
  1919. void Layout::levelsEnterNodes (GRAPH *graph, int pullup)
  1920. {
  1921.     int levels;
  1922.     int i;
  1923.     NODE *node;
  1924.  
  1925.     levels = sortApplyLevel (graph);     /* apply levels */
  1926.  
  1927.     /*
  1928.      * check for levels allready there
  1929.      */
  1930.     if (!levels) {
  1931.     fprintf (stderr," levelsEnterNodes: internal Error\n");
  1932.     exit (INTERNAL);
  1933.     }
  1934.     if (!graph->level) {
  1935.     /*
  1936.      * create levels
  1937.      */
  1938.     graphCreateLevels (graph, levels);
  1939.     } else {
  1940.     /*
  1941.      * maybee we have to add some levels
  1942.      */
  1943.     if (levels > graph->levels) {
  1944.         graphAddLevels (graph, levels - graph->levels);
  1945.     }
  1946.     }
  1947.     for ( i = 0 ; i < PRIME ; i++ ) {
  1948.     node = graph->hashtab[i] ;
  1949.     while (node) {
  1950.         /*
  1951.          * add only new nodes ..
  1952.          */
  1953.         if (!node->layouted) {
  1954.         /* 
  1955.          * node was previously not
  1956.          * layouted -- add it
  1957.          */
  1958.         levelsInsertNode (graph,node, node->level);
  1959.         }
  1960.         node = node->hashnext;
  1961.             
  1962.     }
  1963.     }
  1964.     if (pullup) {
  1965.     sortPullupNodes (graph);         /* optimize */
  1966.     }
  1967. }
  1968.     
  1969. /*
  1970.  * levelsIndex
  1971.  * apply an index to a level: the first node of a level will get
  1972.  * index=1, the second index=2, ....
  1973.  */
  1974.  
  1975. void Layout::levelsIndex (NODE **level)
  1976. {
  1977.     int i = 1;
  1978.     NODE *node;
  1979.  
  1980.     node = *level ;
  1981.     while (node) {
  1982.     node->index = i;
  1983.     i++;
  1984.     node = node->right;
  1985.     }
  1986. }
  1987.  
  1988. /*
  1989.  * levelsLength
  1990.  * return the number of elements of a given level
  1991.  */
  1992.  
  1993. int Layout::levelsLength (NODE **level) 
  1994. {
  1995.     NODE *node;
  1996.     int len = 0;
  1997.  
  1998.     node = *level;
  1999.     while (node) {
  2000.     len++;
  2001.     node = node->right;
  2002.     }
  2003.     return len;
  2004. }
  2005.  
  2006.  
  2007. /*****************************************************************************
  2008.     Sorting functions
  2009. *****************************************************************************/
  2010.  
  2011.  
  2012. typedef int (*QuicksortCompareProc)(const void *, const void *);
  2013.  
  2014. /*
  2015.  * sortApplyLevel
  2016.  * apply a level to each node of the graph and return the number of
  2017.  * levels inside the graph
  2018.  */
  2019.  
  2020. int Layout::sortApplyLevel (GRAPH *graph)
  2021. {
  2022.     int level ;
  2023.     int maxlevel = 0;
  2024.     NODE *node;
  2025.     int i;
  2026.  
  2027.     for (i=0; i < PRIME; i++) {
  2028.     node = graph->hashtab[i];
  2029.     while (node) {
  2030.         if (node->level == NOLEVEL) {
  2031.         level = distance (node,node);
  2032.         } else {
  2033.         level = node->level;
  2034.         }
  2035.         maxlevel = ( level > maxlevel ? level : maxlevel );
  2036.         node = node->hashnext;
  2037.     }
  2038.     }
  2039.     return ++maxlevel;
  2040. }
  2041.  
  2042. /*
  2043.  * sortPullupNodes
  2044.  * each node should reside one level below the minimum of the levels
  2045.  * of its anchestors.
  2046.  * This function improves the assigned levels in the way mentioned
  2047.  * above. This works only for graph with no hints inside !
  2048.  */
  2049.  
  2050. void Layout::sortPullupNodes (GRAPH *graph)
  2051. {
  2052.     NODE **level;
  2053.     NODE *node;
  2054.     NODE *rightnode;
  2055.     int newlevel ;
  2056.     
  2057.     if (graph->levels < 2) {
  2058.     return ;
  2059.     }
  2060.     level = graph->level+(graph->levels-1);
  2061.     do {
  2062.     level--;
  2063.     node = *level;
  2064.         
  2065.     while (node) {
  2066.         newlevel = minimumLevel (node) - 1;
  2067.         rightnode = node->right;
  2068.         if (newlevel != node->level) {
  2069.         /*
  2070.          * pull it up
  2071.          */
  2072.         levelsRemoveNode (graph, node, node->level);
  2073.         node->left = (NODE*) NULL;
  2074.         node->right = (NODE*) NULL;
  2075.         levelsInsertNode (graph, node, newlevel);
  2076.         }
  2077.         node = rightnode;
  2078.     }
  2079.         
  2080.     } while ( level != graph->level);
  2081. }
  2082.  
  2083.  
  2084. /*
  2085.  * minimumLevel
  2086.  * return the minimum level of the anchestors of a given regular node.
  2087.  */
  2088.  
  2089. int Layout::minimumLevel (NODE *node)
  2090. {
  2091.     EDGE *edge;
  2092.     int min = 1000 ;
  2093.     int tmp;
  2094.  
  2095.     if (node->type != Regular) {
  2096.     fprintf (stderr,"minimumLevel: not a regular Node!\n");
  2097.     exit (NOT_REGULAR);
  2098.     }
  2099.     
  2100.     edge = node->attr.node.up.head ;
  2101.     if (edge) {
  2102.     while (edge) {
  2103.         tmp = edge->target->level;
  2104.         min = ( tmp < min ? tmp : min);
  2105.         edge = edge->next;
  2106.     }
  2107.     return min;
  2108.     } else {
  2109.     return node->level + 1;
  2110.     }
  2111. }
  2112.         
  2113.  
  2114. /*
  2115.  * distance
  2116.  * determine the max. number of descendants of a given node. Enter this
  2117.  * value to the 'level' component and return it. 
  2118.  */
  2119.  
  2120. int Layout::distance (NODE *node, NODE *origin)
  2121. {
  2122.     int dist = 0;
  2123.     int maxdist = 0;
  2124.     EDGE *edge;
  2125.     EDGE *tmpedge;
  2126.  
  2127.     node->mark = origin;
  2128.     /*
  2129.      * have a look at the type of the node ...
  2130.      */
  2131.     if (node->type == Regular) {
  2132.     edge = node->attr.node.down.head ;
  2133.     while (edge) {
  2134.         if (edge->node->level != NOLEVEL) {
  2135.         dist = 1 + edge->node->level;
  2136.         edge = edge->next;
  2137.         } else if ( edge->node->mark == origin ) {
  2138.         /*
  2139.          * cycle detected ...
  2140.          * there is a cycle (following the
  2141.          * down-references) which is 
  2142.          * closed by the path from node to
  2143.          * edge->node
  2144.          * The cycle can be brocken up by 
  2145.          * inverting the edge between
  2146.          * node and edge->node.
  2147.          */
  2148.         dist = 0;
  2149.         tmpedge = edge->next;
  2150.         graphInvertEdge (node,edge->node);
  2151.         edge = tmpedge;
  2152.         } else {
  2153.         tmpedge = edge->next;
  2154.         dist = 1 + distance (edge->node, origin);
  2155.         edge = tmpedge;
  2156.         }
  2157.         maxdist = (dist > maxdist ? dist : maxdist);
  2158.     }
  2159.     }
  2160.     else {
  2161.     fprintf (stderr,"distance: unleveled Hint!\n");
  2162.     exit (INTERNAL);
  2163.     }
  2164.     /*
  2165.      * enter the distance to the node and return maxdist
  2166.      */
  2167.     node->level = maxdist;
  2168.     return maxdist;
  2169. }
  2170.  
  2171. /*
  2172.  * sortInsertHints
  2173.  * check the descendants of each node. If a descendant is more than one
  2174.  * level apart insert hints on the level inbetween.
  2175.  */
  2176.  
  2177. void Layout::sortInsertHints (GRAPH *graph) 
  2178. {
  2179.     NODE *node;
  2180.     NODE **level;
  2181.     int i;
  2182.  
  2183.     level = graph->level+(graph->levels-1);
  2184.     for ( i = 0 ; i < graph->levels ; i++ ) {
  2185.     node = *level;
  2186.     while (node) {
  2187.         sortCheckNode (graph,node);
  2188.         node = node->right;
  2189.     }
  2190.     level--;
  2191.     }
  2192. }
  2193.  
  2194. /*
  2195.  * sortCheckNode
  2196.  * check the descaendants of a node: if a descandant is more than
  2197.  * one level away insert a hint node.
  2198.  */
  2199.  
  2200. void Layout::sortCheckNode (GRAPH *graph, NODE *node)
  2201. {
  2202.     EDGE *edge;
  2203.     NODE *des;
  2204.     NODE *hint;
  2205.  
  2206.     if (node->type == Regular) {
  2207.     edge = node->attr.node.down.head ;
  2208.     while (edge) {
  2209.         des = edge->node;
  2210.         if (des->level < node->level-1) {
  2211.         /* 
  2212.          * insert hint
  2213.          */
  2214.         hint = graphInsertHint (graph,node, des);
  2215.         levelsInsertNode (graph, hint, node->level-1);
  2216.         }
  2217.         edge = edge->next;
  2218.     }
  2219.     } else {
  2220.     if ( node->attr.hint.down
  2221.          && node->attr.hint.down->level < node->level-1 ) {
  2222.         /*
  2223.          * insert hint
  2224.          */
  2225.         hint = graphInsertHint (graph,node, 
  2226.                     node->attr.hint.down);
  2227.         levelsInsertNode (graph, hint, node->level-1);
  2228.     }
  2229.     }
  2230. }
  2231.  
  2232.  
  2233. /*
  2234.  * sortNodeUpperBary
  2235.  * calculate the bary center of a node according to its ancestors.
  2236.  * ATTENTION: the 'index'-components of the anchestors must be valid!
  2237.  */
  2238.     
  2239.  
  2240. int Layout::sortNodeUpperBary (NODE *node)
  2241. {
  2242.     int sum = 0;
  2243.     int count = 0;
  2244.     EDGE *upnode;
  2245.  
  2246.     if (node->type == Hint) {
  2247.     if (node->attr.hint.up) {
  2248.         return (node->attr.hint.up->index * 10);
  2249.     } else {
  2250.         return 0;
  2251.     }
  2252.     } else {
  2253.     if (node->attr.node.up.length == 0) {
  2254.         return 0;
  2255.     } else {
  2256.         upnode = node->attr.node.up.head;
  2257.         while (upnode) {
  2258.         sum += upnode->node->index;
  2259.         count++;
  2260.         upnode=upnode->next;
  2261.         }
  2262.         return ( (sum * 10) / count );
  2263.     }
  2264.     }
  2265. }
  2266.             
  2267.  
  2268. /*
  2269.  * sortNodeLowerBary
  2270.  * calculate the bary center og a node according to its descendants.
  2271.  * ATTENTION: the 'index'-components of the descendabts must be valid!
  2272.  */
  2273.     
  2274. int Layout::sortNodeLowerBary (NODE *node)
  2275. {
  2276.     int sum = 0;
  2277.     int count = 0;
  2278.     EDGE *downnode;
  2279.  
  2280.     if (node->type == Hint) {
  2281.     if (node->attr.hint.down) {
  2282.         return (node->attr.hint.down->index * 10);
  2283.     } else {
  2284.         return 0;
  2285.     }
  2286.     } else {
  2287.     if (node->attr.node.down.length == 0) {
  2288.         return 0;
  2289.     } else {
  2290.         downnode = node->attr.node.down.head;
  2291.         while (downnode) {
  2292.         sum += downnode->node->index;
  2293.         count++;
  2294.         downnode=downnode->next;
  2295.         }
  2296.         return ( (sum * 10) / count );
  2297.     }
  2298.     }
  2299. }
  2300.             
  2301. /*
  2302.  * sortGraphUpperBary
  2303.  * assign to every node of every level its bary center according to its
  2304.  * anchestors and sort each level by the centers. The algorithm will
  2305.  * start with the top levels and will move down. If the flag is set,
  2306.  * the determined center will not be written to 'center' but 'upcenter' 
  2307.  * and the level won't be sorted. This will be done later by the 
  2308.  * sortAvrgCenter-function.
  2309.  */
  2310.  
  2311. void Layout::sortGraphUpperBary (GRAPH *graph)
  2312. {
  2313.     NODE **uplevel;
  2314.     NODE **level;
  2315.     NODE *node;
  2316.  
  2317.     if (graph->levels < 2) {
  2318.     /* only one level - nothing to do */
  2319.     return;
  2320.     }
  2321.  
  2322.     uplevel = graph->level+(graph->levels-1) ;
  2323.     level = uplevel;
  2324.  
  2325.     do {
  2326.     level--;
  2327.     levelsIndex (uplevel);
  2328.     node = *level;
  2329.     while (node) {
  2330.         node->center = sortNodeUpperBary (node);
  2331.         node = node->right;
  2332.     }
  2333.     sortByCenter (level);
  2334.     uplevel--;
  2335.         
  2336.     } while (level != graph->level);
  2337.  
  2338. }
  2339.  
  2340. /*
  2341.  * sortGraphLowerBary
  2342.  * assign to every node of every level its bary center according to its
  2343.  * descendants and sort each level by the centers. The algorithm will
  2344.  * start with the lowest levels and will move up.
  2345.  * If the flag is set,
  2346.  * the determined center will not be written to 'center' but 'downcenter' 
  2347.  * and the level won't be sorted. This will be done later by the 
  2348.  * sortAvrgCenter-function.
  2349.  */
  2350.  
  2351. void Layout::sortGraphLowerBary (GRAPH *graph)
  2352. {
  2353.     NODE **downlevel;
  2354.     NODE **toplevel;
  2355.     NODE **level;
  2356.     NODE *node;
  2357.  
  2358.     if (graph->levels < 2) {
  2359.     /* only one level - nothing to do */
  2360.     return;
  2361.     }
  2362.  
  2363.     toplevel = graph->level+(graph->levels-1);
  2364.     downlevel = graph->level ;
  2365.     level = downlevel;
  2366.  
  2367.     do {
  2368.     level++;
  2369.     levelsIndex (downlevel);
  2370.     node = *level;
  2371.     while (node) {
  2372.         node->center = sortNodeLowerBary (node);
  2373.         node = node->right;
  2374.     }
  2375.     sortByCenter (level);
  2376.     downlevel++;
  2377.         
  2378.     } while (level != toplevel);
  2379. }
  2380.  
  2381. /*
  2382.  * sortByCenter
  2383.  * sort a level by the bary centers of its nodes. The function will 
  2384.  * first calculate the order and then rebuild the level (i.e. its
  2385.  * list. 
  2386.  */
  2387.  
  2388. void Layout::sortByCenter (NODE **level) 
  2389. {
  2390.     NODE **index;
  2391.     NODE **tmp;
  2392.     NODE *node;
  2393.     int len = levelsLength (level);
  2394.     int i;
  2395.     
  2396.     if (len < 2) {
  2397.     return;
  2398.     }
  2399.     
  2400.     index = (NODE**) malloc (sizeof (NODE*) * len);
  2401.     if (!index) {
  2402.     fprintf (stderr,"sortByCenter: out of memory!\n");
  2403.     exit (MEMORY_ERROR);
  2404.     }
  2405.  
  2406.     /* fill the index */
  2407.     
  2408.     tmp = index;
  2409.     node = *level;
  2410.     while (node) {
  2411.     *(tmp++) = node;
  2412.     node = node->right;
  2413.     }
  2414.  
  2415.     /* sort the index */
  2416.  
  2417.     qsort ( (char*) index , len, sizeof (NODE*), 
  2418.         (QuicksortCompareProc)sortCmpCenters );
  2419.  
  2420.     /*
  2421.      * build up a new list according to the sorted index
  2422.      */
  2423.  
  2424.     tmp = index;
  2425.     *level = *tmp;
  2426.     (*level)->left = (NODE*) NULL;
  2427.  
  2428.     for (i=1 ; i < len ; i++) {
  2429.     (*tmp)->right = *(tmp+1);
  2430.     (*(tmp+1))->left = *tmp;
  2431.     tmp++;
  2432.     }
  2433.     (*tmp)->right = (NODE*) NULL;
  2434.  
  2435.     free ( (char*) index);
  2436. }
  2437.  
  2438. #if 0
  2439. /*
  2440.  * sortAvrgCenter
  2441.  * calculate the average bary center for each node by its upper and 
  2442.  * lower bary center. This value will be stored in 'center' of each
  2443.  * node. Each level will be sorted by the average bary center.
  2444.  */
  2445.  
  2446. void Layout::sortAvrgCenter (GRAPH *graph)
  2447. {
  2448.     NODE **level;
  2449.     NODE *node;
  2450.     int i;
  2451.     
  2452.     level = graph->level;
  2453.     for (i=0; i < graph->levels; i++) {
  2454.     node = *level;
  2455.     while (node) {
  2456.         node->center = (node->upcenter + node->downcenter) / 2;
  2457.         node = node->right;
  2458.     }
  2459.     sortByCenter (level);
  2460.     level++;
  2461.     }
  2462. }
  2463.         
  2464. #endif
  2465.  
  2466. /*
  2467.  * sortCmpCenters
  2468.  * compare the centers of two nodes
  2469.  */
  2470.  
  2471. int Layout::sortCmpCenters (NODE **_n1, NODE **_n2) 
  2472. {    
  2473.     NODE *n1 = *_n1;
  2474.     NODE *n2 = *_n2;
  2475.  
  2476.     // Compare by center
  2477.     int ret = n1->center - n2->center;
  2478.     if (ret != 0 || compare_callback == 0)
  2479.     return ret;
  2480.  
  2481.     // Compare by target name
  2482.     while (n1 && n1->type == Hint)
  2483.     n1 = n1->attr.hint.target;
  2484.     while (n2 && n2->type == Hint)
  2485.     n2 = n2->attr.hint.target;
  2486.  
  2487.     assert (n1 != 0);
  2488.     assert (n1->type == Regular);
  2489.     assert (n2 != 0);
  2490.     assert (n2->type == Regular);
  2491.  
  2492.     char *label1 = n1->attr.node.label;
  2493.     char *label2 = n2->attr.node.label;
  2494.  
  2495.     return compare_callback(label1, label2);
  2496. }
  2497.  
  2498.                 
  2499.                  
  2500. /*
  2501.  * sortInitX
  2502.  * assign initial x-ccordinates to all nodes. Nodes of the same level 
  2503.  * will have at least the minimum distance.
  2504.  * The x- and y-ccordinates of a node represent its center!
  2505.  */
  2506.  
  2507. void Layout::sortInitX (GRAPH *graph) 
  2508. {
  2509.     NODE **level = graph->level;
  2510.     NODE *node;
  2511.     int x;
  2512.     int nodex;
  2513.     int i;
  2514.     
  2515.     for (i=0; i < graph->levels; i++) {
  2516.     node = *level;
  2517.     x = 0;
  2518.     while (node) {
  2519.         if (node->type == Regular) {
  2520.         nodex = x + node->attr.node.w / 2;
  2521.         } else {
  2522.         nodex = x ;
  2523.         }
  2524.         node->x = nodex;
  2525.         x += graph->minxdist ;
  2526.         if (node->type == Regular) {
  2527.         x +=  node->attr.node.w ;
  2528.         } 
  2529.         node = node->right;
  2530.     }
  2531.     level++;
  2532.     }
  2533. }
  2534.  
  2535. /*
  2536.  * sortGraphUpX
  2537.  * assign a x-coordinate to each node of the graph. Each x-coordinate
  2538.  * is determined by the anchestors of each node. The function starts
  2539.  * with the highest level and moves down.
  2540.  */
  2541.  
  2542. void Layout::sortGraphUpX (GRAPH *graph)
  2543. {
  2544.     NODE **level;
  2545.  
  2546.     if (graph->levels < 2) {
  2547.     /* only one level - nothing to do */
  2548.     return;
  2549.     }
  2550.  
  2551.     level = graph->level+(graph->levels-1) ;
  2552.  
  2553.     do {
  2554.     level--;
  2555.     sortLevelUpX (level, graph->minxdist);
  2556.         
  2557.     } while (level != graph->level);
  2558.     
  2559. }
  2560.  
  2561. /*
  2562.  * sortGraphDownX
  2563.  * assign a x-coordinate to each node of the graph. Each x-coordinate
  2564.  * is determined by the descendants of each node. The function starts
  2565.  * with the lowest level and moves up.
  2566.  */
  2567.  
  2568. void Layout::sortGraphDownX (GRAPH *graph)
  2569. {
  2570.     NODE **level;
  2571.     NODE **toplevel = graph->level+(graph->levels-1);
  2572.  
  2573.     if (graph->levels < 2) {
  2574.     /* only one level - nothing to do */
  2575.     return;
  2576.     }
  2577.  
  2578.     level = graph->level;
  2579.  
  2580.     do {
  2581.     level++;
  2582.     sortLevelDownX (level, graph->minxdist);
  2583.     } while (level != toplevel);
  2584. }
  2585.  
  2586. /*
  2587.  * sortLevelUpX
  2588.  * assign x-ccordinates to each node of a level. The preferred x-position 
  2589.  * of a nodes is the average x-position of its anchestors. For resolving
  2590.  * conflicts each node gets a priority depending on its number of
  2591.  * anchestors. Nodes with high priority will be placed on its preferred
  2592.  * position with a higher probability.
  2593.  */
  2594.  
  2595. void Layout::sortLevelUpX (NODE **level, int dist)
  2596. {
  2597.     NODE **index;
  2598.     NODE **tmp;
  2599.     NODE *node;
  2600.  
  2601.     int len = levelsLength (level);
  2602.     int newx;
  2603.  
  2604.     index = (NODE**) malloc (sizeof (NODE*) * (len+1));
  2605.     if (!index) {
  2606.     fprintf (stderr,"sortByCenter: out of memory!\n");
  2607.     exit (MEMORY_ERROR);
  2608.     }
  2609.  
  2610.     /* fill the index */
  2611.     
  2612.     tmp = index;
  2613.     node = *level;
  2614.     while (node) {
  2615.     *(tmp++) = node;
  2616.     node = node->right;
  2617.     }
  2618.     *tmp = (NODE*) NULL;
  2619.  
  2620.     /* 
  2621.      * sort the index by node priority (from low to high)
  2622.      */
  2623.  
  2624.     qsort ( (char*)index, len, sizeof (NODE*), 
  2625.         (QuicksortCompareProc)sortCmpUpperPrio);
  2626.  
  2627.     tmp = index;
  2628.     while (*tmp) {
  2629.     newx = sortAvrgUpperX (*tmp) ;
  2630.     sortMove (*tmp, newx, dist);
  2631.     tmp++;
  2632.     }
  2633.  
  2634.     free ( (char*) index);
  2635. }
  2636.  
  2637. /*
  2638.  * sortLevelDownX
  2639.  * assign x-ccordinates to each node of a level. The preferred x-position 
  2640.  * of a nodes is the average x-position of its descendants. For resolving
  2641.  * conflicts each node gets a priority depending on its number of
  2642.  * descendants. Nodes with high priority will be placed on its preferred
  2643.  * position with a higher probability.
  2644.  */
  2645.  
  2646. void Layout::sortLevelDownX (NODE **level, int dist)
  2647. {
  2648.     NODE **index;
  2649.     NODE **tmp;
  2650.     NODE *node;
  2651.  
  2652.     int len = levelsLength (level);
  2653.     int newx;
  2654.  
  2655.     index = (NODE**) malloc (sizeof (NODE*) * (len+1));
  2656.     if (!index) {
  2657.     fprintf (stderr,"sortLevelDownX: out of memory!\n");
  2658.     exit (MEMORY_ERROR);
  2659.     }
  2660.  
  2661.     /* fill the index */
  2662.     
  2663.     tmp = index;
  2664.     node = *level;
  2665.     while (node) {
  2666.     *(tmp++) = node;
  2667.     node = node->right;
  2668.     }
  2669.     *tmp = (NODE*) NULL;
  2670.  
  2671.     /* 
  2672.      * sort the index by node priority (from low to high)
  2673.      */
  2674.  
  2675.     qsort ( (char*)index, len, sizeof (NODE*), 
  2676.         (QuicksortCompareProc)sortCmpLowerPrio);
  2677.  
  2678.     tmp = index;
  2679.     while (*tmp) {
  2680.     newx = sortAvrgLowerX (*tmp) ;
  2681.     sortMove (*tmp, newx, dist);
  2682.     tmp++;
  2683.     }
  2684.  
  2685.     free ( (char*) index);
  2686. }
  2687.  
  2688. /*
  2689.  * sortLeftSpace
  2690.  * return the free space to the left of a node. The free space is the 
  2691.  * ammount of space you can push all nodes to the left without falling
  2692.  * below the minimum distance between two nodes.
  2693.  */
  2694.  
  2695. int Layout::sortLeftSpace (NODE *node, int dist) 
  2696. {
  2697.     int space = 0;
  2698.     NODE *left;
  2699.     
  2700.     left = node->left;
  2701.     while (left) {
  2702.     space += node->x - left->x - dist;
  2703.     if (node->type == Regular) {
  2704.         space -= node->attr.node.w / 2;
  2705.     }
  2706.     if (left->type == Regular) {
  2707.         space -= left->attr.node.w / 2;
  2708.     }
  2709.     node = left;
  2710.     left = left->left;
  2711.     }
  2712.     space += node->x ;
  2713.     if (node->type == Regular) {
  2714.     space -= node->attr.node.w / 2;
  2715.     }
  2716.     return space;
  2717. }
  2718.  
  2719. /*
  2720.  * sortMoveLeft
  2721.  * move a given node to the left. All nodes to the left of the node
  2722.  * will be moved to the left if required but the minimum distance between 
  2723.  * two nodes won't be influenced. The function assumes, that there is at least
  2724.  * enough space to the left of the node!
  2725.  */
  2726.  
  2727. void Layout::sortMoveLeft (NODE *node, int newx, int dist)
  2728. {
  2729.     int maxleftx = 0;
  2730.     int ready    = 0;
  2731.  
  2732.     do {
  2733.     node->x = newx;
  2734.     if (node->left) {
  2735.         maxleftx = newx - dist;
  2736.         if (node->type == Regular) {
  2737.         maxleftx -= node->attr.node.w / 2;
  2738.         }
  2739.         if (node->left->type == Regular) {
  2740.         maxleftx -= node->left->attr.node.w / 2;
  2741.         }
  2742.         ready = ( node->left->x < maxleftx );
  2743.             
  2744.     }
  2745.     node = node->left;            
  2746.     newx = maxleftx;
  2747.  
  2748.     } while (node && !ready) ;
  2749.     
  2750. }
  2751.  
  2752. /*
  2753.  * sortMoveRight
  2754.  * move a given node to the right. All nodes to the right of the node
  2755.  * will be moved to the right if required but the minimum distance between 
  2756.  * two nodes won't be influenced. 
  2757.  */
  2758.  
  2759. void Layout::sortMoveRight (NODE *node, int newx, int mindist)
  2760. {
  2761.     int minrightx = 0;
  2762.     int ready     = 0;
  2763.  
  2764.     do {
  2765.     node->x = newx;
  2766.  
  2767.     if (node->right) {
  2768.         minrightx = newx + mindist ;
  2769.         if (node->type == Regular) {
  2770.         minrightx += node->attr.node.w /2;
  2771.         }
  2772.         if (node->right->type == Regular) {
  2773.         minrightx += node->right->attr.node.w /2;
  2774.         }
  2775.     }
  2776.     ready =  !(node->right) ||  (node->right->x > minrightx );
  2777.  
  2778.     node = node->right;
  2779.     newx = minrightx;
  2780.  
  2781.     } while (!ready) ;
  2782. }
  2783.  
  2784. /*
  2785.  * sortMove
  2786.  * move a node to a new x-ccordinate. All other nodes of the same level
  2787.  * will be moved, too if required. The minimum distance between two 
  2788.  * node won't be influenced.
  2789.  */ 
  2790.  
  2791. void Layout::sortMove (NODE *node, int newx, int mindist)
  2792. {
  2793.     int leftspace;
  2794.     int oldx;
  2795.     int move;
  2796.  
  2797.     oldx = node->x;
  2798.     if (newx < oldx) {
  2799.     move = oldx - newx;
  2800.     leftspace = sortLeftSpace (node, mindist);
  2801.     if ( move > leftspace ) {
  2802.         newx = oldx - leftspace;
  2803.     }
  2804.     sortMoveLeft (node,newx,mindist);
  2805.     } else if (newx > oldx) {
  2806.     sortMoveRight (node,newx,mindist);
  2807.     }
  2808. }
  2809.     
  2810. /*
  2811.  * sortAvrgUpperX
  2812.  * determine the average x-position of a nodes anchestors.
  2813.  */
  2814.  
  2815. int Layout::sortAvrgUpperX (NODE *node)
  2816. {
  2817.     EDGE *edge;
  2818.     int sumx = 0;
  2819.     int count = 0;
  2820.  
  2821.     if (node->type == Regular) {
  2822.     edge = node->attr.node.up.head ;
  2823.     while (edge) {
  2824.         sumx += edge->node->x;
  2825.         count++;
  2826.         edge = edge->next;
  2827.     }
  2828.     } else if (node->attr.hint.up) {
  2829.     sumx = node->attr.hint.up->x;
  2830.     count = 1;
  2831.     }
  2832.     
  2833.     if (count) {
  2834.     return (sumx / count);
  2835.     } else {
  2836.     return ((node->x * 3) / 4);
  2837.     }
  2838. }
  2839. /*
  2840.  * sortAvrgLowerX
  2841.  * determine the average x-position of a nodes descendants.
  2842.  */
  2843.  
  2844. int Layout::sortAvrgLowerX (NODE *node)
  2845. {
  2846.     EDGE *edge;
  2847.     int sumx = 0;
  2848.     int count = 0;
  2849.  
  2850.     if (node->type == Regular) {
  2851.     edge = node->attr.node.down.head ;
  2852.     while (edge) {
  2853.         sumx += edge->node->x;
  2854.         count++;
  2855.         edge = edge->next;
  2856.     }
  2857.     } else if (node->attr.hint.down) {
  2858.     sumx = node->attr.hint.down->x;
  2859.     count = 1;
  2860.     }
  2861.     
  2862.     if (count) {
  2863.     return (sumx / count);
  2864.     } else {
  2865.     return ((node->x * 3) / 4);
  2866.     }
  2867. }
  2868.  
  2869. /*
  2870.  * sortCmpUpperPrio
  2871.  * compare two nodes by its x-layout-priority: hint nodes will have
  2872.  * the highest priority, other nodes will have a priority equal to
  2873.  * their number of anchestors.
  2874.  */
  2875.  
  2876. int Layout::sortCmpUpperPrio (NODE **fst, NODE **snd)
  2877. {
  2878.     int fstprio, sndprio;
  2879.  
  2880.     if ( (*fst)->type == Hint ) {
  2881.     fstprio = HINTPRIO;
  2882.     } else {
  2883.     fstprio = (*fst)->attr.node.up.length ;
  2884.     }
  2885.     if ( (*snd)->type == Hint ) {
  2886.     sndprio = HINTPRIO;
  2887.     } else {
  2888.     sndprio = (*snd)->attr.node.up.length ;
  2889.     }
  2890.  
  2891.     return (fstprio - sndprio);
  2892. }
  2893.  
  2894. /*
  2895.  * sortCmpLowerPrio
  2896.  * compare two nodes by its x-layout-priority: hint nodes will have
  2897.  * the highest priority, other nodes will have a priority equal to
  2898.  * their number of descendants.
  2899.  */
  2900.  
  2901. int Layout::sortCmpLowerPrio (NODE **fst, NODE **snd)
  2902. {
  2903.     int fstprio, sndprio;
  2904.  
  2905.     if ( (*fst)->type == Hint ) {
  2906.     fstprio = HINTPRIO;
  2907.     } else {
  2908.     fstprio = (*fst)->attr.node.down.length ;
  2909.     }
  2910.     if ( (*snd)->type == Hint ) {
  2911.     sndprio = HINTPRIO;
  2912.     } else {
  2913.     sndprio = (*snd)->attr.node.down.length ;
  2914.     }
  2915.  
  2916.     return (fstprio - sndprio);
  2917. }
  2918.  
  2919. /*
  2920.  * sortLevelVertical
  2921.  * apply y-coordinates to all nodes of a level. Attention: the coordinates 
  2922.  * of a node represent its center! The function will return the highest
  2923.  * y-coordinate covered by the level. 
  2924.  */
  2925.  
  2926. int Layout::sortLevelVertical (NODE **level, int miny, int minydist)
  2927. {
  2928.     int length = 0 ;
  2929.     int maxheight = 0;
  2930.     int newy;
  2931.     NODE *node;
  2932.  
  2933.     /* 
  2934.      * calculate the max. height of the nodes at this level
  2935.      */
  2936.  
  2937.     node = *level;
  2938.     while (node) {
  2939.     if (node->type == Regular && 
  2940.         node->attr.node.h > maxheight) {
  2941.         maxheight = node->attr.node.h;
  2942.     }
  2943.     length++;
  2944.     node = node->right;
  2945.     }
  2946.     /*
  2947.      * the distance to the previous level will be 'minydist'
  2948.      * and some additional dynamic space.
  2949.      */
  2950.     
  2951.     newy = miny + minydist + maxheight / 2 + (length * maxheight) / 5;
  2952.  
  2953.     node = *level;
  2954.     while (node) {
  2955.     node->y = newy;
  2956.     node = node->right;
  2957.     }
  2958.  
  2959.     return newy + maxheight / 2;
  2960. }
  2961.     
  2962. /*
  2963.  * sortGraphVertical
  2964.  * apply a y-coordinate to each node.
  2965.  */
  2966.  
  2967. void Layout::sortGraphVertical (GRAPH *graph)
  2968. {
  2969.     int y = (- graph->minydist) + 1; /* for top level  */
  2970.     NODE **level;
  2971.     int i;
  2972.     
  2973.     if (!graph->levels) {
  2974.     /* nothing to do */
  2975.     return;
  2976.     }
  2977.  
  2978.     level = graph->level+(graph->levels-1);
  2979.     for (i = 0; i < graph->levels; i++) {
  2980.     y = sortLevelVertical (level,y, graph->minydist);
  2981.     level-- ;
  2982.     } 
  2983. }
  2984.