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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
/*
* Copyright (c) 2014 Cisco Systems, Inc. All rights reserved.
* Copyright (c) 2017 Amazon.com, Inc. or its affiliates. All Rights
* reserved.
* $COPYRIGHT$
*
* Additional copyrights may follow
*
* $HEADER$
*/
/*
* This file defines a number of internal structures to the BP graph
* code which need to be exposed only for unit testing. This file
* should not be included in code that uses the BP graph interface.
*/
#ifndef BIPARTITE_GRAPH_INTERNAL
#define BIPARTITE_GRAPH_INTERNAL 1
struct opal_bp_graph_edge_t {
opal_object_t super;
opal_list_item_t outbound_li;
opal_list_item_t inbound_li;
/** source of this edge */
int source;
/** v_index of target of this edge */
int target;
/** cost (weight) of this edge */
int64_t cost;
/**
* (flow-network) capacity of this edge. Zero-capacity edges essentially do
* not exist and will be ignored by most of the algorithms implemented here.
*/
int capacity;
/** any other information associated with this edge */
void *e_data;
};
struct opal_bp_graph_vertex_t {
/** index in the graph's array of vertices */
int v_index;
/** any other information associated with the vertex */
void *v_data;
/** linked list of edges for which this vertex is a source */
opal_list_t out_edges;
/** linked list of edges for which this vertex is a target */
opal_list_t in_edges;
};
struct opal_bp_graph_t {
/** number of vertices currently in this graph */
int num_vertices;
/** vertices in this graph (with number of set elements == num_vertices) */
opal_pointer_array_t vertices;
/** index of the source vertex, or -1 if not present */
int source_idx;
/** index of the sink vertex, or -1 if not present */
int sink_idx;
/** user callback to clean up the v_data */
opal_bp_graph_cleanup_fn_t v_data_cleanup_fn;
/** user callback to clean up the e_data */
opal_bp_graph_cleanup_fn_t e_data_cleanup_fn;
};
#define LIST_FOREACH_CONTAINED(item, list, type, member) \
for (item = container_of( (list)->opal_list_sentinel.opal_list_next, type, member ); \
&item->member != &(list)->opal_list_sentinel; \
item = container_of( \
((opal_list_item_t *) (&item->member))->opal_list_next, type, member ))
#define LIST_FOREACH_SAFE_CONTAINED(item, next, list, type, member) \
for (item = container_of( (list)->opal_list_sentinel.opal_list_next, type, member ), \
next = container_of( \
((opal_list_item_t *) (&item->member))->opal_list_next, type, member ); \
&item->member != &(list)->opal_list_sentinel; \
item = next, \
next = container_of( \
((opal_list_item_t *) (&item->member))->opal_list_next, type, member ))
#define NUM_VERTICES(g) (g->num_vertices)
#define CHECK_VERTEX_RANGE(g,v) \
do { \
if ((v) < 0 || \
(v) >= NUM_VERTICES(g)) { \
return OPAL_ERR_BAD_PARAM; \
} \
} while (0)
/* cast away any constness of &g->vertices b/c the opal_pointer_array API is
* not const-correct */
#define V_ID_TO_PTR(g, v_id) \
((opal_bp_graph_vertex_t *) \
opal_pointer_array_get_item((opal_pointer_array_t *)&g->vertices, v_id))
#define FOREACH_OUT_EDGE(g,v_id,e_ptr) \
LIST_FOREACH_CONTAINED(e_ptr, \
&(V_ID_TO_PTR(g, v_id)->out_edges), \
opal_bp_graph_edge_t, \
outbound_li)
#define FOREACH_IN_EDGE(g,v_id,e_ptr) \
LIST_FOREACH_CONTAINED(e_ptr, \
&(V_ID_TO_PTR(g, v_id)->in_edges), \
opal_bp_graph_edge_t, \
inbound_li)
/* Iterate over (u,v) edge pairs along the given path, where path is defined
* by the predecessor array "pred". Stops when a -1 predecessor is
* encountered. Note: because it is a *predecessor* array, the traversal
* starts at the sink and progresses towards the source. */
#define FOREACH_UV_ON_PATH(pred, source, sink, u, v) \
for (u = pred[sink], v = sink; u != -1; v = u, u = pred[u])
bool opal_bp_graph_bellman_ford(opal_bp_graph_t *gx,
int source,
int target,
int *pred);
int opal_bp_graph_bipartite_to_flow(opal_bp_graph_t *g);
#endif
|
