Inroduction

The following document describes my contributions to the organization Haskell.Org during GSoC 2019. All my contribution are towards a project called Alga.

Note :

1. This document is subject to change in the near future.
2. All module name are prepended with Algebra.Graph. It is omitted in the following document for readability.

Expected task list

1. Implement the acyclic data type: Acyclic.AdjacencyMap.
2. Implement generic shortest path algorithms for acyclic graphs: Acyclic.Labelled.AdjacencyMap.Algorithm
3. Implement generic shortest path algorithms for labelled graphs: Labelled.AdjacencyMap.Algorithm

Please check the following links for more information: HSoC - Idea List, Draft work programme (Adithya's task)

Pull Requests

Open

219

• Contains the implementation of Acyclic.Labelled.AdjacencyMap.
• Contains the implementations of Acyclic.Labelled.AdjacencyMap.Algorithm.
• -.Algorithm contains the implementation of optimumPath and fold.
• Improvement of documentation and review required to be merged.

225

• Contains the implementation of Labelled.AdjacencyMap.Algorithm.
• -.Algorithm contains dijkstra, floydWarshall and bellmanFord.
• Improvement of documentation and review required to be merged.

232

• Has property tests for structures in label such as semirings, dioids etc.
• Completness of code and review required to be merged.

Merged

203

• Has the initial implementation of Acyclic.AdjacecncyMap.
• Straightforward functions with coerce.
• Implements fromGraph.
• fromGraph removes due to issues with safety.

215

• Contains implementation of Acyclic.Ord.
• Acyclic.Ord is an extension to Acyclic.AdjacecncyMap.
• Renamed as Acyclic.AdjacencyMap.Ord.

230

• Minor change removing an unecessary Num constraint.

Unmerged

188

• Consists of a generic single source shortest path algorithm based on a paper by Mehryar Mohri.
• Was experimental and hence unmerged.

194

• Experimental version of Dijkstra.
• Was experimental and hence unmerged.

199

• Initial experimental type safe acyclic adjacency int map.
• Was experimental and hence unmerged.

200

• Experimentation of yet another typesafe acyclic construction using monads.
• Was not user friendly and hence unmerged.

214

• Experimentation of yet another typesafe acyclic construction using monads.
• Was not user friendly and hence unmerged.

221

• Changes implementation of Labelled.AdjacencyMap.isSubGraph.
• Unmerged as the previous implementation was correct but did not work with semirings like Sum.
• Problem appended to issue 175

231

• Contains implementation of prim's algorithm.
• Unmerged as MST for directed graphs does not make sense.
• Can be reopened after Undirected.Labelled.AdjacencyMap is implemented.