HMath.Graph.Analysis¶

Description

Finite graph analysis. Centralities use unweighted distances unless their name explicitly mentions weights. Undirected community algorithms use nonnegative weights; loops contribute twice to degree. Exponential exact coloring, Hamiltonian and edit searches require explicit work budgets.

On this page¶

API	Purpose
bipartiteColors	Return Just Bool colors for every vertex if the underlying undirected adjacency is bipartite, including disconnected components; conflicting edges/loops yield Nothing.
greedyColoring	Return zero-based greedy colors in vertex order using underlying undirected adjacency.
exactColoring	Given work budget then graph with at most 24 vertices, search for a minimum proper coloring.
eulerianPath	Hierholzer trail, consuming each original edge identity once.
hamiltonianPath	Given search budget then graph, find a path visiting every vertex once, returning Maybe vertex list.
nearestNeighborTour	Nearest-neighbor closed tour heuristic; incomplete graphs may fail.
twoOptTour	Given improvement-step budget,graph,then closed Hamiltonian tour, improve via pairwise segment reversals.
pageRank	Given iteration budget,tolerance,damping,then graph, return vertex PageRank scores with dangling-node redistribution.
degreeCentrality	Return outgoing traversal degree divided by n-1 for each vertex; n<=1 yields zeros.
betweennessCentrality	Return unweighted shortest-path betweenness by vertex, accounting for shortest-path multiplicities.
closenessCentrality	Return unweighted closeness with reachable-component correction: reachable^2((n-1)*sumDistances).
eigenvectorCentrality	Shifted power iteration on (I+A), avoiding sign oscillation on bipartite graphs.
katzCentrality	Given iterations,tolerance,alpha,beta,then graph, iterate weighted Katz scores.
clusteringCoefficients	Return local undirected clustering coefficients from distinct non-self neighbor sets.
density	Simple graph density: parallel edges and loops are ignored.
diameterRadius	Nothing if disconnected (not strongly connected for directed graphs).
graphLaplacian	Given normalized Bool then nonnegative-weight undirected graph, return dense combinatorial or normalized Laplacian rows.
laplacianSpectrum	Symmetric Jacobi rotations; eigenvalues sorted ascending.
randomWalk	Weighted walk with a reproducible 64-bit SplitMix stream.
labelPropagation	Deterministic asynchronous label propagation.
louvain	Louvain local modularity moves followed by graph aggregation, repeated until no communities merge.
modularity	Given undirected nonnegative-weight graph then one community label per vertex, return weighted modularity.
graphSimilarity	Jaccard similarity of labeled weighted edge multisets (vertex labels fixed), counting matching multiplicities.
graphEditDistance	Exact unlabeled graph edit distance: unit vertexedge insertiondeletion, edge weights are exact labels; relabeling vertices is free.

Documentation

bipartiteColors

bipartiteColors :: Graph -> Maybe [Bool] Source #

Return Just Bool colors for every vertex if the underlying undirected adjacency is bipartite, including disconnected components; conflicting edges/loops yield Nothing.

greedyColoring

greedyColoring :: Graph -> Either MathError [Int] Source #

Return zero-based greedy colors in vertex order using underlying undirected adjacency. A self-loop makes proper coloring impossible and returns Left DomainError. Minimal color count is not guaranteed.

exactColoring

exactColoring :: Int -> Graph -> Either MathError [Int] Source #

Given work budget then graph with at most 24 vertices, search for a minimum proper coloring. Invalid budget/size or self-loops fail; exhausted search returns NonConvergence.

eulerianPath

eulerianPath :: Graph -> Either MathError (Maybe ([Int], [Int])) Source #

Hierholzer trail, consuming each original edge identity once. A directed trail follows edge directions; disconnected nonisolated components fail.

hamiltonianPath

hamiltonianPath :: Int -> Graph -> Either MathError (Maybe [Int]) Source #

Given search budget then graph, find a path visiting every vertex once, returning Maybe vertex list. Invalid options/exhausted budget fail; Nothing means exhaustive search found no path.

nearestNeighborTour

nearestNeighborTour :: Graph -> Int -> Either MathError (Maybe (Double, [Int])) Source #

Nearest-neighbor closed tour heuristic; incomplete graphs may fail. This heuristic promises a valid tour, without an optimality/approximation bound.

twoOptTour

twoOptTour :: Int -> Graph -> [Int] -> Either MathError (Double, [Int]) Source #

Given improvement-step budget,graph,then closed Hamiltonian tour, improve via pairwise segment reversals. Validate the tour permutation/edges and finite cost. Return (cost,tour); invalid input or missing edges fails.

pageRank

pageRank :: Int -> Double -> Double -> Graph -> Either MathError [Double] Source #

Given iteration budget,tolerance,damping,then graph, return vertex PageRank scores with dangling-node redistribution. Require nonnegative weights, finite damping in [0,1), valid tolerancebudget; nonconvergencenumeric failure returns Left MathError.

degreeCentrality

degreeCentrality :: Graph -> [Double] Source #

Return outgoing traversal degree divided by n-1 for each vertex; n<=1 yields zeros. Undirected loops contribute twice and parallel edges are retained, so values can exceed one.

betweennessCentrality

betweennessCentrality :: Graph -> [Double] Source #

Return unweighted shortest-path betweenness by vertex, accounting for shortest-path multiplicities. Undirected scores are halved; edge weights are not path lengths here.

closenessCentrality

closenessCentrality :: Graph -> [Double] Source #

Return unweighted closeness with reachable-component correction: reachable^2((n-1)*sumDistances). Isolatedsingleton vertices yield zero.

eigenvectorCentrality

eigenvectorCentrality :: Int -> Double -> Graph -> Either MathError [Double] Source #

Shifted power iteration on (I+A), avoiding sign oscillation on bipartite graphs. For reducible graphs the initial all-ones vector selects a Perron combination; convergence and uniqueness are not promised.

katzCentrality

katzCentrality :: Int -> Double -> Double -> Double -> Graph -> Either MathError [Double] Source #

Given iterations,tolerance,alpha,beta,then graph, iterate weighted Katz scores. Require finite alpha>=0 and alpha times maximum absolute incoming weight sum <1. Invalid input or nonconvergence fails.

clusteringCoefficients

clusteringCoefficients :: Graph -> Either MathError [Double] Source #

Return local undirected clustering coefficients from distinct non-self neighbor sets. Degree below two yields zero. Directed graphs fail.

density

density :: Graph -> Double Source #

Simple graph density: parallel edges and loops are ignored.

diameterRadius

diameterRadius :: Graph -> Maybe (Int, Int) Source #

Nothing if disconnected (not strongly connected for directed graphs). The empty graph has no diameter/radius; a singleton has (0,0).

graphLaplacian

graphLaplacian :: Bool -> Graph -> Either MathError [[Double]] Source #

Given normalized Bool then nonnegative-weight undirected graph, return dense combinatorial or normalized Laplacian rows. Directed/negative-weight graphs or non-finite arithmetic fail.

laplacianSpectrum

laplacianSpectrum :: Int -> Double -> Bool -> Graph -> Either MathError [Double] Source #

Symmetric Jacobi rotations; eigenvalues sorted ascending. Budget counts rotations, tolerance is relative to the matrix's largest absolute entry.

randomWalk

randomWalk :: Int -> Word64 -> Graph -> Int -> Either MathError [Int] Source #

Weighted walk with a reproducible 64-bit SplitMix stream. At a sink it remains in place. Zero-weight edges are never selected.

labelPropagation

labelPropagation :: Int -> Graph -> Either MathError [Int] Source #

Deterministic asynchronous label propagation. Budget counts full sweeps; equal weighted votes retain the current label when possible.

louvain

louvain :: Int -> Graph -> Either MathError [Int] Source #

Louvain local modularity moves followed by graph aggregation, repeated until no communities merge. Deterministic local optimum, not a global optimum. Budget counts every modularity candidate evaluation across levels.

modularity

modularity :: Graph -> [Int] -> Either MathError Double Source #

Given undirected nonnegative-weight graph then one community label per vertex, return weighted modularity. Invalid graph/label length or arithmetic fails; loops follow the module degree convention.

Jaccard similarity of labeled weighted edge multisets (vertex labels fixed), counting matching multiplicities. Empty edge multisets have similarity one.

graphEditDistance

graphEditDistance :: Int -> Graph -> Graph -> Either MathError Int Source #

Exact unlabeled graph edit distance: unit vertexedge insertiondeletion, edge weights are exact labels; relabeling vertices is free. Substitution is deletion plus insertion. Enumerates padded vertex bijections, at most 9 nodes.