Paper Info
Title
Algebraic graphs with class (functional pearl).
Abstract
The paper presents a minimalistic and elegant approach to working with graphs in Haskell. It is built on a rigorous mathematical foundation --- an algebra of graphs --- that allows us to apply equational reasoning for proving the correctness of graph transformation algorithms. Algebraic graphs let us avoid partial functions typically caused by `malformed graphs' that contain an edge referring to a non-existent vertex. This helps to liberate APIs of existing graph libraries from partial functions. The algebra of graphs can represent directed, undirected, reflexive and transitive graphs, as well as hypergraphs, by appropriately choosing the set of underlying axioms. The flexibility of the approach is demonstrated by developing a library for constructing and transforming polymorphic graphs.
Year
DOI
Venue
2017
10.1145/3156695.3122956
Haskell
Keywords
Field
DocType
Haskell, algebra, graph theory
Indifference graph,Modular decomposition,Programming language,Graph isomorphism,Computer science,Chordal graph,Cograph,Graph product,Pathwidth,Maximal independent set
Conference
Volume
Issue
ISSN
52
10
0362-1340
ISBN
Citations 
PageRank 
978-1-4503-5182-9
3
0.42
References 
Authors
9
1
Name
Order
Citations
PageRank
Andrey Mokhov113626.57