mathematicskit.graph_theory#

mathematicskit.graph_theory hub · History · Examples · API reference

A lightweight own graph container (no networkx dependency); shortest-path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall) via scipy.sparse.csgraph; minimum spanning tree (Kruskal via scipy, Prim hand-rolled for comparison); maximum flow/minimum cut via scipy.sparse.csgraph.maximum_flow; graph coloring (greedy and exact backtracking, hand-rolled – NP-complete, no scipy equivalent); and spectral graph theory (Laplacian via scipy, eigendecomposition via numpy.linalg.eigh).

mathematicskit.graph_theory: graph algorithms on a lightweight own graph container.

A minimal Graph container (adjacency list, no networkx dependency) supports: shortest-path algorithms (scipy.sparse.csgraph.dijkstra/bellman_ford/floyd_warshall); minimum spanning tree (scipy.sparse.csgraph.minimum_spanning_tree, Kruskal-based, alongside a hand-rolled Prim’s implementation kept for comparison); maximum flow / minimum cut (scipy.sparse.csgraph.maximum_flow); graph coloring (greedy heuristic and exact backtracking, hand-rolled – NP-complete in general, no scipy equivalent); and spectral graph theory (graph Laplacian via scipy.sparse.csgraph.laplacian, algebraic connectivity and spectral bipartition via numpy.linalg.eigh); Kirchhoff’s spanning-tree count; Hamiltonian cycles by backtracking; bipartite matching (Hopcroft-Karp via scipy) with König vertex covers; Turán graphs and clique numbers; the assignment problem (scipy.optimize.linear_sum_assignment); connected components and the Erdős-Rényi giant component; A* search; and PageRank.

class mathematicskit.graph_theory.AssignmentResult(rows, cols, total_cost)[source]#

Bases: object

Container for a solved assignment problem.

Parameters:

rows (ndarray)
cols (ndarray)
total_cost (float)

cols: ndarray#

Row rows[k] is assigned to column cols[k].

Type:: ndarray, int

rows: ndarray#

total_cost: float#

class mathematicskit.graph_theory.BipartiteMatchingResult(pairs, vertex_cover=<factory>)[source]#

Bases: object

Container for a maximum matching in a bipartite graph.

Parameters:

pairs (dict)
vertex_cover (list)

pairs: dict#

{left_vertex: right_vertex} for every matched left vertex.

Type:: dict

property size: int#

Number of matched pairs.

Type:: int

vertex_cover: list#

A minimum vertex cover, of the same size as the matching (König’s theorem).

Type:: list of int

class mathematicskit.graph_theory.ColoringResult(coloring, num_colors, method='')[source]#

Bases: object

Container for a graph-coloring result.

Parameters:

coloring (dict)
num_colors (int)
method (str)

coloring: dict#

{vertex: color_index}, with colors numbered from 0.

Type:: dict

method: str = ''#

"greedy" or "backtracking".

Type:: str

num_colors: int#

Number of distinct colors used. This is the graph’s chromatic number for method="backtracking", but only an upper bound on it for the "greedy" heuristic.

Type:: int

class mathematicskit.graph_theory.ComponentsResult(n_components, labels, sizes)[source]#

Bases: object

Container for the connected components of a graph.

Parameters:

n_components (int)
labels (ndarray)
sizes (ndarray)

labels: ndarray#

Component label of each vertex.

Type:: ndarray, int

n_components: int#

sizes: ndarray#

Component sizes, largest first.

Type:: ndarray, int

class mathematicskit.graph_theory.Graph(n_vertices, directed=False)[source]#

Bases: object

A lightweight directed or undirected weighted graph.

Vertices are the integers 0, ..., n_vertices - 1. Stored as an adjacency dict of dicts (self._adj[u][v] = weight); edges with no explicit weight default to 1.0. Deliberately has no algorithms of its own beyond construction/conversion – every algorithm lives in systems/, most calling to_sparse() to hand a scipy.sparse.csr_matrix to scipy.sparse.csgraph.

Parameters:

n_vertices (int)
directed (bool)

Examples

>>> g = Graph(3)
>>> g.add_edge(0, 1, weight=2.0)
>>> g.add_edge(1, 2, weight=3.0)
>>> g.to_sparse().toarray()
array([[0., 2., 0.],
       [2., 0., 3.],
       [0., 3., 0.]])

add_edge(u, v, weight=1.0)[source]#

Add an edge (or update its weight if it already exists).

Parameters:

u (int)
v (int)
weight (float)

Return type:

None

edges()[source]#

list of (int, int, float): Every edge as (u, v, weight).

For an undirected graph, each edge is listed once (u < v).

Return type:: list

neighbors(u)[source]#

dict: {neighbor: weight} for vertex u.

Return type:: dict
Parameters:: u (int)

to_sparse()[source]#

Build a scipy.sparse.csr_matrix adjacency/weight matrix.

Returns:: scipy.sparse.csr_matrix, shape (n_vertices, n_vertices)

class mathematicskit.graph_theory.MSTResult(edges, total_weight, method='')[source]#

Bases: object

Container for a minimum-spanning-tree/-forest computation.

Parameters:

edges (list)
total_weight (float)
method (str)

edges: list#

The MST’s edges as (u, v, weight).

Type:: list of (int, int, float)

method: str = ''#

e.g. "kruskal" (via scipy) or "prim" (hand-rolled).

Type:: str

total_weight: float#

Sum of the tree’s edge weights – the quantity an MST minimizes, and therefore identical across any correct MST algorithm, even when the trees themselves differ (as they can when weights tie).

Type:: float

class mathematicskit.graph_theory.MaxFlowResult(flow_value, flow_matrix, min_cut=None)[source]#

Bases: object

Container for a maximum-flow computation.

Parameters:

flow_value (float)
flow_matrix (ndarray)
min_cut (tuple | None)

flow_matrix: ndarray#

Flow assigned to each edge.

Type:: ndarray, shape (n, n)

flow_value: float#

The maximum flow from source to sink – equal, by the max-flow min-cut theorem, to the total capacity crossing min_cut.

Type:: float

min_cut: tuple | None = None#

(source_side, sink_side) vertex partitions defining the corresponding minimum cut.

Type:: tuple of (ndarray, ndarray), optional

class mathematicskit.graph_theory.PageRankResult(scores, iterations)[source]#

Bases: object

Container for a PageRank computation.

Parameters:

scores (ndarray)
iterations (int)

iterations: int#

scores: ndarray#

PageRank of each vertex; sums to 1.

Type:: ndarray

class mathematicskit.graph_theory.SearchResult(path, distance, n_expanded)[source]#

Bases: object

Container for a single-pair shortest-path search.

Parameters:

path (list)
distance (float)
n_expanded (int)

distance: float#

n_expanded: int#

Number of vertices removed from the priority queue.

Type:: int

path: list#

Vertices from source to target (empty if unreachable).

Type:: list of int

class mathematicskit.graph_theory.ShortestPathResult(distances, predecessors, method='')[source]#

Bases: object

Container for a shortest-path computation.

Parameters:

distances (ndarray)
predecessors (ndarray)
method (str)

distances: ndarray#

Shortest-path distance(s); shape (n,) for a single source, or (n_sources, n) for multiple sources.

Type:: ndarray

method: str = ''#

e.g. "dijkstra", "bellman_ford", "floyd_warshall".

Type:: str

predecessors: ndarray#

Predecessor-tree indices (-9999 for unreachable/root, following scipy.sparse.csgraph’s convention).

Type:: ndarray, int

class mathematicskit.graph_theory.SpectralResult(laplacian, eigenvalues, eigenvectors, algebraic_connectivity, bipartition=<factory>)[source]#

Bases: object

Container for a spectral graph-theory computation.

Parameters:

laplacian (ndarray)
eigenvalues (ndarray)
eigenvectors (ndarray)
algebraic_connectivity (float)
bipartition (ndarray)

algebraic_connectivity: float#

The second-smallest Laplacian eigenvalue (Fiedler value); zero iff the graph is disconnected.

Type:: float

bipartition: ndarray#

Spectral bipartition from the Fiedler vector’s sign (True/False per vertex).

Type:: ndarray, bool

eigenvalues: ndarray#

Laplacian eigenvalues, ascending. The smallest is always 0 (the all-ones eigenvector).

Type:: ndarray, shape (n,)

eigenvectors: ndarray#

Orthonormal eigenvectors as columns, in the same order as eigenvalues; column 1 is the Fiedler vector.

Type:: ndarray, shape (n, n)

laplacian: ndarray#

The combinatorial Laplacian \(L = D - A\), degree matrix minus adjacency.

Type:: ndarray, shape (n, n)

mathematicskit.graph_theory.astar_shortest_path(graph, source, target, heuristic=None)[source]#

Shortest path from source to target, expanding vertices in order of \(g(v) + h(v)\).

\(g\) is the best known distance from the source and \(h\) an estimate of the remaining distance. If \(h\) never overestimates (it is admissible) and is consistent, the first time the target is expanded its distance is optimal. With \(h = 0\) the search is Dijkstra’s algorithm.

Parameters:

graph (Graph) – Non-negative edge weights.
source (int)
target (int)
heuristic (Callable[[int], float] | None) – heuristic(v) estimates the distance from v to target; defaults to 0.

Return type:

SearchResult

Returns:

SearchResult

Examples

>>> from mathematicskit.graph_theory.utils.generators import grid_graph
>>> g, pos = grid_graph(5, 5)
>>> manhattan = lambda v: abs(pos[v] - pos[24]).sum()
>>> result = astar_shortest_path(g, 0, 24, manhattan)
>>> result.distance, len(result.path)
(8.0, 9)

mathematicskit.graph_theory.backtracking_coloring(graph, max_colors=None)[source]#

Exact minimum graph coloring via backtracking search.

Tries increasing values of k (number of colors) and searches exhaustively (with pruning: a vertex is only assigned a color not already used by an adjacent, already-colored vertex) for a valid k-coloring, stopping at the first k that succeeds – so the result is the graph’s true chromatic number, at exponential worst-case cost. Feasible only for small graphs. See Cormen et al., Introduction to Algorithms, 3rd ed., Ch. 34.5.1 (as an example NP-complete decision problem, 3-colorability).

Parameters:

graph (Graph)
max_colors (int | None) – Upper bound on colors tried; defaults to graph.n_vertices (always sufficient, one color per vertex).

Return type:

ColoringResult

Returns:

ColoringResult

Examples

>>> from mathematicskit.graph_theory.core.base import Graph
>>> # A complete graph on 4 vertices (K4) needs exactly 4 colors.
>>> g = Graph(4)
>>> for i in range(4):
...     for j in range(i + 1, 4):
...         g.add_edge(i, j)
>>> result = backtracking_coloring(g)
>>> result.num_colors
4

mathematicskit.graph_theory.bellman_ford_shortest_paths(graph, sources=None)[source]#

Single- or multi-source shortest paths via Bellman-Ford.

Unlike dijkstra_shortest_paths(), tolerates negative edge weights (raising if a negative-weight cycle is reachable, since shortest paths are then undefined). Via scipy.sparse.csgraph.bellman_ford(). See Cormen et al., Introduction to Algorithms, 3rd ed., Ch. 24.1.

Parameters:

graph (Graph)
sources (int or sequence of int, optional)

Return type:

ShortestPathResult

Returns:

ShortestPathResult

Examples

>>> g = Graph(3, directed=True)
>>> g.add_edge(0, 1, 4.0)
>>> g.add_edge(0, 2, 5.0)
>>> g.add_edge(1, 2, -2.0)  # a negative edge weight
>>> result = bellman_ford_shortest_paths(g, sources=0)
>>> result.distances
array([0., 4., 2.])

mathematicskit.graph_theory.bipartite_matching(graph, left)[source]#

A maximum matching of a bipartite graph, and a minimum vertex cover of the same size.

König’s construction: from every unmatched left vertex, follow alternating paths (non-matching edges left to right, matching edges right to left). With \(Z\) the vertices reached, the cover is (left not in \(Z\)) plus (right in \(Z\)).

Parameters:

graph (Graph) – Undirected and bipartite.
left (iterable of int) – The vertices on one side; every edge must join left to the rest.

Return type:

BipartiteMatchingResult

Returns:

BipartiteMatchingResult

Examples

>>> from mathematicskit.graph_theory.utils.generators import complete_bipartite_graph
>>> result = bipartite_matching(complete_bipartite_graph(2, 3), left=[0, 1])
>>> result.size, len(result.vertex_cover)
(2, 2)

mathematicskit.graph_theory.clique_number(graph)[source]#

The size of the largest clique, by Bron-Kerbosch search with pivoting.

Exponential in the worst case; intended for small graphs.

Parameters:: graph (Graph) – Undirected.
Return type:: int
Returns:: int

Examples

>>> clique_number(turan_graph(9, 3))
3

mathematicskit.graph_theory.complete_bipartite_graph(m, n)[source]#

The complete bipartite graph \(K_{m,n}\): vertices 0..m-1 joined to every vertex m..m+n-1.

Parameters:

m (int)
n (int)

Return type:

Graph

Returns:

Graph

Examples

>>> len(complete_bipartite_graph(3, 4).edges())
12

mathematicskit.graph_theory.complete_graph(n)[source]#

The complete graph \(K_n\): every pair of vertices connected.

Parameters:: n (int)
Return type:: Graph
Returns:: Graph

Examples

>>> g = complete_graph(4)
>>> len(g.edges())
6

mathematicskit.graph_theory.connected_components(graph)[source]#

The connected components of an undirected graph (weak components if directed).

Parameters:: graph (Graph)
Return type:: ComponentsResult
Returns:: ComponentsResult

Examples

>>> from mathematicskit.graph_theory.utils.generators import path_graph
>>> connected_components(path_graph(4)).n_components
1

mathematicskit.graph_theory.count_spanning_trees(graph)[source]#

The number of spanning trees of an undirected graph, \(\det L_{(0)}\).

Deleting any one row and the matching column of the Laplacian \(L = D - A\) leaves a matrix whose determinant counts spanning trees (weighted by the product of edge weights, when edges are weighted). Exact for integer counts up to about \(10^{15}\).

Parameters:: graph (Graph) – Undirected; multigraph-free.
Return type:: int
Returns:: int

Examples

>>> from mathematicskit.graph_theory.utils.generators import complete_graph
>>> count_spanning_trees(complete_graph(5))  # Cayley: 5^3
125

mathematicskit.graph_theory.cycle_graph(n)[source]#

The cycle graph \(C_n\): vertices 0, ..., n-1 in a ring.

Parameters:: n (int)
Return type:: Graph
Returns:: Graph

Examples

>>> g = cycle_graph(5)
>>> len(g.edges())
5

mathematicskit.graph_theory.dijkstra_shortest_paths(graph, sources=None)[source]#

Single- or multi-source shortest paths via Dijkstra’s algorithm.

Requires non-negative edge weights. Via scipy.sparse.csgraph.dijkstra(). See Cormen et al., Introduction to Algorithms, 3rd ed., Ch. 24.3.

Parameters:

graph (Graph)
sources (int or sequence of int, optional) – Defaults to every vertex (all-pairs).

Return type:

ShortestPathResult

Returns:

ShortestPathResult

Examples

>>> g = Graph(4)
>>> g.add_edge(0, 1, 1.0)
>>> g.add_edge(1, 2, 2.0)
>>> g.add_edge(0, 2, 5.0)
>>> g.add_edge(2, 3, 1.0)
>>> result = dijkstra_shortest_paths(g, sources=0)
>>> result.distances
array([0., 1., 3., 4.])

mathematicskit.graph_theory.dodecahedron_graph()[source]#

The 20-vertex, 30-edge graph of the regular dodecahedron, the board of Hamilton’s icosian game.

Vertices 0-4 form the outer pentagon, 5-9 and 10-14 the two middle rings, and 15-19 the inner pentagon.

Return type:: Graph
Returns:: Graph

Examples

>>> g = dodecahedron_graph()
>>> g.n_vertices, len(g.edges())
(20, 30)

mathematicskit.graph_theory.floyd_warshall_shortest_paths(graph)[source]#

All-pairs shortest paths via Floyd-Warshall.

\(O(n^3)\) dynamic program over intermediate vertices – typically preferred over running Dijkstra/Bellman-Ford from every source when the graph is dense. Via scipy.sparse.csgraph.floyd_warshall(). See Cormen et al., Introduction to Algorithms, 3rd ed., Ch. 25.2.

Parameters:: graph (Graph)
Return type:: ShortestPathResult
Returns:: ShortestPathResult – distances shape (n, n): all-pairs distance matrix.

Examples

>>> g = Graph(3)
>>> g.add_edge(0, 1, 1.0)
>>> g.add_edge(1, 2, 2.0)
>>> result = floyd_warshall_shortest_paths(g)
>>> result.distances
array([[0., 1., 3.],
       [1., 0., 2.],
       [3., 2., 0.]])

mathematicskit.graph_theory.giant_component_fraction(graph)[source]#

Fraction of the vertices in the largest connected component.

In the Erdős-Rényi graph \(G(n, c/n)\) this fraction tends to 0 for \(c < 1\) and to the positive root \(s\) of \(s = 1 - e^{-cs}\) for \(c > 1\).

Parameters:: graph (Graph)
Return type:: float
Returns:: float

Examples

>>> from mathematicskit.graph_theory.utils.generators import complete_graph
>>> giant_component_fraction(complete_graph(5))
1.0

mathematicskit.graph_theory.greedy_coloring(graph, order=None)[source]#

Greedy graph coloring: color each vertex with the lowest color not used by its already-colored neighbors.

Fast (\(O(V+E)\)) but not optimal – the number of colors used depends on vertex order and can exceed the graph’s true chromatic number by an arbitrarily large factor in the worst case (though it’s exact for common structured graphs like trees and bipartite graphs with a good order). See West, Introduction to Graph Theory, 2nd ed., Sec. 5.1.

Parameters:

graph (Graph)
order (sequence of int, optional) – Vertex processing order; defaults to 0, 1, ..., n-1.

Return type:

ColoringResult

Returns:

ColoringResult

Examples

>>> from mathematicskit.graph_theory.core.base import Graph
>>> g = Graph(4)
>>> g.add_edge(0, 1)
>>> g.add_edge(1, 2)
>>> g.add_edge(2, 3)
>>> g.add_edge(3, 0)
>>> result = greedy_coloring(g)  # a 4-cycle is bipartite: 2 colors suffice
>>> result.num_colors
2
>>> greedy_coloring(Graph(0)).num_colors  # the empty graph needs no colors
0

mathematicskit.graph_theory.grid_graph(rows, cols, blocked=())[source]#

A 4-connected grid graph with unit edge weights, and the planar position of each vertex.

Vertex r * cols + c sits at position (c, r). Cells listed in blocked (as (row, col) pairs) get no edges.

Parameters:

rows (int)
cols (int)
blocked (iterable of (int, int))

Return type:

tuple

Returns:

tuple of (Graph, ndarray) – The graph and an array of shape (rows * cols, 2) of positions.

Examples

>>> g, pos = grid_graph(2, 3)
>>> len(g.edges()), pos[4].tolist()
(7, [1.0, 1.0])

mathematicskit.graph_theory.hamiltonian_cycle(graph, start=0)[source]#

A cycle through every vertex exactly once, or None if there is none.

Extends a path one vertex at a time, trying unvisited neighbours in order of fewest remaining unvisited neighbours (Warnsdorff’s heuristic), and backtracks at dead ends.

Parameters:

graph (Graph) – Undirected.
start (int)

Return type:

list | None

Returns:

list of int or None – The cycle’s vertices, beginning at start; the closing edge back to start is implied.

Examples

>>> from mathematicskit.graph_theory.utils.generators import dodecahedron_graph, complete_bipartite_graph
>>> len(hamiltonian_cycle(dodecahedron_graph()))  # Hamilton's icosian game
20
>>> hamiltonian_cycle(complete_bipartite_graph(2, 3)) is None  # unbalanced bipartite
True

mathematicskit.graph_theory.kruskal_mst(graph)[source]#

Minimum spanning tree via Kruskal’s algorithm.

Via scipy.sparse.csgraph.minimum_spanning_tree(), which sorts edges by weight and adds each one that doesn’t close a cycle (tracked internally with a disjoint-set structure) until every vertex is connected. See Cormen et al., Introduction to Algorithms, 3rd ed., Ch. 23.2.

Parameters:: graph (Graph) – Undirected (the notion of a spanning tree assumes this).
Return type:: MSTResult
Returns:: MSTResult

Examples

>>> g = Graph(4)
>>> g.add_edge(0, 1, 1.0)
>>> g.add_edge(1, 2, 2.0)
>>> g.add_edge(2, 3, 3.0)
>>> g.add_edge(0, 3, 10.0)
>>> g.add_edge(0, 2, 4.0)
>>> result = kruskal_mst(g)
>>> result.total_weight
6.0

mathematicskit.graph_theory.max_flow_min_cut(graph, source, sink, method='dinic')[source]#

Maximum flow from source to sink, and the corresponding minimum cut.

Edge weights are used as integer capacities (required by scipy.sparse.csgraph.maximum_flow(), which needs integer-valued capacities). The minimum cut is found by a reachability search from source in the residual graph (capacity - flow): by the max-flow min-cut theorem, the set of edges from reachable to unreachable vertices is a minimum cut, with total capacity equal to the maximum flow value. See Cormen et al., Introduction to Algorithms, 3rd ed., Ch. 26.2, Theorem 26.6.

Parameters:

graph (Graph) – Directed, with positive integer edge weights (capacities).
source (int)
sink (int)
method (str) – Forwarded to scipy.sparse.csgraph.maximum_flow().

Return type:

MaxFlowResult

Returns:

MaxFlowResult

Examples

>>> g = Graph(4, directed=True)
>>> g.add_edge(0, 1, 3)
>>> g.add_edge(0, 2, 2)
>>> g.add_edge(1, 3, 2)
>>> g.add_edge(2, 3, 3)
>>> g.add_edge(1, 2, 1)
>>> result = max_flow_min_cut(g, source=0, sink=3)
>>> result.flow_value
5.0
>>> # Fractional capacities are rejected rather than silently truncated.
>>> frac = Graph(2, directed=True)
>>> frac.add_edge(0, 1, 2.7)
>>> max_flow_min_cut(frac, source=0, sink=1)
Traceback (most recent call last):
    ...
ValueError: edge capacities must be integers, but edge (0, 1) has weight 2.7

mathematicskit.graph_theory.pagerank(graph, damping=0.85, tol=1e-12, max_iter=1000)[source]#

The PageRank vector: the stationary distribution of a random surfer.

With probability damping the surfer follows a random out-link (edge weights act as relative link strengths); otherwise, or from a page with no out-links, it jumps to a uniformly random page. The scores solve

\[\pi = d\, \pi P + \frac{1-d}{n}\mathbf{1},\]

and power iteration converges at rate damping.

Parameters:

graph (Graph) – Directed (an undirected edge counts as links both ways).
damping (float)
tol (float) – Stop when the L1 change between iterates falls below tol.
max_iter (int)

Return type:

PageRankResult

Returns:

PageRankResult

Examples

>>> from mathematicskit.graph_theory.core.base import Graph
>>> g = Graph(3, directed=True)
>>> for u, v in [(0, 1), (1, 2), (2, 0), (0, 2)]:
...     g.add_edge(u, v)
>>> np.round(pagerank(g).scores, 4).tolist()
[0.3878, 0.2148, 0.3974]

mathematicskit.graph_theory.path_graph(n)[source]#

The path graph \(P_n\): vertices 0, ..., n-1 in a line.

Parameters:: n (int)
Return type:: Graph
Returns:: Graph

Examples

>>> g = path_graph(5)
>>> len(g.edges())
4

mathematicskit.graph_theory.prim_mst(graph, start=0)[source]#

Minimum spanning tree via Prim’s algorithm (hand-rolled).

Grows a single tree from start, at each step adding the cheapest edge leaving the current tree to a not-yet-included vertex (via a binary min-heap of candidate edges) – unlike Kruskal, Prim always maintains one connected tree rather than a forest. Kept hand-rolled specifically to compare against kruskal_mst(), not as the primary MST API. See Cormen et al., Introduction to Algorithms, 3rd ed., Ch. 23.2.

Parameters:

graph (Graph) – Undirected and connected.
start (int) – Starting vertex.

Return type:

MSTResult

Returns:

MSTResult

Examples

>>> g = Graph(4)
>>> g.add_edge(0, 1, 1.0)
>>> g.add_edge(1, 2, 2.0)
>>> g.add_edge(2, 3, 3.0)
>>> g.add_edge(0, 3, 10.0)
>>> g.add_edge(0, 2, 4.0)
>>> result = prim_mst(g)
>>> result.total_weight
6.0

mathematicskit.graph_theory.random_graph(n, p, seed=0, directed=False)[source]#

An Erdős-Rényi random graph \(G(n, p)\): each possible edge present independently with probability p.

Parameters:

n (int)
p (float) – Edge probability, 0 <= p <= 1.
seed (int)
directed (bool)

Return type:

Graph

Returns:

Graph

Examples

>>> g = random_graph(10, p=0.3, seed=0)
>>> 0 <= len(g.edges()) <= 45
True

mathematicskit.graph_theory.solve_assignment(cost, maximize=False)[source]#

Assign each row to a distinct column so that the total cost is minimal (or maximal).

Equivalently, a minimum-weight perfect matching in a complete bipartite graph. For an \(n \times n\) matrix there are \(n!\) assignments; Kuhn’s method finds the best in polynomial time.

Parameters:

cost (array_like, shape (m, n))
maximize (bool)

Return type:

AssignmentResult

Returns:

AssignmentResult

Examples

>>> result = solve_assignment([[4, 1, 3], [2, 0, 5], [3, 2, 2]])
>>> result.cols.tolist(), result.total_cost
([1, 0, 2], 5.0)

mathematicskit.graph_theory.spectral_analysis(graph)[source]#

Graph Laplacian, its spectrum, algebraic connectivity, and spectral bipartition.

The (combinatorial) Laplacian \(L = D - A\) (degree matrix minus adjacency), via scipy.sparse.csgraph.laplacian(), is symmetric positive semi-definite for an undirected graph, with smallest eigenvalue always 0 (eigenvector: all-ones). The second-smallest eigenvalue (the algebraic connectivity, or Fiedler value) is positive iff the graph is connected, and larger values indicate a more robustly connected graph; its eigenvector (the Fiedler vector) partitions vertices by sign into two well-separated communities – spectral clustering’s simplest form. See Chung, Spectral Graph Theory, 1997, Ch. 1, and Fiedler (1973), Czechoslovak Math. J. 23.

Parameters:: graph (Graph) – Undirected.
Return type:: SpectralResult
Returns:: SpectralResult

Examples

>>> g = Graph(4)
>>> g.add_edge(0, 1)
>>> g.add_edge(1, 2)
>>> g.add_edge(2, 3)
>>> g.add_edge(3, 0)
>>> result = spectral_analysis(g)
>>> np.round(result.eigenvalues, 6)
array([-0.,  2.,  2.,  4.])
>>> round(result.algebraic_connectivity, 6)
2.0

mathematicskit.graph_theory.turan_graph(n, r)[source]#

The Turán graph \(T(n, r)\): n vertices split into r near-equal parts, joined across parts.

Parameters:

n (int)
r (int) – Number of parts, r >= 1.

Return type:

Graph

Returns:

Graph

Examples

>>> len(turan_graph(6, 2).edges())  # K_{3,3}
9

mathematicskit.graph_theory.turan_number(n, r)[source]#

The number of edges of \(T(n, r)\), the maximum for an n-vertex graph with no \(K_{r+1}\).

Parameters:

n (int)
r (int)

Return type:

int

Returns:

int

Examples

>>> turan_number(10, 2)  # Mantel (1907): floor(n^2 / 4) edges without a triangle
25