/* SCCS-info %W% %E% */ /*--------------------------------------------------------------------*/ /* */ /* VCG : Visualization of Compiler Graphs */ /* -------------------------------------- */ /* */ /* file: folding.c */ /* version: 1.00.00 */ /* creation: 17.9.1993 */ /* author: I. Lemke (...-Version 0.99.99) */ /* G. Sander (Version 1.00.00-...) */ /* Universitaet des Saarlandes, 66041 Saarbruecken */ /* ESPRIT Project #5399 Compare */ /* description: Folding and Unfolding of the graph */ /* status: in work */ /* */ /*--------------------------------------------------------------------*/ #ifndef lint static char *id_string="$Id: folding.c,v 3.11 1995/02/08 11:11:14 sander Exp $"; #endif /* * Copyright (C) 1993-2005 Saarland University * * This program and documentation is free software; you can redistribute * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. * * The software is available per anonymous ftp at ftp.cs.uni-sb.de. * Contact sander@cs.uni-sb.de for additional information. */ /* $Log: folding.c,v $ * Revision 3.11 1995/02/08 11:11:14 sander * Distribution version 1.3. * * Revision 3.10 1994/12/23 18:12:45 sander * Manhatten layout added. * Option interface cleared. * * Revision 3.9 1994/11/23 14:50:47 sander * Bug in folding operations corrected. * * Revision 3.8 1994/08/05 12:13:25 sander * Treelayout added. Attributes "treefactor" and "spreadlevel" added. * Scaling as abbreviation of "stretch/shrink" added. * * Revision 3.7 1994/08/03 13:58:44 sander * Horizontal order mechanism changed. * Attribute horizontal_order for edges added. * * Revision 3.6 1994/05/16 08:56:03 sander * shape attribute (boxes, rhombs, ellipses, triangles) added. * * Revision 3.5 1994/05/05 08:20:30 sander * Algorithm late labels added: If labels are inserted * after partitioning, this may yield a better layout. * * Revision 3.4 1994/04/27 16:05:19 sander * Some general changes for the PostScript driver. * Horizontal order added. Bug fixes of the folding phases: * Folding of nested graphs works now. * * Revision 3.3 1994/03/04 19:11:24 sander * Specification of levels per node added. * X11 geometry behaviour (option -geometry) changed such * that the window is now opened automatically. * * Revision 3.2 1994/03/02 11:48:54 sander * Layoutalgoritms mindepthslow, maxdepthslow, minindegree, ... mandegree * added. * Anchors and nearedges are not anymore allowed to be intermixed. * Escapes in strings are now allowed. * * Revision 3.1 1994/03/01 10:59:55 sander * Copyright and Gnu Licence message added. * Problem with "nearedges: no" and "selfloops" solved. * * Revision 2.4 1994/02/08 09:55:18 sander * Hide edge algorithm changed: now all edges of a node must be hidden, * not only the forward edges, to hide the node itself. * * Revision 2.3 1994/01/21 19:33:46 sander * VCG Version tested on Silicon Graphics IRIX, IBM R6000 AIX and Sun 3/60. * Option handling improved. Option -grabinputfocus installed. * X11 Font selection scheme implemented. The user can now select a font * during installation. * Sun K&R C (a nonansi compiler) tested. Some portabitility problems solved. * */ /************************************************************************ * The situation here is the following: * ----------------------------------- * All exisiting nodes and edges come directly from the specification. * graphlist contains the list of all invisible subgraph summary nodes. * nodelist contains the list of all visible nodes. * edgelist contains the list of all edges, visible or not. * temporary nodes and edges are given free, * i.e. tmpnodelist = tmpedgelist = NULL. * invis_nodes contains all nodes that are invisible because of a previous * edge class hiding. * Graphs and regions may be folded, but it is irrelevant which edges are * hidden, because the adjacency lists still not exist (e.g. they are removed * just before folding). * * Note again (see also alloc.h): * Folded graphs have a summary node in nodelist and all nodes of this * graphs outside nodelist. * Unfolded graphs have the nodes in nodelist and the summary node in * graphlist. * NSGRAPH(r) is the list of nodes of subgraph r * NROOT(n) = r if n is node of subgraph r * Folded regions have a summary node in nodelist, and all nodes of * this region outside nodelist. * NREGREPL(r) is the start node of the region which has the summary * node r. * NREGION(r) is the list of nodes of region r (except the start node) * NREGROOT(n) = r if n is invisible and node of region r * * The task of the driver function `folding' is now to create the correct * adjacency lists by respecting new graph/region foldings or unfoldings * and hidden edge classes. * * The `folding keepers' are storages to remark which nodes must be folded * or unfolded. The function folding folds with respect to the folding * keepers. After that, it reinitializes the folding keepers. * The folding keepers DO NOT indicate which subgraphs or regions ARE * ACTUALLY FOLDED ! They indicate which actions must be done next. * The management of the array hide_class is different. It is initialized * once before reading the specification, and changed incrementally by * actions. At every time point, it indicates which edge classes ARE hidden. * * After folding, the following invariants hold: * 1) We have proper adjacency lists. * 2) All visible nodes are in the nodelist or in the labellist. * More exactly: all visible nodes originated directly by the * specification are in the nodelist, and all visible edge label nodes * are in the labellist. * 3) All nodes from the nodelist that are invisible because of * edge class hiding are in the list invis_nodes. * 4) All potentially visible edges are in the lists edgelist or tmpedgelist. * Visible edges can be detected by the EINVISIBLE flag (==0) in these * lists. Note: invisible edges may also be in edgelist or tmpedgelist. * Except the INVISIBLE flag, the edgelist IS NEVER CHANGED !!! * 5) An edge is visible iff it is used in the adjacency lists. For some * edges, we create substeds; then, the substed is visible but the original * edge is not visible. * 6) The locFlag is 1, if all visible nodes have positions (x,y). * * * This file provides the following functions: * ------------------------------------------ * add_sgfoldstart add a start point to the subgraph folding keepers * add_foldstart add a start point to the region folding keepers * add_foldstop add a stop point to the region folding keepers * clear_hide_class reinitialize hide_class[] (the array indicating which * edge classes are hidden) * folding do all foldings and create the adjacency lists * create_adjedge insert an edge into the adjacency lists of its source * and target node. * delete_adjedge delete an adjacency edge from source and target, * i.e. make the edge invisible. ************************************************************************/ #include #include #include #include "globals.h" #include "grammar.h" #include "alloc.h" #include "main.h" #include "options.h" #include "timelim.h" #include "drawlib.h" #include "folding.h" #include "steps.h" /* Prototypes * ---------- */ static void revert_subgraph _PP((GNODE v)); static int foldstop_reached _PP((GNODE v)); static void delete_node _PP((GNODE v,int k)); static void insert_node _PP((GNODE v,int k)); static void delete_sgnodes _PP((GNODE u)); static void fold_sg _PP((GNODE u)); static void unfold_sg _PP((GNODE u)); static void refresh_all_nodes _PP((GNODE v)); static void refresh _PP((void)); static void sort_all_nodes _PP((void)); static int compare_ndfs _PP((const GNODE *a,const GNODE *b)); static long no_dfs _PP((GNODE n)); static long no_indeg _PP((GNODE n)); static long no_outdeg _PP((GNODE n)); static long no_degree _PP((GNODE n)); static void create_adjacencies _PP((void)); static void create_lab_adjacencies _PP((void)); static void adapt_labelpos _PP((GNODE v,GEDGE e)); static GNODE search_visible _PP((GNODE v)); static GEDGE substed_edge _PP((GEDGE e)); static void unfold_region _PP((GNODE n)); static void fold_region _PP((GNODE n, int k)); static void recursive_fold _PP((GNODE v, GNODE n, int k)); static void hide_edge_classes _PP((void)); static void summarize_edges _PP((void)); static void split_double_edges _PP((void)); #ifdef DEBUG static void db_print_somenode_list(GNODE w,GNODE wend); #endif /*--------------------------------------------------------------------*/ /* For Debugging only */ /*--------------------------------------------------------------------*/ #ifdef NEVER GNODE mydebugnode; #ifdef ANSI_C void init_mydebugnode(void) #else void init_mydebugnode() #endif { GNODE v; mydebugnode = NULL; v = nodelist; while (v) { if ((NTITLE(v)) && (strcmp(NTITLE(v),"")==0)) { PRINTF("found in nodelist\n"); mydebugnode = v; } v = NNEXT(v); } v = graphlist; while (v) { if ((NTITLE(v)) && (strcmp(NTITLE(v),"")==0)) { PRINTF("found in graphlist\n"); mydebugnode = v; } v = NNEXT(v); } if (!mydebugnode) PRINTF("not found\n"); } #ifdef ANSI_C int check_mydebugnode(void) #else int check_mydebugnode() #endif { ADJEDGE a; if (!mydebugnode) return(1); a = NSUCC(mydebugnode); while (a) { if (SOURCE(a)!=mydebugnode) { printf("%d\n",SOURCE(a)); return(0); } a = ANEXT(a); } a = NPRED(mydebugnode); while (a) { if (TARGET(a)!=mydebugnode) { printf("%d\n",TARGET(a)); return(0); } a = ANEXT(a); } return(1); } #ifdef ANSI_C static void print_all_nodes(char *x, GNODE v) #else static void print_all_nodes(x,v) char *x; GNODE v; #endif { printf("List %s: ",x); while (v) { PRINTF("%s ",(NTITLE(v)?NTITLE(v):"(null)")); v = NNEXT(v); } printf("\n"); } #endif /*--------------------------------------------------------------------*/ /* Management of folding keepers */ /*--------------------------------------------------------------------*/ /* Global variables * ---------------- */ GNLIST f_subgraphs; /* List of subgraph nodes to folding */ GNLIST uf_subgraphs;/* Node where subgraph unfolding starts */ GNLIST foldstops; /* List of nodes where a fold region operation stops */ GNLIST foldstart; /* List of nodes where a fold region operation starts */ GNLIST ufoldstart; /* Node where region unfolding starts */ /* Fold starters and stoppers * ========================== * Region fold starter are halfreverted, region fold stopper or * subgraph stopper etc. are reverted. */ /* Clear all fold starter or stopper lists. * --------------------------------------- */ #ifdef ANSI_C void clear_folding_keepers(void) #else void clear_folding_keepers() #endif { GNLIST l; /* Set folding keeper to NOREVERT */ l = f_subgraphs; while (l) { NREVERT(GNNODE(l))= NOREVERT; revert_subgraph(GNNODE(l)); l = GNNEXT(l); } l = uf_subgraphs; while (l) { NREVERT(GNNODE(l))= NOREVERT; l = GNNEXT(l); } l = foldstops; while (l) { NREVERT(GNNODE(l))= NOREVERT; l = GNNEXT(l); } l = foldstart; while (l) { NREVERT(GNNODE(l))= NOREVERT; l = GNNEXT(l); } l = ufoldstart; while (l) { NREVERT(GNNODE(l))= NOREVERT; l = GNNEXT(l); } free_foldnodelists(); ufoldstart = NULL; foldstart = NULL; foldstops = NULL; f_subgraphs = NULL; uf_subgraphs= NULL; } /* Add fold subgraph starter * ------------------------- * Add a new fold subgraph starter v to the list foldstart. * Note: v is the root node of the graph. */ #ifdef ANSI_C void add_sgfoldstart(GNODE v) #else void add_sgfoldstart(v) GNODE v; #endif { GNLIST l,*lp; if (!v) return; debugmessage("add_sgfoldstart",(NTITLE(v)?NTITLE(v):"(null)")); if (NREVERT(v)==AREVERT) { /* delete it from sgfoldstart */ NREVERT(v) = NOREVERT; l = f_subgraphs; lp = &f_subgraphs; while (l) { if (GNNODE(l)==v) { *lp = GNNEXT(l); break; } lp = &GNNEXT(l); l = GNNEXT(l); } revert_subgraph(v); return; } NREVERT(v) = AREVERT; l = foldnodelist_alloc(); GNNODE(l) = v; GNNEXT(l) = f_subgraphs; f_subgraphs = l; revert_subgraph(v); } /* Revert subgraph * --------------- * If a subgraph is selected for folding, all its nodes * are reverted, to easy the menu selection. * The nodes get the same revert-flag as the root node. */ #ifdef ANSI_C static void revert_subgraph(GNODE v) #else static void revert_subgraph(v) GNODE v; #endif { GNODE w; GNLIST l; int rev; debugmessage("revert_subgraph",(NTITLE(v)?NTITLE(v):"(null)")); rev = NREVERT(v); l = NSGRAPH(v); while (l) { w = GNNODE(l); NREVERT(w) = rev; if (NSGRAPH(w)) { revert_subgraph(w); } l = GNNEXT(l); } } /* Add unfold subgraph starter * --------------------------- * Add a new unfold subgraph starter v to the list foldstart. */ #ifdef ANSI_C void add_sgunfoldstart(GNODE v) #else void add_sgunfoldstart(v) GNODE v; #endif { GNLIST l,*lp; if (!v) return; debugmessage("add_sgunfoldstart",(NTITLE(v)?NTITLE(v):"(null)")); if (NREVERT(v)==AREVERT) { /* delete it from uf_subgraphs */ NREVERT(v) = NOREVERT; l = uf_subgraphs; lp = &uf_subgraphs; while (l) { if (GNNODE(l)==v) { *lp = GNNEXT(l); break; } lp = &GNNEXT(l); l = GNNEXT(l); } return; } NREVERT(v) = AREVERT; l = foldnodelist_alloc(); GNNODE(l) = v; GNNEXT(l) = uf_subgraphs; uf_subgraphs = l; } /* Add fold region starter * ----------------------- * Add a new fold region starter v to the list foldstarters. */ #ifdef ANSI_C void add_foldstart(GNODE v) #else void add_foldstart(v) GNODE v; #endif { GNLIST l,*lp; if (!v) return; debugmessage("add_foldstart",(NTITLE(v)?NTITLE(v):"(null)")); if (NREVERT(v)==BREVERT) { /* delete it from foldstart */ NREVERT(v) = NOREVERT; l = foldstart; lp = &foldstart; while (l) { if (GNNODE(l)==v) { *lp = GNNEXT(l); break; } lp = &GNNEXT(l); l = GNNEXT(l); } return; } if (NREVERT(v)==AREVERT) return; NREVERT(v) = BREVERT; l = foldnodelist_alloc(); GNNODE(l) = v; GNNEXT(l) = foldstart; foldstart = l; } /* Add unfold region starter * ------------------------- * Add a new unfold region starter v to the list foldstarters. */ #ifdef ANSI_C void add_unfoldstart(GNODE v) #else void add_unfoldstart(v) GNODE v; #endif { GNLIST l,*lp; if (!v) return; debugmessage("add_unfoldstart",(NTITLE(v)?NTITLE(v):"(null)")); if (NREVERT(v)==AREVERT) { /* delete it from ufoldstart */ NREVERT(v) = NOREVERT; l = ufoldstart; lp = &ufoldstart; while (l) { if (GNNODE(l)==v) { *lp = GNNEXT(l); break; } lp = &GNNEXT(l); l = GNNEXT(l); } return; } NREVERT(v) = AREVERT; l = foldnodelist_alloc(); GNNODE(l) = v; GNNEXT(l) = ufoldstart; ufoldstart = l; } /* Add fold region stopper * ----------------------- * Add a new fold region stopper v to the list foldstops. */ #ifdef ANSI_C void add_foldstop(GNODE v) #else void add_foldstop(v) GNODE v; #endif { GNLIST l,*lp; if (!v) return; debugmessage("add_foldstop",(NTITLE(v)?NTITLE(v):"(null)")); if (NREVERT(v)==AREVERT) { /* delete it from foldstops */ NREVERT(v) = NOREVERT; l = foldstops; lp = &foldstops; while (l) { if (GNNODE(l)==v) { *lp = GNNEXT(l); break; } lp = &GNNEXT(l); l = GNNEXT(l); } return; } NREVERT(v) = AREVERT; l = foldnodelist_alloc(); GNNODE(l) = v; GNNEXT(l) = foldstops; foldstops = l; } /* Check fold stopper * ------------------ * Returns 1 if v is in the list foldstops, i.e. if v is a fold stopper. */ #ifdef ANSI_C static int foldstop_reached(GNODE v) #else static int foldstop_reached(v) GNODE v; #endif { GNLIST l; if (!v) return(1); debugmessage("foldstop_reached",(NTITLE(v)?NTITLE(v):"(null)")); l = foldstops; while (l) { if (GNNODE(l) == v) return(1); l = GNNEXT(l); } return(0); } /*--------------------------------------------------------------------*/ /* Folding and creation of adjacency lists */ /*--------------------------------------------------------------------*/ /* Defines * ------- * To have the possibility to revert foldings, or to find * appropritate substitution node, we must notate why a node * is invisible. Thus we set the INVISIBLE flag: * 0 -> the node is visible * 1 -> the node is a unfolded subgraph * 2 -> the node is part of a folded subgraph * 3 -> the node is part of a folded region * 4 -> the node is invisible because it is only reacheable * by hidden edge classes */ #define UNFOLDED_SGRAPH 1 #define FOLDED_SGNODE 2 #define FOLDED_RGNODE 3 #define HIDDEN_CNODE 4 /* Folding main driver * =================== * We try to do as much as possible BEFORE the adjacency lists are * created, because given all visible nodes, it is relatively simple * to create the adjacency lists of those edges that are visible. * We do subgraph folding, subgraph unfolding and region unfolding * before the adjacency lists are created. * However, to fold subgraphs or to hide edges, we need the adjacency * lists, thus this is done later. * Note that there is no operation `unhide edge class' because * adjacency lists are always created new which automatically respects * only those edges that are unhidden. * At last, we check whether all visible nodes have (x,y) locations, * and set the locFlag according. * * The fold stoppers are set by the specification * or by menu interaction. */ #ifdef ANSI_C void folding(void) #else void folding() #endif { GNODE v,vn; GNLIST l; int rclass; debugmessage("folding",""); assert((labellist == NULL)); assert((tmpnodelist == NULL)); assert((tmpedgelist == NULL)); if (G_displayel==NO) edge_label_phase=0; if (G_dirtyel==YES) edge_label_phase=0; /* 1) make all node that are invisible because of edge classes * visible */ gs_wait_message('f'); v = invis_nodes; while (v) { vn = NNEXT(v); insert_node(v,HIDDEN_CNODE); v = vn; /* because insert_node changes NNEXT(v) */ } invis_nodes = NULL; /* 2) subgraph folding */ l = f_subgraphs; while (l) { fold_sg(GNNODE(l)); l = GNNEXT(l); } /* 3) subgraph unfolding */ l = uf_subgraphs; while (l) { unfold_sg(GNNODE(l)); l = GNNEXT(l); } /* 4) Unfold region (independent of the class) */ l = ufoldstart; while (l) { unfold_region(GNNODE(l)); l = GNNEXT(l); } /* 5) refresh the situation: initialize indegree of nodes, * visibility flag of edges etc. Clear adjacency lists. */ gs_wait_message('f'); refresh(); /* 6) Construct adjacency lists first time */ create_adjacencies(); hide_edge_classes(); /* 7) Fold region: fold first the lower then the higher classes */ for (rclass=0; rclass<17; rclass++) { l = foldstart; while (l) { if (GNNODE(l) && (NFOLDING(GNNODE(l))==rclass)) fold_region(GNNODE(l),rclass); l = GNNEXT(l); } } /* 8) If labels necessary, create labels */ refresh(); if ((G_displayel==YES) && (G_dirtyel==NO) && (edge_label_phase==0)) create_lab_adjacencies(); else create_adjacencies(); /* 9) Hide edge classes */ gs_wait_message('f'); hide_edge_classes(); /* For stable layout: sort nodelist */ sort_all_nodes(); /* 10) check whether all nodes have already locations * and transfer the specified locations. */ locFlag = 1; v = nodelist; while (v && locFlag) { if ((NSX(v)==0L) && (NSY(v)==0L)) locFlag=0; NX(v) = NSX(v); NY(v) = NSY(v); v = NNEXT(v); } /* 11) If labels, we calculate edge positions without labels. */ if (locFlag && (G_displayel==YES)) { free_tmpnodes(); refresh(); create_adjacencies(); gs_wait_message('f'); hide_edge_classes(); v = nodelist; while (v) { NX(v) = NSX(v); NY(v) = NSY(v); v = NNEXT(v); } } /* 12) If necessary, remove double edges from the adjacency * lists. */ gs_wait_message('f'); if (summarize_double_edges) summarize_edges(); /* 13) Otherwise split edges which are doubled, such that they * can be recognized better. */ if ((!locFlag) && (!summarize_double_edges)) split_double_edges(); /* 14) Reinit the folding keepers to get a clean situation * for the next folding. */ clear_folding_keepers(); } /*--------------------------------------------------------------------*/ /* Folding primitives */ /*--------------------------------------------------------------------*/ /* Insertion and deletion at the node list * ======================================= * As long as the adjacency lists are not created, folding and is * simply done by insertion and deletion of nodes at the nodelist. * With this method, `fold subgraph' and `unfold subgraph' and * `unfold region' can be implemented. * To have the possibility to revert such foldings, or to find * appropritate substitution node (see substed_edge), we must notate * why a node is invisible. Thus we set the INVISIBLE flag: * 0 -> the node is visible * 1 -> the node is a unfolded subgraph * 2 -> the node is part of a folded subgraph * 3 -> the node is part of a folded region * 4 -> the node is invisible because it is only reacheable * by hidden edge classes * See above the defines of * UNFOLDED_SGRAPH, FOLDED_SGNODE, FOLDED_RGNODE, HIDDEN_CNODE */ /* Abbreviation to delete and insert nodes in double linked lists */ #define del_node_from_dl_list(v,l,le) { \ if (NBEFORE(v)) NNEXT(NBEFORE(v)) = NNEXT(v); \ else l = NNEXT(v); \ if (NNEXT(v)) NBEFORE(NNEXT(v)) = NBEFORE(v); \ else le = NBEFORE(v); \ } #define ins_node_in_dl_list(v,l,le) { \ NBEFORE(v) = le; \ if (le) NNEXT(le) = v; \ le = v; \ if (!l) l = v; \ } /* Delete a node v from the nodelist * --------------------------------- * The node becomes invisible. * The invisibly flag is set to k, which is the reason why the node * is invisible. */ #ifdef ANSI_C static void delete_node(GNODE v,int k) #else static void delete_node(v,k) GNODE v; int k; #endif { assert((v)); assert((k!=0)); debugmessage("delete_node",(NTITLE(v)?NTITLE(v):"(null)")); if (!NINLIST(v)) return; NINLIST(v) = 0; NINVISIBLE(v) = k; del_node_from_dl_list(v,nodelist,nodelistend); NNEXT(v) = NULL; NBEFORE(v) = NULL; if (NSGRAPH(v)) { /* a subgraph comes back into the graph list */ if (k==UNFOLDED_SGRAPH) { ins_node_in_dl_list(v,graphlist,graphlistend); } } nodeanz--; } /* Inserts a node v into the nodelist * ---------------------------------- * The node becomes visible. * The reason of becoming visible is, that invisibility reason k * is not anymore valid. If k was not the invisibility reason, * then the insertion cannot be done. */ #ifdef ANSI_C static void insert_node(GNODE v,int k) #else static void insert_node(v,k) GNODE v; int k; #endif { assert((v)); assert((k!=0)); debugmessage("insert_node",(NTITLE(v)?NTITLE(v):"(null)")); if (NINLIST(v)) return; if (NINVISIBLE(v)!=k) return; NINLIST(v) = 1; NINVISIBLE(v) = 0; if (NSGRAPH(v)) { /* a subgraph must be removed from the graph list */ if (k==UNFOLDED_SGRAPH) { del_node_from_dl_list(v,graphlist,graphlistend); } } NNEXT(v) = NULL; NBEFORE(v) = NULL; ins_node_in_dl_list(v,nodelist,nodelistend); nodeanz++; } /*--------------------------------------------------------------------*/ /* Folding of subgraphs */ /*--------------------------------------------------------------------*/ /* Delete all nodes of a subgraph from the nodelist * ------------------------------------------------ * i.e. it hides the subgraph u (and all its subgraphs too). */ #ifdef ANSI_C static void delete_sgnodes(GNODE u) #else static void delete_sgnodes(u) GNODE u; #endif { GNODE v; GNLIST s; if (!u) return; debugmessage("delete_sgnodes",(NTITLE(u)?NTITLE(u):"(null)")); s = NSGRAPH(u); while (s) { v = GNNODE(s); delete_node(v,FOLDED_SGNODE); if (NSGRAPH(v)) delete_sgnodes(v); s = GNNEXT(s); } } /* Fold a subgraph * --------------- * u is the root node of the subgraph * Folding means: delete all nodes of this subgraph from the nodelist * and insert the summary node. */ #ifdef ANSI_C static void fold_sg(GNODE u) #else static void fold_sg(u) GNODE u; #endif { if (!u) return; debugmessage("fold_sg",(NTITLE(u)?NTITLE(u):"(null)")); delete_sgnodes(u); insert_node(u,UNFOLDED_SGRAPH); } /* Unfold a subgraph * ----------------- * u is the root node of the subgraph * Unfolding means: delete this subgraph summary node from the nodelist * and insert all its nodes. */ #ifdef ANSI_C static void unfold_sg(GNODE u) #else static void unfold_sg(u) GNODE u; #endif { GNODE v; GNLIST s; if (!u) return; debugmessage("unfold_sg",(NTITLE(u)?NTITLE(u):"(null)")); s = NSGRAPH(u); while (s) { v = GNNODE(s); insert_node(v,FOLDED_SGNODE); /* If v was an unfolded subgraph before the folding, * it was before not visible, thus it is not inserted, * since the insert reason FOLDED_SGNODE is not the * delete reason UNFOLDED_SG. Then we have to unfold its * subnodes, too. */ if (NSGRAPH(v) && (NINVISIBLE(v)==UNFOLDED_SGRAPH)) unfold_sg(v); s = GNNEXT(s); } delete_node(u,UNFOLDED_SGRAPH); } /*--------------------------------------------------------------------*/ /* Folding of regions */ /*--------------------------------------------------------------------*/ /* Note that region operations are not inverse implemented, even * if the effect is inverse. * The reason is, that unfolding is done BEFORE the adjacency lists * exist, but folding can only be done AFTER the adjacency lists exist. * Firther we use a dirty trick here: instead of creating a summary * node of the region, we use the start node of the region as summary * node. This has the advantage that the summary node is in the correct * subgraph, and that we have no problems with the hashtable to * search node title. An auxiliary node is created as REGREPL, to contain * the information of the originally start node. This must be done * because the originally start node could be a summary node of a * previous region folding. */ /* Fold Region * ----------- * Starting from a node n, all nodes and edges reacheable by * edges of class <= k are folded. * Before, the adjacency lists were created. */ #ifdef ANSI_C static void fold_region(GNODE n,int k) #else static void fold_region(n,k) GNODE n; int k; #endif { ADJEDGE a; GEDGE e; GNODE h; assert((n)); debugmessage("fold_region",(NTITLE(n)?NTITLE(n):"(null)")); /* First, we create a stable replacement node, that stores * all information of the node. Then we use the start node * as summary node, because the start node is part of the * right graph. */ h = nodealloc(n); NTITLE(h) = NTITLE(n); NROOT(h) = NROOT(n); NREGREPL(h) = NREGREPL(n); NREGION(h) = NREGION(n); NREGROOT(h) = NREGROOT(n); NSX(n) = NSY(n) = 0L; /* Locations are not inherited ! */ NWIDTH(n) = NHEIGHT(n) = -1; /* Sizes are not inherited */ delete_node(h,FOLDED_RGNODE); /* h is invisible */ /* Now: h has the purpose of n, and n is the summary node * Now we change the properties of the summary nodes according * to the defaults. */ inherit_foldnode_attributes(&foldnode, n); NREGREPL(n) = h; NREGION(n) = NULL; /* here we collect the nodes of this region */ /* Fold the nodes recursively */ a = NSUCC(n); while (a) { e = AKANTE(a); if ( ECLASS(e)<=k ) { if ( !foldstop_reached(EEND(e)) ) { EINVISIBLE(e) = 1; recursive_fold(EEND(e),n,k); } } a = ANEXT(a); } } /* Recursive fold region * --------------------- * This is an auxiliary function of fold_region. * It folds the region of class <=k starting at v. The summary node * of the region is n. It makes the nodes of the region invisible, * and calculates substitutions for edges. * The function is a little bit inefficient if we have cross edges * inside the folded region, because these might be substituted * and the substed will be later removed. */ #ifdef ANSI_C static void recursive_fold(GNODE v,GNODE n,int k) #else static void recursive_fold(v,n,k) GNODE v; GNODE n; int k; #endif { ADJEDGE a; GEDGE e,ee; GNLIST l; assert((v)); assert((n)); debugmessage("recursive_fold",(NTITLE(v)?NTITLE(v):"(null)")); /* Check of cycle: both checks means the same */ if ( !NINLIST(v) ) return; if ( NREGROOT(v) == n ) return; /* Check of cycle: this is the node we started folding */ if ( v == n ) return; /* Add v to the region list of n */ NREGROOT(v) = n; l = nodelist_alloc(v); if ( !NREGION(n) ) { GNNEXT(l) = NULL; NREGION(n) = l; } else { GNNEXT(l) = NREGION(n); NREGION(n) = l; } delete_node(v,FOLDED_RGNODE); /* Go into the recursion */ a = NSUCC(v); while (a) { e = AKANTE(a); if ( ECLASS(e) <= k ) { if ( !foldstop_reached(EEND(e)) ) { EINVISIBLE(e) = 1; recursive_fold(EEND(e),n,k); } } a = ANEXT(a); } /* Substitute the predecessor edges of v */ a = NPRED(v); while (a) { e = AKANTE(a); ee = substed_edge(e); if (ee!=e) { /* Edge e invisible or substituted: * Remove edge e from adjacency list of the source. */ delete_adjedge(e); /* and insert new edge, but avoid self loops at * the region node. */ assert((!ee)||(EEND(ee)==n)); if (ee && (ESTART(ee)!=n)) create_adjedge(ee); } a = ANEXT(a); } /* Substitute the successor edges of v */ a = NSUCC(v); while (a) { e = AKANTE(a); ee = substed_edge(e); if (ee!=e) { /* Edge e invisible or substituted: * Remove edge e from adjacency list of the source. */ delete_adjedge(e); /* and insert new edge, but avoid self loops at * the region node. */ assert((!ee)||(ESTART(ee)==n)); if (ee && (EEND(ee)!=n)) create_adjedge(ee); } a = ANEXT(a); } NPRED(v) = NSUCC(v) = NULL; /* because v is invisible */ } /* Unfold Region * ------------- * Different than "fold region", this is done BEFORE the adjacency * lists exist. Unfold the region that has summary node n. */ #ifdef ANSI_C static void unfold_region(GNODE n) #else static void unfold_region(n) GNODE n; #endif { GNLIST l, startl; GNODE h; assert((n)); debugmessage("unfold_region",(NTITLE(n)?NTITLE(n):"(null)")); if (NREGREPL(n)==NULL) return; /* it was no region */ h = NREGREPL(n); startl = l = NREGION(n); /* Make n again a normal node, i.e. restore the attributes from h. */ NLABEL(n) = NLABEL(h); NTEXTMODE(n) = NTEXTMODE(h); NWIDTH(n) = NWIDTH(h); NHEIGHT(n) = NHEIGHT(h); NBORDERW(n) = NBORDERW(h); NSX(n) = NSX(h); NSY(n) = NSY(h); NFOLDING(n) = NFOLDING(h); NCOLOR(n) = NCOLOR(h); NTCOLOR(n) = NTCOLOR(h); NBCOLOR(n) = NBCOLOR(h); NSHRINK(n) = NSHRINK(h); NSTRETCH(n) = NSTRETCH(h); NINFO1(n) = NINFO1(h); NINFO2(n) = NINFO2(h); NINFO3(n) = NINFO3(h); NLEVEL(n) = NLEVEL(h); NSHAPE(n) = NSHAPE(h); NHORDER(n) = NHORDER(h); NROOT(n) = NROOT(h); NREGREPL(n) = NREGREPL(h); NREGION(n) = NREGION(h); NREGROOT(n) = NREGROOT(h); free_node(h); /* give h free */ while (l) { h = GNNODE(l); NREGROOT(h) = NULL; insert_node(h,FOLDED_RGNODE); l = GNNEXT(l); } free_regionnodelist(startl); /* give the region cons cells free */ } /*--------------------------------------------------------------------*/ /* Hiding of edges */ /*--------------------------------------------------------------------*/ /* Management of Edge Classes * ========================== * The hidden edge classes i have hide_class[i]=1. * The nodes from the nodelist that are hidden are pushed into * the list invis_nodes. * At the beginning of the layout process, these nodes are * repushed into the nodelist. */ int *hide_class=NULL; /* table which edge classes are hidden*/ /* Initialization * -------------- * All classes are visible, no class is hidden. */ #ifdef ANSI_C void clear_hide_class(void) #else void clear_hide_class() #endif { int i; debugmessage("clear_hide_class",""); if (!hide_class) return; for (i=0;i