Efficient bidirectional graph representation

[rolyp]

• [x] Graph type class presenting API required to implement graph evaluation
• [x] Initial naive implementation based on adjacency lists (or sets)
• [x] Efficient implementation of isomorphism between $G$ and $G^-1$

[JosephBond]

As described in a bullet point in #634, we have some considerations on how we are going to implement the dependence graphs: There are 3 main representations for graphs in general:

• Adjacency lists, generally good for sparse stuff but they are slow for lookup, so could be a problem for slicing
• Adjacency matrix, very quick for lookup, however space inefficient and slow to grow, however can very simply store the inverse graph
• Incidence matrix, not sure on these, need to revise

We need to choose the best option based both on the asymptotic performance of the operations we are going to perform the most often, but also to bear in mind the most efficient purescript representations (in particular I need to consider ForeignObject and maybe StringMap)

We can also consider some other more algorithmic concerns, for example if we can calculate the number of nodes we are going to need ahead of time, we could allocate the entire matrix in one go and then fill in the edge entries efficiently. Will fill in this issue as I gather more information

[rolyp]

Hi @JosephBond. A good way to proceed here would be to define an interface (in the form of a type class) which is just rich enough to support the implementation of the graph semantics (Fig. 13). For now we probably just need the ability to allocate a fresh vertex and merge two graphs with disjoint keys (perhaps optimised for the singleton case). If we can get this in place first, Min can make a start on the graph evaluation while you finalise the internal representation. We may be able to use newtype to implement $G^{-1}$. I’ve added some corresponding todo’s to the issue body.

[JosephBond]

At this stage, keeping things simple seems to be the best option, to that end we will start with an Adjacency list representation, built off ForeignObject (as they seem to be quite snappy, which is obviously a benefit to us).

I need to do a little more work on the representation itself before we can start implementing the semantics, in particular we will probably want/need some other typeclasses implemented for the graphs so that Min can work with usual functional design patterns

[rolyp]

Something like the following should be enough to implement graph eval:

module Graph where

import Data.Set (Set)
import Util (Endo)

newtype Vertex = Vertex String

class Graph g where
   -- deterministic for now
   fresh :: g -> Vertex
   -- optimised for singleton case for now
   disjUnion :: Vertex -> Set Vertex -> Endo g

[rolyp]

Updated to subsume disjUnion by union, and add methods required for forward and backward slicing:

class Graph g where
   -- fresh vertex; deterministic for now
   fresh :: g -> Vertex
   -- union with another (singleton) graph
   union :: Vertex -> Set Vertex -> Endo g
   -- out-neighbours
   outN :: g -> Vertex -> Set Vertex
   -- singleton graph
   singleton :: Vertex -> Set Vertex -> g
   -- remove vertex and associated edges
   remove :: Vertex -> Endo g
   -- opposite graph
   opp :: Endo g

[rolyp]

Hi Joe, looks like a reasonable start! Some initial comments/suggestions:

• [x] Let’s adopt the same metavariable conventions as the paper (modulo whatever adjustments are needed to align with PureScript):
  • α for vertices
  • αs for sets of vertices
• [x] Use × instead of Tuple
• [x] Rename DependenceGraph to Graph for now
• [x] SimpleGraph probably isn’t a good name as it’s a technical term in graph theory; maybe GraphImpl, or something suggested by the efficient opp implementation (see below)
• [x] for opp, let’s use the implementation we discussed last week with Cristina: maintain a pair of Object (Set Vertex) maps, one for each direction, and then implement opp as swap
• [x] union as currently implemented isn’t commutative: it needs to combine the entries for any overlapping keys using union (using unionWith)
• [x] outN should be undefined (rather than empty) if α $\notin g$
• [ ] Related to last point: singleton needs to have a key for every neighbour as well (mapping to the empty set)
• [ ] Idiomatically you can write \node -> (Tuple v node) as (Tuple v _)
• [x] derive instance Newtype Vertex _ will give you unwrap
• [x] File is missing closing line terminator

[rolyp]

Hi @JosephBond. A summary of what I can see as the remaining outstanding implementation tasks; then I think you’re good to close off this issue and move onto #639 and #638. (I agree it would be good to start thinking about performance testing too, but starting on slicing will be exciting and will also thrash out remaining issues with the Graph interface!)

• [x] Delete redundant definitions (e.g. unwrap, AnnGraph, allEdges, adjEdges and reverseEdges)
• [x] Finalise inStar/outStar implementations (either foldl with SM.insert rather than unionWith union, or use SM.fromFoldable)
• [x] outN is probably preferable to getOutN for the name of the class method; the local variables outN and inN could be renamed to out and in_ or similar