在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
开源软件名称(OpenSource Name):snowleopard/alga开源软件地址(OpenSource Url):https://github.com/snowleopard/alga开源编程语言(OpenSource Language):Haskell 100.0%开源软件介绍(OpenSource Introduction):Algebraic graphsAlga is a library for algebraic construction and manipulation of graphs in Haskell. See this Haskell Symposium paper and the corresponding talk for the motivation behind the library, the underlying theory and implementation details. There is also a Haskell eXchange talk, and a tutorial by Alexandre Moine. Main ideaConsider the following data type, which is defined in the top-level module Algebra.Graph of the library: data Graph a = Empty | Vertex a | Overlay (Graph a) (Graph a) | Connect (Graph a) (Graph a) We can give the following semantics to the constructors in terms of the pair (V, E) of graph vertices and edges:
Alternatively, we can give an algebraic semantics to the above graph construction primitives by defining the following type class and specifying a set of laws for its instances (see module Algebra.Graph.Class): class Graph g where
type Vertex g
empty :: g
vertex :: Vertex g -> g
overlay :: g -> g -> g
connect :: g -> g -> g The laws of the type class are remarkably similar to those of a semiring,
so we use
This algebraic structure corresponds to unlabelled directed graphs: every expression represents a graph, and every graph can be represented by an expression. Other types of graphs (e.g. undirected) can be obtained by modifying the above set of laws. Algebraic graphs provide a convenient, safe and powerful interface for working with graphs in Haskell, and allow the application of equational reasoning for proving the correctness of graph algorithms. To represent non-empty graphs, we can drop the To represent edge-labelled graphs, we can switch to the following data type, as explained in my Haskell eXchange 2018 talk: data Graph e a = Empty
| Vertex a
| Connect e (Graph e a) (Graph e a) Here How fast is the library?Alga can handle graphs comprising millions of vertices and billions of edges in a matter of seconds, which is fast enough for many applications. We believe there is a lot of potential for improving the performance of the library, and this is one of our top priorities. If you come across a performance issue when using the library, please let us know. Some preliminary benchmarks can be found here. Blog postsThe development of the library has been documented in the series of blog posts:
Algebraic graphs in other languagesAlgebraic graphs were implemented in a few other languages, including Agda, F#, Scala and TypeScript. |
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
请发表评论