Create a better interface for the "graph object"

[recursion-ninja]

Issue by recursion-ninja Monday Mar 27, 2017 at 18:40 GMT Originally opened as https://github.com/ima-hima/PCG/issues/14

---

We should probably have separate interfaces for manipulating the "data matrix" of the graph and the topology of the graph. Should probably be designed by committee to elicit API requirements and then refactored in secret to actually work and be beautiful.

[recursion-ninja]

Graph operations:

• Get leaf set: DAGGraph -> NonEmpty Node

• Get root set: DAGGraph -> NonEmpty Node

  • Get node set: DAGGraph -> NonEmpty Node

  • Get edge set: DAGGraph -> NonEmpty Edge

  • Get node set: DAGGraph -> NonEmpty Node

  • Get children: DAGGraph -> [Node]

  • Get parents: DAGGraph -> [Node]

  • Get incident edges: DAGGraph -> [Edge]

  • Remove edge: Edge -> DAGForest -> DAGForest

  • Join Graph Objects (directed): Node/Edge -> Node/Edge -> DAGForest -> DAGForest

  • Get node data: Node -> DAGGraph e n -> n

  • Get edge data: Edge -> DAGGraph e n -> e

  • Get column: DAGGraph e n -> Word -> Vector (Block e n))

  • Get block summary: DAGGraph e n -> CharSeq (Block e n))

  • Post-order traversal: (n -> n') -> DAGGraph e n -> DAGGraph e n'

  • Pre-order traversal: (n -> n') -> DAGGraph e n -> DAGGraph e n'

[recursion-ninja]

Note that is if the leaf nodes are placed at vector indices [0, n-1] then we can reused the BitVector representations of the leafset of a sub tree between graph rearrangements without worrying about the BitVector indices falling out of sync with the rest of the data structure.

[Boarders]

One initial idea for an interface using associated types is something like:

class DAGGraph g n where
  type Node g      :: *
  type Edge g      :: *
  type DAGForest g  :: *
  type EdgeData g   :: *

  getLeafSet       :: g -> NonEmpty (Node g)
  getRootSet       :: g -> NonEmpty (Node g)
  getNodeSet       :: g -> NonEmpty (Node g)
  getEdgeSet       :: g -> NonEmpty (Edge g)
  getChildren      :: g -> Node g -> [Node g]
  getParents       :: g -> Node g -> [Node g]
  getIncidentEdges :: g -> Node g -> [Edge g]
  getNodeData      :: Node g -> g -> n
  getEdgeData      :: Edge g -> g -> EdgeData g
  getColumn        :: g -> Word -> Vector (Block (EdgeData g) n)
  getBlockSummary  :: g -> CharSeq (Block (EdgeData g) n)

  removeEdge :: Edge g -> DAGForest g -> DAGForest g
  joinGraphObjects
    :: Either (Node g) (Edge g)
    -> Either (Node g) (Edge g)
    -> DAGForest g
    -> DAGForest g

  postorderTraversal :: (n -> n') -> g -> DAGGraph (EdgeData g) n'
  preorderTraversal  :: (n -> n') -> g -> DAGGraph (EdgeData g) n'

I'm not sure how that fits with the above ideas in terms of indexing or using type families so I don't know how useful it is as a starting point.