home *** CD-ROM | disk | FTP | other *** search
/ cs.rhul.ac.uk / www.cs.rhul.ac.uk.zip / www.cs.rhul.ac.uk / pub / rdp / rdp_cs3470.tar / rdp_supp / graph.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-05-07  |  17.0 KB  |  572 lines
  1. /*******************************************************************************
  2. *
  3. * RDP release 1.50 by Adrian Johnstone (A.Johnstone@rhbnc.ac.uk) 20 December 1997
  4. *
  5. * graph.c - graph creation and manipulation routines
  6. *
  7. * This file may be freely distributed. Please mail improvements to the author.
  8. *
  9. *******************************************************************************/
  10. #include <stddef.h>
  11. #include <stdio.h>
  12. #include <stdlib.h>
  13. #include <string.h>
  14. #include "graph.h"
  15. #include "textio.h"
  16. #include "memalloc.h"
  17. /*******************************************************************************
  18. *
  19. * Graphs are represented using doubly linked lists of `atoms'. Each atom
  20. * contains three pointers: `succ1' (successor1), `succ2' (successor2) and
  21. * `pred' (predecessor). These three pointers will either contain NULL or the
  22. * adddress of the base address of another atom.
  23. *
  24. * Whenever an atom is created, a user data block of `size' bytes may be
  25. * included. User data is stored after the pointers, and all user level
  26. * references are to the base of the user data block so that the internal
  27. * pointers are invisible to the user.
  28. *
  29. * Operations on atoms use the base of the internal pointers, other
  30. * operations use the base of the user data.
  31. *
  32. *******************************************************************************/
  33.  
  34. /* The basic graph pointer block used by edges, nodes and graph headers */
  35. /* Designed to be part of a doubly linked list with data hooks */
  36. typedef struct graph_atom_struct
  37. {
  38.   struct graph_atom_struct
  39.   * succ1,                    /* successor 1: used for next graph, next edge, or start of edge list */
  40.   * succ2,                    /* successor 2: used for next node or start of node list and as edge backpointer */
  41.   * pred;                     /* pointer to previous node */
  42.   long int atom_number;       /* creation number for this atom: nodes have negative numbers, edges and graphs positive */
  43. }graph_atom; 
  44.  
  45. #define NEXT_GRAPH succ1
  46. #define NEXT_NODE succ2
  47. #define NEXT_EDGE succ1
  48. #define EDGE_TARGET succ2
  49.  
  50. /* Global variables */
  51. static graph_atom graph_list = {NULL, NULL, NULL, 0};  /* The list of active graph structures */
  52. static long int graph_atom_count = 1;  /* The number of the next atom to be created */
  53.  
  54. /* Comparison routines for the first data item in the user data block:
  55.    routines for double length reals, long integers, raw memory and strings.
  56.    It's easy to add new tests by following the routines given here. */
  57. int graph_compare_double(void * left, void * right)
  58. {
  59.   if (*((double *) left)== *((double *) right))
  60.     return 0; 
  61.   else if (*((double *) left)> *((double *) right))
  62.     return 1; 
  63.   else
  64.     return - 1; 
  65. }
  66.  
  67. int graph_compare_long(void * left, void * right)
  68. {
  69.   if (*((long *) left)== *((long *) right))
  70.     return 0; 
  71.   else if (*((long *) left)> *((long *) right))
  72.     return 1; 
  73.   else
  74.     return - 1; 
  75. }
  76.  
  77. int graph_compare_mem(void * left, void * right, size_t size)
  78. /* compare size characters of two memory blocks */
  79. {
  80.   char * ll =(char *) left; 
  81.   char * rr =(char *) right; 
  82.   
  83.   while (size-- > 0 && * ll == * rr)
  84.   {
  85.     ll++; 
  86.     rr++; 
  87.   }
  88.   if (* ll == * rr)
  89.     return 0; 
  90.   else if (* ll > * rr)
  91.     return 1; 
  92.   else
  93.     return - 1; 
  94. }
  95.  
  96. int graph_compare_string(void * left, void * right)
  97. {
  98.   char * left_str = *(char * *) left; 
  99.   char * right_str = *(char * *) right; 
  100.   
  101.   return strcmp(left_str, right_str); 
  102. }
  103.  
  104. void graph_delete_edge(void * edge)
  105. {
  106.   graph_atom * base =(graph_atom *) edge - 1; 
  107.   
  108.   /* unlink this edge */
  109.   
  110.   if (base->NEXT_EDGE != NULL) /* make next node point back to our predecessor */
  111.     base->NEXT_EDGE->pred = base->pred; 
  112.   
  113.   base->pred->NEXT_EDGE = base->NEXT_EDGE;  /* point predecessor node at our successor */
  114.   
  115.   /* and free the edge's memory */
  116.   mem_free(base); 
  117. }
  118.  
  119. void graph_delete_graph(void * graph)
  120. {
  121.   graph_atom * base =(graph_atom *) graph - 1; 
  122.   
  123.   /* delete nodes */
  124.   while (base->NEXT_NODE != NULL)
  125.     graph_delete_node(base->NEXT_NODE + 1); 
  126.   
  127.   /* now unlink this graph */
  128.   
  129.   if (base->NEXT_GRAPH != NULL) /* make next node point back to our predecessor */
  130.     base->NEXT_GRAPH->pred = base->pred; 
  131.   
  132.   base->pred->NEXT_GRAPH = base->NEXT_GRAPH;  /* point predecessor node at our successor */
  133.   
  134.   /* and free the graph's memory */
  135.   mem_free(base); 
  136. }
  137.  
  138. void graph_delete_node(void * node)
  139. {
  140.   graph_atom * base =(graph_atom *) node - 1; 
  141.   
  142.   /* delete edges */
  143.   
  144.   while (base->NEXT_EDGE != NULL)
  145.     graph_delete_edge(base->NEXT_EDGE + 1); 
  146.   
  147.   /* now unlink this node */
  148.   
  149.   if (base->NEXT_NODE != NULL) /* make next node point back to our predecessor */
  150.     base->NEXT_NODE->pred = base->pred; 
  151.   
  152.   base->pred->NEXT_NODE = base->NEXT_NODE;  /* point predecessor node at our successor */
  153.   
  154.   /* and free the node's memory */
  155.   mem_free(base); 
  156. }
  157.  
  158. unsigned long graph_get_atom_number(const void * graph_or_node_or_edge)
  159. {
  160.   long atom_number =((graph_atom *) graph_or_node_or_edge - 1)->atom_number; 
  161.   
  162.   return atom_number < 0 ? - atom_number: atom_number; 
  163. }
  164.  
  165. void * graph_get_edge_target(const void * edge)
  166. {
  167.   if (edge == NULL)
  168.     return NULL; 
  169.   else
  170.   {
  171.     graph_atom * temp =((graph_atom *) edge - 1)->EDGE_TARGET; 
  172.     
  173.     return temp == NULL ? temp: temp + 1; 
  174.   }
  175. }
  176.  
  177. void * graph_get_final_edge(const void * node_or_edge)
  178. {
  179.   graph_atom * temp =(graph_atom *) node_or_edge - 1; 
  180.   
  181.   while (temp->NEXT_EDGE != NULL)
  182.     temp = temp->NEXT_EDGE; 
  183.   
  184.   return temp == NULL ? temp: temp + 1; 
  185. }
  186.  
  187. void * graph_get_final_node(const void * node_or_edge)
  188. {
  189.   graph_atom * temp =(graph_atom *) node_or_edge - 1; 
  190.   
  191.   while (temp->NEXT_NODE != NULL)
  192.     temp = temp->NEXT_NODE; 
  193.   
  194.   return temp == NULL ? temp: temp + 1; 
  195. }
  196.  
  197. void * graph_get_next_edge(const void * node_or_edge)
  198. {
  199.   graph_atom * temp =((graph_atom *) node_or_edge - 1)->NEXT_EDGE; 
  200.   
  201.   return temp == NULL ? temp: temp + 1; 
  202. }
  203.  
  204. void * graph_get_next_node(const void * graph_or_node)
  205. {
  206.   graph_atom * temp =((graph_atom *) graph_or_node - 1)->NEXT_NODE; 
  207.   
  208.   return temp == NULL ? temp: temp + 1; 
  209. }
  210.  
  211. void * graph_get_previous_edge(const void * node_or_edge)
  212. {
  213.   graph_atom * temp =((graph_atom *) node_or_edge - 1)->pred; 
  214.   
  215.   return temp->pred->NEXT_EDGE != temp ? NULL: temp + 1; 
  216. }
  217.  
  218. void * graph_get_previous_node(const void * node_or_edge)
  219. {
  220.   graph_atom * temp =((graph_atom *) node_or_edge - 1)->pred; 
  221.   
  222.   return temp->pred->NEXT_NODE != temp ? NULL: temp + 1; 
  223. }
  224.  
  225. void * graph_insert_edge(size_t size, void * target_node, void * node_or_edge)
  226. {
  227.   graph_atom * base =(graph_atom *) node_or_edge - 1; 
  228.   graph_atom * temp =(graph_atom *) mem_calloc(sizeof(graph_atom)+ size, 1); 
  229.   
  230.   temp->atom_number = graph_atom_count++; 
  231.   
  232.   /* Now insert after node_or_edge */
  233.   temp->NEXT_EDGE = base->NEXT_EDGE;  /* look at rest of list */
  234.   base->NEXT_EDGE = temp;     /* point previous at this node */
  235.   
  236.   temp->pred = base;          /* point backlink at base pointer */
  237.   
  238.   if (temp->NEXT_EDGE != NULL) /* if rest of list is non-null... */
  239.     (temp->NEXT_EDGE)->pred = temp;  /* point next node back at us */
  240.   
  241.   temp->EDGE_TARGET =(graph_atom *) target_node - 1; 
  242.   
  243.   return temp + 1; 
  244. }
  245.  
  246.  
  247. void * graph_insert_graph(char * id)
  248. {
  249.   graph_atom * base = & graph_list; 
  250.   graph_atom * temp =(graph_atom *) mem_calloc(sizeof(graph_atom)+ sizeof(char *), 1); 
  251.   
  252.   temp->atom_number = graph_atom_count++; 
  253.   temp->NEXT_NODE = NULL; 
  254.   
  255.   /* Now insert at head of graph_list */
  256.   temp->NEXT_GRAPH = base->NEXT_GRAPH;  /* look at rest of list */
  257.   base->NEXT_GRAPH = temp;    /* point previous at this node */
  258.   
  259.   temp->pred = base;          /* point backlink at base pointer */
  260.   
  261.   if (temp->NEXT_GRAPH != NULL) /* if rest of list is non-null... */
  262.     (temp->NEXT_GRAPH)->pred = temp;  /* point next node back at us */
  263.   
  264.   *((char * *)(++temp))= id; 
  265.   
  266.   return temp; 
  267. }
  268.  
  269. void * graph_insert_node(size_t size, void * node_or_graph)
  270. {
  271.   graph_atom * base =(graph_atom *) node_or_graph - 1; 
  272.   graph_atom * temp =(graph_atom *) mem_calloc(sizeof(graph_atom)+ size, 1); 
  273.   
  274.   temp->atom_number = -(graph_atom_count++); 
  275.   temp->NEXT_EDGE = NULL; 
  276.   
  277.   /* Now insert after node_or_graph */
  278.   temp->NEXT_NODE = base->NEXT_NODE;  /* look at rest of list */
  279.   base->NEXT_NODE = temp;     /* point previous at this node */
  280.   
  281.   temp->pred = base;          /* point backlink at base pointer */
  282.   
  283.   if (temp->NEXT_NODE != NULL) /* if rest of list is non-null... */
  284.     (temp->NEXT_NODE)->pred = temp;  /* point next node back at us */
  285.   
  286.   return temp + 1; 
  287. }
  288.  
  289. void * graph_insert_node_child(size_t node_size, size_t edge_size, void * parent_node)
  290. /* make a new node and insert in a graqph, and then add an edge from a source
  291.    node to the new node. Return the node
  292.  
  293.    This version is a bit kludgy to ensure that RDP adds child nodes at the end
  294.    We should build a tree library instead, I think
  295. */
  296. {
  297.   void * insert_node, 
  298.   * temp = graph_insert_node(node_size, parent_node); 
  299.   
  300.   insert_node = graph_get_final_edge(parent_node); 
  301.   
  302.   graph_insert_edge(edge_size, temp, insert_node); 
  303.   
  304.   return temp; 
  305. }
  306.  
  307. void * graph_insert_node_parent(size_t node_size, size_t edge_size, void * child_node)
  308. /* This slightly tricky routine is a sort of dual to graph_insert_node_child.
  309.    The idea is to make a new node that will become the parent of the child node.
  310.    The problem is that anythin pointing to child_node at entry must be left
  311.    pointing at the new parent, so the trick is to reuse the existing child_node.
  312.  
  313.    1. Make a new node
  314.    2. Copy the contents of child_node into it, so that it becomes a clone.
  315.    3. Make the first edge point back at the clone instead of child_node
  316.    4. Clear the contents of child_node and its edge list.
  317.    5. Add a new edge from child_node to the clone.
  318. */
  319. {
  320.   graph_atom * child_base, * clone_base; 
  321.   void * clone_node = graph_insert_node(node_size, child_node); 
  322.   
  323.   child_base =(graph_atom *) child_node - 1; 
  324.   clone_base =(graph_atom *) clone_node - 1; 
  325.   
  326.   /* Copy child contents to clone */
  327.   memcpy(clone_node, child_node, node_size); 
  328.   
  329.   /* Link the child's edges to the clone  */
  330.   clone_base->NEXT_EDGE = child_base->NEXT_EDGE; 
  331.   if (clone_base->NEXT_EDGE != NULL)
  332.     (clone_base->NEXT_EDGE)->pred = clone_base; 
  333.   
  334.   memset(child_node, 0, node_size);  /* Clear data fields in child node */
  335.   child_base->NEXT_EDGE = NULL;  /* Clear edge list in child node */
  336.   
  337.   graph_insert_edge(edge_size, clone_node, child_node); 
  338.   
  339.   return child_node; 
  340. }
  341.  
  342. unsigned graph_hash_double(unsigned hash_prime, void * data)
  343. {                             /* hash a string */
  344.   return(unsigned)((long) hash_prime * *((long *) data)); 
  345. }
  346.  
  347. unsigned graph_hash_long(unsigned hash_prime, void * data)
  348. {                             /* hash a string */
  349.   return(unsigned)((long) hash_prime * *((long *) data)); 
  350. }
  351.  
  352. unsigned graph_hash_mem(unsigned hash_prime, void * data)
  353. {                             /* hash a string */
  354.   unsigned hashnumber = 0; 
  355.   unsigned count = *(unsigned *) data; 
  356.   char * string = *(char * *)((unsigned *) data + 1); 
  357.   
  358.   if (string != NULL)         /* Don't try and scan a vacuous string */
  359.     while (count-- > 0)       /* run up string */
  360.     hashnumber = * string++ + hash_prime * hashnumber; 
  361.   return hashnumber; 
  362. }
  363.  
  364. unsigned graph_hash_string(unsigned hash_prime, void * data)
  365. {                             /* hash a string */
  366.   unsigned hashnumber = 0; 
  367.   char * str = *(char * *) data; 
  368.   
  369.   if (str != NULL)            /* Don't try and scan a vacuous string */
  370.     while (* str != 0)        /* run up string */
  371.     hashnumber = * str++ + hash_prime * hashnumber; 
  372.   return hashnumber; 
  373. }
  374.  
  375. static void graph_vcg_graph(graph_atom * curr_graph, 
  376. void(* graph_action)(const void * graph), 
  377. void(* node_action)(const void * node), 
  378. void(* edge_action)(const void * edge)
  379. )
  380. {
  381.   graph_atom * curr_node, 
  382.   * curr_edge; 
  383.   
  384.   if (graph_action != NULL)   /* print a user defined label field */
  385.     graph_action(curr_graph + 1); 
  386.   
  387.   curr_node = curr_graph->NEXT_NODE; 
  388.   
  389.   while (curr_node != NULL)
  390.   {
  391.     text_printf("node:{title:\"%li\"", curr_node->atom_number); 
  392.     
  393.     if (node_action != NULL)  /* print a user defined label field */
  394.       node_action(curr_node + 1); 
  395.     else
  396.       text_printf("label: \"Node:%li\"", - curr_node->atom_number); 
  397.     
  398.     text_printf("}\n"); 
  399.     
  400.     curr_edge = curr_node->NEXT_EDGE; 
  401.     
  402.     while (curr_edge != NULL)
  403.     {
  404.       text_printf("edge:{sourcename:\"%li\" targetname:\"%li\"", curr_node->atom_number, curr_edge->EDGE_TARGET->atom_number); 
  405.       
  406.       if (edge_action != NULL) /* print a user defined label field */
  407.         edge_action(curr_edge + 1); 
  408. /*
  409.       else
  410.         text_printf("label: \"Edge:%li\"", curr_edge->atom_number);
  411. */
  412.       
  413.       text_printf("}\n"); 
  414.       
  415.       curr_edge = curr_edge->NEXT_EDGE; 
  416.     }
  417.     curr_node = curr_node->NEXT_NODE; 
  418.   }
  419. }
  420.  
  421. void graph_vcg(void * graph, 
  422. void(* graph_action)(const void * graph), 
  423. void(* node_action)(const void * node), 
  424. void(* edge_action)(const void * edge)
  425. )
  426. {
  427.   text_printf("graph:{\norientation:top_to_bottom"
  428.   "\nedge.arrowsize:7"
  429.   "\nedge.thickness:1"
  430.   "\ndisplay_edge_labels:yes"
  431.   "\narrowmode:free"
  432.   "\nnode.borderwidth:1\n"); 
  433.   
  434.   if (graph == NULL)
  435.   {
  436.     /* dump all graphs */
  437.     graph_atom * curr_graph = graph_list.NEXT_GRAPH; 
  438.     
  439.     while (curr_graph != NULL)
  440.     {
  441.       graph_vcg_graph(curr_graph, graph_action, node_action, edge_action); 
  442.       
  443.       curr_graph = curr_graph->NEXT_GRAPH; 
  444.     }
  445.   }
  446.   else
  447.     /* dump specific graph */
  448.   graph_vcg_graph((graph_atom *) graph - 1, graph_action, node_action, edge_action); 
  449.   
  450.   text_printf("\n}\n"); 
  451. }
  452.  
  453. static unsigned long graph_vcg_atoms_graph(long unsigned graph_offset, 
  454. graph_atom * curr_graph, 
  455. void(* graph_action)(const void * graph), 
  456. void(* node_action)(const void * node), 
  457. void(* edge_action)(const void * edge)
  458. )
  459. {
  460.   #define xscale 120
  461.   #define yscale 50
  462.   #define width "100"
  463.   
  464.   graph_atom * curr_node, 
  465.   * curr_edge; 
  466.   unsigned node_count = 1; 
  467.   unsigned long max_edges = 0; 
  468.   
  469.   text_printf("\nnode:{loc:{x:1 y:%li} title:\"%li\"", graph_offset, curr_graph->atom_number); 
  470.   
  471.   if (graph_action != NULL)   /* print a user defined label field */
  472.     graph_action(curr_graph + 1); 
  473.   else
  474.     text_printf("label: \"Graph:%li\"", curr_graph->atom_number); 
  475.   text_printf("}\n"); 
  476.   
  477.   curr_node = curr_graph->NEXT_NODE; 
  478.   
  479.   if (curr_node != NULL)
  480.     text_printf("edge:{sourcename:\"%li\" targetname:\"%li\"}\n", curr_graph->atom_number, curr_node->atom_number); 
  481.   
  482.   while (curr_node != NULL)
  483.   {
  484.     unsigned edge_count = 1; 
  485.     
  486.     text_printf("\nnode:{loc:{x:%u y:%u} title:\"%li\"", node_count * xscale, graph_offset, curr_node->atom_number); 
  487.     
  488.     if (node_action != NULL)  /* print a user defined label field */
  489.       node_action(curr_node + 1); 
  490.     else
  491.       text_printf("label: \"Node:%li\"", - curr_node->atom_number); 
  492.     text_printf("}\n"); 
  493.     
  494.     if (curr_node->NEXT_NODE != NULL)
  495.       text_printf("edge:{sourcename:\"%li\" targetname:\"%li\"}\n", curr_node->atom_number, curr_node->NEXT_NODE->atom_number); 
  496.     
  497.     curr_edge = curr_node->NEXT_EDGE; 
  498.     
  499.     if (curr_edge != NULL)
  500.       text_printf("edge:{sourcename:\"%li\" targetname:\"%li\"}\n", curr_node->atom_number, curr_edge->atom_number); 
  501.     
  502.     while (curr_edge != NULL)
  503.     {
  504.       text_printf("\nnode:{loc:{x:%u y:%u} title:\"%li\"", node_count * xscale, edge_count * yscale + graph_offset, curr_edge->atom_number); 
  505.       
  506.       if (edge_action != NULL) /* print a user defined label field */
  507.         edge_action(curr_edge + 1); 
  508.       else
  509.         text_printf("label: \"Edge:%li\"", curr_edge->atom_number); 
  510.       text_printf("}\n"); 
  511.       
  512.       if (curr_edge->NEXT_EDGE != NULL)
  513.         text_printf("edge:{sourcename:\"%li\" targetname:\"%li\"}\n", curr_edge->atom_number, curr_edge->NEXT_EDGE->atom_number); 
  514.       
  515.       text_printf("edge:{backarrowstyle:none sourcename:\"%li\" targetname:\"%li\"}\n", curr_edge->atom_number, curr_edge->EDGE_TARGET->atom_number); 
  516.       
  517.       curr_edge = curr_edge->NEXT_EDGE; 
  518.       
  519.       if (edge_count > max_edges)
  520.         max_edges = edge_count; 
  521.       
  522.       edge_count++; 
  523.     }
  524.     curr_node = curr_node->NEXT_NODE; 
  525.     node_count++; 
  526.   }
  527.   return max_edges * yscale; 
  528. }
  529.  
  530. void graph_vcg_atoms(void * graph, 
  531. void(* graph_action)(const void * graph), 
  532. void(* node_action)(const void * node), 
  533. void(* edge_action)(const void * edge)
  534. )
  535. {
  536.   long unsigned graph_offset = 0; 
  537.   
  538.   text_printf("graph:{\n"
  539.   "\nport_sharing:yes"
  540.   "\nnode.width:" width
  541.   "\nedge.backarrowsize:7"
  542.   "\nedge.backarrowstyle:solid"
  543.   "\nedge.arrowsize:7"
  544.   "\nedge.thickness:1"
  545.   "\nnode.borderwidth:1\n"); 
  546.   
  547.   if (graph == NULL)
  548.   {
  549.     /* dump all graphs */
  550.     graph_atom * curr_graph = graph_list.NEXT_GRAPH; 
  551.     
  552.     while (curr_graph != NULL)
  553.     {
  554.       graph_offset += graph_vcg_atoms_graph(graph_offset, curr_graph, graph_action, node_action, edge_action); 
  555.       
  556.       if (curr_graph->NEXT_GRAPH != NULL) /* if there is another graph, add an edge */
  557.         text_printf("edge:{ sourcename:\"%li\" targetname:\"%li\"}\n", curr_graph->atom_number, curr_graph->NEXT_GRAPH->atom_number); 
  558.       
  559.       graph_offset += yscale; 
  560.       
  561.       curr_graph = curr_graph->NEXT_GRAPH; 
  562.     }
  563.   }
  564.   else
  565.     /* dump specific graph */
  566.   graph_vcg_atoms_graph(0, (graph_atom *) graph - 1, graph_action, node_action, edge_action); 
  567.   
  568.   text_printf("\n}\n"); 
  569. }
  570.  
  571. /* End of graph.c */
  572.