pyrival.graphs¶

pyrival.graphs.bellman_ford¶

pyrival.graphs.bellman_ford.bellman_ford(n, edges, start)¶

pyrival.graphs.bfs¶

pyrival.graphs.bfs.bfs(graph, start=0)¶

pyrival.graphs.bfs.layers(graph, start=0)¶

pyrival.graphs.components¶

pyrival.graphs.components.connected_components(n, graph)¶

pyrival.graphs.cycle_finding¶

pyrival.graphs.cycle_finding.cycle_finding(f, x0)¶

pyrival.graphs.dfs¶

pyrival.graphs.dfs.dfs(graph, start=0)¶

pyrival.graphs.dijkstra¶

pyrival.graphs.dijkstra.dijkstra(graph, start)¶: Uses Dijkstra’s algortihm to find the shortest path from node start to all other nodes in a directed weighted graph.

pyrival.graphs.dinic¶

class pyrival.graphs.dinic.Dinic(n)¶

Bases: object

add_edge(a, b, c, rcap=0)¶

calc(s, t)¶

dfs(v, t, f)¶

pyrival.graphs.euler_walk¶

pyrival.graphs.euler_walk.euler_walk(n, adj)¶

pyrival.graphs.find_path¶

pyrival.graphs.find_path.find_path(start, end, parents)¶: Constructs a path between two vertices, given the parents of all vertices.

pyrival.graphs.floyd_warshall¶

pyrival.graphs.floyd_warshall.floyd_warshall(n, edges)¶

pyrival.graphs.hopcroft_karp¶

Produces a maximum cardinality matching of a bipartite graph

Example:

0—0

1—1

/

/

/ 2 2

/

/

/

3

>>>> n = 4 >>>> m = 3 >>>> graph = [[0, 1], [1, 2], [1], [2]] >>>> match1, match2 = hopcroft_karp(graph, n, m) >>>> match1 [0, 1, -1, 2] >>>> match2 [0, 1, 3]

Meaning

0—0

1—1

2 2: /

/

/

3

pyrival.graphs.hopcroft_karp.hopcroft_karp(graph, n, m)¶: Maximum bipartite matching using Hopcroft-Karp algorithm, running in O(|E| sqrt(|V|))

pyrival.graphs.is_bipartite¶

pyrival.graphs.is_bipartite.is_bipartite(graph)¶

pyrival.graphs.kruskal¶

class pyrival.graphs.kruskal.UnionFind(n)¶

Bases: object

find(a)¶

merge(a, b)¶

pyrival.graphs.kruskal.kruskal(n, U, V, W)¶

pyrival.graphs.lca¶

class pyrival.graphs.lca.LCA(root, graph)¶: Bases: object

class pyrival.graphs.lca.RangeQuery(data, func=<built-in function min>)¶

Bases: object

query(begin, end)¶

pyrival.graphs.maximum_matching¶

pyrival.graphs.maximum_matching.maximum_matching(edges, mod=1073750017)¶

Returns the maximum cardinality matching of any simple graph (undirected, unweighted, no self-loops) Uses a randomized algorithm to compute the rank of the Tutte matrix The rank of the Tutte matrix is equal to twice the size of the maximum matching with high probability The probability for error is not more than n/mod

Complexity: O(n ^ 3) worst case, O(n * |matching_size|) on average

Parameters:	edges – a list of edges, assume nodes can be anything numbered from 0 to max number in edges mod – optional, a large random prime
Returns:	the maximum cardinality matching of the graph

pyrival.graphs.prim¶

pyrival.graphs.prim.prim(n, adj)¶

pyrival.graphs.scc¶

Given a directed graph, find_SCC returns a list of lists containing the strongly connected components in topological order.

Note that this implementation can be also be used to check if a directed graph is a DAG, and in that case it can be used to find the topological ordering of the nodes.

pyrival.graphs.scc.find_SCC(graph)¶

pyrival.graphs.toposort¶

pyrival.graphs.toposort.kahn(graph)¶

pyrival.graphs.toposort.toposort(graph)¶