This source file includes following definitions.
- check_add64_overflow
- edge_constructor
- edge_destructor
- dump_vec
- dump_vec64
- dump_flow
- get_capacity
- set_capacity
- free_vertex
- opal_bp_graph_create
- opal_bp_graph_free
- opal_bp_graph_clone
- opal_bp_graph_indegree
- opal_bp_graph_outdegree
- opal_bp_graph_add_edge
- opal_bp_graph_add_vertex
- opal_bp_graph_order
- shrink_flow_matrix
- bottleneck_path
- opal_bp_graph_bellman_ford
- opal_bp_graph_bipartite_to_flow
- min_cost_flow_ssp
- opal_bp_graph_solve_bipartite_assignment
1
2
3
4
5
6
7
8
9
10
11
12 #include "opal_config.h"
13
14 #include <stdlib.h>
15 #include <stddef.h>
16
17 #include "opal_stdint.h"
18 #include "opal/constants.h"
19 #include "opal/class/opal_list.h"
20 #include "opal/class/opal_pointer_array.h"
21 #include "opal/util/output.h"
22 #include "opal/util/error.h"
23
24 #include "opal/util/bipartite_graph.h"
25 #include "opal/util/bipartite_graph_internal.h"
26
27 #ifndef container_of
28 #define container_of(ptr, type, member) ( \
29 (type *)( ((char *)(ptr)) - offsetof(type,member) ))
30 #endif
31
32 #define GRAPH_DEBUG 0
33 #if GRAPH_DEBUG
34 # define GRAPH_DEBUG_OUT(args) printf(args)
35 #else
36 # define GRAPH_DEBUG_OUT(args) do {} while(0)
37 #endif
38
39 #define MAX_COST INT64_MAX
40
41 #ifndef MAX
42 # define MAX(a,b) ((a) > (b) ? (a) : (b))
43 #endif
44
45 #ifndef MIN
46 # define MIN(a,b) ((a) < (b) ? (a) : (b))
47 #endif
48
49 #define f(i,j) flow[n*i + j]
50
51
52 static inline void check_add64_overflow(int64_t a, int64_t b)
53 {
54 assert(!((b > 0) && (a > (INT64_MAX - b))) &&
55 !((b < 0) && (a < (INT64_MIN - b))));
56 }
57
58 static void edge_constructor(opal_bp_graph_edge_t *e)
59 {
60 OBJ_CONSTRUCT(&e->outbound_li, opal_list_item_t);
61 OBJ_CONSTRUCT(&e->inbound_li, opal_list_item_t);
62 }
63
64 static void edge_destructor(opal_bp_graph_edge_t *e)
65 {
66 OBJ_DESTRUCT(&e->outbound_li);
67 OBJ_DESTRUCT(&e->inbound_li);
68 }
69
70 OBJ_CLASS_DECLARATION(opal_bp_graph_edge_t);
71 OBJ_CLASS_INSTANCE(opal_bp_graph_edge_t, opal_object_t,
72 edge_constructor, edge_destructor);
73
74 static void dump_vec(const char *name, int *vec, int n)
75 __opal_attribute_unused__;
76
77 static void dump_vec(const char *name, int *vec, int n)
78 {
79 int i;
80 fprintf(stderr, "%s={", name);
81 for (i = 0; i < n; ++i) {
82 fprintf(stderr, "[%d]=%2d, ", i, vec[i]);
83 }
84 fprintf(stderr, "}\n");
85 }
86
87 static void dump_vec64(const char *name, int64_t *vec, int n)
88 __opal_attribute_unused__;
89
90 static void dump_vec64(const char *name, int64_t *vec, int n)
91 {
92 int i;
93 fprintf(stderr, "%s={", name);
94 for (i = 0; i < n; ++i) {
95 fprintf(stderr, "[%d]=%2" PRIi64 ", ", i, vec[i]);
96 }
97 fprintf(stderr, "}\n");
98 }
99
100
101 static void dump_flow(int *flow, int n)
102 __opal_attribute_unused__;
103
104 static void dump_flow(int *flow, int n)
105 {
106 int u, v;
107
108 fprintf(stderr, "flow={\n");
109 for (u = 0; u < n; ++u) {
110 fprintf(stderr, "u=%d| ", u);
111 for (v = 0; v < n; ++v) {
112 fprintf(stderr, "%2d,", f(u,v));
113 }
114 fprintf(stderr, "\n");
115 }
116 fprintf(stderr, "}\n");
117 }
118
119
120 static int get_capacity(opal_bp_graph_t *g, int source, int target)
121 {
122 opal_bp_graph_edge_t *e;
123
124 CHECK_VERTEX_RANGE(g, source);
125 CHECK_VERTEX_RANGE(g, target);
126
127 FOREACH_OUT_EDGE(g, source, e) {
128 assert(e->source == source);
129 if (e->target == target) {
130 return e->capacity;
131 }
132 }
133
134 return 0;
135 }
136
137 static int
138 set_capacity(opal_bp_graph_t *g, int source, int target, int cap)
139 {
140 opal_bp_graph_edge_t *e;
141
142 CHECK_VERTEX_RANGE(g, source);
143 CHECK_VERTEX_RANGE(g, target);
144
145 FOREACH_OUT_EDGE(g, source, e) {
146 assert(e->source == source);
147 if (e->target == target) {
148 e->capacity = cap;
149 return OPAL_SUCCESS;
150 }
151 }
152
153 return OPAL_ERR_NOT_FOUND;
154 }
155
156 static void free_vertex(opal_bp_graph_t *g,
157 opal_bp_graph_vertex_t *v)
158 {
159 if (NULL != v) {
160 if (NULL != g->v_data_cleanup_fn && NULL != v->v_data) {
161 g->v_data_cleanup_fn(v->v_data);
162 }
163 free(v);
164 }
165 }
166
167 int opal_bp_graph_create(opal_bp_graph_cleanup_fn_t v_data_cleanup_fn,
168 opal_bp_graph_cleanup_fn_t e_data_cleanup_fn,
169 opal_bp_graph_t **g_out)
170 {
171 int err;
172 opal_bp_graph_t *g = NULL;
173
174 if (NULL == g_out) {
175 return OPAL_ERR_BAD_PARAM;
176 }
177 *g_out = NULL;
178
179 g = calloc(1, sizeof(*g));
180 if (NULL == g) {
181 OPAL_ERROR_LOG(OPAL_ERR_OUT_OF_RESOURCE);
182 err = OPAL_ERR_OUT_OF_RESOURCE;
183 goto out_free_g;
184 }
185
186 g->source_idx = -1;
187 g->sink_idx = -1;
188
189 g->v_data_cleanup_fn = v_data_cleanup_fn;
190 g->e_data_cleanup_fn = e_data_cleanup_fn;
191
192
193 OBJ_CONSTRUCT(&g->vertices, opal_pointer_array_t);
194 err = opal_pointer_array_init(&g->vertices, 0, INT_MAX, 32);
195 if (OPAL_SUCCESS != err) {
196 goto out_free_g;
197 }
198
199 *g_out = g;
200 return OPAL_SUCCESS;
201
202 out_free_g:
203 free(g);
204 return err;
205 }
206
207 int opal_bp_graph_free(opal_bp_graph_t *g)
208 {
209 int i;
210 opal_bp_graph_edge_t *e, *next;
211 opal_bp_graph_vertex_t *v;
212
213
214 for (i = 0; i < NUM_VERTICES(g); ++i) {
215 v = V_ID_TO_PTR(g, i);
216 LIST_FOREACH_SAFE_CONTAINED(e, next, &v->out_edges,
217 opal_bp_graph_edge_t, outbound_li) {
218 opal_list_remove_item(&v->out_edges, &e->outbound_li);
219 OBJ_RELEASE(e);
220 }
221 }
222
223 for (i = 0; i < NUM_VERTICES(g); ++i) {
224 v = V_ID_TO_PTR(g, i);
225 LIST_FOREACH_SAFE_CONTAINED(e, next, &v->in_edges,
226 opal_bp_graph_edge_t, inbound_li) {
227 opal_list_remove_item(&v->in_edges, &e->inbound_li);
228
229 if (NULL != g->e_data_cleanup_fn && NULL != e->e_data) {
230 g->e_data_cleanup_fn(e->e_data);
231 }
232 OBJ_RELEASE(e);
233 }
234
235 free_vertex(g, V_ID_TO_PTR(g, i));
236 opal_pointer_array_set_item(&g->vertices, i, NULL);
237 }
238 g->num_vertices = 0;
239
240 OBJ_DESTRUCT(&g->vertices);
241 free(g);
242
243 return OPAL_SUCCESS;
244 }
245
246 int opal_bp_graph_clone(const opal_bp_graph_t *g,
247 bool copy_user_data,
248 opal_bp_graph_t **g_clone_out)
249 {
250 int err;
251 int i;
252 int index;
253 opal_bp_graph_t *gx;
254 opal_bp_graph_edge_t *e;
255
256 if (NULL == g_clone_out) {
257 return OPAL_ERR_BAD_PARAM;
258 }
259 *g_clone_out = NULL;
260
261 if (copy_user_data) {
262 opal_output(0, "[%s:%d:%s] user data copy requested but not yet supported",
263 __FILE__, __LINE__, __func__);
264 abort();
265 return OPAL_ERR_FATAL;
266 }
267
268 gx = NULL;
269 err = opal_bp_graph_create(NULL, NULL, &gx);
270 if (OPAL_SUCCESS != err) {
271 return err;
272 }
273 assert(NULL != gx);
274
275
276 for (i = 0; i < NUM_VERTICES(g); ++i) {
277 err = opal_bp_graph_add_vertex(gx, NULL, &index);
278 if (OPAL_SUCCESS != err) {
279 goto out_free_gx;
280 }
281 assert(index == i);
282 }
283
284
285
286 for (i = 0; i < NUM_VERTICES(g); ++i) {
287 FOREACH_OUT_EDGE(g, i, e) {
288 assert(i == e->source);
289 err = opal_bp_graph_add_edge(gx, e->source, e->target,
290 e->cost, e->capacity, NULL);
291 if (OPAL_SUCCESS != err) {
292 goto out_free_gx;
293 }
294 }
295 }
296
297 *g_clone_out = gx;
298 return OPAL_SUCCESS;
299
300 out_free_gx:
301
302
303 opal_bp_graph_free(gx);
304 return err;
305 }
306
307 int opal_bp_graph_indegree(const opal_bp_graph_t *g,
308 int vertex)
309 {
310 opal_bp_graph_vertex_t *v;
311
312 v = V_ID_TO_PTR(g, vertex);
313 return opal_list_get_size(&v->in_edges);
314 }
315
316 int opal_bp_graph_outdegree(const opal_bp_graph_t *g,
317 int vertex)
318 {
319 opal_bp_graph_vertex_t *v;
320
321 v = V_ID_TO_PTR(g, vertex);
322 return opal_list_get_size(&v->out_edges);
323 }
324
325 int opal_bp_graph_add_edge(opal_bp_graph_t *g,
326 int from,
327 int to,
328 int64_t cost,
329 int capacity,
330 void *e_data)
331 {
332 opal_bp_graph_edge_t *e;
333 opal_bp_graph_vertex_t *v_from, *v_to;
334
335 if (from < 0 || from >= NUM_VERTICES(g)) {
336 return OPAL_ERR_BAD_PARAM;
337 }
338 if (to < 0 || to >= NUM_VERTICES(g)) {
339 return OPAL_ERR_BAD_PARAM;
340 }
341 if (cost == MAX_COST) {
342 return OPAL_ERR_BAD_PARAM;
343 }
344 if (capacity < 0) {
345
346
347 return OPAL_ERR_BAD_PARAM;
348 }
349 FOREACH_OUT_EDGE(g, from, e) {
350 assert(e->source == from);
351 if (e->target == to) {
352 return OPAL_EXISTS;
353 }
354 }
355
356
357 e = OBJ_NEW(opal_bp_graph_edge_t);
358 if (NULL == e) {
359 OPAL_ERROR_LOG(OPAL_ERR_OUT_OF_RESOURCE);
360 return OPAL_ERR_OUT_OF_RESOURCE;
361 }
362
363 e->source = from;
364 e->target = to;
365 e->cost = cost;
366 e->capacity = capacity;
367 e->e_data = e_data;
368
369 v_from = V_ID_TO_PTR(g, from);
370 opal_list_append(&v_from->out_edges, &e->outbound_li);
371
372 OBJ_RETAIN(e);
373 v_to = V_ID_TO_PTR(g, to);
374 opal_list_append(&v_to->in_edges, &e->inbound_li);
375
376 return OPAL_SUCCESS;
377 }
378
379 int opal_bp_graph_add_vertex(opal_bp_graph_t *g,
380 void *v_data,
381 int *index_out)
382 {
383 opal_bp_graph_vertex_t *v;
384
385 v = calloc(1, sizeof(*v));
386 if (NULL == v) {
387 OPAL_ERROR_LOG(OPAL_ERR_OUT_OF_RESOURCE);
388 return OPAL_ERR_OUT_OF_RESOURCE;
389 }
390
391
392
393 v->v_index = opal_pointer_array_add(&g->vertices, v);
394 if (-1 == v->v_index) {
395 free(v);
396 OPAL_ERROR_LOG(OPAL_ERR_OUT_OF_RESOURCE);
397 return OPAL_ERR_OUT_OF_RESOURCE;
398 }
399 assert(v->v_index == g->num_vertices);
400
401 ++g->num_vertices;
402
403 v->v_data = v_data;
404 OBJ_CONSTRUCT(&v->out_edges, opal_list_t);
405 OBJ_CONSTRUCT(&v->in_edges, opal_list_t);
406
407 if (NULL != index_out) {
408 *index_out = v->v_index;
409 }
410
411 return OPAL_SUCCESS;
412 }
413
414 int opal_bp_graph_order(const opal_bp_graph_t *g)
415 {
416 return NUM_VERTICES(g);
417 }
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439 static void shrink_flow_matrix(int *flow, int old_n, int new_n)
440 {
441 int u, v;
442
443 assert(old_n > new_n);
444
445 for (u = 0; u < new_n; ++u) {
446 for (v = 0; v < new_n; ++v) {
447 flow[new_n*u + v] = flow[old_n*u + v];
448 }
449 }
450 }
451
452
453
454
455
456 static int
457 bottleneck_path(
458 opal_bp_graph_t *gx,
459 int n,
460 int *pred)
461 {
462 int u, v;
463 int min;
464
465 min = INT_MAX;
466 FOREACH_UV_ON_PATH(pred, gx->source_idx, gx->sink_idx, u, v) {
467 int cap_f_uv = get_capacity(gx, u, v);
468 min = MIN(min, cap_f_uv);
469 }
470
471 return min;
472 }
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487 bool opal_bp_graph_bellman_ford(opal_bp_graph_t *gx,
488 int source,
489 int target,
490 int *pred)
491 {
492 int64_t *dist;
493 int i;
494 int n;
495 int u, v;
496 bool found_target = false;
497
498 if (NULL == gx) {
499 OPAL_ERROR_LOG(OPAL_ERR_BAD_PARAM);
500 return false;
501 }
502 if (NULL == pred) {
503 OPAL_ERROR_LOG(OPAL_ERR_BAD_PARAM);
504 return false;
505 }
506 if (source < 0 || source >= NUM_VERTICES(gx)) {
507 return OPAL_ERR_BAD_PARAM;
508 }
509 if (target < 0 || target >= NUM_VERTICES(gx)) {
510 return OPAL_ERR_BAD_PARAM;
511 }
512
513
514 n = opal_bp_graph_order(gx);
515 dist = malloc(n * sizeof(*dist));
516 if (NULL == dist) {
517 OPAL_ERROR_LOG(OPAL_ERR_OUT_OF_RESOURCE);
518 goto out;
519 }
520 for (i = 0; i < n; ++i) {
521 dist[i] = MAX_COST;
522 pred[i] = -1;
523 }
524 dist[source] = 0;
525
526
527 for (i = 1; i < NUM_VERTICES(gx); ++i) {
528 bool relaxed = false;
529 #if GRAPH_DEBUG
530 dump_vec("pred", pred, NUM_VERTICES(gx));
531 dump_vec64("dist", dist, NUM_VERTICES(gx));
532 #endif
533
534 for (u = 0; u < NUM_VERTICES(gx); ++u) {
535 opal_bp_graph_edge_t *e_ptr;
536
537 FOREACH_OUT_EDGE(gx, u, e_ptr) {
538 v = e_ptr->target;
539
540
541
542 if (e_ptr->capacity > 0 &&
543 dist[u] != MAX_COST) {
544 check_add64_overflow(dist[u], e_ptr->cost);
545 if ((dist[u] + e_ptr->cost) < dist[v]) {
546 dist[v] = dist[u] + e_ptr->cost;
547 pred[v] = u;
548 relaxed = true;
549 }
550 }
551 }
552 }
553
554
555 if (!relaxed) {
556 GRAPH_DEBUG_OUT(("relaxed==false, breaking out"));
557 break;
558 }
559 }
560
561
562 for (u = 0; u < NUM_VERTICES(gx); ++u) {
563 opal_bp_graph_edge_t * e_ptr;
564
565 FOREACH_OUT_EDGE(gx, u, e_ptr) {
566 v = e_ptr->target;
567 if (e_ptr->capacity > 0 &&
568 dist[u] != MAX_COST &&
569 (dist[u] + e_ptr->cost) < dist[v]) {
570 opal_output(0, "[%s:%d:%s] negative-weight cycle detected",
571 __FILE__, __LINE__, __func__);
572 abort();
573 goto out;
574 }
575 }
576 }
577
578 if (dist[target] != MAX_COST) {
579 found_target = true;
580 }
581
582 out:
583 #if GRAPH_DEBUG
584 dump_vec("pred", pred, NUM_VERTICES(gx));
585 #endif
586 assert(pred[source] == -1);
587 free(dist);
588 GRAPH_DEBUG_OUT(("bellman_ford: found_target=%s", found_target ? "true" : "false"));
589 return found_target;
590 }
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610 int opal_bp_graph_bipartite_to_flow(opal_bp_graph_t *g)
611 {
612 int err;
613 int order;
614 int u, v;
615 int num_left, num_right;
616
617
618 order = opal_bp_graph_order(g);
619
620 err = opal_bp_graph_add_vertex(g, NULL, &g->source_idx);
621 if (OPAL_SUCCESS != err) {
622 return err;
623 }
624 err = opal_bp_graph_add_vertex(g, NULL, &g->sink_idx);
625 if (OPAL_SUCCESS != err) {
626 return err;
627 }
628
629
630
631
632
633
634
635
636 num_left = 0;
637 num_right = 0;
638 for (u = 0; u < order; ++u) {
639 int inbound = opal_bp_graph_indegree(g, u);
640 int outbound = opal_bp_graph_outdegree(g, u);
641
642 if (inbound > 0 && outbound > 0) {
643 opal_output(0, "[%s:%d:%s] graph is not (unidirectionally) bipartite",
644 __FILE__, __LINE__, __func__);
645 abort();
646 }
647 else if (inbound > 0) {
648
649 ++num_right;
650 err = opal_bp_graph_add_edge(g, u, g->sink_idx,
651 0,
652 1,
653 NULL);
654 if (OPAL_SUCCESS != err) {
655 GRAPH_DEBUG_OUT(("add_edge failed"));
656 return err;
657 }
658 }
659 else if (outbound > 0) {
660
661 ++num_left;
662 err = opal_bp_graph_add_edge(g, g->source_idx, u,
663 0,
664 1,
665 NULL);
666 if (OPAL_SUCCESS != err) {
667 GRAPH_DEBUG_OUT(("add_edge failed"));
668 return err;
669 }
670 }
671 }
672
673
674
675 if (num_right == 0 || num_left == 0) {
676 return OPAL_ERR_BAD_PARAM;
677 }
678
679
680
681
682
683
684 order = opal_bp_graph_order(g);
685
686 for (u = 0; u < order; ++u) {
687 opal_bp_graph_edge_t * e_ptr;
688 FOREACH_OUT_EDGE(g, u, e_ptr) {
689 v = e_ptr->target;
690
691
692
693
694 err = opal_bp_graph_add_edge(g, v, u,
695 -e_ptr->cost,
696 0,
697 NULL);
698 if (OPAL_SUCCESS != err && OPAL_EXISTS != err) {
699 return err;
700 }
701 }
702 }
703
704 return OPAL_SUCCESS;
705 }
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748 static int min_cost_flow_ssp(opal_bp_graph_t *gx,
749 int **flow_out)
750 {
751 int err = OPAL_SUCCESS;
752 int n;
753 int *pred = NULL;
754 int *flow = NULL;
755 int u, v;
756 int c;
757
758 GRAPH_DEBUG_OUT(("begin min_cost_flow_ssp()"));
759
760 if (NULL == flow_out) {
761 return OPAL_ERR_BAD_PARAM;
762 }
763 *flow_out = NULL;
764
765 n = opal_bp_graph_order(gx);
766
767 pred = malloc(n*sizeof(*pred));
768 if (NULL == pred) {
769 OPAL_ERROR_LOG(OPAL_ERR_OUT_OF_RESOURCE);
770 err = OPAL_ERR_OUT_OF_RESOURCE;
771 goto out_error;
772 }
773
774
775 flow = calloc(n*n, sizeof(*flow));
776 if (NULL == flow) {
777 OPAL_ERROR_LOG(OPAL_ERR_OUT_OF_RESOURCE);
778 err = OPAL_ERR_OUT_OF_RESOURCE;
779 goto out_error;
780 }
781
782
783 while (opal_bp_graph_bellman_ford(gx, gx->source_idx, gx->sink_idx, pred)) {
784 int cap_f_path;
785
786
787 GRAPH_DEBUG_OUT(("start outer iteration of SSP algorithm"));
788 #if GRAPH_DEBUG
789 dump_vec("pred", pred, NUM_VERTICES(gx));
790 dump_flow(flow, n);
791 #endif
792
793 cap_f_path = bottleneck_path(gx, n, pred);
794
795
796 FOREACH_UV_ON_PATH(pred, gx->source_idx, gx->sink_idx, u, v) {
797 assert(u == pred[v]);
798
799 f(u,v) = f(u,v) + cap_f_path;
800 f(v,u) = f(v,u) - cap_f_path;
801
802 assert(f(u,v) == -f(v,u));
803
804
805
806 c = get_capacity(gx, u, v) - cap_f_path;
807 assert(c >= 0);
808 err = set_capacity(gx, u, v, c);
809 if (OPAL_SUCCESS != err) {
810 opal_output(0, "[%s:%d:%s] unable to set capacity, missing edge?",
811 __FILE__, __LINE__, __func__);
812 abort();
813 }
814
815 c = get_capacity(gx, v, u) + cap_f_path;
816 assert(c >= 0);
817 err = set_capacity(gx, v, u, c);
818 if (OPAL_SUCCESS != err) {
819 opal_output(0, "[%s:%d:%s] unable to set capacity, missing edge?",
820 __FILE__, __LINE__, __func__);
821 abort();
822 }
823 }
824 }
825
826 out:
827 *flow_out = flow;
828 free(pred);
829 return err;
830
831 out_error:
832 free(*flow_out);
833 GRAPH_DEBUG_OUT(("returning error %d", err));
834 goto out;
835 }
836
837 int opal_bp_graph_solve_bipartite_assignment(const opal_bp_graph_t *g,
838 int *num_match_edges_out,
839 int **match_edges_out)
840 {
841 int err;
842 int i;
843 int u, v;
844 int n;
845 int *flow = NULL;
846 opal_bp_graph_t *gx = NULL;
847
848 if (NULL == match_edges_out || NULL == num_match_edges_out) {
849 return OPAL_ERR_BAD_PARAM;
850 }
851 *num_match_edges_out = 0;
852 *match_edges_out = NULL;
853
854
855 err = opal_bp_graph_clone(g, false, &gx);
856 if (OPAL_SUCCESS != err) {
857 GRAPH_DEBUG_OUT(("opal_bp_graph_clone failed"));
858 goto out;
859 }
860
861
862
863
864
865
866
867
868
869
870
871
872
873 err = opal_bp_graph_bipartite_to_flow(gx);
874 if (OPAL_SUCCESS != err) {
875 GRAPH_DEBUG_OUT(("bipartite_to_flow failed"));
876 OPAL_ERROR_LOG(err);
877 return err;
878 }
879
880
881
882
883
884
885
886 err = min_cost_flow_ssp(gx, &flow);
887 if (OPAL_SUCCESS != err) {
888 GRAPH_DEBUG_OUT(("min_cost_flow_ssp failed"));
889 return err;
890 }
891 assert(NULL != flow);
892
893
894 n = opal_bp_graph_order(g);
895
896 #if GRAPH_DEBUG
897 dump_flow(flow, NUM_VERTICES(gx));
898 #endif
899 shrink_flow_matrix(flow, opal_bp_graph_order(gx), n);
900 #if GRAPH_DEBUG
901 dump_flow(flow, n);
902 #endif
903
904 for (u = 0; u < n; ++u) {
905 for (v = 0; v < n; ++v) {
906 if (f(u,v) > 0) {
907 ++(*num_match_edges_out);
908 }
909 }
910 }
911
912 if (0 == *num_match_edges_out) {
913
914 goto out;
915 }
916
917 *match_edges_out = malloc(*num_match_edges_out * 2 * sizeof(int));
918 if (NULL == *match_edges_out) {
919 *num_match_edges_out = 0;
920 OPAL_ERROR_LOG(OPAL_ERR_OUT_OF_RESOURCE);
921 err = OPAL_ERR_OUT_OF_RESOURCE;
922 goto out;
923 }
924
925 i = 0;
926 for (u = 0; u < n; ++u) {
927 for (v = 0; v < n; ++v) {
928
929 if (f(u,v) > 0) {
930 (*match_edges_out)[i++] = u;
931 (*match_edges_out)[i++] = v;
932 }
933 }
934 }
935
936 out:
937 free(flow);
938 opal_bp_graph_free(gx);
939 return err;
940 }