19 #include <grass/gis.h>
20 #include <grass/Vect.h>
21 #include <grass/glocale.h>
22 #include <grass/dgl/graph.h>
23 #include <grass/neta.h>
48 struct ilist *sink_list,
int *flow)
50 int nnodes, nlines, i;
54 char *is_source, *is_sink;
55 int begin, end, total_flow;
61 is_source = (
char *)G_calloc(nnodes + 3,
sizeof(
char));
62 is_sink = (
char *)G_calloc(nnodes + 3,
sizeof(
char));
63 if (!queue || !prev || !is_source || !is_sink) {
68 for (i = 0; i < source_list->n_values; i++)
69 is_source[source_list->value[i]] = 1;
70 for (i = 0; i < sink_list->n_values; i++)
71 is_sink[sink_list->value[i]] = 1;
73 for (i = 0; i <= nlines; i++)
82 for (i = 0; i < source_list->n_values; i++)
83 queue[end++] = source_list->value[i];
85 for (i = 1; i <= nnodes; i++) {
88 while (begin != end && found == -1) {
100 if (!is_source[to] && prev[to] ==
NULL &&
101 cap >
sign(
id) * flow[abs(
id)]) {
119 prev[node]) -
sign(edge_id) * flow[abs(edge_id)];
120 while (!is_source[node]) {
127 sign(edge_id) * flow[abs(edge_id)];
128 if (residue < min_residue)
129 min_residue = residue;
132 total_flow += min_residue;
135 while (!is_source[node]) {
137 flow[abs(edge_id)] +=
sign(edge_id) * min_residue;
166 struct ilist *sink_list,
int *flow,
struct ilist *cut)
172 int begin, end, total_flow;
176 visited = (
char *)G_calloc(nnodes + 3,
sizeof(
char));
177 if (!queue || !visited) {
182 total_flow = begin = end = 0;
184 for (i = 1; i <= nnodes; i++)
187 for (i = 0; i < source_list->n_values; i++) {
188 queue[end++] = source_list->value[i];
189 visited[source_list->value[i]] = 1;
193 while (begin != end) {
205 if (!visited[to] && cap >
sign(
id) * flow[abs(
id)]) {
214 for (i = 1; i <= nnodes; i++) {
228 if (!visited[to] && flow[edge_id] != 0) {
230 total_flow += abs(flow[abs(edge_id)]);
261 { 360000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
281 cost = node_costs[v];
282 if (cost > max_node_cost)
283 max_node_cost = cost;
284 dglAddEdge(out, 2 * v - 1, 2 * v, cost, edge_cnt);
302 dglAddEdge(out, 2 * v, 2 * to - 1, max_node_cost + 1, edge_cnt);