git.gag.com Git - fw/sdcc/blob - src/pic16/graph.h

   1 /*-------------------------------------------------------------------------
   2
   3   graph.h - header file for graph.c
   4
   5    Written By -  Raphael Neider <rneider AT web.de> (2005)
   6
   7    This program is free software; you can redistribute it and/or modify it
   8    under the terms of the GNU General Public License as published by the
   9    Free Software Foundation; either version 2, or (at your option) any
  10    later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program; if not, write to the Free Software
  19    Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  20 -------------------------------------------------------------------------*/
  21
  22 /* $Id$ */
  23
  24 #ifndef __GRAPH_H__
  25 #define __GRAPH_H__
  26
  27 #include "../common.h"
  28
  29 typedef unsigned int hash_t;
  30
  31 struct GraphNode;
  32
  33 typedef struct GraphEdge {
  34   struct GraphNode *src;        // starting node of this edge
  35   struct GraphNode *node;       // other end of this edge
  36   unsigned int weight;          // weight assigned to this edge
  37   struct GraphEdge *prev;       // link to previous edge
  38   struct GraphEdge *next;       // link to next edge
  39 } GraphEdge;
  40
  41 typedef struct GraphNode {
  42   void *data;                   // data stored in this node
  43   hash_t hash;                  // hash value for "data"
  44
  45   GraphEdge *edge;              // first edge leaving this node
  46   struct GraphNode *prev;       // link to previous node
  47   struct GraphNode *next;       // link to next edge
  48 } GraphNode;
  49
  50 // compare function, returns 0 for different items and 1 for equal items
  51 typedef int Graph_compareData(void *item1, void *item2);
  52
  53 typedef struct {
  54   GraphNode *node;              // first node in this graph
  55   Graph_compareData *compare;   // function used to compare two data items
  56 } Graph;
  57
  58 /* Create a new edge from src to dest.
  59  * Returns a pointer to the new edge. */
  60 GraphEdge *newGEdge (GraphNode *src, GraphNode *dest, unsigned int weight);
  61
  62 /* Delete an edge and remove it from the containing list.
  63  * Returns a pointer to the previous edge or (if there is NULL) to its successor. */
  64 GraphEdge *deleteGEdge (GraphEdge *edge);
  65
  66
  67
  68 /* Create a new node. */
  69 GraphNode *newGNode (void *data, hash_t hash);
  70
  71 /* Delete a node and all its edges. this also removes the node
  72  * from its containing list.
  73  * Returns the previous node in the list or (if there is NULL)
  74  * its successor. */
  75 GraphNode *deleteGNode (GraphNode *node);
  76
  77 /* Adds an edge with the given weight. If the edge already exists,
  78  * its weight its increased instead! */
  79 GraphEdge *addGEdge (GraphNode *from, GraphNode *to, unsigned int weight);
  80
  81 /* Adds the edges (from,to) and (to,from) with the specified weights. */
  82 void addGEdge2 (GraphNode *from, GraphNode *to, unsigned int weight, unsigned int weight_back);
  83
  84 /* Remove an edge from the node. This deletes the edge and updates the
  85  * list of edges attached to the "from" node. */
  86 void remGEdge (GraphNode *from, GraphNode *to);
  87
  88 /* Returns the edge (from,to) or NULL if no such edge exists. */
  89 GraphEdge *getGEdge (GraphNode *from, GraphNode *to);
  90
  91
  92
  93 /* Create a new graph which uses the given compare function to test
  94  * its nodes' data for equality. */
  95 Graph *newGraph (Graph_compareData *compare);
  96
  97 /* Delete a graph, all its contained nodes and their edges. */
  98 void deleteGraph (Graph *graph);
  99
 100 /* Add a node to the graph. */
 101 GraphNode *addGNode (Graph *graph, void *data, hash_t hash);
 102
 103 /* Remove a node from the graph. This also deletes the node and all
 104  * its associated (outbound) edges. */
 105 void remGNode (Graph *graph, void *data, hash_t hash);
 106
 107 /* Returns the specified node or NULL if no such node exists. */
 108 GraphNode *getGNode (Graph *graph, void *data, hash_t hash);
 109
 110 /* Returns the specified node (after creating it if neccessary). */
 111 GraphNode *getOrAddGNode (Graph *graph, void *data, hash_t hash);
 112
 113 #endif