1 /*-------------------------------------------------------------------------
2
3 graph.c - implementation of general graphs
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: graph.c 9490 2016-01-31 11:44:32Z molnarkaroly $ */
23
24 #include "graph.h"
25
26 /* === helpers ====================================================== */
27
default_compare(void * data1,void * data2)28 int default_compare (void *data1, void *data2)
29 {
30 return (data1 == data2);
31 }
32
33 /* === GraphEdge ==================================================== */
34
newGEdge(GraphNode * src,GraphNode * dest,unsigned int weight)35 GraphEdge *newGEdge (GraphNode *src, GraphNode *dest, unsigned int weight) {
36 GraphEdge *edge = (GraphEdge *)Safe_alloc(sizeof(GraphEdge));
37 edge->src = src;
38 edge->node = dest;
39 edge->weight = weight;
40 return edge;
41 }
42
deleteGEdge(GraphEdge * edge)43 GraphEdge *deleteGEdge (GraphEdge *edge) {
44 GraphEdge *head;
45 // remove edge from list
46 if (edge->next) edge->next->prev = edge->prev;
47 if (edge->prev) edge->prev->next = edge->next;
48
49 if (edge->prev) head = edge->prev; else head = edge->next;
50 Safe_free (edge);
51 return head;
52 }
53
54 /* === GraphNode ==================================================== */
55
newGNode(void * data,hash_t hash)56 GraphNode *newGNode (void *data, hash_t hash) {
57 GraphNode *node = (GraphNode*)Safe_alloc(sizeof(GraphNode));
58 node->data = data;
59 node->hash = hash;
60 return node;
61 }
62
deleteGNode(GraphNode * node)63 GraphNode * deleteGNode (GraphNode *node) {
64 GraphNode *head;
65
66 if (!node) return NULL;
67
68 // delete all edges
69 while (node->edge) {
70 node->edge = deleteGEdge (node->edge);
71 } // while
72
73 // remove node from list
74 if (node->next) node->next->prev = node->prev;
75 if (node->prev) node->prev->next = node->next;
76
77 if (node->prev) head = node->prev; else head = node->next;
78 Safe_free (node);
79 return head;
80 }
81
addGEdge(GraphNode * from,GraphNode * to,unsigned int weight)82 GraphEdge *addGEdge (GraphNode *from, GraphNode *to, unsigned int weight) {
83 GraphEdge *edge = getGEdge (from, to);
84 if (edge == NULL) {
85 edge = newGEdge (from, to, weight);
86 // insert edge into list
87 if (from->edge) from->edge->prev = edge;
88 edge->next = from->edge;
89 from->edge = edge;
90 } else
91 edge->weight += weight;
92
93 assert (edge->src == from && edge->node == to);
94 return edge;
95 }
96
addGEdge2(GraphNode * from,GraphNode * to,unsigned int weight,unsigned int weight_back)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);
100 }
101
remGEdge(GraphNode * from,GraphNode * to)102 void remGEdge (GraphNode *from, GraphNode *to) {
103 GraphEdge *curr = from->edge;
104 while (curr && curr->node != to) curr = curr->next;
105
106 if (!curr) return;
107
108 if (from->edge == curr)
109 from->edge = deleteGEdge (curr);
110 else
111 deleteGEdge (curr);
112 }
113
getGEdge(GraphNode * from,GraphNode * to)114 GraphEdge *getGEdge (GraphNode *from, GraphNode *to) {
115 GraphEdge *curr = from->edge;
116 while (curr && curr->node != to) {
117 assert (curr->src == from);
118 curr = curr->next;
119 }
120 return curr;
121 }
122
123 /* === Graph ======================================================== */
124
newGraph(Graph_compareData * compare)125 Graph *newGraph (Graph_compareData *compare) {
126 Graph *graph = (Graph*)Safe_alloc(sizeof(Graph));
127 graph->compare = compare;
128 if (!compare) graph->compare = default_compare;
129
130 return graph;
131 }
132
deleteGraph(Graph * graph)133 void deleteGraph (Graph *graph) {
134 // remove all nodes
135 while (graph->node) {
136 graph->node = deleteGNode (graph->node);
137 } // while
138
139 Safe_free (graph);
140 }
141
addGNode(Graph * graph,void * data,hash_t hash)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;
146 graph->node = node;
147 return node;
148 }
149
remGNode(Graph * graph,void * data,hash_t hash)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)))) {
153 curr = curr->next;
154 } // while
155
156 if (!curr) return;
157
158 if (graph->node == curr)
159 graph->node = deleteGNode (curr);
160 else
161 deleteGNode (curr);
162 }
163
getGNode(Graph * graph,void * data,hash_t hash)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)))) {
167 curr = curr->next;
168 } // while
169
170 return curr;
171 }
172
getOrAddGNode(Graph * graph,void * data,hash_t hash)173 GraphNode *getOrAddGNode (Graph *graph, void *data, hash_t hash) {
174 GraphNode *curr = getGNode (graph, data, hash);
175 if (!curr)
176 curr = addGNode (graph, data, hash);
177
178 assert (curr != NULL);
179 return curr;
180 }
181