HMath.Graph.Core¶
Module index · Numerical conventions
Description
Checked finite labeled multigraphs. Vertices are [0,n); input edge order
assigns stable edge IDs. Loops and parallel edges are retained. In undirected
graphs every edge yields two traversal arcs (a loop therefore has degree two).
Limits: 512 vertices, 65536 edges. Ties use vertex/edge order.
On this page¶
| API | Purpose |
|---|---|
| Graph | Opaque validated directed/undirected finite multigraph, constructed with graph or checked conversion functions. |
| Edge | Finite weighted multigraph edge with stable identity and zero-based endpoints. |
| Edge | Declaration and type contract below. |
| edgeId | Stable zero-based identity assigned by original input edge order. |
| edgeFrom | Zero-based source endpoint of the original edge. |
| edgeTo | Zero-based destination endpoint of the original edge. |
| edgeWeight | Finite Double edge weight, retaining loops/parallel-edge identity. |
| directed | Return whether the graph is directed. |
| vertexCount | Return graph vertex count. |
| edges | Return original labeled edges in input order, preserving loops, multiplicity and stable edge IDs. |
| graph | Given directed flag,vertex count,then (from,to,weight) triples, construct a multigraph with stable input-order edge IDs. |
| arcs | Return directed traversal arcs. |
| neighbors | Given graph then vertex, return sorted (destination,weight,edge ID) traversal entries leaving that vertex. |
| fromAdjacencyList | Lossless labeled adjacency-list conversion. |
| fromLabeledAdjacencyMatrix | Given directed flag,square cells of (edge ID,weight) lists,then original edge orientations, reconstruct a lossless graph. |
| adjacencyList | Return one sorted neighbors row per zero-based vertex, retaining weight and edge identity for every traversal arc. |
| adjacencyMatrix | Cells contain every (edge ID,weight), preserving edge multiplicity. |
| fromAdjacencyMatrix | Matrix cells are weights; undirected matrices must be exactly symmetric. |
| CSR | Lossless labeled compressed adjacency storage. |
| CSR | Declaration and type contract below. |
| csrDirected | Whether CSR traversal represents a directed graph. |
| csrVertices | Number of graph vertices, including isolated rows. |
| csrOffsets | Row pointer array of length vertices+1, starting at zero and ending at traversal entry count. |
| csrTargets | Destination vertex for each compressed traversal entry. |
| csrWeights | Finite edge weight for each traversal entry. |
| csrIds | Original edge ID for each traversal entry; an undirected edge contributes two arcs sharing its ID. |
| csrOrientations | Original endpoint orientation for each edge ID, required for lossless undirected round-trip. |
| toCSR | Convert a graph to lossless CSR rows with offsets, targets, weights, IDs and original edge orientations. |
| fromCSR | Validate CSR sizes, offsets, endpointweightID arrays and original orientations, then reconstruct a canonical graph. |
| BipartiteGraph | Validated graph with explicit left/right vertex partition. |
| bipartiteGraph | Given left count,right count,then (left-local,right-local,weight) triples, construct an undirected bipartite graph. |
| bipartiteParts | Return (left vertex count,right vertex count) of a bipartite graph. |
| bipartiteBase | Return underlying undirected graph, whose right-part global labels start at the left-part count. |
| Hypergraph | Validated finite vertex set with canonical sorted distinct vertices per hyperedge. |
| hypergraph | Given vertex count then hyperedge vertex lists, validate bounded size/endpoints and construct a hypergraph. |
| hyperVertices | Return the number of zero-based vertices in a hypergraph. |
| hyperedges | Return canonical hyperedge lists with sorted distinct member vertices, preserving hyperedge list order. |
| serializeBipartiteGraph | Versioned Haskell tuple grammar. |
| deserializeBipartiteGraph | Read a versioned bipartite serialization, then validate part counts, endpoints and weights. |
| serializeGraph | Serialize graph direction, vertex count and input-ordered edges with HMath.Graph/1 marker; stable IDs reconstruct from edge order. |
| deserializeGraph | Read complete HMath.Graph/1 encoding and reconstruct via checked graph constructor. |
| serializeHypergraph | Serialize vertex count and canonical hyperedges with HMath.Hypergraph/1 version marker. |
| deserializeHypergraph | Read versioned hypergraph encoding and validate through hypergraph. |
| bfs | Given graph then valid start vertex, return breadth-first reachable-vertex order with sorted neighbor tie-breaking. |
| dfs | Given graph then valid start vertex, return depth-first reachable-vertex order with deterministic sorted neighbors. |
| iterativeDeepening | Iterative deepening simple-path DFS. |
| topologicalSort | Return a deterministic topological order of all vertices of a directed acyclic graph. |
| hasCycle | Test for a directed or undirected cycle, respecting original edge identities. |
| connectedComponents | Return weak connected components as sorted vertex lists, ignoring edge direction and retaining isolated vertices. |
| tarjanSCC | Tarjan's single-pass index/low-link stack algorithm. |
| kosarajuSCC | Return sorted strongly connected components via Kosaraju traversal; undirected graphs reduce to ordinary connected components. |
| articulationPoints | Removal-based reference algorithms, retaining parallel-edge identity. |
| bridges | Return original IDs of bridges in an undirected multigraph; parallel edges are treated distinctly. |
| kruskal | Return a minimum spanning forest of an undirected weighted graph by Kruskal, breaking ties by stable edge ID. |
| prim | All three MST routines return a minimum spanning forest on disconnected inputs. |
| boruvka | Return an undirected minimum spanning forest by repeatedly merging components along cheapest outgoing edges. |
| checkVertex | Given graph then vertex index, return Right () only for a label in [0,vertexCount). |
| requireUndirected | Return Right () for an undirected graph; directed input returns Left InvalidArgument. |
| finite | Test whether a Double is neither NaN nor infinite; used by checked graph weight/arithmetic validation. |
Documentation
Graph
Opaque validated directed/undirected finite multigraph, constructed with graph or checked conversion functions.
Edge
Finite weighted multigraph edge with stable identity and zero-based endpoints. Parallel edges and loops retain separate IDs.
Constructors
| Edge | |
directed
directed :: Graph -> Bool Source #
Return whether the graph is directed. Undirected edges are represented once in edges and twice in arcs, including loops.
vertexCount
vertexCount :: Graph -> Int Source #
Return graph vertex count. Valid vertex labels are zero-based integers below this count.
edges
edges :: Graph -> [Edge] Source #
Return original labeled edges in input order, preserving loops, multiplicity and stable edge IDs.
graph
graph :: Bool -> Int -> [(Int, Int, Double)] -> Either MathError Graph Source #
Given directed flag,vertex count,then (from,to,weight) triples, construct a multigraph with stable input-order edge IDs. Require 0<=vertices<=512, <=65536 edges, valid endpoints and finite weights; otherwise return Left InvalidArgument.
arcs
arcs :: Graph -> [Edge] Source #
Return directed traversal arcs. An undirected edge yields forward and reverse arcs sharing one original ID; a loop therefore yields two arcs.
neighbors
neighbors :: Graph -> Int -> [(Int, Double, Int)] Source #
Given graph then vertex, return sorted (destination,weight,edge ID) traversal entries leaving that vertex. Parallel edges/loops are preserved. This query does not itself reject invalid vertex labels.
fromAdjacencyList
fromAdjacencyList :: Bool -> [[(Int, Double, Int)]] -> [(Int, Int)] -> Either MathError Graph Source #
Lossless labeled adjacency-list conversion. The final argument records the original direction of each undirected edge, which symmetric arcs alone cannot distinguish. IDs must be contiguous; rows are canonical sorted order.
fromLabeledAdjacencyMatrix
fromLabeledAdjacencyMatrix :: Bool -> [[[(Int, Double)]]] -> [(Int, Int)] -> Either MathError Graph Source #
Given directed flag,square cells of (edge ID,weight) lists,then original edge orientations, reconstruct a lossless graph. Validate square shape, canonical IDs/arcs and graph bounds through fromCSR; malformed input fails.
adjacencyList
adjacencyList :: Graph -> [[(Int, Double, Int)]] Source #
Return one sorted neighbors row per zero-based vertex, retaining weight and edge identity for every traversal arc.
adjacencyMatrix
adjacencyMatrix :: Graph -> [[[(Int, Double)]]] Source #
Cells contain every (edge ID,weight), preserving edge multiplicity.
fromAdjacencyMatrix
fromAdjacencyMatrix :: Bool -> [[[Double]]] -> Either MathError Graph Source #
Matrix cells are weights; undirected matrices must be exactly symmetric. Diagonal entries denote one loop each, rather than duplicated traversal arcs.
CSR
Lossless labeled compressed adjacency storage. Offsets index targetweightID arrays; orientations preserve original undirected edge direction.
Constructors
| CSR | |
Fields
| |
toCSR
toCSR :: Graph -> CSR Source #
Convert a graph to lossless CSR rows with offsets, targets, weights, IDs and original edge orientations. Preserve loops and multiedge identity.
fromCSR
fromCSR :: CSR -> Either MathError Graph Source #
Validate CSR sizes, offsets, endpointweightID arrays and original orientations, then reconstruct a canonical graph. Malformed or noncanonical data returns Left InvalidArgument.
BipartiteGraph
data BipartiteGraph Source #
Validated graph with explicit left/right vertex partition. Construct from part-local endpoints using bipartiteGraph.
Instances
| Show BipartiteGraph Source # | |
Defined in HMath.Graph.Core Methods showsPrec :: Int -> BipartiteGraph -> ShowS # show :: BipartiteGraph -> String # showList :: [BipartiteGraph] -> ShowS # | |
| Eq BipartiteGraph Source # | |
Defined in HMath.Graph.Core Methods (==) :: BipartiteGraph -> BipartiteGraph -> Bool # (/=) :: BipartiteGraph -> BipartiteGraph -> Bool # | |
bipartiteGraph
bipartiteGraph :: Int -> Int -> [(Int, Int, Double)] -> Either MathError BipartiteGraph Source #
Given left count,right count,then (left-local,right-local,weight) triples, construct an undirected bipartite graph. Right vertices are offset by left count internally. Negative/out-of-range endpoints, non-finite weights or graph size bounds fail.
bipartiteParts
bipartiteParts :: BipartiteGraph -> (Int, Int) Source #
Return (left vertex count,right vertex count) of a bipartite graph.
bipartiteBase
bipartiteBase :: BipartiteGraph -> Graph Source #
Return underlying undirected graph, whose right-part global labels start at the left-part count.
Hypergraph
data Hypergraph Source #
Validated finite vertex set with canonical sorted distinct vertices per hyperedge. Construct with hypergraph.
Instances
| Show Hypergraph Source # | |
Defined in HMath.Graph.Core Methods showsPrec :: Int -> Hypergraph -> ShowS # show :: Hypergraph -> String # showList :: [Hypergraph] -> ShowS # | |
| Eq Hypergraph Source # | |
Defined in HMath.Graph.Core | |
hypergraph
hypergraph :: Int -> [[Int]] -> Either MathError Hypergraph Source #
Given vertex count then hyperedge vertex lists, validate bounded size/endpoints and construct a hypergraph. Canonicalize vertices within each hyperedge by sorting/deduplicating. Invalid bounds fail.
hyperVertices
hyperVertices :: Hypergraph -> Int Source #
Return the number of zero-based vertices in a hypergraph.
hyperedges
hyperedges :: Hypergraph -> [[Int]] Source #
Return canonical hyperedge lists with sorted distinct member vertices, preserving hyperedge list order.
serializeBipartiteGraph
serializeBipartiteGraph :: BipartiteGraph -> String Source #
Versioned Haskell tuple grammar. Deserialization validates all invariants, requires full-input parsing and limits input text to 16 MiB.
Serialize a bipartite graph with HMath.BipartiteGraph/1 version marker and local part labels. Pair with deserializeBipartiteGraph for checked round-trip.
deserializeBipartiteGraph
deserializeBipartiteGraph :: String -> Either MathError BipartiteGraph Source #
Read a versioned bipartite serialization, then validate part counts, endpoints and weights. Reject unknown/malformed encoding or input longer than 16777216 characters.
serializeGraph
serializeGraph :: Graph -> String Source #
Serialize graph direction, vertex count and input-ordered edges with HMath.Graph/1 marker; stable IDs reconstruct from edge order.
deserializeGraph
deserializeGraph :: String -> Either MathError Graph Source #
Read complete HMath.Graph/1 encoding and reconstruct via checked graph constructor. Unknown version, malformed text, input over 16777216 characters or invalid graph data fails.
serializeHypergraph
serializeHypergraph :: Hypergraph -> String Source #
Serialize vertex count and canonical hyperedges with HMath.Hypergraph/1 version marker.
deserializeHypergraph
deserializeHypergraph :: String -> Either MathError Hypergraph Source #
Read versioned hypergraph encoding and validate through hypergraph. Reject unknown/malformed input, more than 16777216 characters or invalid graph bounds.
bfs
bfs :: Graph -> Int -> Either MathError [Int] Source #
Given graph then valid start vertex, return breadth-first reachable-vertex order with sorted neighbor tie-breaking. Invalid start fails; disconnected unreachable vertices are omitted.
dfs
dfs :: Graph -> Int -> Either MathError [Int] Source #
Given graph then valid start vertex, return depth-first reachable-vertex order with deterministic sorted neighbors. Invalid start fails; each reached vertex appears once.
iterativeDeepening
iterativeDeepening :: Int -> Graph -> Int -> Int -> Either MathError (Maybe [Int]) Source #
Iterative deepening simple-path DFS. Fuel counts visited search nodes.
topologicalSort
topologicalSort :: Graph -> Either MathError [Int] Source #
Return a deterministic topological order of all vertices of a directed acyclic graph. Undirected graphs or directed cycles return Left MathError.
hasCycle
hasCycle :: Graph -> Bool Source #
Test for a directed or undirected cycle, respecting original edge identities. Loops and parallel undirected edges can form cycles.
connectedComponents
connectedComponents :: Graph -> [[Int]] Source #
Return weak connected components as sorted vertex lists, ignoring edge direction and retaining isolated vertices.
kosarajuSCC
kosarajuSCC :: Graph -> [[Int]] Source #
Return sorted strongly connected components via Kosaraju traversal; undirected graphs reduce to ordinary connected components.
articulationPoints
articulationPoints :: Graph -> Either MathError [Int] Source #
Removal-based reference algorithms, retaining parallel-edge identity.
bridges
bridges :: Graph -> Either MathError [Int] Source #
Return original IDs of bridges in an undirected multigraph; parallel edges are treated distinctly. Directed input returns Left InvalidArgument.
kruskal
kruskal :: Graph -> Either MathError [Edge] Source #
Return a minimum spanning forest of an undirected weighted graph by Kruskal, breaking ties by stable edge ID. Disconnected graphs return a forest; directed input fails.
prim
prim :: Graph -> Either MathError [Edge] Source #
All three MST routines return a minimum spanning forest on disconnected inputs. Self-loops are ignored, negative finite weights are supported.
boruvka
boruvka :: Graph -> Either MathError [Edge] Source #
Return an undirected minimum spanning forest by repeatedly merging components along cheapest outgoing edges. Preserve original edge identity; directed input fails.
checkVertex
checkVertex :: Graph -> Int -> Either MathError () Source #
Given graph then vertex index, return Right () only for a label in [0,vertexCount). Invalid labels return Left InvalidArgument.