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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
/*
* Copyright (c) 2014-2022 Cisco Systems, Inc. All rights reserved
* Copyright (c) 2017-2019 Amazon.com, Inc. or its affiliates. All Rights
* reserved.
* $COPYRIGHT$
*
* Additional copyrights may follow
*
* $HEADER$
*/
/* Implements an adjacency-list-based weighted directed graph (digraph),
* focused on supporting bipartite digraphs and flow-network problems.
*
* Note that some operations might be more efficient if this structure were
* converted to use an adjacency matrix instead of an adjacency list. OTOH
* that complicates other pieces of the implementation (specifically, adding
* and removing edges). */
#ifndef OPAL_BP_GRAPH_H
#define OPAL_BP_GRAPH_H
struct opal_bp_graph_vertex_t;
struct opal_bp_graph_edge_t;
struct opal_bp_graph_t;
typedef struct opal_bp_graph_vertex_t opal_bp_graph_vertex_t;
typedef struct opal_bp_graph_edge_t opal_bp_graph_edge_t;
typedef struct opal_bp_graph_t opal_bp_graph_t;
/**
* callback function pointer type for cleaning up user data associated with a
* vertex or edge */
typedef void (*opal_bp_graph_cleanup_fn_t)(void *user_data);
/**
* create a new empty graph
*
* Any new vertices will have NULL user data associated.
*
* @param[in] v_data_cleanup_fn cleanup function to use for vertex user data
* @param[in] e_data_cleanup_fn cleanup function to use for edge user data
* @param[out] g_out the created graph
*
* @returns OPAL_SUCCESS or an OMPI error code
*/
int opal_bp_graph_create(opal_bp_graph_cleanup_fn_t v_data_cleanup_fn,
opal_bp_graph_cleanup_fn_t e_data_cleanup_fn, opal_bp_graph_t **g_out);
/**
* free the given graph
*
* Any user data associated with vertices or edges in the graph will have
* the given edge/vertex cleanup callback invoked in some arbitrary order.
*
* @returns OPAL_SUCCESS or an OMPI error code
*/
int opal_bp_graph_free(opal_bp_graph_t *g);
/**
* clone (deep copy) the given graph
*
* Note that copy_user_data==true is not currently supported (requires the
* addition of a copy callback for user data).
*
* @param[in] g the graph to clone
* @param[in] copy_user_data if true, copy vertex/edge user data to the new
* graph
* @param[in] g_clone_out the resulting cloned graph
* @returns OPAL_SUCCESS or an OMPI error code
*/
int opal_bp_graph_clone(const opal_bp_graph_t *g, bool copy_user_data,
opal_bp_graph_t **g_clone_out);
/**
* return the number of edges for which this vertex is a destination
*
* @param[in] g the graph to query
* @param[in] vertex the vertex id to query
* @returns the number of edges for which this vertex is a destination
*/
int opal_bp_graph_indegree(const opal_bp_graph_t *g, int vertex);
/**
* return the number of edges for which this vertex is a source
*
* @param[in] g the graph to query
* @param[in] vertex the vertex id to query
* @returns the number of edges for which this vertex is a source
*/
int opal_bp_graph_outdegree(const opal_bp_graph_t *g, int vertex);
/**
* add an edge to the given graph
*
* @param[in] from source vertex ID
* @param[in] to target vertex ID
* @param[in] cost cost value for this edge (lower is better)
* @param[in] capacity maximum flow transmissible on this edge
* @param[in] e_data caller data to associate with this edge, useful for
* debugging or minimizing state shared across components
*
* @returns OPAL_SUCCESS or an OMPI error code
*/
int opal_bp_graph_add_edge(opal_bp_graph_t *g, int from, int to, int64_t cost, int capacity,
void *e_data);
/**
* add a vertex to the given graph
*
* @param[in] g graph to manipulate
* @param[in] v_data data to associate with the new vertex
* @param[out] index_out integer index of the new vertex. May be NULL.
*
* @returns OPAL_SUCCESS or an OMPI error code
*/
int opal_bp_graph_add_vertex(opal_bp_graph_t *g, void *v_data, int *index_out);
/**
* Get a pointer to the vertex data given the graph and vertex index
* associated with the vertex.
*
* @param[in] g graph the vertex belongs to
* @param[in] v_index integer index of the vertex
* @param[out] v_data_out data associated with the new vertex, may be NULL.
*
* @returns OPAL_SUCCESS or an OMPI error code
*/
int opal_bp_graph_get_vertex_data(opal_bp_graph_t *g, int v_index, void **v_data_out);
/**
* compute the order of a graph (number of vertices)
*
* @param[in] g the graph to query
*/
int opal_bp_graph_order(const opal_bp_graph_t *g);
/**
* This function solves the "assignment problem":
* https://en.wikipedia.org/wiki/Assignment_problem
*
* The goal is to find a maximum cardinality, minimum cost matching in a
* weighted bipartite graph. Maximum cardinality takes priority over minimum
* cost.
*
* Capacities in the given graph are ignored (assumed to be 1 at the start).
* It is also assumed that the graph only contains edges from one vertex set
* to the other and that no edges exist in the reverse direction ("forward"
* edges only).
*
* The algorithm(s) used will be deterministic. That is, given the exact same
* graph, two calls to this routine will result in the same matching result.
*
* @param[in] g an acyclic bipartite directed graph for
* which a matching is sought
* @param[out] num_match_edges_out number edges found in the matching
* @param[out] match_edges_out an array of (u,v) vertex pairs indicating
* which edges are in the matching
*
* @returns OPAL_SUCCESS or an OMPI error code
*/
int opal_bp_graph_solve_bipartite_assignment(const opal_bp_graph_t *g, int *num_match_edges_out,
int **match_edges_out);
#endif /* OPAL_BP_GRAPH_H */
|
