[Haskell-cafe] A composable, local graph representation as an open discussion
predictivestatmech at gmail.com
Tue Oct 25 13:44:50 UTC 2016
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:
>> 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
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.
More information about the Haskell-Cafe