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

On 24 October 2016 at 23:56, David Rogers 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

On 10/24/16 6:49 PM, Ivan Lazar Miljenovic wrote: 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