-
Notifications
You must be signed in to change notification settings - Fork 31
/
graph.inl
114 lines (94 loc) · 2.83 KB
/
graph.inl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/* graph.cpp */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "graph.h"
template <typename captype, typename tcaptype, typename flowtype>
Graph<captype, tcaptype, flowtype>::Graph(int node_num_max, int edge_num_max, void (*err_function)(const char *))
: node_num(0),
nodeptr_block(NULL),
error_function(err_function)
{
if (node_num_max < 16) node_num_max = 16;
if (edge_num_max < 16) edge_num_max = 16;
nodes = (node*) malloc(node_num_max*sizeof(node));
arcs = (arc*) malloc(2*edge_num_max*sizeof(arc));
if (!nodes || !arcs) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }
node_last = nodes;
node_max = nodes + node_num_max;
arc_last = arcs;
arc_max = arcs + 2*edge_num_max;
maxflow_iteration = 0;
flow = 0;
}
template <typename captype, typename tcaptype, typename flowtype>
Graph<captype,tcaptype,flowtype>::~Graph()
{
if (nodeptr_block)
{
delete nodeptr_block;
nodeptr_block = NULL;
}
free(nodes);
free(arcs);
}
template <typename captype, typename tcaptype, typename flowtype>
void Graph<captype,tcaptype,flowtype>::reset()
{
node_last = nodes;
arc_last = arcs;
node_num = 0;
if (nodeptr_block)
{
delete nodeptr_block;
nodeptr_block = NULL;
}
maxflow_iteration = 0;
flow = 0;
}
template <typename captype, typename tcaptype, typename flowtype>
void Graph<captype,tcaptype,flowtype>::reallocate_nodes(int num)
{
int node_num_max = (int)(node_max - nodes);
node* nodes_old = nodes;
node_num_max += node_num_max / 2;
if (node_num_max < node_num + num) node_num_max = node_num + num;
nodes = (node*) realloc(nodes_old, node_num_max*sizeof(node));
if (!nodes) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }
node_last = nodes + node_num;
node_max = nodes + node_num_max;
if (nodes != nodes_old)
{
arc* a;
for (a=arcs; a<arc_last; a++)
{
a->head = (node*) ((char*)a->head + (((char*) nodes) - ((char*) nodes_old)));
}
}
}
template <typename captype, typename tcaptype, typename flowtype>
void Graph<captype,tcaptype,flowtype>::reallocate_arcs()
{
int arc_num_max = (int)(arc_max - arcs);
int arc_num = (int)(arc_last - arcs);
arc* arcs_old = arcs;
arc_num_max += arc_num_max / 2; if (arc_num_max & 1) arc_num_max ++;
arcs = (arc*) realloc(arcs_old, arc_num_max*sizeof(arc));
if (!arcs) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }
arc_last = arcs + arc_num;
arc_max = arcs + arc_num_max;
if (arcs != arcs_old)
{
node* i;
arc* a;
for (i=nodes; i<node_last; i++)
{
if (i->first) i->first = (arc*) ((char*)i->first + (((char*) arcs) - ((char*) arcs_old)));
}
for (a=arcs; a<arc_last; a++)
{
if (a->next) a->next = (arc*) ((char*)a->next + (((char*) arcs) - ((char*) arcs_old)));
a->sister = (arc*) ((char*)a->sister + (((char*) arcs) - ((char*) arcs_old)));
}
}
}