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.h < prev    next >
C/C++ Source or Header  |  1998-03-25  |  9KB  |  243 lines
  1. // $Id: layout.h,v 1.9 1998/03/25 12:46:07 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. #ifndef _DDD_layout_h
  30. #define _DDD_layout_h
  31.  
  32. #ifdef __GNUG__
  33. #pragma interface
  34. #endif
  35.  
  36. #ifndef TRUE
  37. #define TRUE 1
  38. #endif
  39.  
  40. #ifndef FALSE
  41. #define FALSE 0
  42. #endif
  43.  
  44. // All these should be defined in the LayouterExpert class,
  45. // but I can't get gcc 2.3.3 swallow it...
  46. enum EDGEARROW { Here, Other };
  47. enum NODETYPE { Regular, Hint };
  48.  
  49. typedef struct _EGDE EDGE;
  50. typedef struct _EDGELIST EDGELIST;
  51. typedef struct _REGULAR REGULAR;
  52. typedef struct _HINT HINT;
  53. typedef union _ATTRIBUTES ATTRIBUTES;
  54. typedef union _ID ID;
  55. typedef struct _NODE NODE;
  56. typedef struct _GRAPH GRAPH;
  57.  
  58. #define PRIME 809
  59. #define SMALLPRIME 41
  60. typedef GRAPH *GRAPHTAB[SMALLPRIME];
  61.  
  62. // More definitions
  63. struct _EGDE {
  64.     NODE *node;
  65.     NODE *target;
  66.     EDGEARROW arrow;        /* kind of edge */
  67.     EDGE *next;             /* next entry of list */
  68.     EDGE *prev;             /* previous entry */
  69. };
  70.  
  71. struct _EDGELIST {
  72.     EDGE *head;             /* first entry */
  73.     EDGE *tail;             /* last entry */
  74.     int length;             /* number of elements */
  75. };
  76.  
  77. struct _REGULAR {
  78.     char *label;            /* the name of the node */
  79.     int w,h;                /* regular nodes have width & height */
  80.     EDGELIST up;            /* ancestors */
  81.     EDGELIST down;          /* descendants */
  82. };
  83. struct _HINT {
  84.     int id;                 /* hints are identified by ids */
  85.     NODE *up;
  86.     NODE *down;
  87.     NODE *source;           /* the two nodes connected by */
  88.     NODE *target;           /* the edge this hint belongs to */
  89. };
  90.  
  91. union _ATTRIBUTES {
  92.     REGULAR node;
  93.     HINT hint;
  94. };
  95.  
  96. union _ID {
  97.     int id;
  98.     char *label;
  99. };
  100.  
  101. struct _NODE {
  102.     int x,y;                /* position */
  103.     int oldx,oldy;          /* previous position */
  104.  
  105.     int layouted;           /* flag: already layouted? */
  106.     int level;              /* level inside graph */
  107.     int center;             /* avrg. bary-center of node */
  108.     int loop;               /* flag for loop */
  109.     int index;              /* auxilliary */
  110.     NODE *mark;             /* auxilliary */
  111.  
  112.     NODE *left;             /* same level - to the left */
  113.     NODE *right;            /* same level - to the right */
  114.     
  115.     NODE *hashnext;         /* double linked list for hashtab */
  116.     NODE *hashprev;
  117.  
  118.     NODETYPE type ;         /* type of node and tag for union */
  119.     ATTRIBUTES attr;
  120. };
  121.  
  122. struct _GRAPH {
  123.     NODE *hashtab[PRIME];
  124.  
  125.     int levels;
  126.     NODE **level;    
  127.     char *label;
  128.     GRAPH *hashnext;
  129.     GRAPH *hashprev;
  130.  
  131.     int minxdist;
  132.     int minydist;
  133.     int reverseflag;
  134.     int xiterations;
  135.     int pullup;
  136.  
  137.     int layouted;           /* flag, if graph was layouted recently */
  138. };
  139.  
  140. // Interface
  141. class Layout {
  142. public:
  143.     static void add_graph(char *g);
  144.     static void add_node(char *g, char *node);
  145.     static void add_edge(char *g, char *node1, char *node2);
  146.     static void set_node_width(char *g, char *node, int width);
  147.     static void set_node_height(char *g, char *node, int height);
  148.     static void set_node_position(char *g, char *node, int x, int y);
  149.     static void add_edge_hint(char *g, char *node1, char *node2, 
  150.                   int x, int y);
  151.     static void remove_edge_hint(char *g, char *node1, char *node2, 
  152.                  int x, int y);
  153.     static void remove_edge(char *g, char *node1, char *node2);
  154.     static void remove_node(char *g, char *label);
  155.     static void remove_graph(char *g);
  156.     static void layout(char *g);
  157.     
  158.     static void (*node_callback)(char *, int, int);
  159.     static void (*hint_callback)(char *, char *, int, int);
  160.     static int (*compare_callback)(char *, char *);
  161.  
  162.  
  163.     // Data
  164.     // static GRAPHTAB tab;
  165.  
  166.     // Helpers
  167.     static void dddDebug(char *g);
  168.     static void inc_layout(GRAPH *graph);
  169.     static void new_layout(GRAPH *graph);
  170.     static void dddOutput(GRAPH *graph);
  171.     static void dddNodeOut(char *graph,NODE *node);
  172.     static void debugNode(NODE *node);
  173.     static void debugLevel(GRAPH *graph, int n);
  174.     static void debugAllLevel(GRAPH *graph);
  175.     static void debugAllNodes(GRAPH *graph);
  176.     static void debugNodeXFig(NODE *nd);
  177.     static void debugEdgeXFig(NODE *source, NODE *target, int arrow);
  178.     static void debugGraphXFig(GRAPH *graph);
  179.     static void listInit(EDGELIST *list);
  180.     static EDGE *listInsertEdge(EDGELIST *list, NODE *node);
  181.     static void listRemoveEdge(EDGELIST *list, EDGE *edge);
  182.     static EDGE *listFindNode(EDGELIST *list, NODE *node);
  183.     static EDGE *listFindTarget(EDGELIST *list, NODE *target);
  184.     static void listRemove(EDGELIST *list);
  185.     static void nodeInit(NODE* node, ID *id , NODETYPE type);
  186.     static void nodeRemove(NODE *node);
  187.     static void graphInit(GRAPH *graph, char *label);
  188.     static NODE *graphEnterNode(GRAPH *graph, ID *id, NODETYPE type);
  189.     static NODE *graphGetNode(GRAPH *graph, ID *id, NODETYPE type);
  190.     static void graphRemoveNode(GRAPH *graph, ID *id, NODETYPE type);
  191.     static void graphCreateLevels(GRAPH *graph, int n);
  192.     static void graphRemoveLevels(GRAPH *graph);
  193.     static void graphAddLevels(GRAPH *graph, int n);
  194.     static void graphInsertEdge(GRAPH *graph,NODE *source,NODE *target);
  195.     static void graphInvertEdge(NODE *source, NODE *target);
  196.     static int graphNewNodeID();
  197.     static NODE *graphInsertHint(GRAPH *graph, NODE *source, NODE* target);
  198.     static EDGE *graphFindEdgeAtSource(NODE *source, NODE *target);
  199.     static EDGE *graphFindEdgeAtTarget(NODE *source, NODE *target);
  200.     static void graphResetLevels(GRAPH *graph);
  201.     static int graphHashStr(char *str, int prime);
  202.     static GRAPH *graphGet(GRAPHTAB *tab, char *label);
  203.     static GRAPH *graphNew(GRAPHTAB *tab,char *label);
  204.     static void graphRemove(GRAPHTAB *tab, char *label);
  205.     static void graphTabInit(GRAPHTAB *tab);
  206.     static void levelsInsertNode(GRAPH *graph, NODE *node, int n);
  207.     static void levelsRemoveNode(GRAPH *graph, NODE *node, int n);
  208.     static void levelsEnterNodes(GRAPH *graph, int pullup);
  209.     static void levelsIndex(NODE **level);
  210.     static int levelsLength(NODE **level);
  211.     static int sortApplyLevel(GRAPH *graph);
  212.     static void sortPullupNodes(GRAPH *graph);
  213.     static int minimumLevel(NODE *node);
  214.     static int distance(NODE *node, NODE *origin);
  215.     static void sortInsertHints(GRAPH *graph);
  216.     static void sortCheckNode(GRAPH *graph, NODE *node);
  217.     static int sortNodeUpperBary(NODE *node);
  218.     static int sortNodeLowerBary(NODE *node);
  219.     static void sortGraphUpperBary(GRAPH *graph);
  220.     static void sortGraphLowerBary(GRAPH *graph);
  221.     static void sortByCenter(NODE **level);
  222.     static void sortAvrgCenter(GRAPH *graph);
  223.     static int sortCmpCenters(NODE **first, NODE **second);
  224.     static void sortInitX(GRAPH *graph);
  225.     static void sortGraphUpX(GRAPH *graph);
  226.     static void sortGraphDownX(GRAPH *graph);
  227.     static void sortLevelUpX(NODE **level, int dist);
  228.     static void sortLevelDownX(NODE **level, int dist);
  229.     static int sortLeftSpace(NODE *node, int dist);
  230.     static void sortMoveLeft(NODE *node, int newx, int dist);
  231.     static void sortMoveRight(NODE *node, int newx, int mindist);
  232.     static void sortMove(NODE *node, int newx, int mindist);
  233.     static int sortAvrgUpperX(NODE *node);
  234.     static int sortAvrgLowerX(NODE *node);
  235.     static int sortCmpUpperPrio(NODE **fst, NODE **snd);
  236.     static int sortCmpLowerPrio(NODE **fst, NODE **snd);
  237.     static int sortLevelVertical(NODE **level, int miny, int minydist);
  238.     static void sortGraphVertical(GRAPH *graph);
  239. };
  240.  
  241. #endif // _DDD_layout_h
  242. // DON'T ADD ANYTHING BEHIND THIS #endif
  243.