Enable lookup in Data.Graph.Inductive.NodeMap

[jchia]

NodeMap only allows insertion of nodes with automatic duplicate prevention. It does not support checking whether a node exists or reporting whether mkNode actually created a new node, though this feature should be easy to add.

Some graph construction algorithms involve inserting some initial nodes to an empty graph and operating recursively on newly-inserted nodes, where the recursion generates additional nodes to insert. If a generated node already exists in the graph, the algorithm does not recurse into it, so the algorithm needs to know whether a generated node already exists.

NodeMap doesn't support this use case. It can be supported by a variant of mkNode that additionally returns a boolean indicating whether the node already existed or was newly inserted. Another approach is to add a lookupNode function, which though more general, may be less performant because then when processing a new node (not yet inserted into the graph) there will be two lookups instead of one, one lookup from lookupNode and one lookup from mkNode.

[jchia]

I meant insMapNode, not mkNode.

[ivan-m]

I've never touched NodeMap myself, and can make no promises about when I might work on it. Pull requests accepted!

[cdupont]

I also need a way to look up a Node's context in a graph, using its label... So I thought that NodeMap might help. I was thinking:

1. find the node attached to the label in a NodeMap
2. find the context of that node.

Unfortunately, the constructors of NodeMap (called "map" and "key") are nor exposed: https://hackage.haskell.org/package/fgl-5.7.0.3/docs/src/Data.Graph.Inductive.NodeMap.html#NodeMap So I cannot lookup in the map.

[Montmorency]

Same issue. Would a pull request to expose the NodeMap Constructor be welcomed? The type is exported but not the constructor.

Functions like mkMapGraph return a tuple (Gr a b, NodeMap) but we can't deconstruct NodeMap to access the map to fetch a node from a label.