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