[Haskell-cafe] A composable, local graph representation as an open discussion

[David Rogers]

On 10/24/16 6:49 PM, Ivan Lazar Miljenovic wrote:
> On 24 October 2016 at 23:56, David Rogers <predictivestatmech at gmail.com> wrote:
>> Haskell-Cafe:
>>
>>    I have been working on the following idea, and would appreciate
>> any comments on the novelty or usefulness in your own applications.
>> A scan of the usual Haskell documents turns up lots of clever data
>> structures, but nothing particularly enlightening for graphs.
>> Here is my attempt:
> I haven't looked through your entire email in detail, but from a quick
> skim there's a few interesting ideas I want to play with.
>
>>    Graphs are difficult to represent in functional languages
>> because they express arbitrary undirected connectivity between nodes,
>> whereas functional code naturally expresses directed trees.
>>
>>    Most functional algorithms for graphs use an edge-list
>> with global labels.  Although effective, this method
>> loses compositionality and does not exploit the type system
>> for enforcing graph invariants such as consistency of the edge list.
>>
>>    This note presents a functional method for constructing
>> a local representation for undirected graphs functionally as
>> compositions of other graphs.  The resulting data structure
>> does not use unique node labels,
>  From practice, I've found that unique node labels are extremely
> important/useful; so are unique edge labels.  As such, this means that
> this representation may not be sufficient for general graph
> processing.
   I started with a version of the code that generates sequential node 
numbers.  It requires 2 changes.  First, the Grph structure has to store 
a count of total internal nodes.  Second, the run and env functions must 
pass the starting number to each sub-graph.  It's easy to see that this 
generates sequential numbers, since the run function does a 
tree-traversal down to the nodes, and the number of internal nodes is 
known for each subgraph.

~ David