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 /* Implements an adjacency-list-based weighted directed graph (digraph),
13 * focused on supporting bipartite digraphs and flow-network problems.
14 *
15 * Note that some operations might be more efficient if this structure were
16 * converted to use an adjacency matrix instead of an adjacency list. OTOH
17 * that complicates other pieces of the implementation (specifically, adding
18 * and removing edges). */
19
20 #ifndef OPAL_BP_GRAPH_H
21 #define OPAL_BP_GRAPH_H
22
23 struct opal_bp_graph_vertex_t;
24 struct opal_bp_graph_edge_t;
25 struct opal_bp_graph_t;
26
27 typedef struct opal_bp_graph_vertex_t opal_bp_graph_vertex_t;
28 typedef struct opal_bp_graph_edge_t opal_bp_graph_edge_t;
29 typedef struct opal_bp_graph_t opal_bp_graph_t;
30
31 /**
32 * callback function pointer type for cleaning up user data associated with a
33 * vertex or edge */
34 typedef void (*opal_bp_graph_cleanup_fn_t)(void *user_data);
35
36 /**
37 * create a new empty graph
38 *
39 * Any new vertices will have NULL user data associated.
40 *
41 * @param[in] v_data_cleanup_fn cleanup function to use for vertex user data
42 * @param[in] e_data_cleanup_fn cleanup function to use for edge user data
43 * @param[out] g_out the created graph
44 *
45 * @returns OPAL_SUCCESS or an OMPI error code
46 */
47 int opal_bp_graph_create(opal_bp_graph_cleanup_fn_t v_data_cleanup_fn,
48 opal_bp_graph_cleanup_fn_t e_data_cleanup_fn,
49 opal_bp_graph_t **g_out);
50
51 /**
52 * free the given graph
53 *
54 * Any user data associated with vertices or edges in the graph will have
55 * the given edge/vertex cleanup callback invoked in some arbitrary order.
56 *
57 * @returns OPAL_SUCCESS or an OMPI error code
58 */
59 int opal_bp_graph_free(opal_bp_graph_t *g);
60
61 /**
62 * clone (deep copy) the given graph
63 *
64 * Note that copy_user_data==true is not currently supported (requires the
65 * addition of a copy callback for user data).
66 *
67 * @param[in] g the graph to clone
68 * @param[in] copy_user_data if true, copy vertex/edge user data to the new
69 * graph
70 * @param[in] g_clone_out the resulting cloned graph
71 * @returns OPAL_SUCCESS or an OMPI error code
72 */
73 int opal_bp_graph_clone(const opal_bp_graph_t *g,
74 bool copy_user_data,
75 opal_bp_graph_t **g_clone_out);
76
77 /**
78 * return the number of edges for which this vertex is a destination
79 *
80 * @param[in] g the graph to query
81 * @param[in] vertex the vertex id to query
82 * @returns the number of edges for which this vertex is a destination
83 */
84 int opal_bp_graph_indegree(const opal_bp_graph_t *g,
85 int vertex);
86
87 /**
88 * return the number of edges for which this vertex is a source
89 *
90 * @param[in] g the graph to query
91 * @param[in] vertex the vertex id to query
92 * @returns the number of edges for which this vertex is a source
93 */
94 int opal_bp_graph_outdegree(const opal_bp_graph_t *g,
95 int vertex);
96
97 /**
98 * add an edge to the given graph
99 *
100 * @param[in] from source vertex ID
101 * @param[in] to target vertex ID
102 * @param[in] cost cost value for this edge (lower is better)
103 * @param[in] capacity maximum flow transmissible on this edge
104 * @param[in] e_data caller data to associate with this edge, useful for
105 * debugging or minimizing state shared across components
106 *
107 * @returns OPAL_SUCCESS or an OMPI error code
108 */
109 int opal_bp_graph_add_edge(opal_bp_graph_t *g,
110 int from,
111 int to,
112 int64_t cost,
113 int capacity,
114 void *e_data);
115
116 /**
117 * add a vertex to the given graph
118 *
119 * @param[in] g graph to manipulate
120 * @param[in] v_data data to associate with the new vertex
121 * @param[out] index_out integer index of the new vertex. May be NULL.
122 *
123 * @returns OPAL_SUCCESS or an OMPI error code
124 */
125 int opal_bp_graph_add_vertex(opal_bp_graph_t *g,
126 void *v_data,
127 int *index_out);
128
129 /**
130 * compute the order of a graph (number of vertices)
131 *
132 * @param[in] g the graph to query
133 */
134 int opal_bp_graph_order(const opal_bp_graph_t *g);
135
136 /**
137 * This function solves the "assignment problem":
138 * http://en.wikipedia.org/wiki/Assignment_problem
139 *
140 * The goal is to find a maximum cardinality, minimum cost matching in a
141 * weighted bipartite graph. Maximum cardinality takes priority over minimum
142 * cost.
143 *
144 * Capacities in the given graph are ignored (assumed to be 1 at the start).
145 * It is also assumed that the graph only contains edges from one vertex set
146 * to the other and that no edges exist in the reverse direction ("forward"
147 * edges only).
148 *
149 * The algorithm(s) used will be deterministic. That is, given the exact same
150 * graph, two calls to this routine will result in the same matching result.
151 *
152 * @param[in] g an acyclic bipartite directed graph for
153 * which a matching is sought
154 * @param[out] num_match_edges_out number edges found in the matching
155 * @param[out] match_edges_out an array of (u,v) vertex pairs indicating
156 * which edges are in the matching
157 *
158 * @returns OPAL_SUCCESS or an OMPI error code
159 */
160 int opal_bp_graph_solve_bipartite_assignment(const opal_bp_graph_t *g,
161 int *num_match_edges_out,
162 int **match_edges_out);
163
164 #endif /* OPAL_BP_GRAPH_H */