CMR  1.3.0
graph.h
Go to the documentation of this file.
1 #ifndef CMR_GRAPH_H
2 #define CMR_GRAPH_H
3 
13 #include <cmr/env.h>
14 #include <cmr/element.h>
15 
16 #include <stdio.h>
17 
18 #ifdef __cplusplus
19 extern "C" {
20 #endif
21 
30 typedef int CMR_GRAPH_NODE;
31 typedef int CMR_GRAPH_EDGE;
32 typedef int CMR_GRAPH_ITER;
34 typedef struct
35 {
36  int prev;
37  int next;
38  int firstOut;
40 
41 typedef struct
42 {
43  int target;
44  int prev;
45  int next;
47 
48 typedef struct
49 {
50  size_t numNodes;
51  size_t memNodes;
53  int firstNode;
54  int freeNode;
56  size_t numEdges;
57  size_t memEdges;
59  int freeEdge;
60 } CMR_GRAPH;
61 
66 static inline
68  CMR_GRAPH* graph
69 )
70 {
71  assert(graph);
72 
73  return graph->memNodes;
74 }
75 
80 static inline
82  CMR_GRAPH* graph
83 )
84 {
85  assert(graph);
86 
87  return graph->numNodes;
88 }
89 
94 static inline
96  CMR_GRAPH* graph
97 )
98 {
99  assert(graph);
100 
101  return graph->memEdges;
102 }
103 
108 static inline
110  CMR_GRAPH* graph
111 )
112 {
113  assert(graph);
114 
115  return graph->numEdges;
116 }
117 
122 static inline
123 CMR_GRAPH_NODE CMRgraphEdgeU(
124  CMR_GRAPH* graph,
125  CMR_GRAPH_EDGE e
126 )
127 {
128  assert(graph);
129 
130  return graph->arcs[2*e+1].target;
131 }
132 
137 static inline
138 CMR_GRAPH_NODE CMRgraphEdgeV(
139  CMR_GRAPH* graph,
140  CMR_GRAPH_EDGE e
141 )
142 {
143  assert(graph);
144 
145  return graph->arcs[2*e].target;
146 }
147 
152 CMR_EXPORT
154  CMR* cmr,
155  CMR_GRAPH** pgraph,
156  int memNodes,
157  int memEdges
158 );
159 
164 CMR_EXPORT
166  CMR* cmr,
167  CMR_GRAPH** pgraph
168 );
169 
174 CMR_EXPORT
176  CMR* cmr,
177  CMR_GRAPH* graph
178 );
179 
188 CMR_EXPORT
190  CMR* cmr,
191  CMR_GRAPH* graph,
192  CMR_GRAPH_NODE* pnode
193 );
194 
203 CMR_EXPORT
205  CMR* cmr,
206  CMR_GRAPH* graph,
207  CMR_GRAPH_NODE u,
208  CMR_GRAPH_NODE v,
209  CMR_GRAPH_EDGE* pedge
210 );
211 
216 CMR_EXPORT
218  CMR* cmr,
219  CMR_GRAPH* graph,
220  CMR_GRAPH_NODE v
221 );
222 
227 CMR_EXPORT
229  CMR* cmr,
230  CMR_GRAPH* graph,
231  CMR_GRAPH_EDGE e
232 );
233 
238 static inline
239 CMR_GRAPH_NODE CMRgraphNodesFirst(
240  CMR_GRAPH* graph
241 )
242 {
243  assert(graph);
244 
245  return graph->firstNode;
246 }
247 
252 static inline
254  CMR_GRAPH* graph,
255  CMR_GRAPH_NODE v
256 )
257 {
258  assert(graph);
259 
260  return v >= 0;
261 }
262 
267 static inline
268 CMR_GRAPH_NODE CMRgraphNodesNext(
269  CMR_GRAPH* graph,
270  CMR_GRAPH_NODE v
271 )
272 {
273  assert(graph);
274 
275  return graph->nodes[v].next;
276 }
277 
282 static inline
283 CMR_GRAPH_ITER CMRgraphIncFirst(
284  CMR_GRAPH* graph,
285  CMR_GRAPH_NODE v
286 )
287 {
288  assert(graph);
289 
290  CMR_GRAPH_ITER i = graph->nodes[v].firstOut;
291  while (true)
292  {
293  if (i < 0)
294  return -1;
295  if ((graph->arcs[i].target != (graph)->arcs[i ^ 1].target) || !(i & 0x1))
296  return i;
297  i = graph->arcs[i].next;
298  }
299 }
300 
305 static inline
307  CMR_GRAPH* graph,
308  CMR_GRAPH_ITER i
309 )
310 {
311  assert(graph);
312 
313  return i >= 0;
314 }
315 
320 static inline
321 CMR_GRAPH_ITER CMRgraphIncNext(
322  CMR_GRAPH* graph,
323  CMR_GRAPH_ITER i
324 )
325 {
326  assert(graph);
327 
328  while (true)
329  {
330  i = graph->arcs[i].next;
331  if (i < 0)
332  return -1;
333  if (((graph)->arcs[i].target != (graph)->arcs[i ^ 1].target) || !(i & 0x1))
334  return i;
335  }
336 }
337 
342 static inline
343 CMR_GRAPH_EDGE CMRgraphIncEdge(
344  CMR_GRAPH* graph,
345  CMR_GRAPH_ITER i
346 )
347 {
348  assert(graph);
349 
350  return i/2;
351 }
352 
357 static inline
358 CMR_GRAPH_NODE CMRgraphIncSource(
359  CMR_GRAPH* graph,
360  CMR_GRAPH_ITER i
361 )
362 {
363  return graph->arcs[i^1].target;
364 }
365 
370 static inline
371 CMR_GRAPH_NODE CMRgraphIncTarget(
372  CMR_GRAPH* graph,
373  CMR_GRAPH_ITER i
374 )
375 {
376  return graph->arcs[i].target;
377 }
378 
383 static inline
384 CMR_GRAPH_ITER CMRgraphEdgesNext(
385  CMR_GRAPH* graph,
386  CMR_GRAPH_ITER i
387 )
388 {
389  CMR_GRAPH_NODE source = graph->arcs[i ^ 1].target;
390  CMR_GRAPH_ITER j = graph->arcs[i].next;
391  while (true)
392  {
393  while (j >= 0)
394  {
395  if (!(j & 0x1))
396  return j;
397  j = graph->arcs[j].next;
398  }
399  source = graph->nodes[source].next;
400  if (source < 0)
401  return -1;
402 
403  j = graph->nodes[source].firstOut;
404  }
405 }
406 
411 static inline
412 CMR_GRAPH_ITER CMRgraphEdgesFirst(
413  CMR_GRAPH* graph
414 )
415 {
416  assert(graph);
417 
418  for (CMR_GRAPH_NODE v = CMRgraphNodesFirst(graph); CMRgraphNodesValid(graph, v);
419  v = CMRgraphNodesNext(graph, v))
420  {
421  CMR_GRAPH_ITER i = graph->nodes[v].firstOut;
422  if (i >= 0)
423  {
424  /* We found some node with an incident edge. */
425  if (i & 0x1)
426  i = CMRgraphEdgesNext(graph, i);
427  return i;
428  }
429  }
430  return -1;
431 }
432 
437 static inline
439  CMR_GRAPH* graph,
440  CMR_GRAPH_ITER i
441 )
442 {
443  assert(graph);
444 
445  return i >= 0;
446 }
447 
452 static inline
453 CMR_GRAPH_EDGE CMRgraphEdgesEdge(
454  CMR_GRAPH* graph,
455  CMR_GRAPH_ITER i
456 )
457 {
458  assert(graph);
459 
460  return i/2;
461 }
462 
467 CMR_EXPORT
469  FILE* stream,
470  CMR_GRAPH* graph
471 );
472 
477 CMR_EXPORT
479  CMR* cmr,
480  CMR_GRAPH* graph,
481  CMR_GRAPH_NODE u,
482  CMR_GRAPH_NODE v
483 );
484 
485 
486 CMR_EXPORT
488  CMR* cmr,
489  CMR_GRAPH** pgraph,
490  CMR_ELEMENT** pedgeElements,
491  char*** pnodeLabels,
492  FILE* stream
493 );
494 
497 #ifdef __cplusplus
498 }
499 #endif
500 
501 #endif /* CMR_GRAPH_H */
CMR_EXPORT CMR_ERROR CMRgraphAddNode(CMR *cmr, CMR_GRAPH *graph, CMR_GRAPH_NODE *pnode)
Adds a node to a graph.
Definition: graph.c:175
int firstNode
Index of first node.
Definition: graph.h:53
Functionality for the row and column elements of a matrix.
int next
Previous arc in out-arc list of source node.
Definition: graph.h:45
Definition: graph.h:41
CMR_EXPORT CMR_ERROR CMRgraphMergeNodes(CMR *cmr, CMR_GRAPH *graph, CMR_GRAPH_NODE u, CMR_GRAPH_NODE v)
Merges two nodes u and v of graph.
Definition: graph.c:394
int freeEdge
Beginning of free-list of arc.
Definition: graph.h:59
size_t memEdges
Number of edges for which memory is allocated.
Definition: graph.h:57
static CMR_GRAPH_NODE CMRgraphNodesFirst(CMR_GRAPH *graph)
Returns a node iterator for iterating over all nodes.
Definition: graph.h:239
CMR_EXPORT CMR_ERROR CMRgraphCreateEmpty(CMR *cmr, CMR_GRAPH **pgraph, int memNodes, int memEdges)
Creates an empty graph.
Definition: graph.c:91
int CMR_GRAPH_EDGE
Reference to an edge of CMR_GRAPH.
Definition: graph.h:31
CMR_GRAPH_NODE_DATA * nodes
Array containing node data.
Definition: graph.h:52
static CMR_GRAPH_NODE CMRgraphEdgeV(CMR_GRAPH *graph, CMR_GRAPH_EDGE e)
Returns node v of edge e.
Definition: graph.h:138
static size_t CMRgraphMemNodes(CMR_GRAPH *graph)
Returns number of nodes for which memory is allocated.
Definition: graph.h:67
static size_t CMRgraphMemEdges(CMR_GRAPH *graph)
Returns number of edges for which memory is allocated.
Definition: graph.h:95
Basic functionality of the software library.
CMR_EXPORT CMR_ERROR CMRgraphDeleteNode(CMR *cmr, CMR_GRAPH *graph, CMR_GRAPH_NODE v)
Removes node v and all its incident edges from graph.
Definition: graph.c:286
CMR_ERROR
Type for return codes of library functions.
Definition: env.h:26
size_t numEdges
Number of edges.
Definition: graph.h:56
static bool CMRgraphEdgesValid(CMR_GRAPH *graph, CMR_GRAPH_ITER i)
Returns true if and only if iterator i for all edges is valid.
Definition: graph.h:438
int next
Previous node in node list.
Definition: graph.h:37
static CMR_GRAPH_NODE CMRgraphEdgeU(CMR_GRAPH *graph, CMR_GRAPH_EDGE e)
Returns node u of edge e.
Definition: graph.h:123
CMR_EXPORT CMR_ERROR CMRgraphDeleteEdge(CMR *cmr, CMR_GRAPH *graph, CMR_GRAPH_EDGE e)
Removes edge e from graph.
Definition: graph.c:323
Definition: env_internal.h:44
size_t memNodes
Number of nodes for which memory is allocated.
Definition: graph.h:51
static CMR_GRAPH_NODE CMRgraphIncTarget(CMR_GRAPH *graph, CMR_GRAPH_ITER i)
Returns the end node of the edge corresponding to this iterator i.
Definition: graph.h:371
static CMR_GRAPH_ITER CMRgraphIncFirst(CMR_GRAPH *graph, CMR_GRAPH_NODE v)
Returns an iterator for all edges incident to node v.
Definition: graph.h:283
CMR_GRAPH_ARC_DATA * arcs
Array containing arc data.
Definition: graph.h:58
int prev
Next arc in out-arc list of source node.
Definition: graph.h:44
int CMR_GRAPH_NODE
Reference to a node of CMR_GRAPH.
Definition: graph.h:30
CMR_EXPORT CMR_ERROR CMRgraphClear(CMR *cmr, CMR_GRAPH *graph)
Removes all nodes and columns, keeping the memory.
Definition: graph.c:151
static CMR_GRAPH_NODE CMRgraphIncSource(CMR_GRAPH *graph, CMR_GRAPH_ITER i)
Returns the node of which iterator i traverses through incident edges.
Definition: graph.h:358
static CMR_GRAPH_EDGE CMRgraphEdgesEdge(CMR_GRAPH *graph, CMR_GRAPH_ITER i)
Returns the actual edge, iterator i represents.
Definition: graph.h:453
int target
Target node of this arc.
Definition: graph.h:43
Definition: graph.h:34
CMR_EXPORT CMR_ERROR CMRgraphPrint(FILE *stream, CMR_GRAPH *graph)
Prints the graph, writing to stream.
Definition: graph.c:375
size_t numNodes
Number of nodes.
Definition: graph.h:50
static CMR_GRAPH_ITER CMRgraphEdgesFirst(CMR_GRAPH *graph)
Returns iterator for all edges of graph.
Definition: graph.h:412
int CMR_GRAPH_ITER
Reference to an edge iterator of CMR_GRAPH.
Definition: graph.h:32
CMR_EXPORT CMR_ERROR CMRgraphFree(CMR *cmr, CMR_GRAPH **pgraph)
Frees a graph.
Definition: graph.c:128
static size_t CMRgraphNumNodes(CMR_GRAPH *graph)
Returns number of nodes.
Definition: graph.h:81
static CMR_GRAPH_ITER CMRgraphIncNext(CMR_GRAPH *graph, CMR_GRAPH_ITER i)
Returns the iterator following iterator i for all edges incident to some node.
Definition: graph.h:321
int firstOut
First out-arc of this node.
Definition: graph.h:38
int prev
Next node in node list.
Definition: graph.h:36
static CMR_GRAPH_EDGE CMRgraphIncEdge(CMR_GRAPH *graph, CMR_GRAPH_ITER i)
Converts an iterator for edges incident to a node to the actual edge.
Definition: graph.h:343
static bool CMRgraphIncValid(CMR_GRAPH *graph, CMR_GRAPH_ITER i)
Returns true if iterator i for all incident edges of some node is valid.
Definition: graph.h:306
Definition: graph.h:48
static bool CMRgraphNodesValid(CMR_GRAPH *graph, CMR_GRAPH_NODE v)
Return true if and only if this v is not the last node in node iteration.
Definition: graph.h:253
static size_t CMRgraphNumEdges(CMR_GRAPH *graph)
Returns number of edges.
Definition: graph.h:109
static CMR_GRAPH_ITER CMRgraphEdgesNext(CMR_GRAPH *graph, CMR_GRAPH_ITER i)
Returns iterator of next edge in list of all edges.
Definition: graph.h:384
CMR_EXPORT CMR_ERROR CMRgraphCreateFromEdgeList(CMR *cmr, CMR_GRAPH **pgraph, CMR_ELEMENT **pedgeElements, char ***pnodeLabels, FILE *stream)
Definition: graph.c:424
int CMR_ELEMENT
Definition: element.h:20
CMR_EXPORT CMR_ERROR CMRgraphAddEdge(CMR *cmr, CMR_GRAPH *graph, CMR_GRAPH_NODE u, CMR_GRAPH_NODE v, CMR_GRAPH_EDGE *pedge)
Adds an edge to a graph.
Definition: graph.c:221
static CMR_GRAPH_NODE CMRgraphNodesNext(CMR_GRAPH *graph, CMR_GRAPH_NODE v)
Returns the next node after v.
Definition: graph.h:268
int freeNode
Beginning of free-list of nodes.
Definition: graph.h:54