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(n, graph, start)¶: Uses Dijkstra’s algortihm to find the shortest path between in a 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¶

pyrival.graphs.scc.scc(graph)¶: Finds what strongly connected components each node is a part of in a directed graph, it also finds a weak topological ordering of the nodes

pyrival.graphs.toposort¶

pyrival.graphs.toposort.kahn(graph)¶

pyrival.graphs.toposort.toposort(graph)¶