Andrey Mokhov
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.
- Arseniy Alekseyev. 2014. Compositional approach to design of digital circuits. Ph.D. Dissertation. Newcastle University.Google Scholar
- Jonathan Beaumont, Andrey Mokhov, Danil Sokolov, and Alex Yakovlev. 2015. Compositional design of asynchronous circuits from behavioural concepts. In ACM/IEEE International Conference on Formal Methods and Models for Codesign (MEMOCODE). IEEE, 118–127. Google ScholarDigital Library
- Filippo Bonchi, Pawel Sobocinski, and Fabio Zanasi. 2015. Full abstraction for signal flow graphs. In ACM SIGPLAN Notices, Vol. 50. ACM, 515–526. Google ScholarDigital Library
- Manuel Chakravarty, Gabriele Keller, and Simon Peyton Jones. 2005. Associated type synonyms. In ACM SIGPLAN Notices, Vol. 40. ACM, 241–253. Google ScholarDigital Library
- Derek G Corneil, H Lerchs, and L Stewart Burlingham. 1981. Complement reducible graphs. Discrete Applied Mathematics 3, 3 (1981), 163–174.Google ScholarCross Ref
- Stephen Dolan. 2013. Fun with semirings: a functional pearl on the abuse of linear algebra. In ACM SIGPLAN Notices, Vol. 48. ACM, 101–110. Google ScholarDigital Library
- Martin Erwig. 2001. Inductive graphs and functional graph algorithms. Journal of Functional Programming 11, 05 (2001), 467–492. Google ScholarDigital Library
- Jeremy Gibbons. 1995. An initial-algebra approach to directed acyclic graphs. In International Conference on Mathematics of Program Construction. Springer, 282– 303. Google ScholarDigital Library
- Jeremy Gibbons and Nicolas Wu. 2014. Folding domain-specific languages: Deep and shallow embeddings (functional pearl). In ACM SIGPLAN Notices, Vol. 49. ACM, 339–347. Google ScholarDigital Library
- Jonathan S Golan. 1999. Semirings and their Applications. Springer Science & Business Media.Google Scholar
- Frank Harary. 1969. Graph theory. Addison-Wesley.Google Scholar
- David J King and John Launchbury. 1995. Structuring depth-first search algorithms in Haskell. In Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages. ACM, 344–354. Google ScholarDigital Library
- John Launchbury and Simon L Peyton Jones. 1994. Lazy functional state threads. In ACM SIGPLAN Notices, Vol. 29. ACM, 24–35. Google ScholarDigital Library
- Saunders Mac Lane and Garrett Birkhoff. 1999. Algebra. Chelsea Publishing Company.Google Scholar
- Ross M McConnell and Fabien De Montgolfier. 2005. Linear-time modular decomposition of directed graphs. Discrete Applied Mathematics 145, 2 (2005), 198–209. Google ScholarDigital Library
- Andrey Mokhov. 2015. Algebra of switching networks. IET Computers & Digital Techniques (2015).Google Scholar
- Andrey Mokhov and Victor Khomenko. 2014. Algebra of Parameterised Graphs. ACM Transactions on Embedded Computing Systems 13, 4s (2014), 1–22. Google ScholarDigital Library
- Tadao Murata. 1989. Petri nets: Properties, analysis and applications. Proc. IEEE 77, 4 (1989), 541–580.Google ScholarCross Ref
- Peter Selinger. 2010. A survey of graphical languages for monoidal categories. In New structures for physics. Springer, 289–355.Google Scholar
- Robert E Tarjan and Jan Van Leeuwen. 1984. Worst-case analysis of set union algorithms. Journal of the ACM (JACM) 31, 2 (1984), 245–281. Google ScholarDigital Library
- Jacobo Valdes, Robert E Tarjan, and Eugene L Lawler. 1979. The recognition of series parallel digraphs. In Proceedings of the eleventh annual ACM symposium on Theory of computing. ACM, 1–12. Google ScholarDigital Library
Index Terms
- Algebraic graphs with class (functional pearl)
Recommendations
Algebraic graphs with class (functional pearl)
Haskell '17The 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 ...
On the adjacent vertex distinguishing edge colourings of graphs
A k-adjacent vertex distinguishing edge colouring or a k-avd-colouring of a graph G is a proper k-edge colouring of G such that no pair of adjacent vertices meets the same set of colours. The avd-chromatic number, denoted by χ'a(G), is the minimum ...
Even and odd holes in cap-free graphs
It is an old problem in graph theory to test whether a graph contains a chordless cycle of length greater than three (hole) with a specific parity (even, odd). Studying the structure of graphs without odd holes has obvious implications for Berge's ...
Comments