1 /*-------------------------------------------------------------------------
3 graph.c - implementation of general graphs
5 Written By - Raphael Neider rneider@web.de (2005)
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
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.
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 -------------------------------------------------------------------------*/
26 /* === helpers ====================================================== */
28 int default_compare (void *data1, void *data2)
30 return (data1 == data2);
33 /* === GraphEdge ==================================================== */
35 GraphEdge *newGEdge (GraphNode *src, GraphNode *dest, unsigned int weight) {
36 GraphEdge *edge = (GraphEdge *)Safe_calloc (1, sizeof (GraphEdge));
39 edge->weight = weight;
43 GraphEdge *deleteGEdge (GraphEdge *edge) {
45 // remove edge from list
46 if (edge->next) edge->next->prev = edge->prev;
47 if (edge->prev) edge->prev->next = edge->next;
49 if (edge->prev) head = edge->prev; else head = edge->next;
54 /* === GraphNode ==================================================== */
56 GraphNode *newGNode (void *data, hash_t hash) {
57 GraphNode *node = (GraphNode*)Safe_calloc (1, sizeof (GraphNode));
63 GraphNode * deleteGNode (GraphNode *node) {
66 if (!node) return NULL;
70 node->edge = deleteGEdge (node->edge);
73 // remove node from list
74 if (node->next) node->next->prev = node->prev;
75 if (node->prev) node->prev->next = node->next;
77 if (node->prev) head = node->prev; else head = node->next;
82 GraphEdge *addGEdge (GraphNode *from, GraphNode *to, unsigned int weight) {
83 GraphEdge *edge = getGEdge (from, to);
85 edge = newGEdge (from, to, weight);
86 // insert edge into list
87 if (from->edge) from->edge->prev = edge;
88 edge->next = from->edge;
91 edge->weight += weight;
93 assert (edge->src == from && edge->node == to);
97 void addGEdge2 (GraphNode *from, GraphNode *to, unsigned int weight, unsigned int weight_back) {
98 addGEdge (from, to, weight);
99 addGEdge (to, from, weight_back);
102 void remGEdge (GraphNode *from, GraphNode *to) {
103 GraphEdge *curr = from->edge;
104 while (curr && curr->node != to) curr = curr->next;
108 if (from->edge == curr)
109 from->edge = deleteGEdge (curr);
114 GraphEdge *getGEdge (GraphNode *from, GraphNode *to) {
115 GraphEdge *curr = from->edge;
116 while (curr && curr->node != to) {
117 assert (curr->src == from);
123 /* === Graph ======================================================== */
125 Graph *newGraph (Graph_compareData *compare) {
126 Graph *graph = (Graph*) Safe_calloc (1, sizeof (Graph));
127 graph->compare = compare;
128 if (!compare) graph->compare = default_compare;
133 void deleteGraph (Graph *graph) {
135 while (graph->node) {
136 graph->node = deleteGNode (graph->node);
142 GraphNode *addGNode (Graph *graph, void *data, hash_t hash) {
143 GraphNode *node = newGNode (data, hash);
144 if (graph->node) graph->node->prev = node;
145 node->next = graph->node;
150 void remGNode (Graph *graph, void *data, hash_t hash) {
151 GraphNode *curr = graph->node;
152 while (curr && ((curr->hash != hash) || (!graph->compare(curr->data, data)))) {
158 if (graph->node == curr)
159 graph->node = deleteGNode (curr);
164 GraphNode *getGNode (Graph *graph, void *data, hash_t hash) {
165 GraphNode *curr = graph->node;
166 while (curr && ((curr->hash != hash) || (!graph->compare(curr->data, data)))) {
173 GraphNode *getOrAddGNode (Graph *graph, void *data, hash_t hash) {
174 GraphNode *curr = getGNode (graph, data, hash);
176 curr = addGNode (graph, data, hash);
178 assert (curr != NULL);