URL https://opencores.org/ocsvn/or1k_old/or1k_old/trunk
Subversion Repositories or1k_old

[/] [or1k_old/] [trunk/] [insight/] [libgui/] [src/] [tkCanvLayout.c] - Blame information for rev 1782

Details | Compare with Previous | View Log

/*
 * Copyright (c) 1993 by Sven Delmas
 * All rights reserved.
 * See the file COPYRIGHT for the copyright notes.
 *
 */
 
/* renamed from layout.c to tkCanvLayout.c by Will Taylor 09nov95 */
/* converted to Tk4.1 by Will Taylor 05may96 */
 
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#ifdef HAVE_UNISTD_H
#include <unistd.h>
#endif
 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <tcl.h>
#include "tkCanvLayout.h"
 
#if defined (__MSVC__) && ! defined (HAVE_RAND)
#define HAVE_RAND
#endif
 
/*
 * Functions to compute random numbers.  These don't have to be
 * particular good random number generators.
 */
#ifdef HAVE_RANDOM
#define RANDOM random ()
#define SRANDOM srandom
#else /* HAVE_RANDOM */
#ifdef HAVE_DRAND48
#define MY_RAND_MAX 65536
#define RANDOM ((long) (drand48 () * MY_RAND_MAX))
#define SRANDOM srand48
#else /* HAVE_DRAND48 */
#ifdef HAVE_RAND
#define RANDOM rand ()
#define SRANDOM srand
#else
#warning no random number generator specified, default: random, srandom
#define HAVE_RANDOM
#define RANDOM random ()
#define SRANDOM srandom
#endif /* HAVE_RAND */
#endif /* HAVE_DRAND48 */
#endif /* HAVE_RANDOM */
 
#define LAYOUT_OK TCL_OK
#define LAYOUT_ERROR TCL_ERROR
 
/*
 * This value is added to the line length in pixels, so the distance
 * between two nodes can be calculated correctly.
 */
#define LINE_INCREMENT 10
 
/*
 * Turn on/off debugging.
 */
#define DEBUGGING 1
#define DEBUG_LAYOUT 0
#define DEBUG_PLACE 0
#define TESTING 0
 
/*
 * the datastructures used for layouting.
 */
 
/*
 * these datas/variables are used by the tree layouter.
 */
 
struct TreeData {
  double tmpX;                        /* A temporary x position. */
  double tmpY;                        /* A temporary y position. */
};
typedef struct TreeData TreeData;
 
#define TREE_TMP_X_POS(node)           (node)->treeData.tmpX
#define SET_TREE_TMP_X_POS(node,pos)   (node)->treeData.tmpX = (pos)
#define TREE_TMP_Y_POS(node)           (node)->treeData.tmpY
#define SET_TREE_TMP_Y_POS(node,pos)   (node)->treeData.tmpY = (pos)
 
#if DEBUGGING
#define DEBUG_PRINT_TREE_NODE_POS(node, s) TkCanvLayoutDebugging(node, s, 1)
#else
#define DEBUG_PRINT_TREE_NODE_POS(node, s)
#endif
 
 
/*
 * A topologically ordered node. stored in the global array toplist
 * (0 to toplistnum).
 */
struct Topology {
  struct Nodes *nodePtr;
};
typedef struct Topology Topology;
 
/*
Define edge information
*/
 
struct Edge {
        pItem edgeid;           /* edge identifier */
        ItemGeom info;
        struct Nodes* fromNode; /* A pointer to the ``from'' node struct. */
        struct Nodes* toNode;   /* A pointer to the ``to'' node struct. */
        int ignore;             /* Ignore this edge. */
        int visited;    /* This edge was visited. */
};
typedef struct Edge Edge;
 
/*
 * A graph node. stored in a global array named nodes
 * (0 to nodenum).
 */
struct Nodes {
  pItem itemPtr;        /* Pointer to the Node dual. */
  ItemGeom info;        /* bounding box of the dual */
  int ignore;           /* Ignore this node. */
  int visited;          /* This node was already */
                        /* visited/layouted. */
  double x;             /* The calculated x position. */
  double y;             /* The calculated y position. */
  int parentNum;        /* The number of parent nodes. */
  Edge** parent;        /* The array of parent nodes. */
  int succNum;          /* The number of successor nodes. */
  Edge** succ;          /* The array of successor nodes. */
  struct TreeData treeData; /* temporary tree layout nodes */
#if 0
  char *data;           /* Special data attached to */
                        /* this node. The contents */
                        /* depend from the layouting */
                        /* algorithms. */
#endif
};
typedef struct Nodes Nodes;
typedef struct Nodes Node;
 
/*
 * Defines that hide internal functionality.
 */
 
/*
 * Get and set the edge ignore flag. Edges which are ignored will not
 * be traversed. The first parameter is the edge, and the second
 * parameter (if you call the setting) is the new value of the
 * ignore flag.
 */
#define IGNORE_EDGE(edge)             (edge)->ignore
#define SET_IGNORE_EDGE(edge,mode)    (edge)->ignore=mode
 
/*
 * Get and set the edge visited flag. This flag is usually set to true
 * when the edge was visited. The first parameter is the edge, and the
 * second parameter (if you call the setting) is the new value of the
 * visited flag.
 */
#define VISITED_EDGE(edge)            (edge)->visited
#define SET_VISITED_EDGE(edge,mode)   (edge)->visited=mode
 
/*
 * Get and set the node ignore flag. Nodes which are ignored will not
 * be traversed, and they are not placed/layouted. The first parameter
 * is the node, and the second parameter (if you call the setting) is
 * the new value of the ignore flag.
 */
#define IGNORE_NODE(node)             (node)->ignore
#define SET_IGNORE_NODE(node,mode)    (node)->ignore=mode
#define RESET_IGNORE_NODE(i)          for (i = 0; i < THIS(nodeNum); i++) nodes[i]->ignore=0;
 
/*
 * Get and set the node visited flag. This flag is usually set to true
 * when the node was visited. Currently this flag is mainly used for the
 * topological sorting. The first parameter is the node, and the
 * second parameter (if you call the setting) is the new value of the
 * visited flag.
 */
#define VISITED_NODE(node)            (node)->visited
#define SET_VISITED_NODE(node,mode)   (node)->visited=mode
#define RESET_VISITED_NODE(i)         for (i = 0; i < THIS(nodeNum); i++) THIS(nodes)[i]->visited=0;
 
/*
 * Get and set the number of parent nodes. The first parameter is the
 * node, and the second parameter (if you call the setting) is the new
 * number of parents.
 */
#define PARENT_NUM(node)              (node)->parentNum
#define SET_PARENT_NUM(node,num)      (node)->parentNum=num
 
/*
 * Get and set the number of successor nodes. The first parameter is
 * the node, and the second parameter (if you call the setting) is the
 * new number of successors.
 */
#define SUCC_NUM(node)                (node)->succNum
#define SET_SUCC_NUM(node,num)        (node)->succNum=num
 
/*
 * Get and set the node item. This item is the corresponding dual
 * item for this node. The first parameter is the node, and the second
 * parameter (if you call the setting) is the new dual item pointer.
 */
#define NODE_ITEM(node)               (node)->itemPtr
#define SET_NODE_ITEM(node,item)      (node)->itemPtr=item
 
/* Get and set the node x1,x2,y1, and y2 positions. */
#define NODE_X1_POS(node)              (node)->info.x1
#define NODE_Y1_POS(node)              (node)->info.y1
#define NODE_X2_POS(node)              (node)->info.x2
#define NODE_Y2_POS(node)              (node)->info.y2
 
#define SET_NODE_X1_POS(node,v)              (node)->info.x1 = (v)
#define SET_NODE_Y1_POS(node,v)              (node)->info.y1 = (v)
#define SET_NODE_X2_POS(node,v)              (node)->info.x2 = (v)
#define SET_NODE_Y2_POS(node,v)              (node)->info.y2 = (v)
 
/* Get, by calculation, the node's width and height */
#define CALC_NODE_HEIGHT(n)         (NODE_Y2_POS(n) - NODE_Y1_POS(n))
#define CALC_NODE_WIDTH(n)         (NODE_X2_POS(n) - NODE_X1_POS(n))
 
/* Get/Set the node dual geom */
#define NODE_GEOM(node)              (node)->info
#define SET_NODE_GEOM(node,inf)      (node)->info = (inf)
 
/*
 * Get and set the node x position. This is the value for the final
 * placing of the node. The first parameter is the node, and the
 * second parameter (if you call the setting) is the new x position.
 */
#define NODE_X_POS(node)              (node)->x
#define SET_NODE_X_POS(node,pos)      (node)->x=pos
 
/*
 * Get and set the node y position. This is the value for the final
 * placing of the node. The first parameter is the node, and the
 * second parameter (if you call the setting) is the new y position.
 */
#define NODE_Y_POS(node)              (node)->y
#define SET_NODE_Y_POS(node,pos)      (node)->y=pos
 
/*
 * Get and set the nodes width. The parameter specifies the node
 * whose width and height will be returned.
 */
#define NODE_WIDTH(node)              (node)->info.width
#define SET_NODE_WIDTH(node,size)     (node)->info.width=size
 
/*
 * Get and set the nodes height. The parameter specifies the node
 * whose width and height will be returned.
 */
#define NODE_HEIGHT(node)             (node)->info.height
#define SET_NODE_HEIGHT(node,size)    (node)->info.height=size
 
#define EDGE_ITEM(edge)               (edge)->edgeid
#define SET_EDGE_ITEM(edge,item)      (edge)->edgeid=item
 
/*
 * Return the parent/successor edge/node for the specified node. The
 * second parameter is a integer counter that is used as index for the
 * parent/successor array. Usually this index is generated by a
 * FOR_ALL_* macro.
 */
#define PARENT_EDGE(node, i)          (node)->parent[i]
#define PARENT_NODE(node, i)          (node)->parent[i]->fromNode
#define PARENT_ID(node, i)            (node)->parent[i]->edgeid
#define SUCC_EDGE(node, i)            (node)->succ[i]
#define SUCC_NODE(node, i)            (node)->succ[i]->toNode
#define SUCC_ID(node, i)              (node)->succ[i]->edgeid
#define DUMMY_NODE(node)              ((node)->itemPtr == (pItem) NULL)
 
/* Get and set the edge x1,x2,y1, and y2 positions. */
#define EDGE_X1_POS(edge)              (edge)->info.x1
#define EDGE_X2_POS(edge)              (edge)->info.x2
#define EDGE_Y1_POS(edge)              (edge)->info.y1
#define EDGE_Y2_POS(edge)              (edge)->info.y2
 
/* Get/Set the edge dual geom */
#define EDGE_GEOM(edge)              (edge)->info
#define SET_EDGE_GEOM(edge,inf)      (edge)->info = inf
 
/*
 * Return the node specified by the integer counter passed to this
 * macro. The nodes in the array are topologically ordered (beginning
 * with the index 0. The index is usually created by the macro
 * FOR_ALL_TOP_NODES.
 */
#define TOP_NODE(i)                   THIS(topList)[i]->nodePtr
 
/*
 * Walk through all nodes that are currently defined. The only
 * parameter is the integer counter that is used to index the array.
 */
#define FOR_ALL_NODES(i)              for (i = 0; i < THIS(nodeNum); i++)
 
/*
 * Walk through all edges that are currently defined. The only
 * parameter is the integer counter that is used to index the array.
 */
#define FOR_ALL_EDGES(i)              for (i = 0; i < THIS(edgeNum); i++)
 
/*
 * Walk through all parents/successors of the specified node. The
 * second parameter is the integer counter that is used to index the
 * array.
 */
#define FOR_ALL_PARENTS(node, i)      for (i = 0; i < (node)->parentNum; i++)
#define FOR_ALL_SUCCS(node, i)        for (i = 0; i < (node)->succNum; i++)
 
/*
 * Walk through all nodes in topological order. The only parameter is
 * the integer counter that is used to index the array. This call
 * requires a call of the topological order function, before it can be
 * used.
 */
#define FOR_ALL_TOP_NODES(i)          for (i = 0; i < THIS(topListNum); i++)
 
/*
 * DEBUGGING MACROS.
 */
#if DEBUGGING
#define DEBUG_PRINT_NODE_POS(GRAPH, NODE, S) LayoutDebugging(GRAPH, NODE, S, 0)
#define DEBUG_PRINT_STRING(S1, S2)    fprintf(stderr, "%s %s<\n", S2, S1);
#else
#define DEBUG_PRINT_NODE_POS(GRAPH, NODE, S)
#define DEBUG_PRINT_STRING(S1, S2)
#endif
 
 
#define THIS(x) This->x
 
struct Layout_Graph {
        /* Start with user settable configuration items */
        long iconSpaceV;                /* The vertical space between icons. */
        long iconSpaceH;                /*The horizontal space between icons.*/
        int graphOrder;                 /* Ordering... 0 = LR, 1 = TD. */
        Node *rootNode;                 /* The root node. */
        long xOffset;                   /* The x offset for the placing. */
        long yOffset;                   /* The y offset for the placing. */
 
        /*
         * These datas/variables are used by the random layouter.
         */
        int keepRandomPositions;        /* Don't change the position of */
                                        /* already placed icons when */
                                        /* layouting with the random */
                                        /* placer. */
        long maxX, maxY;                /* Maximal X and Y coordinates */
                                        /* for the random placer. */
        /*
         * Misc. variables used for layouting.
         */
 
        int nodeNum;                    /* The number of graph nodes. */
        Node** nodes;                   /* The list of graph nodes. */
        int edgeNum;                    /* The number of graph edges. */
        Edge** edges;                   /* The list of graph edges. */
        int topListNum;                 /* The current node number. */
        Topology **topList;             /* The sorted nodes. */
        int computeiconsize;            /* Use the biggest icon size. */
        int elementsPerLine;            /* How many elements per line. */
        int hideEdges;                  /* make edges zero length (Matrix)*/
        int edgeHeight;                 /* The standard height of an edge. */
        int edgeOrder;                  /* Set the edges to the layout order.*/
        int edgeWidth;                  /* The standard width of an edge. */
        int iconHeight, iconWidth;      /* The standard icon size. */
        double posX1, posY1, posX2, posY2;      /* Coordinates */
        double maxXPosition;            /* Maximal X and Y coordinates */
        double maxYPosition;            /* for the random placer. */
        int layoutTypesNum;             /* The number of layout types. */
        char **layoutTypes;             /* The types of items that will
                                           be layouted. */
        int gridlock;                   /* avoid using diagnal lines */
        char* errmsg;
 
#ifdef ignore
        char* graphName
        char *idlist;                   /* The list of ids to layout. */
        char *sortcommand;              /* The Tcl procedure called for */
        long rootId;
        char convertBuffer[100];        /* Convert numbers to strings.*/
#endif
};
 
typedef struct Layout_Graph Layout_Graph;
 
static  int deleteedge _ANSI_ARGS_((Layout_Graph*,Edge*,int));
static  int deletenode _ANSI_ARGS_((Layout_Graph*,Node*,int));
static  void compress_succ _ANSI_ARGS_((Layout_Graph*,Node*));
static  void compress_parent _ANSI_ARGS_((Layout_Graph*,Node*));
 
static  void LayoutISISetX _ANSI_ARGS_((Layout_Graph*, Node*));
static  void LayoutISISetY _ANSI_ARGS_((Layout_Graph*, Node*/*, int type*/));
static  void LayoutTreeSetX _ANSI_ARGS_((Layout_Graph*, Node*));
static  void LayoutTreeSetY _ANSI_ARGS_((Layout_Graph*, Node*));
static  int LayoutBuildGraph _ANSI_ARGS_((Layout_Graph*));
static  Node* LayoutGraphRoot _ANSI_ARGS_((Layout_Graph*));
static  void LayoutGraphSortTopological _ANSI_ARGS_((Layout_Graph*, Node*));
static  int LayoutGraphPlaceNodes _ANSI_ARGS_((Layout_Graph*));
static  int LayoutGraphPlaceEdges _ANSI_ARGS_((Layout_Graph*));
static  int LayoutEdgeWidth _ANSI_ARGS_((Layout_Graph*));
static  int LayoutEdge _ANSI_ARGS_((Layout_Graph*, Edge*, Node*, Node*));
 
#if(defined(__cplusplus) || defined(c_plusplus))
#define AC1(t1,a1) (t1 a1)
#define AC2(t1,a1,t2,a2) (t1 a1, t2 a2)
#define AC3(t1,a1,t2,a2,t3,a3) (t1 a1, t2 a2, t3 a3)
#define AC4(t1,a1,t2,a2,t3,a3,t4,a4) (t1 a1, t2 a2, t3 a3, t4 a4)
#define AC5(t1,a1,t2,a2,t3,a3,t4,a4,t5,a5) (t1 a1, t2 a2, t3 a3, t4 a4, t5 a5)
#else
#define AC1(t1,a1) (a1) t1 a1;
#define AC2(t1,a1,t2,a2) (a1,a2) t1 a1; t2 a2;
#define AC3(t1,a1,t2,a2,t3,a3) (a1,a2,a3) t1 a1; t2 a2; t3 a3;
#define AC4(t1,a1,t2,a2,t3,a3,t4,a4) (a1,a2,a3,a4) t1 a1; t2 a2; t3 a3; t4 a4;
#define AC5(t1,a1,t2,a2,t3,a3,t4,a4,t5,a5) (a1,a2,a3,a4,a5) t1 a1; t2 a2; t3 a3; t4 a4; t5 a5;
#endif
 
static
void
MY_LayoutISISetY _ANSI_ARGS_((Layout_Graph*, Node*, double));
 
 
 
/*
 *--------------------------------------------------------------
 *
 * LayoutDebugging --
 *
 *      This procedure is invoked to print debugging informations.
 *
 * Results:
 *      None
 *
 * Side effects:
 *      See the user documentation.
 *
 *--------------------------------------------------------------
 */
 
#if DEBUGGING
void
LayoutDebugging(
     Layout_Graph* This,
     Node *currentNode,                /* This is the current node. */
     char *string,
     int type)
{
  double tmpX, tmpY;
 
  if(THIS(graphOrder)) {
    /* Place nodes top down. */
    tmpX = THIS(xOffset) - NODE_HEIGHT(THIS(rootNode));
    tmpY = THIS(yOffset) - NODE_WIDTH(THIS(rootNode));
  } else {
    /* Place nodes left to right. */
    tmpX = THIS(xOffset) - NODE_WIDTH(THIS(rootNode));
    tmpY = THIS(yOffset) - NODE_HEIGHT(THIS(rootNode));
  }
 
  if(!DUMMY_NODE(currentNode)) {
    fprintf(stderr, "%-6s Node %-3ld: x=%-g y=%-g x=%-g y=%-g\n",
            /* string, CANVAS_ITEM_ID(NODE_ITEM(currentNode)), 08nov95 wmt */
            string, 0L,
            NODE_X_POS(currentNode) + tmpX,
            NODE_Y_POS(currentNode) + tmpY,
            NODE_X_POS(currentNode),
            NODE_Y_POS(currentNode));
  } else {
    fprintf(stderr, "%-6s Node dummy: x=%-g y=%-g x=%-g y=%-g\n",
            string, NODE_X_POS(currentNode) + tmpX,
            NODE_Y_POS(currentNode) + tmpY,
            NODE_X_POS(currentNode),
            NODE_Y_POS(currentNode));
  }
  switch (type) {
  case 1:
    fprintf(stderr,
            "                 x=%-g y=%-g x=%-g y=%-g\n",
            TREE_TMP_X_POS(currentNode) + tmpX,
            TREE_TMP_Y_POS(currentNode) + tmpY,
            TREE_TMP_X_POS(currentNode),
            TREE_TMP_Y_POS(currentNode));
    break;
  default:
    break;
  }
}
#endif
 
/*
 *--------------------------------------------------------------
 *
 * LayoutISISetX --
 *
 *      This procedure is invoked to calculate the x ISI position.
 *
 * Results:
 *      None
 *
 * Side effects:
 *      See the user documentation.
 *
 *--------------------------------------------------------------
 */
#ifndef max
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) > (b) ? (b) : (a))
#endif
static
void
LayoutISISetX AC2(Layout_Graph*,This, Node*,currentNode) /* This is the current node. */
{
  int counter, visitedAllChilds = 1;
 
  if(IGNORE_NODE(currentNode)) {
    return;
  }
  if(VISITED_NODE(currentNode)) {
    return;
  }
 
  FOR_ALL_SUCCS(currentNode, counter) {
    /* Are there un layouted children ? */
    if(IGNORE_EDGE(SUCC_EDGE(currentNode, counter))) {
      continue;
    }
    if(IGNORE_NODE(SUCC_NODE(currentNode, counter))) {
      continue;
    }
    if(!VISITED_NODE(SUCC_NODE(currentNode, counter))) {
      visitedAllChilds = 0;
    }
  }
 
/*  SET_VISITED_NODE(currentNode, 1);*/
  if(!visitedAllChilds) {
    FOR_ALL_SUCCS(currentNode, counter) {
      /* Layout the children of this node. */
      if(IGNORE_EDGE(SUCC_EDGE(currentNode, counter))) {
        continue;
      }
      if(IGNORE_NODE(SUCC_NODE(currentNode, counter))) {
        continue;
      }
      if(!VISITED_NODE(SUCC_NODE(currentNode, counter))) {
        LayoutISISetX(This,SUCC_NODE(currentNode, counter));
      }
    }
    if(SUCC_NUM(currentNode) == 1) {
      SET_NODE_X_POS(currentNode,
                     NODE_X_POS(SUCC_NODE(currentNode, 0)));
    }
    else
    {
 
      /* Khamis 8:30 23 Oct 1996 */
        int i, pingo = 0;
        double x1 = 0.0, x2 = 0.0;
        FOR_ALL_SUCCS (currentNode, i)
        {
           if(IGNORE_NODE(SUCC_NODE(currentNode, i)))
             continue;
           /*
           if(! VISITED_NODE(SUCC_NODE(currentNode, i)))
                continue;
            */
           if (PARENT_NODE(SUCC_NODE(currentNode, i), 0) !=
                        currentNode)
             continue;
           if (! pingo)
           {
             x1 = NODE_X_POS(SUCC_NODE(currentNode, i));
             pingo = 1;
           }
           x1 = min (x1, NODE_X_POS(SUCC_NODE(currentNode, i)));
           x2 = max (x2, NODE_X_POS(SUCC_NODE(currentNode, i)));
        }
        if (! pingo)
        {
          x1 = x2 = NODE_X_POS (SUCC_NODE(currentNode, 0));
        }
 
#if 1   /* Khamis 8:30 23 Oct 1996 */
        SET_NODE_X_POS(currentNode, x1 + (x2 - x1) / 2.0);
#else   /* original */
        SET_NODE_X_POS(currentNode,
                     NODE_X_POS(SUCC_NODE(currentNode, 0)) +
                     ((NODE_X_POS(SUCC_NODE(currentNode,
                                           SUCC_NUM(currentNode)-1)) -
                       NODE_X_POS(SUCC_NODE(currentNode, 0))) / 2));
#endif
    }
  }
  else
  {
    /* Set the x position of the current node. */
    if(THIS(graphOrder)) {
      /* Place nodes top down. */
      SET_NODE_X_POS(currentNode, THIS(maxXPosition));
      THIS(maxXPosition) = NODE_X_POS(currentNode) + THIS(iconSpaceH) +
        THIS(edgeWidth) + NODE_WIDTH(currentNode);
    } else {
      /* Place nodes left to right. */
      SET_NODE_X_POS(currentNode, THIS(maxXPosition));
      THIS(maxXPosition) = NODE_X_POS(currentNode) + THIS(iconSpaceV) +
        THIS(edgeHeight) + NODE_HEIGHT(currentNode);
    }
  }
  SET_VISITED_NODE(currentNode, 1);
}
 
/*
 *--------------------------------------------------------------
 *
 * LayoutISISetY --
 *
 *      This procedure is invoked to calculate the y ISI position.
 *
 * Results:
 *      None
 *
 * Side effects:
 *      See the user documentation.
 *
 *--------------------------------------------------------------
 */
 
    /* ARGSUSED */
static
void
LayoutISISetY AC2(Layout_Graph*,This, Node*,currentNode) /* This is the current node. */
{
  int counter;
  double tmpMaxY;
 
  /* Was this node already layouted ? */
  if(IGNORE_NODE(currentNode)) {
    return;
  }
  if(VISITED_NODE(currentNode)) {
    return;
  }
 
  SET_VISITED_NODE(currentNode, 1);
 
  if(PARENT_NUM(currentNode) != 0) {
    FOR_ALL_PARENTS(currentNode, counter) {
      /* Are there un layouted parents ? */
      if(IGNORE_EDGE(PARENT_EDGE(currentNode, counter))) {
        /*continue;*/
        break;
      }
      if(IGNORE_NODE(PARENT_NODE(currentNode, counter))) {
        /*continue;*/
        break;
      }
      if(!VISITED_NODE(PARENT_NODE(currentNode, counter))) {
        LayoutISISetY(This,PARENT_NODE(currentNode, counter));
      }
      break;
    }
    tmpMaxY = 0;
    FOR_ALL_PARENTS(currentNode, counter) {
      if(THIS(graphOrder)) {
        if(NODE_Y_POS(PARENT_NODE(currentNode, counter)) +
            NODE_HEIGHT(PARENT_NODE(currentNode, counter)) > tmpMaxY) {
          tmpMaxY = NODE_Y_POS(PARENT_NODE(currentNode, counter)) +
            NODE_HEIGHT(PARENT_NODE(currentNode, counter));
        }
      } else {
        if(NODE_Y_POS(PARENT_NODE(currentNode, counter)) +
            NODE_WIDTH
            (PARENT_NODE(currentNode, counter)) > tmpMaxY) {
          tmpMaxY = NODE_Y_POS(PARENT_NODE(currentNode, counter)) +
            NODE_WIDTH(PARENT_NODE(currentNode, counter));
        }
      }
      break;
    }
    if(THIS(graphOrder)) {
      /* Place nodes top down. */
      SET_NODE_Y_POS(currentNode, tmpMaxY + THIS(edgeHeight) + THIS(iconSpaceV));
    } else {
      /* Place nodes left to right. */
      SET_NODE_Y_POS(currentNode, tmpMaxY + THIS(edgeWidth) + THIS(iconSpaceH));
    }
  } else {
    if(THIS(graphOrder)) {
      /* Place nodes top down. */
      SET_NODE_Y_POS(currentNode, 0);
    } else {
      /* Place nodes left to right. */
      SET_NODE_Y_POS(currentNode, 0);
    }
  }
 
  /*SET_VISITED_NODE(currentNode, 1);*/
}
 
/*********************************************************/
static
void
MY_LayoutISISetY AC3(Layout_Graph*,This, Node*,currentNode, double, y)
{
  int counter;
  double tmpMaxY;
 
  /* Was this node already layouted ? */
  if(IGNORE_NODE(currentNode)) {
    return;
  }
  if(VISITED_NODE(currentNode)) {
    return;
  }
 
  SET_VISITED_NODE(currentNode, 1);
 
  SET_NODE_Y_POS(currentNode, y);
 
  FOR_ALL_SUCCS (currentNode, counter) {
      /* Are there un layouted parents ? */
      if(IGNORE_EDGE(PARENT_EDGE(currentNode, counter))) {
        /*continue;*/
        break;
      }
      if(IGNORE_NODE(PARENT_NODE(currentNode, counter))) {
        /*continue;*/
        break;
      }
 
      if (PARENT_NODE(SUCC_NODE(currentNode, counter), 0) !=
          currentNode)
        continue;
 
      if(THIS(graphOrder)) {
        tmpMaxY = NODE_Y_POS  (currentNode) + NODE_HEIGHT (currentNode);
                /*+ THIS(edgeHeight) + THIS(iconSpaceV); */
      } else {
        tmpMaxY = NODE_Y_POS(currentNode) +
                  NODE_WIDTH(currentNode) +
                  THIS(edgeWidth) + THIS(iconSpaceH);
      }
 
      MY_LayoutISISetY(This, PARENT_NODE(currentNode, counter),
                       tmpMaxY);
  }
}
/*********************************************************/
 
 
 
/*
 *--------------------------------------------------------------
 *
 * LayoutTreeSetX --
 *
 *      This procedure is invoked to calculate the x tree position.
 *      The procedure is called for all icons in the topological
 *      order.
 *
 * Results:
 *      None
 *
 * Side effects:
 *      See the user documentation.
 *
 *--------------------------------------------------------------
 */
 
static
void
LayoutTreeSetX AC2(Layout_Graph*,This, Node*,currentNode) /* This is the current node */
{
  int counter;
 
  /* Was this node already layouted ? */
  if(TREE_TMP_X_POS(currentNode) != -1 || IGNORE_NODE(currentNode)) {
    return;
  }
  if(DUMMY_NODE(currentNode)) {
    return;
  }
 
  SET_VISITED_NODE(currentNode, 1);
  if(PARENT_NUM(currentNode) > 0 &&
      VISITED_NODE(PARENT_NODE(currentNode, 0))) {
    /* There are parents, and the parent was already visited. This */
    /* means that this node is the first child we layout at this */
    /* level. That means it occurs at the same level as the parent. */
    SET_VISITED_NODE(PARENT_NODE(currentNode, 0), 0);
    SET_TREE_TMP_X_POS(currentNode,
                       TREE_TMP_X_POS(PARENT_NODE(currentNode, 0)));
  } else {
    /* Append the icon to the current maximal x position. It is not */
    /* the first child of the parent. */
    SET_TREE_TMP_X_POS(currentNode, THIS(maxXPosition));
  }
 
  /* Set the x position of the current node. If the order is top down, */
  /* we use the maximum edge width. */
  if(THIS(graphOrder)) {
    /* Place nodes top down. */
    SET_NODE_X_POS(currentNode, TREE_TMP_X_POS(currentNode));
    /* Do we have a new maximal x position ? */
    if(NODE_X_POS(currentNode) + THIS(iconSpaceH) + THIS(edgeWidth) +
        NODE_WIDTH(currentNode) > THIS(maxXPosition)) {
      THIS(maxXPosition) = NODE_X_POS(currentNode) + THIS(iconSpaceH) +
        THIS(edgeWidth) + NODE_WIDTH(currentNode);
    }
  } else {
    /* Place nodes left to right. */
    SET_NODE_X_POS(currentNode, TREE_TMP_X_POS(currentNode));
    /* Do we have a new maximal x position ? */
    if((NODE_X_POS(currentNode) + THIS(iconSpaceV) + THIS(edgeHeight) +
         NODE_HEIGHT(currentNode)) > THIS(maxXPosition)) {
      THIS(maxXPosition) = NODE_X_POS(currentNode) + THIS(iconSpaceV) +
        THIS(edgeHeight) + NODE_HEIGHT(currentNode);
    }
  }
 
  /* Walk through all successors. */
  FOR_ALL_SUCCS(currentNode, counter) {
    /* Layout the children of this node. */
    if(IGNORE_NODE(SUCC_EDGE(currentNode, counter))) {
      continue;
    }
    LayoutTreeSetX(This,SUCC_NODE(currentNode, counter));
  }
}
 
/*
 *--------------------------------------------------------------
 *
 * LayoutTreeSetY --
 *
 *      This procedure is invoked to calculate the y tree position.
 *
 * Results:
 *      None
 *
 * Side effects:
 *      See the user documentation.
 *
 *--------------------------------------------------------------
 */
 
static
void
LayoutTreeSetY AC2(Layout_Graph*,This, Node*,currentNode) /* This is the current node. */
{
  int counter;
  double tmpMaxY;
 
  if(IGNORE_NODE(currentNode)) {
    return;
  }
  if(DUMMY_NODE(currentNode)) {
    return;
  }
  if(VISITED_NODE(currentNode)) {
    return;
  }
 
  SET_VISITED_NODE(currentNode, 1);
  tmpMaxY = 0;
  /* Walk through all parents. */
  FOR_ALL_PARENTS(currentNode, counter) {
    /* Find the parent of this node that has the greatest Y. This way */
    /* the graph is always growing to the Y direction. */
    if(IGNORE_NODE(PARENT_EDGE(currentNode, counter)) ||
        IGNORE_NODE(PARENT_NODE(currentNode, counter))) {
      continue;
    }
    if(THIS(graphOrder)) {
      /* Place nodes top down. */
      if(TREE_TMP_Y_POS(PARENT_NODE(currentNode, counter)) +
          NODE_HEIGHT(PARENT_NODE(currentNode, counter)) +
          THIS(edgeHeight) + THIS(iconSpaceV) > tmpMaxY) {
        tmpMaxY = TREE_TMP_Y_POS(PARENT_NODE(currentNode, counter)) +
          NODE_HEIGHT(PARENT_NODE(currentNode, counter)) + THIS(edgeHeight) +
            THIS(iconSpaceV);
      }
    } else {
      if(TREE_TMP_Y_POS(PARENT_NODE(currentNode, counter)) +
          NODE_WIDTH(PARENT_NODE(currentNode, counter)) +
          THIS(edgeWidth) + THIS(iconSpaceH) > tmpMaxY) {
        tmpMaxY = TREE_TMP_Y_POS(PARENT_NODE(currentNode, counter)) +
          NODE_WIDTH(PARENT_NODE(currentNode, counter)) + THIS(edgeWidth) +
            THIS(iconSpaceH);
      }
    }
  }
 
  /* Set the y position of the current node. */
  if(THIS(graphOrder)) {
    /* Place nodes top down. */
    SET_NODE_Y_POS(currentNode, tmpMaxY);
    /* Keep the maximal y position, this way we can later calculate the */
    /* correct Y position for children of this widget. */
    SET_TREE_TMP_Y_POS(currentNode, NODE_Y_POS(currentNode));
  } else {
    /* Place nodes left to right. */
    SET_NODE_Y_POS(currentNode, tmpMaxY);
    /* Keep the maximal y position, this way we can later calculate the */
    /* correct Y position for children of this widget. */
    SET_TREE_TMP_Y_POS(currentNode, NODE_Y_POS(currentNode));
  }
}
 
/*
 *--------------------------------------------------------------
 *
 * createnode --
 *
 *      This procedure is invoked to create a new node. Optionally the
 *      procedure can be used to create dummy nodes. In that case the
 *      fromNode and toNode parameters are specified.
 *
 * Results:
 *      None
 *
 * Side effects:
 *      See the user documentation.
 *
 *--------------------------------------------------------------
 */
 
int
LayoutCreateNode AC4(Layout_Graph*,This,pItem,itemPtr, pItem,fromNode, pItem, toNode)
{
  int counter1 = 0, counter2 = 0, counter3 = 0, counter4 = 0, found = 0;
  Node *tmpNode;
  Edge *tmpEdge;
  ItemGeom bbox;
 
  /* see if this item was already added */
  FOR_ALL_NODES(counter1) {
        if(NODE_ITEM(THIS(nodes)[counter1]) == itemPtr) {
            THIS(errmsg) = "attempt to insert duplicate graph node";
            return LAYOUT_ERROR;
        }
  }
  THIS(nodeNum)++;
  if(THIS(nodes) == NULL) {
    THIS(nodes) = (Node **) ckalloc(THIS(nodeNum) * sizeof(Node *));
  } else {
    THIS(nodes) = (Node **) ckrealloc((char *) THIS(nodes),
                              THIS(nodeNum) * sizeof(Node *));
  }
  tmpNode = (Node *) ckalloc(sizeof(Node));
  SET_NODE_ITEM(tmpNode, itemPtr);
  SET_IGNORE_NODE(tmpNode, 0);
  SET_VISITED_NODE(tmpNode, 0);
  SET_NODE_X_POS(tmpNode, 0);
  SET_NODE_Y_POS(tmpNode, 0);
  SET_TREE_TMP_X_POS(tmpNode, -1);
  SET_TREE_TMP_Y_POS(tmpNode, -1);
  bbox.x1 = bbox.y1 = bbox.x2 = bbox.y2 = bbox.width = bbox.height = 0;
  SET_NODE_GEOM(tmpNode,bbox);
  SET_PARENT_NUM(tmpNode, 0);
  tmpNode->parent = (Edge**) NULL;
  SET_SUCC_NUM(tmpNode, 0);
  tmpNode->succ = (Edge**) NULL;
  THIS(nodes)[THIS(nodeNum)-1] = tmpNode;
 
#if 0
  /* create the specific data slot. */
  if(createdatanode != NULL) {
    (*createdatanode)(THIS(nodes)[THIS(nodeNum)-1]);
  }
#endif
 
  /* insert the dummy node. */
  if(fromNode != (Node*) NULL && toNode != (Node*) NULL) {
    FOR_ALL_NODES(counter1) {
      if(THIS(nodes)[counter1] == fromNode) {
        FOR_ALL_SUCCS(THIS(nodes)[counter1], counter2) {
          if(SUCC_NODE(THIS(nodes)[counter1], counter2) == toNode) {
            found++;
            break;
          }
        }
        break;
      }
    }
    FOR_ALL_NODES(counter3) {
      if(THIS(nodes)[counter3] == toNode) {
        FOR_ALL_PARENTS(THIS(nodes)[counter3], counter4) {
          if(PARENT_NODE(THIS(nodes)[counter3], counter4) == fromNode) {
            found++;
            break;
          }
        }
        break;
      }
    }
    if(found == 2) {
      DEBUG_PRINT_NODE_POS(This, THIS(nodes)[counter1], "dummy insert from");
      DEBUG_PRINT_NODE_POS(This, THIS(nodes)[counter3], "dummy insert to");
      SET_PARENT_NUM(tmpNode, 1);
      SET_SUCC_NUM(tmpNode, 1);
      SET_NODE_X_POS(tmpNode, 10);
      SET_NODE_Y_POS(tmpNode, 10);
      THIS(nodes)[THIS(nodeNum)-1]->parent = (Edge**)
        ckalloc(THIS(nodes)[THIS(nodeNum)-1]->parentNum * sizeof(Edge*));
      tmpEdge = (Edge* ) ckalloc(sizeof(Edge));
      SET_IGNORE_EDGE(tmpEdge, 0);
      SET_VISITED_EDGE(tmpEdge, 0);
      tmpEdge->fromNode = THIS(nodes)[counter1];
      tmpEdge->toNode = THIS(nodes)[counter3];
      THIS(nodes)[THIS(nodeNum)-1]->parent[0] = tmpEdge;
      THIS(nodes)[THIS(nodeNum)-1]->succ = (Edge**)
        ckalloc(THIS(nodes)[THIS(nodeNum)-1]->succNum * sizeof(Edge* ));
      THIS(nodes)[THIS(nodeNum)-1]->succ[0] = tmpEdge;
      THIS(nodes)[counter3]->parent[counter4]->toNode = tmpNode;
      THIS(nodes)[counter1]->succ[counter2]->fromNode = tmpNode;
    }
  }
  return LAYOUT_OK;
}
 
int
LayoutDeleteNode AC2(Layout_Graph*,This, pItem,nodeid)
{
    register int i;
 
    /* find the matching node*/
    FOR_ALL_NODES(i) {
        if(NODE_ITEM(THIS(nodes)[i]) == nodeid) {
            return deletenode(This,THIS(nodes)[i],i);
        }
    }
    THIS(errmsg) = "node delete: no such node";
    return LAYOUT_ERROR;
}
 
static
int
deletenode AC3(Layout_Graph*,This, Node*,thisnode, int,index)
{
    register int i;
    /* remove all attached edges */
    FOR_ALL_EDGES(i) {
        register Edge* e = THIS(edges)[i];
        if(e->toNode == thisnode
           || e->fromNode == thisnode) {
            deleteedge(This,e,i);
        }
    }
 
    /* clean up node */
    if(thisnode->parent) ckfree((char*)thisnode->parent);
    if(thisnode->succ) ckfree((char*)thisnode->succ);
 
    /* free and clear node */
    THIS(nodeNum)--;
    if(THIS(nodeNum) > 0) {
        THIS(nodes)[index] = THIS(nodes)[THIS(nodeNum)];
    }
    ckfree((char*)thisnode);
    return LAYOUT_OK;
}
 
 
int
LayoutCreateEdge AC4(Layout_Graph*,This, pItem,edgeid, pItem,fromid, pItem,toid)
{
    register int i;
    register Node* n;
    Node* fromnode = NULL;
    Node* tonode = NULL;
    Edge* tmpEdge;
 
    /* see if this item was already added */
    FOR_ALL_EDGES(i) {
        if(EDGE_ITEM(THIS(edges)[i]) == edgeid) {
            THIS(errmsg) = "attempt to insert duplicate graph edge";
            return LAYOUT_ERROR;
        }
    }
    /* locate the actual from and to nodes */
    FOR_ALL_NODES(i) {
        n = THIS(nodes)[i];
        if(NODE_ITEM(n) == fromid) {
            fromnode = n;
        } else if(NODE_ITEM(n) == toid) {
            tonode = n;
        }
    }
    if(!fromnode || !tonode) {
        THIS(errmsg) = "edge was missing from or to node";
        return LAYOUT_ERROR;
    }
 
    /* create Edge */
    tmpEdge = (Edge* ) ckalloc(sizeof(Edge));
    if(!tmpEdge) {
        THIS(errmsg) = "malloc failure";
        return LAYOUT_ERROR;
    }
    SET_IGNORE_EDGE(tmpEdge, 0);
    SET_VISITED_EDGE(tmpEdge, 0);
    tmpEdge->edgeid = edgeid;
    tmpEdge->fromNode = fromnode;
    tmpEdge->toNode = tonode;
 
    THIS(edgeNum)++;
    if(THIS(edges) == NULL) {
        THIS(edges) = (Edge* *) ckalloc(THIS(edgeNum) * sizeof(Edge* ));
    } else {
        THIS(edges) = (Edge* *) ckrealloc((char *) THIS(edges),
                              THIS(edgeNum) * sizeof(Edge* ));
    }
    THIS(edges)[THIS(edgeNum)-1] = tmpEdge;
 
    /* insert the succ and parent edge structs */
    tonode->parentNum++;
    if(tonode->parent == NULL) {
        tonode->parent = (Edge**)
                ckalloc(tonode->parentNum * sizeof(Edge*));
    } else {
        tonode->parent = (Edge**)
                ckrealloc((char *) tonode->parent,
                        tonode->parentNum * sizeof(Edge*));
    }
    tonode->parent[tonode->parentNum - 1] = tmpEdge;
 
    fromnode->succNum++;
    if(fromnode->succ == NULL) {
        fromnode->succ = (Edge**)
                ckalloc(fromnode->succNum * sizeof(Edge*));
    } else {
        fromnode->succ = (Edge**)
                ckrealloc((char *) fromnode->succ,
                        fromnode->succNum * sizeof(Edge*));
    }
    fromnode->succ[fromnode->succNum-1] = tmpEdge;
 
    return LAYOUT_OK;
}
 
static
void
compress_succ AC2(Layout_Graph*,This, Node*,n)
{
    register Edge** p;
    register Edge** q;
 
    for(p=n->succ,q=p+(n->succNum);p < q;p++) {
        if(*p != NULL) continue;
        /* found a null entry earlier than where q is pointing */
        /* move q down to look for a non-null entry */
        do { --q; } while(q > p && *q == NULL);
        if(q <= p) break; /* p points to last non-null entry */
        *p = *q;
    }
    n->succNum = p - n->succ;
}
 
static
void
compress_parent AC2(Layout_Graph*,This, Node*,n)
{
    register Edge** p;
    register Edge** q;
 
    for(p=n->parent,q=p+(n->parentNum);p < q;p++) {
        if(*p != NULL) continue;
        /* found a null entry earlier than where q is pointing */
        /* move q down to look for a non-null entry */
        do { --q; } while(q > p && *q == NULL);
        if(q <= p) break; /* p points to last non-null entry */
        *p = *q;
    }
    n->parentNum = p - n->parent;
}
 
static
int
deleteedge AC3(Layout_Graph*,This, Edge*,e, int,index)
{
    register int i;
    register int j;
    register int found;
 
    /* remove all references to this Edge */
    FOR_ALL_NODES(i) {
        register Node* n = THIS(nodes)[i];
        found = 0;
        FOR_ALL_SUCCS(n,j) {
            if(SUCC_EDGE(n,j) == e) {
                SUCC_EDGE(n,j) = NULL;
                found = 1;
            }
        }
        if(found) {compress_succ(This,n);}
        found = 0;
        FOR_ALL_PARENTS(n,j) {
            if(PARENT_EDGE(n,j) == e) {
                PARENT_EDGE(n,j) = NULL;
                found = 1;
            }
        }
        if(found) {compress_parent(This,n);}
    }
    /* free and clear Edge*/
    THIS(edgeNum)--;
    if(THIS(edgeNum) > 0) {
        THIS(edges)[index] = THIS(edges)[THIS(edgeNum)];
    }
    ckfree((char*)e);
    return LAYOUT_OK;
}
 
int
LayoutDeleteEdge AC2(Layout_Graph*,This, pItem,eid)
{
    register int i;
 
    /* find matching edge object */
    FOR_ALL_EDGES(i) {
        register Edge* e = THIS(edges)[i];
        if(e->edgeid == eid) {
            return deleteedge(This,e,i);
        }
    }
    THIS(errmsg) = "edge delete: no such edge";
    return LAYOUT_ERROR;
}
 
 
/*
 *--------------------------------------------------------------
 *
 * LayoutBuildGraph --
 *
 *      This procedure is invoked to create the internal
 *      graph structure used for layouting.
 *
 * Results:
 *      A standard Tcl result.
 *
 * Side effects:
 *      See the user documentation.
 *
 *--------------------------------------------------------------
 */
 
static
int
LayoutBuildGraph AC1(Layout_Graph*,This)
{
  register int counter;
 
  /* Walk through all nodes to compute various things */
  FOR_ALL_NODES(counter) {
    register Node* n = THIS(nodes)[counter];
    /* Find the greatest icon dimensions. */
    if(NODE_WIDTH(n) > THIS(iconWidth)) {
      THIS(iconWidth) = (int)NODE_WIDTH(n);
    }
    if(NODE_HEIGHT(n) > THIS(iconHeight)) {
      THIS(iconHeight) = (int)NODE_HEIGHT(n);
    }
  }
 
  return LAYOUT_OK;
}
 
/*
 *--------------------------------------------------------------
 *
 * LayoutClearGraph --
 *
 *--------------------------------------------------------------
 */
 
void
LayoutClearGraph AC1(Layout_Graph*,This)
{
  register int counter;
  register Node* n;
 
  /* Free allocated memory. */
  FOR_ALL_EDGES(counter) {
    ckfree((char *) THIS(edges)[counter]);
  }
  THIS(edgeNum) = 0;
  FOR_ALL_NODES(counter) {
    n = THIS(nodes)[counter];
    if (n->parent != NULL)
        ckfree((char*)n->parent);
        if (n->succ != NULL)
        ckfree((char*)n->succ);
    if (n != NULL)
        ckfree((char *)n);
  }
  THIS(nodeNum) = 0;
  FOR_ALL_TOP_NODES(counter) {
    ckfree((char *) THIS(topList)[counter]);
  }
  THIS(topListNum) = 0;
  if (THIS(topList) != NULL)
  {
        ckfree ((char *) (THIS(topList)));
        THIS(topList) = NULL;
  }
  if (THIS(nodes) != NULL)
  {
        ckfree ((char *) (THIS(nodes)));
        THIS(nodes) = NULL;
  }
  THIS(rootNode) = NULL;
}
 
 
/*
 *--------------------------------------------------------------
 *
 * LayoutFreeGraph --
 *
 *      This procedure is invoked to free the graph structures
 *      used for layouting.
 *
 * Results:
 *      A standard Tcl result.
 *
 * Side effects:
 *      See the user documentation.
 *
 *--------------------------------------------------------------
 */
 
void
LayoutFreeGraph AC1(Layout_Graph*,This)
{
  LayoutClearGraph(This);
 
  /* now cleanup the Layout Graph structure */
  if (THIS(edges) != NULL)
  {
        ckfree((char *) THIS(edges));
        THIS(edges) = NULL;
  }
  if (THIS(nodes) != NULL)
  {
        ckfree((char *) THIS(nodes));
        THIS(nodes) = NULL;
  }
  if (THIS(topList) != NULL)
  {
        ckfree((char *) THIS(topList));
        THIS(topList) = NULL;
  }
 
  /* free graph layout structure */
  ckfree ((char *) This);
}
 
/*
 *--------------------------------------------------------------
 *
 * LayoutGraphRoot --
 *
 *      This procedure is invoked to find the root of a graph.
 *
 * Results:
 *      The root node.
 *
 * Side effects:
 *      See the user documentation.
 *
 *--------------------------------------------------------------
 */
 
static
Node*
LayoutGraphRoot AC1(Layout_Graph*,This)
{
  int optimalRootNum = -10000, minParentNum = -1, maxSuccNum = -1,
      counter, counter1, counter2, counter3, lidx;
  Node *tmprootNode, *node;
 
  /* Khamis 27-mar-97
   * reorder nodes, so that nodes with not empty subtree displayed
   * first
   */
  lidx = 0;
  FOR_ALL_NODES(counter)
  {
    if (counter == 0 || IGNORE_NODE(THIS(nodes)[counter]))
      continue;
 
    if (SUCC_NUM(THIS(nodes)[counter]) > SUCC_NUM(THIS(nodes)[lidx]))
    {
      node = THIS(nodes)[counter];
      THIS(nodes)[counter] = THIS(nodes)[lidx];
      THIS(nodes)[lidx] = node;
 
      /* search for next node with no subtree */
      while (SUCC_NUM(THIS(nodes)[lidx]) > 0 && lidx < counter)
      {
        lidx ++;
      }
    }
  }
 
  tmprootNode = THIS(rootNode);
 
  /* Find a root node. This node has no parents. In case we do not */
  /* have such a node... find the node with the smallest number of */
  /* parents. */
 
#if 0 /* Zsolt Koppany */
  tmprootNode = THIS(nodes)[0];
  return tmprootNode;
#endif
  if(!tmprootNode) {
    /* We try to find the node with the most children and the least */
    /* parents. This node will become root. */
    FOR_ALL_NODES(counter) {
      if(IGNORE_NODE(THIS(nodes)[counter])) {
        continue;
      }
      if((SUCC_NUM(THIS(nodes)[counter]) > 0 &&
           optimalRootNum <= (SUCC_NUM(THIS(nodes)[counter]) -
                             PARENT_NUM(THIS(nodes)[counter])) &&
           (minParentNum > PARENT_NUM(THIS(nodes)[counter]) ||
            (minParentNum == PARENT_NUM(THIS(nodes)[counter]) &&
            maxSuccNum < SUCC_NUM(THIS(nodes)[counter])))) ||
          optimalRootNum == -10000 ||
 
          /* khamis: 17-mars-97, root with no parents have more priority */
          PARENT_NUM(THIS(nodes)[counter]) < PARENT_NUM(tmprootNode)) {
        tmprootNode = THIS(nodes)[counter];
 
        minParentNum = PARENT_NUM(THIS(nodes)[counter]);
        maxSuccNum = SUCC_NUM(THIS(nodes)[counter]);
        if(SUCC_NUM(THIS(nodes)[counter]) > 0) {
          optimalRootNum =
            (SUCC_NUM(THIS(nodes)[counter]) - PARENT_NUM(THIS(nodes)[counter]));
        }
      }
    }
  }
 
  /* No nodes... so abort the search. */
  if(tmprootNode == NULL) {
    return NULL;
  }
 
  /* There is no node with no parents. So use the node with the */
  /* smallest number of parents, and ignore the edges leading to this */
  /* node. */
  if(PARENT_NUM(tmprootNode) != 0) {
    for (counter1 = 0; counter1 < PARENT_NUM(tmprootNode); counter1++) {
      SET_IGNORE_NODE(PARENT_EDGE(tmprootNode, counter1), 1);
      FOR_ALL_NODES(counter2) {
        /* Ignore dummy nodes. */
        if(DUMMY_NODE(THIS(nodes)[counter2])) {
          continue;
        }
        if(NODE_ITEM(THIS(nodes)[counter2]) ==
            NODE_ITEM(PARENT_NODE(tmprootNode, counter1))) {
          FOR_ALL_SUCCS(THIS(nodes)[counter2], counter3) {
            if(NODE_ITEM(SUCC_NODE(THIS(nodes)[counter2], counter3)) ==
                NODE_ITEM(tmprootNode)) {
              SET_IGNORE_NODE(SUCC_EDGE(THIS(nodes)[counter2], counter3), 1);
            }
          }
        }
      }
    }
  }
  return tmprootNode;
}
 
/*
 *--------------------------------------------------------------
 *
 * LayoutGraphSortTopological --
 *
 *      This procedure is invoked to sort a graph topological.
 *
 * Results:
 *      None
 *
 * Side effects:
 *      See the user documentation.
 *
 *--------------------------------------------------------------
 */
 
static
void
LayoutGraphSortTopological AC2(Layout_Graph*,This, Node*,currentNode) /* This is the current node. */
{
  int counter;
  Topology *tmpTopology;
 
  if(VISITED_NODE(currentNode) || IGNORE_NODE(currentNode)) {
    return;
  }
 
  /* Append the current node to the list of topologically sorted */
  /* nodes. */
  THIS(topListNum)++;
  if(THIS(topList) == NULL) {
    THIS(topList) = (Topology **) ckalloc(THIS(topListNum) * sizeof(Topology *));
  } else {
    THIS(topList) = (Topology **) ckrealloc((char *) THIS(topList),
                                    THIS(topListNum) * sizeof(Topology *));
  }
  tmpTopology = (Topology *) ckalloc(sizeof(Topology));
  tmpTopology->nodePtr = currentNode;
  THIS(topList)[THIS(topListNum)-1] = tmpTopology;
 
  SET_VISITED_NODE(currentNode, 1);
  /* Walk through all successors. */
  FOR_ALL_SUCCS(currentNode, counter) {
    if(IGNORE_EDGE(SUCC_EDGE(currentNode, counter))) {
      continue;
    }
    if(IGNORE_NODE(SUCC_NODE(currentNode, counter))) {
      continue;
    }
    if(VISITED_NODE(SUCC_NODE(currentNode, counter))) {
      SET_IGNORE_EDGE(SUCC_EDGE(currentNode, counter), 1);
      continue;
    }
    LayoutGraphSortTopological(This,SUCC_NODE(currentNode, counter));
  }
}
 
/*
 *--------------------------------------------------------------
 *
 * LayoutGraphPlaceNodes --
 *
 *      This procedure is invoked to actually place the graph nodes.
 *
 * Results:
 *      A standard Tcl result.
 *
 * Side effects:
 *      See the user documentation.
 *
 *--------------------------------------------------------------
 */
 
static
int
LayoutGraphPlaceNodes AC1(Layout_Graph*,This)
{
  int counter;
  double tmpX, tmpY;
 
  SRANDOM(getpid() + time((time_t *) NULL));
 
  FOR_ALL_NODES(counter) {
    register Node* n = THIS(nodes)[counter];
    if(IGNORE_NODE(n)) {
      continue;
    }
    if(NODE_X_POS(n) != -1 &&
        NODE_Y_POS(n) != -1) {
      if(THIS(graphOrder)) {
        /* Place nodes top down. */
        tmpX = NODE_X_POS(n);
        tmpY = NODE_Y_POS(n);
      } else {
        /* Place nodes left to right. */
        tmpX = NODE_Y_POS(n);
        tmpY = NODE_X_POS(n);
      }
    } else {
      /* are we allowed to place the icon ? */
      if(THIS(keepRandomPositions) &&
          NODE_X_POS(n) > 0 &&
          NODE_Y_POS(n) > 0) {
        continue;
      }
      tmpX = (long) (RANDOM % THIS(maxX)) - NODE_WIDTH(n);
      tmpY = (long) (RANDOM % THIS(maxY)) - NODE_HEIGHT(n);
    }
    if(tmpX < 0) {
      tmpX = 0;
    }
    if(tmpY < 0) {
      tmpY = 0;
    }
    if(!DUMMY_NODE(n)) {
        ItemGeom g;
        g = NODE_GEOM(n);
        /* recalc Item Geom based on our layout */
        g.x1 = tmpX+THIS(xOffset);
        g.y1 = tmpY+THIS(yOffset);
        g.x2 = g.x1 + g.width;
        g.y2 = g.y1 + g.height;
        SET_NODE_GEOM(n,g);
    }
  }
  return LAYOUT_OK;
}
 
/*
 *--------------------------------------------------------------
 *
 * LayoutGraphPlaceEdges --
 *
 *      This procedure is invoked to relayout all edges.
 *
 * Results:
 *      A standard Tcl result.
 *
 * Side effects:
 *      See the user documentation.
 *
 *--------------------------------------------------------------
 */
 
static
int
LayoutGraphPlaceEdges AC1(Layout_Graph*,This)
{
  register int i;
 
  /* scan through all edges */
  FOR_ALL_EDGES(i) {
    /* layout edges. */
    LayoutEdge(This,THIS(edges)[i], NULL, NULL);
  }
  return LAYOUT_OK;
}
 
/*
 *--------------------------------------------------------------
 *
 * LayoutEdgeWidth --
 *
 *      This procedure is invoked to find the widest edge. Widest
 *      means the edge with the maximal x expansion.
 *
 * Results:
 *      A standard Tcl result.
 *
 * Side effects:
 *      See the user documentation.
 *
 *--------------------------------------------------------------
 */
 
static
int
LayoutEdgeWidth AC1(Layout_Graph*,This)
{
#if 1 /* Khamis, 19:00 20 Okt 1996 */
  THIS(edgeHeight) = 0;
  THIS(edgeWidth) = 0;
#else
  register int i;
  if(THIS(edgeWidth) == 0) {
    /* Walk through all edges. */
    FOR_ALL_EDGES(i) {
        if(THIS(edges)[i]->info.height + LINE_INCREMENT > THIS(edgeHeight)) {
          THIS(edgeHeight) = THIS(edges)[i]->info.height + LINE_INCREMENT;
        }
        if(THIS(edges)[i]->info.width + LINE_INCREMENT > THIS(edgeWidth)) {
          THIS(edgeWidth) = THIS(edges)[i]->info.width + LINE_INCREMENT;
        }
    }
  }
 
#endif
 
  return LAYOUT_OK;
}
 
/*
 *--------------------------------------------------------------
 *
 * LayoutEdge --
 *
 *      This procedure is invoked to adjust the edge to the new
 *      locations of the connected nodes. This algorithm only works
 *      for simple edges.
 *
 * Results:
 *      A standard Tcl result.
 *
 * Side effects:
 *      See the user documentation.
 *
 *--------------------------------------------------------------
 */
 
static
int
LayoutEdge AC4(Layout_Graph*,This,
    Edge*,e,                    /* Current edge. */
    Node*,fromNode,                     /* Source node. */
    Node*,toNode)                       /* Target node. */
{
  int result = LAYOUT_OK;
#if 0
  Node *currentNode;
#endif
  ItemGeom geom;
 
  if(fromNode == (Node*) NULL && toNode == (Node*) NULL)
  {
    fromNode = e->fromNode;
    toNode = e->toNode;
  }
#if 0
  else
  {
    /* Place one specific edge... */
    /* WARNING !!! this code is old and not adapted to the new Edge*/
    /* placing. The code is not tested. This stuff will be used to */
    /* display multi point edges.... */
    fromPtr = NODE_ITEM(fromNode);
    while (DUMMY_NODE(toNode) && SUCC_NUM(toNode) > 0) {
      toNode = SUCC_NODE(toNode, 0);
    }
    toPtr = NODE_ITEM(toNode);
    if(itemPtr == (pItem ) NULL) {
      /* Match the numeric id value to a concrete item pointer. */
      FOR_ALL_CANVAS_ITEMS(canvasPtr, itemPtr) {
        if(strcmp(CANVAS_ITEM_TYPE(itemPtr), "edge") == 0) {
          /* Get "from" id */
          Tk_ConfigureInfo(canvasPtr->interp, canvasPtr->tkwin,
                           itemPtr->typePtr->configSpecs,
                           (char *) itemPtr, "-from", 0);
          if(Tcl_SplitList(canvasPtr->interp,
                            canvasPtr->interp->result,
                            &argc2, &argv2) != LAYOUT_OK) {
            return LAYOUT_ERROR;
          }
          fromId = atol(argv2[4]);
          ckfree((char *) argv2);
 
          /* Get "to" id */
          Tk_ConfigureInfo(canvasPtr->interp, canvasPtr->tkwin,
                           itemPtr->typePtr->configSpecs,
                           (char *) itemPtr, "-to", 0);
          if(Tcl_SplitList(canvasPtr->interp,
                            canvasPtr->interp->result,
                            &argc2, &argv2) != LAYOUT_OK) {
            return LAYOUT_ERROR;
          }
          toId = atol(argv2[4]);
          ckfree((char *) argv2);
 
          if(fromId == CANVAS_ITEM_ID(fromPtr) &&
              toId == CANVAS_ITEM_ID(toPtr)) {
            curPtr = itemPtr;
            FOR_ALL_SUCCS(fromNode, counter1) {
              Tcl_DStringInit(&positionString);
              if(fromPtr->x1 > fromPtr->x2) {
                THIS(posX1) = fromPtr->x1 + ((fromPtr->x2 - fromPtr->x1) / 2);
              } else {
                THIS(posX1) = fromPtr->x2 + ((fromPtr->x1 - fromPtr->x2) / 2);
              }
              if(fromPtr->y1 > fromPtr->y2) {
                THIS(posY1) = fromPtr->y1 + ((fromPtr->y2 - fromPtr->y1) / 2);
              } else {
                THIS(posY1) = fromPtr->y2 + ((fromPtr->y1 - fromPtr->y2) / 2);
              }
              if(toPtr->x1 > toPtr->x2) {
                THIS(posX2) = toPtr->x1 + ((toPtr->x2 - toPtr->x1) / 2);
              } else {
                THIS(posX2) = toPtr->x2 + ((toPtr->x1 - toPtr->x2) / 2);
              }
              if(toPtr->y1 > toPtr->y2) {
                THIS(posY2) = toPtr->y1 + ((toPtr->y2 - toPtr->y1) / 2);
              } else {
                THIS(posY2) = toPtr->y2 + ((toPtr->y1 - toPtr->y2) / 2);
              }
 
              if(fromPtr->y2 <= toPtr->y1) {
                sprintf(convertBuffer, "%d %d ", THIS(posX1), fromPtr->y2);
              } else {
                if(fromPtr->y1 >= toPtr->y2) {
                  sprintf(convertBuffer, "%d %d ", THIS(posX1), fromPtr->y1);
                } else {
                  if(fromPtr->x2 < toPtr->x1) {
                    sprintf(convertBuffer, "%d %d ", fromPtr->x2, THIS(posY1));
                  } else {
                    sprintf(convertBuffer, "%d %d ", fromPtr->x1, THIS(posY1));
                  }
                }
              }
 
              Tcl_DStringAppend(&positionString, convertBuffer, -1);
              currentNode = SUCC_NODE(fromNode, counter1);
              while (DUMMY_NODE(currentNode) && SUCC_NUM(currentNode) > 0) {
                currentNode = SUCC_NODE(currentNode, 0);
                sprintf(convertBuffer, "%g %g ", /*300.0, 300.0*/
                        NODE_X_POS(currentNode), NODE_Y_POS(currentNode));
                Tcl_DStringAppend(&positionString, convertBuffer, -1);
              }
              if(NODE_ITEM(currentNode) != toPtr) {
                Tcl_DStringFree(&positionString);
                continue;
              }
              if(fromPtr->y2 <= toPtr->y1) {
                sprintf(convertBuffer, "%d %d ", THIS(posX2), toPtr->y1);
              } else {
                if(fromPtr->y1 >= toPtr->y2) {
                  sprintf(convertBuffer, "%d %d ", THIS(posX2), toPtr->y2);
                } else {
                  if(fromPtr->x2 < toPtr->x1) {
                    sprintf(convertBuffer, "%d %d ", toPtr->x1, THIS(posY2));
                  } else {
                    sprintf(convertBuffer, "%d %d ", toPtr->x2, THIS(posY2));
                  }
                }
              }
              Tcl_DStringAppend(&positionString, convertBuffer, -1);
 
              /* Set new coordinates */
              if(Tcl_SplitList(canvasPtr->interp, positionString.string,
                                &argc2, &argv2) != LAYOUT_OK) {
                return LAYOUT_ERROR;
              }
              Tcl_ResetResult(canvasPtr->interp);
              result = (*curPtr->typePtr->coordProc)
                (canvasPtr, curPtr, argc2, argv2);
              ckfree((char *) argv2);
              Tcl_DStringFree(&positionString);
            }
            return result;
          }
        }
      }
    }
  }
#endif /* #if 0 */
 
  /* Is this a regular edge ? */
  if(fromNode != NULL && toNode != NULL) {
    /* calculate the various node anchors. */
    /* calc center of the from node */
    if(fromNode->info.x1 > fromNode->info.x2) {
      THIS(posX1) = fromNode->info.x1 + ((fromNode->info.x2 - fromNode->info.x1) / 2);
    } else {
      THIS(posX1) = fromNode->info.x2 + ((fromNode->info.x1 - fromNode->info.x2) / 2);
    }
    if(fromNode->info.y1 > fromNode->info.y2) {
      THIS(posY1) = fromNode->info.y1 + ((fromNode->info.y2 - fromNode->info.y1) / 2);
    } else {
      THIS(posY1) = fromNode->info.y2 + ((fromNode->info.y1 - fromNode->info.y2) / 2);
    }
    /* calc center of the to node */
    if(toNode->info.x1 > toNode->info.x2) {
      THIS(posX2) = toNode->info.x1 + ((toNode->info.x2 - toNode->info.x1) / 2);
    } else {
      THIS(posX2) = toNode->info.x2 + ((toNode->info.x1 - toNode->info.x2) / 2);
    }
    if(toNode->info.y1 > toNode->info.y2) {
      THIS(posY2) = toNode->info.y1 + ((toNode->info.y2 - toNode->info.y1) / 2);
    } else {
      THIS(posY2) = toNode->info.y2 + ((toNode->info.y1 - toNode->info.y2) / 2);
    }
 
    if(THIS(edgeOrder)) {
      /* Place the edges according to the graph order... only along
       * the generale layout direction. */
      if(THIS(graphOrder)) {
        /* Place nodes top down. */
        if(fromNode->info.y2 <= toNode->info.y1) {
          geom.x1 = THIS(posX1);
          geom.y1 = fromNode->info.y2;
          geom.x2 = THIS(posX2);
          geom.y2 = toNode->info.y1;
        } else {
          geom.x1 = THIS(posX1);
          geom.y1 = fromNode->info.y1;
          geom.x2 = THIS(posX2);
          geom.y2 = toNode->info.y2;
        }
      } else {
        /* Place nodes left to right. */
        if(fromNode->info.x2 < toNode->info.x1) {
          geom.x1 = fromNode->info.x2;
          geom.y1 = THIS(posY1);
          geom.x2 = toNode->info.x1;
          geom.y2 = THIS(posY2);
        } else {
          geom.x1 = fromNode->info.x1;
          geom.y1 = THIS(posY1);
          geom.x2 = toNode->info.x2;
          geom.y2 = THIS(posY2);
        }
      }
    } else {
      /* Place the edges so that they use the shortest distance. */
      if(fromNode->info.y2 <= toNode->info.y1) {
        /* from is above to */
        if(fromNode->info.x2 <= toNode->info.x1) {
          /* from is left from to */
          if(THIS(graphOrder)) {
            /* Place nodes top down. */
            geom.x1 = THIS(posX1);
            geom.y1 = fromNode->info.y2;
            geom.x2 = THIS(posX2);
            geom.y2 = toNode->info.y1;
          } else {
            geom.x1 = fromNode->info.x2;
            geom.y1 = THIS(posY1);
            geom.x2 = toNode->info.x1;
            geom.y2 = THIS(posY2);
          }
        } else {
          if(fromNode->info.x1 >= toNode->info.x2) {
            /* from is right from to */
            if(THIS(graphOrder)) {
              /* Place nodes top down. */
              geom.x1 = THIS(posX1);
              geom.y1 = fromNode->info.y2;
              geom.x2 = THIS(posX2);
              geom.y2 = toNode->info.y1;
            } else {
              geom.x1 = fromNode->info.x1;
              geom.y1 = THIS(posY1);
              geom.x2 = toNode->info.x2;
              geom.y2 = THIS(posY2);
            }
          } else {
            /* from is at same level as to */
            geom.x1 = THIS(posX1);
            geom.y1 = fromNode->info.y2;
            geom.x2 = THIS(posX2);
            geom.y2 = toNode->info.y1;
          }
        }
      } else {
        if(fromNode->info.y1 >= toNode->info.y2) {
          /* from is below to */
          if(fromNode->info.x2 <= toNode->info.x1) {
            /* from is left from to */
            if(THIS(graphOrder)) {
              /* Place nodes top down. */
              geom.x1 = THIS(posX1);
              geom.y1 = fromNode->info.y1;
              geom.x2 = THIS(posX2);
              geom.y2 = toNode->info.y2;
            } else {
              geom.x1 = fromNode->info.x2;
              geom.y1 = THIS(posY1);
              geom.x2 = toNode->info.x1;
              geom.y2 = THIS(posY2);
            }
          } else {
            if(fromNode->info.x1 >= toNode->info.x2) {
              /* from is right from to */
              if(THIS(graphOrder)) {
                /* Place nodes top down. */
                geom.x1 = THIS(posX1);
                geom.y1 = fromNode->info.y1;
                geom.x2 = THIS(posX2);
                geom.y2 = toNode->info.y2;
              } else {
                geom.x1 = fromNode->info.x1;
                geom.y1 = THIS(posY1);
                geom.x2 = toNode->info.x2;
                geom.y2 = THIS(posY2);
              }
            } else {
              /* from is at same level as to */
              geom.x1 = THIS(posX1);
              geom.y1 = fromNode->info.y1;
              geom.x2 = THIS(posX2);
              geom.y2 = toNode->info.y2;
            }
          }
        } else {
          /* from is at same level as to */
          if(fromNode->info.x2 <= toNode->info.x1) {
            /* from is left from to */
            geom.x1 = fromNode->info.x2;
            geom.y1 = THIS(posY1);
            geom.x2 = toNode->info.x1;
            geom.y2 = THIS(posY2);
          } else {
            if(fromNode->info.x1 > toNode->info.x2) {
              /* from is right from to */
              geom.x1 = fromNode->info.x1;
              geom.y1 = THIS(posY1);
              geom.x2 = toNode->info.x2;
              geom.y2 = THIS(posY2);
            } else {
              if(fromNode->info.x1 <= toNode->info.x1) {
                /* from is partially left from to */
                geom.x1 = fromNode->info.x2;
                geom.y1 = THIS(posY1);
                geom.x2 = toNode->info.x1;
                geom.y2 = THIS(posY2);
              } else {
                /* from is partially right from to */
                geom.x1 = fromNode->info.x1;
                geom.y1 = THIS(posY1);
                geom.x2 = toNode->info.x2;
                geom.y2 = THIS(posY2);
              }
            }
          }
        }
      }
    }
  }
 
  /* Set new coordinates on Edge*/
  SET_EDGE_GEOM(e,geom);
 
  return result;
}
 
/*
 *--------------------------------------------------------------
 *
 * LayoutISI --
 *
 *      This procedure is invoked to place icons with ISI.
 *
 * Results:
 *      A standard Tcl result.
 *
 * Side effects:
 *      See the user documentation.
 *
 *--------------------------------------------------------------
 */
 
int
LayoutISI AC1(Layout_Graph*,This)
{
  int counter, result = LAYOUT_OK;
 
  THIS(maxXPosition) = 0;
  THIS(maxYPosition) = 0;
  if(THIS(topList)) {
    /* free layout specific data slots. */
    for (counter = 0; counter < THIS(topListNum); counter++) {
      ckfree((char *) THIS(topList)[counter]);
    }
    ckfree((char*)THIS(topList));
    THIS(topList) = NULL;
  }
  THIS(topListNum) = 0;
  THIS(topList) = (Topology **) NULL;
 
  /* find the widest/highest edge. */
  LayoutEdgeWidth(This);
 
  /* build the internal graph structure. */
  if(LayoutBuildGraph(This) != LAYOUT_OK) {
    return LAYOUT_ERROR;
  }
 
  /* find root of the graph. */
  if((THIS(rootNode) = LayoutGraphRoot(This)) == NULL) {
    THIS(errmsg) = "no root node";
    return LAYOUT_ERROR;
  }
 
  /* sort the graph topological. */
  LayoutGraphSortTopological(This,THIS(rootNode));
  FOR_ALL_NODES(counter) {
    if(PARENT_NUM(THIS(nodes)[counter]) == 0) {
      LayoutGraphSortTopological(This,THIS(nodes)[counter]);
    }
  }
 
  /* Calculate the x position values. */
  RESET_VISITED_NODE(counter);
  FOR_ALL_NODES(counter) {
    if(PARENT_NUM(THIS(nodes)[counter]) == 0) {
      LayoutISISetX(This,THIS(nodes)[counter]);
    }
  }
 
#if 0
  RESET_VISITED_NODE(counter);
  FOR_ALL_NODES(counter) {
    if(PARENT_NUM(THIS(nodes)[counter]) == 0) {
      MY_LayoutISISetY(This,THIS(nodes)[counter], 0);
    }
  }
#else
  RESET_VISITED_NODE(counter);
  FOR_ALL_NODES(counter) {
    if(SUCC_NUM(THIS(nodes)[counter]) == 0) {
      LayoutISISetY(This,THIS(nodes)[counter]);
    }
  }
#endif
 
#if 1
  if (! THIS(graphOrder)) {
     while (1) {
        int found;
        found = 0;
        FOR_ALL_NODES(counter) {
          if(PARENT_NUM (THIS(nodes)[counter]) > 0 &&
           NODE_Y_POS (THIS(nodes)[counter]) <
           NODE_Y_POS (PARENT_NODE(THIS(nodes)[counter], 0)) +
           NODE_WIDTH (PARENT_NODE(THIS(nodes)[counter], 0)) +
                    THIS(edgeWidth) + THIS(iconSpaceH)) {
           SET_NODE_Y_POS(THIS(nodes)[counter],
 
                     NODE_Y_POS (PARENT_NODE(THIS(nodes)[counter], 0)) +
                     NODE_WIDTH (PARENT_NODE(THIS(nodes)[counter], 0)) +
                     THIS(edgeWidth) + THIS(iconSpaceH));
           found = 1;
          }
 
          if (SUCC_NUM (THIS(nodes)[counter]) == 1 &&
             PARENT_NODE (SUCC_NODE (THIS(nodes)[counter], 0), 0) == THIS(nodes)[counter]) {
             SET_NODE_X_POS(SUCC_NODE (THIS(nodes)[counter], 0),
                          NODE_X_POS(THIS(nodes)[counter]));
          }
       }
       if (! found)
         break;
     }
  }
#endif
 
  /* Place the graph items. */
  if(LayoutGraphPlaceNodes(This) != LAYOUT_OK) {
    result = LAYOUT_ERROR;
  } else if(LayoutGraphPlaceEdges(This) != LAYOUT_OK) {
    result = LAYOUT_ERROR;
  }
  return result;
}
 
/*
 *--------------------------------------------------------------
 *
 * LayoutMatrix --
 *
 *      This procedure is invoked to place icons as matrix.
 *
 * Results:
 *      A standard Tcl result.
 *
 * Side effects:
 *      See the user documentation.
 *
 *--------------------------------------------------------------
 */
 
int
LayoutMatrix AC1(Layout_Graph*,This)
{
    int result = LAYOUT_OK, greatestX = 10,
      greatestY = 10, greatestHeight = 0, columnCounter = 0,
      tmpIconWidth = 0, offset = 0, counter;
    ItemGeom geom;
 
    /* Scan through all canvas items. */
    FOR_ALL_NODES(counter) {
        register Node* n = THIS(nodes)[counter];
        /* Find the greatest icon dimensions. */
        if(THIS(computeiconsize)) {
            if(NODE_WIDTH(n) > THIS(iconWidth)) {
                THIS(iconWidth) = (int)NODE_WIDTH(n);
            }
            if(NODE_HEIGHT(n) > THIS(iconHeight)) {
                THIS(iconHeight) = (int)NODE_HEIGHT(n);
            }
        }
    }
 
    /* Walk through the list of NODES */
    FOR_ALL_NODES(counter) {
        register Node* n = THIS(nodes)[counter];
        geom = NODE_GEOM(n);
        if(THIS(iconWidth) == 0) {
            tmpIconWidth = (int)NODE_WIDTH(n);
            offset = (int) ((NODE_WIDTH(n) / 2.0) - (NODE_WIDTH(n) / 2.0));
        } else {
            tmpIconWidth = THIS(iconWidth);
            offset = (int) ((THIS(iconWidth) / 2.0) - (NODE_WIDTH(n) / 2.0));
        }
        /* Is this the highest icon so far ? */
        if(NODE_HEIGHT(n) > greatestHeight) {
            greatestHeight = (int) NODE_HEIGHT(n);
        }
 
        /* Place icon on the current line. */
        if(greatestX + tmpIconWidth < THIS(maxX) &&
           (THIS(elementsPerLine) == 0 ||
            columnCounter < THIS(elementsPerLine))) {
            geom.x1 = offset + greatestX + THIS(xOffset);
            geom.y1 = greatestY + THIS(yOffset);
            geom.x2 = geom.x1 + geom.width;
            geom.y2 = geom.y1 + geom.height;
            greatestX += (tmpIconWidth + THIS(iconSpaceH));
            columnCounter++;
            SET_NODE_GEOM(n,geom);
        } else {
            /* Place icon on the next line. */
            if(THIS(iconHeight) > 0) {
                greatestY += (THIS(iconHeight) + THIS(iconSpaceV));
            } else {
                greatestY += (greatestHeight + THIS(iconSpaceV));
            }
            geom.x1 = 10 + offset + greatestX + THIS(xOffset);
            geom.y1 = greatestY + THIS(yOffset);
            geom.x2 = geom.x1 + geom.width;
            geom.y2 = geom.y1 + geom.height;
            greatestHeight = (int) geom.height;
            greatestX = 10 + (tmpIconWidth + THIS(iconSpaceH));
            columnCounter = 1;
            SET_NODE_GEOM(n,geom);
        }
    }
 
    if(THIS(hideEdges)) {
        /* make all edges zero length, and place at maxX,MaxY
           to get them out of the way
        */
        FOR_ALL_EDGES(counter) {
            geom.x2 = (geom.x1 = THIS(maxX));
            geom.y2 = (geom.y1 = THIS(maxY));
            geom.width = (geom.height = 0);
            SET_EDGE_GEOM(THIS(edges)[counter],geom);
        }
    } else if(LayoutGraphPlaceEdges(This) != LAYOUT_OK) {
        result = LAYOUT_ERROR;
    }
    return result;
}
 
/*
 *--------------------------------------------------------------
 *
 * LayoutRandom --
 *
 *      This procedure is invoked to place icons randomly.
 *
 * Results:
 *      A standard Tcl result.
 *
 * Side effects:
 *      See the user documentation.
 *
 *--------------------------------------------------------------
 */
 
int
LayoutRandom AC1(Layout_Graph*,This)
{
    int result = LAYOUT_OK;
    int counter;
 
    SRANDOM(getpid() + time((time_t *) NULL));
    /* walk through all nodes */
    FOR_ALL_NODES(counter) {
        register Node* itemptr = THIS(nodes)[counter];
        long tmpx, tmpy;
        ItemGeom geom;
 
        /* randomly place icons. */
        /* are we allowed to place the icon ? */
        if(THIS(keepRandomPositions) &&
                NODE_X_POS(itemptr) > 0 &&
                NODE_Y_POS(itemptr) > 0) {
          continue;
        }
        tmpx = (long) (RANDOM % THIS(maxX)) - (long) NODE_WIDTH(itemptr);
        tmpy = (long) (RANDOM % THIS(maxY)) - (long) NODE_HEIGHT(itemptr);
        if(tmpx <= 0) {
          tmpx = 1;
        }
        if(tmpy <= 0) {
          tmpy = 1;
        }
        geom = NODE_GEOM(itemptr);
        geom.x1 = tmpx + THIS(xOffset);
        geom.y1 = tmpy + THIS(yOffset);
        geom.x2 = geom.x1 + NODE_WIDTH(itemptr);
        geom.y2 = geom.y1 + NODE_HEIGHT(itemptr);
        SET_NODE_GEOM(itemptr,geom);
    }
 
    if(LayoutGraphPlaceEdges(This) != LAYOUT_OK) {
        result = LAYOUT_ERROR;
    }
    return result;
}
 
/*
 *--------------------------------------------------------------
 *
 * LayoutTree --
 *
 *      this procedure is invoked to place icons as tree.
 *
 * results:
 *      a standard tcl result.
 *
 * side effects:
 *      see the user documentation.
 *
 * 09nov95 wmt: add handling of -hideedges
 *--------------------------------------------------------------
 */
 
int
LayoutTree AC1(Layout_Graph*,This)
{
  int result = LAYOUT_OK, counter;
  ItemGeom geom;
 
  THIS(maxXPosition) = 0;
  THIS(maxYPosition) = 0;
  if(THIS(topList)) {
    /* free layout specific data slots. */
    for (counter = 0; counter < THIS(topListNum); counter++) {
      ckfree((char *) THIS(topList)[counter]);
    }
    ckfree((char*)THIS(topList));
  }
  THIS(topListNum) = 0;
  THIS(topList) = (Topology **) NULL;
 
  /* find the widest/highest edge. */
  LayoutEdgeWidth(This);
 
  /* build the internal graph structure. */
  if(LayoutBuildGraph(This) != LAYOUT_OK) {
    return LAYOUT_ERROR;
  }
 
  /* find root of the graph. */
  if((THIS(rootNode) = LayoutGraphRoot(This)) == NULL) {
    THIS(errmsg) = "no root node";
    return LAYOUT_ERROR;
  }
 
  /* sort the graph topological. */
  LayoutGraphSortTopological(This,THIS(rootNode));
  FOR_ALL_NODES(counter) {
    if(PARENT_NUM(THIS(nodes)[counter]) == 0) {
      LayoutGraphSortTopological(This,THIS(nodes)[counter]);
    }
  }
 
  /* calculate the position values. */
  RESET_VISITED_NODE(counter);
  LayoutTreeSetX(This,THIS(rootNode));
  FOR_ALL_NODES(counter) {
    if(PARENT_NUM(THIS(nodes)[counter]) == 0) {
      LayoutTreeSetX(This,THIS(nodes)[counter]);
    }
  }
  RESET_VISITED_NODE(counter);
  FOR_ALL_TOP_NODES(counter) {
    LayoutTreeSetY(This,TOP_NODE(counter));
  }
 
  /* place the graph items. */
  if(LayoutGraphPlaceNodes(This) != LAYOUT_OK) {
    result = LAYOUT_ERROR;
  }
  if(THIS(hideEdges)) {
    /* make all edges zero length, and place at maxX,MaxY
       to get them out of the way
       */
    FOR_ALL_EDGES(counter) {
      geom.x2 = (geom.x1 = THIS(maxX));
      geom.y2 = (geom.y1 = THIS(maxY));
      geom.width = (geom.height = 0);
      SET_EDGE_GEOM(THIS(edges)[counter],geom);
    }
  } else if(LayoutGraphPlaceEdges(This) != LAYOUT_OK) {
    result = LAYOUT_ERROR;
  }
  return result;
}
 
Layout_Graph*
LayoutCreateGraph()
{
    register Layout_Graph* This;
 
    This = (Layout_Graph*)ckalloc(sizeof(Layout_Graph));
    if(!This) return This;
#if 1 /* multiX */
    memset((char *)This,0,sizeof(Layout_Graph));
#endif
    /* Initialize global data. */
    THIS(graphOrder) = 0;
    THIS(iconSpaceH) = 5;
    THIS(iconSpaceV) = 5;
    THIS(xOffset) = 4;
    THIS(yOffset) = 4;
    THIS(maxX) = 0;
    THIS(maxY) = 0;
    THIS(rootNode) = NULL;
 
    THIS(keepRandomPositions) = 0;
    THIS(nodeNum) = 0;
    THIS(nodes) = NULL;
    THIS(edgeNum) = 0;
    THIS(edges) = NULL;
    THIS(topListNum) = 0;
    THIS(topList) = NULL;
    THIS(computeiconsize) = 0;
    THIS(elementsPerLine) = 0;
    THIS(hideEdges) = 0;
    THIS(edgeHeight) = 2;
    THIS(edgeOrder) = 0;
    THIS(edgeWidth) = 0;
    THIS(iconWidth) = 0;
    THIS(iconHeight) = 0;
    THIS(posX1) = 0;
    THIS(posY1) = 0;
    THIS(posX2) = 0;
    THIS(posY2) = 0;
        THIS(gridlock) = 0;
#if 0
    THIS(idlist) = NULL;
#endif
    THIS(maxXPosition) = 0.0;
    THIS(maxYPosition) = 0.0;
#if 1
    THIS(layoutTypesNum) = 0;
#else
    THIS(layoutTypesNum) = 1;
    THIS(layoutTypes) = (char **) ckalloc(2);
    THIS(layoutTypes) = (char **) ckalloc(10);
    *THIS(layoutTypes) = '\0';
    *(1+THIS(layoutTypes))) = '\0';
    *THIS(layoutTypes) = (char *) ckalloc(10);
    strcpy(*THIS(layoutTypes), "icon");
#endif
    THIS(errmsg) = (char*)NULL;
    return This;
}
 
LayoutConfig
GetLayoutConfig(This)
        struct Layout_Graph* This;
{
    LayoutConfig c;
    c.rootnode = THIS(rootNode)?NODE_ITEM(THIS(rootNode)):NULL;
    c.graphorder = THIS(graphOrder);
    c.nodespaceH = (long)THIS(iconSpaceH);
    c.nodespaceV = (long)THIS(iconSpaceV);
    c.xoffset = THIS(xOffset);
    c.yoffset = THIS(yOffset);
    c.computenodesize = THIS(computeiconsize);
    c.elementsperline = THIS(elementsPerLine);
    c.hideedges = THIS(hideEdges);
    c.keeprandompositions = THIS(keepRandomPositions);
    c.maxx = THIS(maxX);
    c.maxy = THIS(maxY);
    c.gridlock = THIS(gridlock);
    return c;
}
 
void
SetLayoutConfig(This,c)
        struct Layout_Graph* This;
        LayoutConfig c;
{
    register int i;
    THIS(graphOrder) = c.graphorder;
    THIS(iconSpaceH) = c.nodespaceH;
    THIS(iconSpaceV) = c.nodespaceV;
    THIS(xOffset) = c.xoffset;
    THIS(yOffset) = c.yoffset;
    THIS(computeiconsize) = c.computenodesize;
    THIS(elementsPerLine) = c.elementsperline;
    THIS(hideEdges) = c.hideedges;
    THIS(keepRandomPositions) = c.keeprandompositions;
    THIS(maxX) = c.maxx;
    THIS(maxY) = c.maxy;
    THIS(gridlock) = c.gridlock;
 
    /* rootNode needs special work */
    if(c.rootnode) {
        FOR_ALL_NODES(i) {
            if(NODE_ITEM(THIS(nodes)[i]) == c.rootnode) {
                THIS(rootNode) = THIS(nodes)[i];
            }
        }
    }
}
 
int
LayoutGetIthNode(This,index,idp)
        struct Layout_Graph* This;
        long index;
        pItem* idp;
{
    if(index < 0 || index >= THIS(nodeNum)) return LAYOUT_ERROR;
    *idp = NODE_ITEM(THIS(nodes)[index]);
    return LAYOUT_OK;
}
 
int
LayoutGetNodeBBox(This,id,geomp)
        struct Layout_Graph* This;
        pItem id;
        ItemGeom* geomp;
{
    register Node* ip = NULL;
    register int i;
 
    /* find matching node */
    FOR_ALL_NODES(i) {
                if(NODE_ITEM(THIS(nodes)[i]) == id) {
                        ip = THIS(nodes)[i];
                        break; /* Khamis 11-oct-96 */
                }
    }
    if(!ip) return LAYOUT_ERROR;
    *geomp = NODE_GEOM(ip);
    return LAYOUT_OK;
}
 
int
LayoutSetNodeBBox(This,id,geom)
        struct Layout_Graph* This;
        pItem id;
        ItemGeom geom;
{
    register Node* ip = NULL;
    register int i;
 
    /* find matching node */
    FOR_ALL_NODES(i) {
        if(NODE_ITEM(THIS(nodes)[i]) == id) {
            ip = THIS(nodes)[i];
            break; /* Khamis 11-oct-96 */
        }
    }
    if(!ip) return LAYOUT_ERROR;
    if(!DUMMY_NODE(ip)) {
        SET_NODE_GEOM(ip,geom);
        SET_NODE_HEIGHT(ip, CALC_NODE_HEIGHT(ip));
        SET_NODE_WIDTH(ip, CALC_NODE_WIDTH(ip));
    } else {
        SET_NODE_HEIGHT(ip, 1);
        SET_NODE_WIDTH(ip, 1);
    }
    return LAYOUT_OK;
}
 
int
LayoutGetIthEdge(This,index,idp)
        struct Layout_Graph* This;
        long index;
        pItem* idp;
{
    if(index < 0 || index >= THIS(edgeNum)) return LAYOUT_ERROR;
    *idp = EDGE_ITEM(THIS(edges)[index]);
    return LAYOUT_OK;
}
 
int
LayoutGetEdgeEndPoints(This,id,geomp)
        struct Layout_Graph* This;
        pItem id;
        ItemGeom* geomp;
{
    register Edge* ip = NULL;
    register int i;
 
    /* find matching edge */
    FOR_ALL_EDGES(i) {
                if(EDGE_ITEM(THIS(edges)[i]) == id) {
                    ip = THIS(edges)[i];
                    break; /* Khamis 11-oct-96 */
                }
    }
    if(!ip) return LAYOUT_ERROR;
    *geomp = EDGE_GEOM(ip);
    return LAYOUT_OK;
}
 
int
LayoutSetEdgeDim(This,id,geom)
        struct Layout_Graph* This;
        pItem id;
        ItemGeom geom;
{
    register Edge* ip = NULL;
    register int i;
 
    /* find matching edge */
    FOR_ALL_EDGES(i) {
        if(EDGE_ITEM(THIS(edges)[i]) == id) {
            ip = THIS(edges)[i];
            break; /* Khamis 11-oct-96 */
        }
    }
    if(!ip) return LAYOUT_ERROR;
    SET_EDGE_GEOM(ip,geom);
    return LAYOUT_OK;
}
 
char*
LayoutGetError(This)
        struct Layout_Graph* This;
{
    register char* msg = THIS(errmsg);
    THIS(errmsg) = (char*)0;
    return msg;
}
 
 
/* KHAMIS */
 
void * MY_EdgeFromNode (This, i)
        struct Layout_Graph* This;
        int i;
{
        return THIS(edges)[i]->fromNode;
}
 
void * MY_EdgeToNode (This, i)
        struct Layout_Graph* This;
        int i;
{
        return THIS(edges)[i]->toNode;
}
 
int MY_EdgeParentNum (This, i)
        struct Layout_Graph* This;
        int i;
{
        return THIS(edges)[i]->toNode->parentNum;
}
 
void * MY_EdgeParent (This, i, num)
        struct Layout_Graph* This;
        int i;
        int num;
{
        return THIS(edges)[i]->toNode->parent[num]->fromNode;
}
 
int MY_EdgeSuccNum (This, i)
        struct Layout_Graph* This;
        int i;
{
        return THIS(edges)[i]->fromNode->succNum;
}
 
void * MY_EdgeSucc (This, i, num)
        struct Layout_Graph* This;
        int i;
{
        return THIS(edges)[i]->fromNode->succ[num]->toNode;
}
 
int MY_graphOrder (This)
        struct Layout_Graph* This;
{
        return THIS(graphOrder);
}
 
/* KHAMIS END */
 
Browse

Tools

Subversion Repositories or1k_old

[/] [or1k_old/] [trunk/] [insight/] [libgui/] [src/] [tkCanvLayout.c] - Blame information for rev 1782

Line No.	Rev	Author	Line
1	578	markom	`/*`
2			`* Copyright (c) 1993 by Sven Delmas`
3			`* All rights reserved.`
4			`* See the file COPYRIGHT for the copyright notes.`
5			`*`
6			`*/`
7
8			`/* renamed from layout.c to tkCanvLayout.c by Will Taylor 09nov95 */`
9			`/* converted to Tk4.1 by Will Taylor 05may96 */`
10
11			`#ifdef HAVE_CONFIG_H`
12			`#include <config.h>`
13			`#endif`
14			`#ifdef HAVE_UNISTD_H`
15			`#include <unistd.h>`
16			`#endif`
17
18			`#include <stdio.h>`
19			`#include <stdlib.h>`
20			`#include <time.h>`
21			`#include <string.h>`
22			`#include <tcl.h>`
23			`#include "tkCanvLayout.h"`
24
25			`#if defined (__MSVC__) && ! defined (HAVE_RAND)`
26			`#define HAVE_RAND`
27			`#endif`
28
29			`/*`
30			`* Functions to compute random numbers. These don't have to be`
31			`* particular good random number generators.`
32			`*/`
33			`#ifdef HAVE_RANDOM`
34			`#define RANDOM random ()`
35			`#define SRANDOM srandom`
36			`#else /* HAVE_RANDOM */`
37			`#ifdef HAVE_DRAND48`
38			`#define MY_RAND_MAX 65536`
39			`#define RANDOM ((long) (drand48 () * MY_RAND_MAX))`
40			`#define SRANDOM srand48`