Reduce dictionary lookups and Maybes in the Graph API

[ggazzi]

The API of module Graph.Graph forces frequent lookups into the association lists, which probably incurs a performance penalty. Also, its functions often return Maybes where the result could be guaranteed to exist.

In order to reduce these issues, a notion of "node context" could be introduced, which allows the user to access the incident edges of a node. This would make the lookups implicit, and the well-formedness of the graphs ensures that such lookups do not fail.

The following is a sketch of the additions/changes to Graph.Graph module

data Node n =
    Node NodeId (Maybe n)

data Edge e =
    Edge EdgeId NodeId NodeId (Maybe e)

type NodeInContext n e =
    (Node n, NodeContext n e)

type EdgeInContext n e =
    (NodeInContext n e, Edge e, NodeInContext n e)

-- The constructor for NodeContext is not exported.
data NodeContext n e =
    NodeContext NodeId (Graph n e)

lookupNodeInContext :: NodeId -> Graph n e -> Maybe (NodeContext n e)

incidentEdges :: NodeContext -> [EdgeInContext n e]

incomingEdges :: NodeContext -> [EdgeInContext n e]

outgoingEdges :: NodeContext -> [EdgeInContext n e]

As an example of usage, this is an implementation of depth-first search using the contexts.

depthFirstSearch :: NodeInContext n e -> [Node n]
depthFirstSearch initialNode =
    search IntSet.empty [initialNode]
    
  where
    search _ [] = []
    
    search visitedNodes ((node, context) : rest) =
      if node `IntSet.member` visitedNodes then
        search visitedNodes rest
      else 
        let
          nextNodes =
            [ target | (_, _, target) <- outgoingEdges context ]
              
        in
          node :: search (IntSet.insert (nodeId node) visitedNodes) (nextNodes ++ rest)

[ggazzi]

Now that the alternatives were added, should we deprecate the functions nodesOf, sourceOf, sourceOfUnsafe, targetOf, targetOfUnsafe and getIncidentEdges, which perform explicit lookups?

[jsbezerra]

I think it is the best approach, but gradually and at a new branch.

[lm-rodrigues]

I think that @jsbezerra's strategy is a good choice 😄

[ggazzi]

Solved and merged into master.