The following document describes my contributions to the organization Haskell.Org during GSoC 2019. All my contribution are towards a project called Alga.
Note :
- This document is subject to change in the near future.
- All module name are prepended with
Algebra.Graph
. It is omitted in the following document for readability.
- Implement the acyclic data type:
Acyclic.AdjacencyMap
. - Implement generic shortest path algorithms for acyclic graphs:
Acyclic.Labelled.AdjacencyMap.Algorithm
- 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)
- Contains the implementation of
Acyclic.Labelled.AdjacencyMap
. - Contains the implementations of
Acyclic.Labelled.AdjacencyMap.Algorithm
. -.Algorithm
contains the implementation ofoptimumPath
andfold
.- Improvement of documentation and review required to be merged.
- Contains the implementation of
Labelled.AdjacencyMap.Algorithm
. -.Algorithm
containsdijkstra
,floydWarshall
andbellmanFord
.- Improvement of documentation and review required to be merged.
- Has property tests for structures in label such as semirings, dioids etc.
- Completness of code and review required to be merged.
- Has the initial implementation of
Acyclic.AdjacecncyMap
. - Straightforward functions with
coerce
. - Implements
fromGraph
. fromGraph
removes due to issues with safety.
- Contains implementation of
Acyclic.Ord
. Acyclic.Ord
is an extension toAcyclic.AdjacecncyMap
.- Renamed as
Acyclic.AdjacencyMap.Ord
.
- Minor change removing an unecessary
Num
constraint.
- Consists of a generic single source shortest path algorithm based on a paper by Mehryar Mohri.
- Was experimental and hence unmerged.
- Experimental version of Dijkstra.
- Was experimental and hence unmerged.
- Initial experimental type safe acyclic adjacency int map.
- Was experimental and hence unmerged.
- Experimentation of yet another typesafe acyclic construction using monads.
- Was not user friendly and hence unmerged.
- Experimentation of yet another typesafe acyclic construction using monads.
- Was not user friendly and hence unmerged.
- 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
- 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.