1 /*
2 * Copyright (c) 2014 Cisco Systems, Inc. All rights reserved.
3 * Copyright (c) 2017 Amazon.com, Inc. or its affiliates. All Rights
4 * reserved.
5 * $COPYRIGHT$
6 *
7 * Additional copyrights may follow
8 *
9 * $HEADER$
10 */
11
12 /*
13 * This file defines a number of internal structures to the BP graph
14 * code which need to be exposed only for unit testing. This file
15 * should not be included in code that uses the BP graph interface.
16 */
17
18 #ifndef BIPARTITE_GRAPH_INTERNAL
19 #define BIPARTITE_GRAPH_INTERNAL 1
20
21 struct opal_bp_graph_edge_t {
22 opal_object_t super;
23
24 opal_list_item_t outbound_li;
25 opal_list_item_t inbound_li;
26
27 /** source of this edge */
28 int source;
29
30 /** v_index of target of this edge */
31 int target;
32
33 /** cost (weight) of this edge */
34 int64_t cost;
35
36 /**
37 * (flow-network) capacity of this edge. Zero-capacity edges essentially do
38 * not exist and will be ignored by most of the algorithms implemented here.
39 */
40 int capacity;
41
42 /** any other information associated with this edge */
43 void *e_data;
44 };
45
46 struct opal_bp_graph_vertex_t {
47 /** index in the graph's array of vertices */
48 int v_index;
49
50 /** any other information associated with the vertex */
51 void *v_data;
52
53 /** linked list of edges for which this vertex is a source */
54 opal_list_t out_edges;
55
56 /** linked list of edges for which this vertex is a target */
57 opal_list_t in_edges;
58 };
59
60 struct opal_bp_graph_t {
61 /** number of vertices currently in this graph */
62 int num_vertices;
63
64 /** vertices in this graph (with number of set elements == num_vertices) */
65 opal_pointer_array_t vertices;
66
67 /** index of the source vertex, or -1 if not present */
68 int source_idx;
69
70 /** index of the sink vertex, or -1 if not present */
71 int sink_idx;
72
73 /** user callback to clean up the v_data */
74 opal_bp_graph_cleanup_fn_t v_data_cleanup_fn;
75
76 /** user callback to clean up the e_data */
77 opal_bp_graph_cleanup_fn_t e_data_cleanup_fn;
78 };
79
80
81 #define LIST_FOREACH_CONTAINED(item, list, type, member) \
82 for (item = container_of( (list)->opal_list_sentinel.opal_list_next, type, member ); \
83 &item->member != &(list)->opal_list_sentinel; \
84 item = container_of( \
85 ((opal_list_item_t *) (&item->member))->opal_list_next, type, member ))
86
87 #define LIST_FOREACH_SAFE_CONTAINED(item, next, list, type, member) \
88 for (item = container_of( (list)->opal_list_sentinel.opal_list_next, type, member ), \
89 next = container_of( \
90 ((opal_list_item_t *) (&item->member))->opal_list_next, type, member ); \
91 &item->member != &(list)->opal_list_sentinel; \
92 item = next, \
93 next = container_of( \
94 ((opal_list_item_t *) (&item->member))->opal_list_next, type, member ))
95
96 #define NUM_VERTICES(g) (g->num_vertices)
97
98 #define CHECK_VERTEX_RANGE(g,v) \
99 do { \
100 if ((v) < 0 || \
101 (v) >= NUM_VERTICES(g)) { \
102 return OPAL_ERR_BAD_PARAM; \
103 } \
104 } while (0)
105
106 /* cast away any constness of &g->vertices b/c the opal_pointer_array API is
107 * not const-correct */
108 #define V_ID_TO_PTR(g, v_id) \
109 ((opal_bp_graph_vertex_t *) \
110 opal_pointer_array_get_item((opal_pointer_array_t *)&g->vertices, v_id))
111
112 #define FOREACH_OUT_EDGE(g,v_id,e_ptr) \
113 LIST_FOREACH_CONTAINED(e_ptr, \
114 &(V_ID_TO_PTR(g, v_id)->out_edges), \
115 opal_bp_graph_edge_t, \
116 outbound_li)
117
118 #define FOREACH_IN_EDGE(g,v_id,e_ptr) \
119 LIST_FOREACH_CONTAINED(e_ptr, \
120 &(V_ID_TO_PTR(g, v_id)->in_edges), \
121 opal_bp_graph_edge_t, \
122 inbound_li)
123
124
125 /* Iterate over (u,v) edge pairs along the given path, where path is defined
126 * by the predecessor array "pred". Stops when a -1 predecessor is
127 * encountered. Note: because it is a *predecessor* array, the traversal
128 * starts at the sink and progresses towards the source. */
129 #define FOREACH_UV_ON_PATH(pred, source, sink, u, v) \
130 for (u = pred[sink], v = sink; u != -1; v = u, u = pred[u])
131
132
133 bool opal_bp_graph_bellman_ford(opal_bp_graph_t *gx,
134 int source,
135 int target,
136 int *pred);
137
138 int opal_bp_graph_bipartite_to_flow(opal_bp_graph_t *g);
139
140 #endif