socialchoicekit.flow module
- socialchoicekit.flow.capacity_across_cut(G: Dict[int, List[Tuple[int, int]]], cut: Set[int]) → int[source]
Computes the capacity across a cut in a flow network.
Parameters
- GDict[int, List[Tuple[int, int]]]
A flow network of the form {i: [(j, c), (k, c), …]} where i is the index of a vertex and [(j, c), (k, c), …] are the indices of the vertices that i is connected to along with the capacity of the edge.
- cutSet[int]
Set of vertices that form the source side of the cut.
Returns
- int
The total capacity across the cut.
- socialchoicekit.flow.convert_bipartite_graph_to_flow_network(G: Dict[int, List[int]], X: list, Y: list) → Dict[int, List[Tuple[int, int]]][source]
Converts a bipartite graph to a flow network by performing the following. - Add a source vertex s and a sink vertex t. In this implementation, s = -1, t = -2. - Add an edge from s to each vertex in X. - Add an edge from each vertex in Y to t. - For each edge in the unweighted graph, assign capacity 1 to each edge.
Must run utils.convert_bipartite_graph on G, X, Y before calling this function.
Parameters
- GDict[int, List[int]]
A bipartite graph of the form {i: [j, k, …]} where i is the index of a vertex and [j, k, …] are the indices of the vertices that i is connected to. The graph may be undirected (as in for every edges from x to y there is an edge from y to x) or directed. If it is directed, then the edges are assumed to be directed from X to Y.
- Xlist
The list of the left vertices (in the first partition) in the bipartite graph G.
- Ylist
The list of the right vertices (in the second partition) in the bipartite graph G.
Returns
- Dict[int, List[Tuple[int, int]]
A graph of the form {i: [(j, c), (k, c), …]} where i is the index of a vertex and [(j, c), (k, c), …] are the indices of the vertices that i is connected to along with the capacity of the edge.
- socialchoicekit.flow.dfs_path(G: Dict[int, List[Tuple[int, int]]], current: int, sink: int, visited: Dict[int, int]) → Tuple[List[int], int] | None[source]
Finds a path from the given vertex to the sink vertex.
Parameters
- GDict[int, List[Tuple[int, int]]]
A flow network of the form {i: [(j, c), (k, c), …]} where i is the index of a vertex and [(j, c), (k, c), …] are the indices of the vertices that i is connected to along with the capacity of the edge. The value of the capacities cannot exceed sys.maxsize.
- currentint
The index of the current vertex.
- sinkint
The index of the sink vertex.
- visitedDict[int, int]
A dictionary of the form {i: j} where i is the index of a vertex and j is 0 if i is not visited, 1 if i is visited.
Returns
- Tuple[List[int], int]
A tuple of the form (path, capacity) where path is a list of vertices in the path from the current vertex to the sink vertex and capacity is the capacity of the path.
- None
If there is no path from the current vertex to the sink vertex.
- socialchoicekit.flow.flow_across_network(flow: Dict[Tuple[int, int], int], s: int) → int[source]
Computes the flow across a network.
Parameters
- flowDict[Tuple[int, int], int]
A flow network with the maximum flow. The flow network is of the form {(i, j): f} where f is the flow from vertex i to vertex j. This flow network includes paths in the original graph where the flow is zero.
- sint
The index of the source vertex. The source vertex should not have any incoming flow.
Returns
- int
The flow across the network.
- socialchoicekit.flow.ford_fulkerson(G: Dict[int, List[Tuple[int, int]]], s: int, t: int) → Tuple[Dict[Tuple[int, int], int], Set[int]][source]
The Ford Fulkerson algorithm for computing the maximum flow and minimum cut in a flow network (with depth first search)
This implementation only works with integral capacities, and we use this to ensure that the algorithm terminates.
Parameters
- GDict[int, List[Tuple[int, int]]]
A flow network of the form {i: [(j, c), (k, c), …]} where i is the index of a vertex and [(j, c), (k, c), …] are the indices of the vertices that i is connected to along with the capacity of the edge. The value of the capacities cannot exceed sys.maxsize.
- sint
The index of the source vertex.
- tint
The index of the sink vertex.
Returns
- Tuple[Dict[Tuple[int, int], int], Set[int]]
For each component, see below.
- Dict[Tuple[int, int], int]
The flow network with the maximum flow. The flow network is of the form {(i, j): f} where f is the flow from vertex i to vertex j. This flow network includes paths in the original graph where the flow is zero.
- Set[int]
A subset of the nodes that are in the source side of the minimum cut.
- socialchoicekit.flow.maximum_cardinality_matching_bipartite(G: Dict[int, List[int]], X: list, Y: list) → List[Tuple[int, int]][source]
The maximum cardinality matching on a bipartite graph. This runs the Ford Fulkerson algorithm (with depth first search).
Parameters
- GDict[int, List[int]]
A dictionary of the form {i: [j, k, …]} where i is the index of a vertex and [j, k, …] are the indices of the vertices that i is connected to. This graph may be directed or undirected. If it is directed, then the edges are assumed to be directed from X to Y. This graph must be bipartite.
- Xlist
The list of the left vertices (in the first partition) in the bipartite graph G.
- Ylist
The list of the right vertices (in the second partition) in the bipartite graph G.
Returns
- List[Tuple[int, int]]
A list of tuples of the form (i, j) where i is a vertex in X and j is a vertex in Y. This represents the maximum cardinality matching.
- socialchoicekit.flow.reachable_vertices(G: Dict[int, List[Tuple[int, int]]], s: int) → Set[int][source]
Finds the vertices that are reachable from a given vertex in a flow residual network.
Parameters
- G_fDict[int, List[Tuple[int, int]]]
A flow residual network of the form {i: [(j, c), (k, c), …]} where i is the index of a vertex and [(j, c), (k, c), …] are the indices of the vertices that i is connected to along with the capacity of the edge.
- s: int
The index to check reachability from.
Returns
- Set[int]
A list of vertices that are reachable from the given vertex.