functional graphs

General techniques are described here:
http://www.cs.cmu.edu/~sleator/papers/making-data-structures-persistent.pdf

But for the case of a general graph, anything will going to be very
slow. With node copying, you can easily end up copying the entire graph
for each update. Fat nodes (explained in paper) would slow down the
graph more and more for each operation. An observation on various work
on pointer-based persistent data structures is this: the less the bound
on incoming pointers for any node, the better. (And in a graph, a node
can have up to N incoming edges, and you may also allow parallel
edges.....). This is why persistence is quite easy on top-down trees,
the in-degree of nodes is at most 1.

On a side note, in a graph framework I developed (sorry for the
self-plug: http://www.csd.uoc.gr/~andreou/flexigraph
), I chose to remove
navigational (and node degrees) functionality from nodes, so they can be
shared amongs graphs. Otherwise when you work with subgraphs, you will
have to maintain lots and lots of node mappings between graphs, to go
from a node in one graph to the "same" node in another. In any case, I
would recommend to first think about the use cases you want to support,
and only under these design restrictions search "for an OO way" to
design it. Doing it the other way you may end up artificially reducing
functionality you didn't mean to.

Dimitris

O/H Avi Pfeffer έγραψε:
> Hi all,
>
> I have a beginner question on being functional with inter-related
> objects. Apologies if this is a FAQ.
>
> I want to create functional graphs. I have a Graph class and a Node
> class. A graph contains nodes, and nodes need to access the graph that
> contains them, e.g. to get their parent set. When I modify the graph,
> say by adding an edge, I create a new graph. However all the nodes
> will still refer to the stale graph. It seems I have to reconstruct
> all the nodes with the new graph, which is inefficient. The only thing
> I can think of is to take all the functionality out of nodes, and put
> it in the Graph class, but that is not very object-oriented. Is there
> a good way to deal with this?
>
> Thanks,
> Avi
>
>

(Duh, Murphy's law, you post a link, and just in time the web server
goes down. In case you'd like to peek, this works:
http://139.91.183.8:3026/hudson/job/FlexiGraph/)

O/H Dimitris Andreou έγραψε:
> General techniques are described here:
> http://www.cs.cmu.edu/~sleator/papers/making-data-structures-persistent.pdf
>
>
> But for the case of a general graph, anything will going to be very
> slow. With node copying, you can easily end up copying the entire
> graph for each update. Fat nodes (explained in paper) would slow down
> the graph more and more for each operation. An observation on various
> work on pointer-based persistent data structures is this: the less the
> bound on incoming pointers for any node, the better. (And in a graph,
> a node can have up to N incoming edges, and you may also allow
> parallel edges.....). This is why persistence is quite easy on
> top-down trees, the in-degree of nodes is at most 1.
>
> On a side note, in a graph framework I developed (sorry for the
> self-plug: http://www.csd.uoc.gr/~andreou/flexigraph
> ), I chose to remove
> navigational (and node degrees) functionality from nodes, so they can
> be shared amongs graphs. Otherwise when you work with subgraphs, you
> will have to maintain lots and lots of node mappings between graphs,
> to go from a node in one graph to the "same" node in another. In any
> case, I would recommend to first think about the use cases you want to
> support, and only under these design restrictions search "for an OO
> way" to design it. Doing it the other way you may end up artificially
> reducing functionality you didn't mean to.
>
> Dimitris
>
> O/H Avi Pfeffer έγραψε:
>> Hi all,
>>
>> I have a beginner question on being functional with inter-related
>> objects. Apologies if this is a FAQ.
>>
>> I want to create functional graphs. I have a Graph class and a Node
>> class. A graph contains nodes, and nodes need to access the graph that
>> contains them, e.g. to get their parent set. When I modify the graph,
>> say by adding an edge, I create a new graph. However all the nodes
>> will still refer to the stale graph. It seems I have to reconstruct
>> all the nodes with the new graph, which is inefficient. The only thing
>> I can think of is to take all the functionality out of nodes, and put
>> it in the Graph class, but that is not very object-oriented. Is there
>> a good way to deal with this?
>>
>> Thanks,
>> Avi
>>
>>
>
>

I guess this is not a good design solution if nodes know to which structure they belong. Imagine you want to build a subgraph, then what? Have a list of graphs to which a node belongs? I'd suggest never to reference the container.

2009/3/16 Avi Pfeffer <avi@eecs.harvard.edu>

Hi all,

I have a beginner question on being functional with inter-related
objects. Apologies if this is a FAQ.

I want to create functional graphs. I have a Graph class and a Node
class. A graph contains nodes, and nodes need to access the graph that
contains them, e.g. to get their parent set. When I modify the graph,
say by adding an edge, I create a new graph. However all the nodes
will still refer to the stale graph. It seems I have to reconstruct
all the nodes with the new graph, which is inefficient. The only thing
I can think of is to take all the functionality out of nodes, and put
it in the Graph class, but that is not very object-oriented. Is there
a good way to deal with this?

Thanks,
 Avi

--
Thanks,
-Vlad

Zippers (http://en.wikibooks.org/wiki/Haskell/Zippers) work well for
functional reuse of graphs. Unfortunately they dont lend themselves
to any approach where each node must know all about itself (like a DOM
node for example).

The simplest approach I could find was to do child only relationships
and maintain a seperate map of child to parent. The map still needs
to be updated for each operation, but it should be less costly (only
to the top graph node) than updating an entire sub tree for parent
changes, however the cost for adding child trees was still significant
enough (out of one cost into another).

I can't say I got far with either approach however, but the zippers
are really elegant and allow alot of graph re-use. Perhaps the "or"
post from earlier in the lists can help modelling the data structure
in scala.

On Mon, Mar 16, 2009 at 7:20 PM, Vlad Patryshev wrote:
> I guess this is not a good design solution if nodes know to which structure
> they belong. Imagine you want to build a subgraph, then what? Have a list of
> graphs to which a node belongs? I'd suggest never to reference the
> container.
>
> 2009/3/16 Avi Pfeffer
>>
>> Hi all,
>>
>> I have a beginner question on being functional with inter-related
>> objects. Apologies if this is a FAQ.
>>
>> I want to create functional graphs. I have a Graph class and a Node
>> class. A graph contains nodes, and nodes need to access the graph that
>> contains them, e.g. to get their parent set. When I modify the graph,
>> say by adding an edge, I create a new graph. However all the nodes
>> will still refer to the stale graph. It seems I have to reconstruct
>> all the nodes with the new graph, which is inefficient. The only thing
>> I can think of is to take all the functionality out of nodes, and put
>> it in the Graph class, but that is not very object-oriented. Is there
>> a good way to deal with this?
>>
>> Thanks,
>>  Avi
>
>
>
> --
> Thanks,
> -Vlad
>

From a cursory look (strange page btw), it seems that zippers weren't
meant for general graphs but only for trees. I fail to see how zippers
could be used to reuse any substructure of a graph that is, for example,
a strongly connected component. In such a graph, any update would incur
a full copy of all existing/remaining edges, or do I miss something?

O/H Chris Twiner έγραψε:
> Zippers (http://en.wikibooks.org/wiki/Haskell/Zippers) work well for
> functional reuse of graphs. Unfortunately they dont lend themselves
> to any approach where each node must know all about itself (like a DOM
> node for example).
>
> The simplest approach I could find was to do child only relationships
> and maintain a seperate map of child to parent. The map still needs
> to be updated for each operation, but it should be less costly (only
> to the top graph node) than updating an entire sub tree for parent
> changes, however the cost for adding child trees was still significant
> enough (out of one cost into another).
>
> I can't say I got far with either approach however, but the zippers
> are really elegant and allow alot of graph re-use. Perhaps the "or"
> post from earlier in the lists can help modelling the data structure
> in scala.
>
> On Mon, Mar 16, 2009 at 7:20 PM, Vlad Patryshev wrote:
>
>> I guess this is not a good design solution if nodes know to which structure
>> they belong. Imagine you want to build a subgraph, then what? Have a list of
>> graphs to which a node belongs? I'd suggest never to reference the
>> container.
>>
>> 2009/3/16 Avi Pfeffer
>>
>>> Hi all,
>>>
>>> I have a beginner question on being functional with inter-related
>>> objects. Apologies if this is a FAQ.
>>>
>>> I want to create functional graphs. I have a Graph class and a Node
>>> class. A graph contains nodes, and nodes need to access the graph that
>>> contains them, e.g. to get their parent set. When I modify the graph,
>>> say by adding an edge, I create a new graph. However all the nodes
>>> will still refer to the stale graph. It seems I have to reconstruct
>>> all the nodes with the new graph, which is inefficient. The only thing
>>> I can think of is to take all the functionality out of nodes, and put
>>> it in the Graph class, but that is not very object-oriented. Is there
>>> a good way to deal with this?
>>>
>>> Thanks,
>>> �Avi
>>>
>>
>> --
>> Thanks,
>> -Vlad
>>
>>
>
>

The structure itself manages the relations, you rotate the structure
to the required point, split it, and zip with new nodes. No copying
should take place but for the place you splice. I think that XMonad
is perhaps the best known example of it.

http://www.st.cs.uni-sb.de/edu/seminare/2005/advanced-fp/docs/huet-zippe...
and
http://cgi.cse.unsw.edu.au/~dons/blog/2007/05/17

are less convoluted to read.

On Mon, Mar 16, 2009 at 9:38 PM, Dimitris Andreou wrote:
> From a cursory look (strange page btw), it seems that zippers weren't meant
> for general graphs but only for trees. I fail to see how zippers could be
> used to reuse any substructure of a graph that is, for example, a strongly
> connected component. In such a graph, any update would incur a full copy of
> all existing/remaining edges, or do I miss something?
>
> O/H Chris Twiner έγραψε:
>>
>> Zippers (http://en.wikibooks.org/wiki/Haskell/Zippers) work well for
>> functional reuse of graphs.  Unfortunately they dont lend themselves
>> to any approach where each node must know all about itself (like a DOM
>> node for example).
>>
>> The simplest approach I could find was to do child only relationships
>> and maintain a seperate map of child to parent.  The map still needs
>> to be updated for each operation, but it should be less costly (only
>> to the top graph node) than updating an entire sub tree for parent
>> changes, however the cost for adding child trees was still significant
>> enough (out of one cost into another).
>>
>> I can't say I got far with either approach however, but the zippers
>> are really elegant and allow alot of graph re-use.  Perhaps the "or"
>> post from earlier in the lists can help modelling the data structure
>> in scala.
>>
>> On Mon, Mar 16, 2009 at 7:20 PM, Vlad Patryshev
>> wrote:
>>
>>>
>>> I guess this is not a good design solution if nodes know to which
>>> structure
>>> they belong. Imagine you want to build a subgraph, then what? Have a list
>>> of
>>> graphs to which a node belongs? I'd suggest never to reference the
>>> container.
>>>
>>> 2009/3/16 Avi Pfeffer
>>>
>>>>
>>>> Hi all,
>>>>
>>>> I have a beginner question on being functional with inter-related
>>>> objects. Apologies if this is a FAQ.
>>>>
>>>> I want to create functional graphs. I have a Graph class and a Node
>>>> class. A graph contains nodes, and nodes need to access the graph that
>>>> contains them, e.g. to get their parent set. When I modify the graph,
>>>> say by adding an edge, I create a new graph. However all the nodes
>>>> will still refer to the stale graph. It seems I have to reconstruct
>>>> all the nodes with the new graph, which is inefficient. The only thing
>>>> I can think of is to take all the functionality out of nodes, and put
>>>> it in the Graph class, but that is not very object-oriented. Is there
>>>> a good way to deal with this?
>>>>
>>>> Thanks,
>>>> �Avi
>>>>
>>>
>>> --
>>> Thanks,
>>> -Vlad
>>>
>>>
>>
>>
>
>

By the way, how would you compare FlexiGraph to Prefuse and Jung?

On Mon, Mar 16, 2009 at 2:19 PM, Andreou Dimitris <jim.andreou@gmail.com> wrote:

(Duh, Murphy's law, you post a link, and just in time the web server goes down. In case you'd like to peek, this works: http://139.91.183.8:3026/hudson/job/FlexiGraph/)

O/H Dimitris Andreou έγραψε:

General techniques are described here:
http://www.cs.cmu.edu/~sleator/papers/making-data-structures-persistent.pdf

But for the case of a general graph, anything will going to be very slow. With node copying, you can easily end up copying the entire graph for each update. Fat nodes (explained in paper) would slow down the graph more and more for each operation. An observation on various work on pointer-based persistent data structures is this: the less the bound on incoming pointers for any node, the better. (And in a graph, a node can have up to N incoming edges, and you may also allow parallel edges.....). This is why persistence is quite easy on top-down trees, the in-degree of nodes is at most 1.

On a side note, in a graph framework I developed (sorry for the self-plug: http://www.csd.uoc.gr/~andreou/flexigraph <http://www.csd.uoc.gr/%7Eandreou/flexigraph> ), I chose to remove navigational (and node degrees) functionality from nodes, so they can be shared amongs graphs. Otherwise when you work with subgraphs, you will have to maintain lots and lots of node mappings between graphs, to go from a node in one graph to the "same" node in another. In any case, I would recommend to first think about the use cases you want to support, and only under these design restrictions search "for an OO way" to design it. Doing it the other way you may end up artificially reducing functionality you didn't mean to.

Dimitris

O/H Avi Pfeffer έγραψε:

Hi all,

I have a beginner question on being functional with inter-related
objects. Apologies if this is a FAQ.

I want to create functional graphs. I have a Graph class and a Node
class. A graph contains nodes, and nodes need to access the graph that
contains them, e.g. to get their parent set. When I modify the graph,
say by adding an edge, I create a new graph. However all the nodes
will still refer to the stale graph. It seems I have to reconstruct
all the nodes with the new graph, which is inefficient. The only thing
I can think of is to take all the functionality out of nodes, and put
it in the Graph class, but that is not very object-oriented. Is there
a good way to deal with this?

Thanks,
 Avi

 

I'm afraid I have to repeat my question: are you talking about *trees*
or about *graphs*? The original poster talked about graphs. In your
links I see "tree" being mentioned several tens of times, while "graph"
only one (a vague "graph editor" reference actually), so I think there
is a confusion here. Many efficient functional (persistent) tree data
structures indeed exist, but none for graphs as far as I know.

O/H Chris Twiner έγραψε:
> The structure itself manages the relations, you rotate the structure
> to the required point, split it, and zip with new nodes. No copying
> should take place but for the place you splice. I think that XMonad
> is perhaps the best known example of it.
>
> http://www.st.cs.uni-sb.de/edu/seminare/2005/advanced-fp/docs/huet-zippe...
> and
> http://cgi.cse.unsw.edu.au/~dons/blog/2007/05/17
>
> are less convoluted to read.
>
> On Mon, Mar 16, 2009 at 9:38 PM, Dimitris Andreou wrote:
>
>> From a cursory look (strange page btw), it seems that zippers weren't meant
>> for general graphs but only for trees. I fail to see how zippers could be
>> used to reuse any substructure of a graph that is, for example, a strongly
>> connected component. In such a graph, any update would incur a full copy of
>> all existing/remaining edges, or do I miss something?
>>
>> O/H Chris Twiner έγραψε:
>>
>>> Zippers (http://en.wikibooks.org/wiki/Haskell/Zippers) work well for
>>> functional reuse of graphs. Unfortunately they dont lend themselves
>>> to any approach where each node must know all about itself (like a DOM
>>> node for example).
>>>
>>> The simplest approach I could find was to do child only relationships
>>> and maintain a seperate map of child to parent. The map still needs
>>> to be updated for each operation, but it should be less costly (only
>>> to the top graph node) than updating an entire sub tree for parent
>>> changes, however the cost for adding child trees was still significant
>>> enough (out of one cost into another).
>>>
>>> I can't say I got far with either approach however, but the zippers
>>> are really elegant and allow alot of graph re-use. Perhaps the "or"
>>> post from earlier in the lists can help modelling the data structure
>>> in scala.
>>>
>>> On Mon, Mar 16, 2009 at 7:20 PM, Vlad Patryshev
>>> wrote:
>>>
>>>
>>>> I guess this is not a good design solution if nodes know to which
>>>> structure
>>>> they belong. Imagine you want to build a subgraph, then what? Have a list
>>>> of
>>>> graphs to which a node belongs? I'd suggest never to reference the
>>>> container.
>>>>
>>>> 2009/3/16 Avi Pfeffer
>>>>
>>>>
>>>>> Hi all,
>>>>>
>>>>> I have a beginner question on being functional with inter-related
>>>>> objects. Apologies if this is a FAQ.
>>>>>
>>>>> I want to create functional graphs. I have a Graph class and a Node
>>>>> class. A graph contains nodes, and nodes need to access the graph that
>>>>> contains them, e.g. to get their parent set. When I modify the graph,
>>>>> say by adding an edge, I create a new graph. However all the nodes
>>>>> will still refer to the stale graph. It seems I have to reconstruct
>>>>> all the nodes with the new graph, which is inefficient. The only thing
>>>>> I can think of is to take all the functionality out of nodes, and put
>>>>> it in the Graph class, but that is not very object-oriented. Is there
>>>>> a good way to deal with this?
>>>>>
>>>>> Thanks,
>>>>> �Avi
>>>>>
>>>>>
>>>> --
>>>> Thanks,
>>>> -Vlad
>>>>
>>>>
>>>>
>>>
>>
>
>

I *know* that the approach works for trees, I suspect it or something
like it may come close to being used for adg but I've no evidence of
it other than similar graph editors. As I said I haven't got that far
with them.

I would suspect however that asking these questions to purely
functional programming lists / groups / sites may gain more responses.

On Mon, Mar 16, 2009 at 10:13 PM, Dimitris Andreou
wrote:
> I'm afraid I have to repeat my question: are you talking about *trees* or
> about *graphs*? The original poster talked about graphs. In your links I see
> "tree" being mentioned several tens of times, while "graph" only one (a
> vague "graph editor" reference actually), so I think there is a confusion
> here. Many efficient functional (persistent) tree data structures indeed
> exist, but none for graphs as far as I know.
>
> O/H Chris Twiner έγραψε:
>>
>> The structure itself manages the relations, you rotate the structure
>> to the required point, split it, and zip with new nodes.  No copying
>> should take place but for the place you splice.  I think that XMonad
>> is perhaps the best known example of it.
>>
>>
>> http://www.st.cs.uni-sb.de/edu/seminare/2005/advanced-fp/docs/huet-zippe...
>>  and
>> http://cgi.cse.unsw.edu.au/~dons/blog/2007/05/17
>>
>> are less convoluted to read.
>>
>> On Mon, Mar 16, 2009 at 9:38 PM, Dimitris Andreou
>> wrote:
>>
>>>
>>> From a cursory look (strange page btw), it seems that zippers weren't
>>> meant
>>> for general graphs but only for trees. I fail to see how zippers could be
>>> used to reuse any substructure of a graph that is, for example, a
>>> strongly
>>> connected component. In such a graph, any update would incur a full copy
>>> of
>>> all existing/remaining edges, or do I miss something?
>>>
>>> O/H Chris Twiner έγραψε:
>>>
>>>>
>>>> Zippers (http://en.wikibooks.org/wiki/Haskell/Zippers) work well for
>>>> functional reuse of graphs.  Unfortunately they dont lend themselves
>>>> to any approach where each node must know all about itself (like a DOM
>>>> node for example).
>>>>
>>>> The simplest approach I could find was to do child only relationships
>>>> and maintain a seperate map of child to parent.  The map still needs
>>>> to be updated for each operation, but it should be less costly (only
>>>> to the top graph node) than updating an entire sub tree for parent
>>>> changes, however the cost for adding child trees was still significant
>>>> enough (out of one cost into another).
>>>>
>>>> I can't say I got far with either approach however, but the zippers
>>>> are really elegant and allow alot of graph re-use.  Perhaps the "or"
>>>> post from earlier in the lists can help modelling the data structure
>>>> in scala.
>>>>
>>>> On Mon, Mar 16, 2009 at 7:20 PM, Vlad Patryshev
>>>> wrote:
>>>>
>>>>
>>>>>
>>>>> I guess this is not a good design solution if nodes know to which
>>>>> structure
>>>>> they belong. Imagine you want to build a subgraph, then what? Have a
>>>>> list
>>>>> of
>>>>> graphs to which a node belongs? I'd suggest never to reference the
>>>>> container.
>>>>>
>>>>> 2009/3/16 Avi Pfeffer
>>>>>
>>>>>
>>>>>>
>>>>>> Hi all,
>>>>>>
>>>>>> I have a beginner question on being functional with inter-related
>>>>>> objects. Apologies if this is a FAQ.
>>>>>>
>>>>>> I want to create functional graphs. I have a Graph class and a Node
>>>>>> class. A graph contains nodes, and nodes need to access the graph that
>>>>>> contains them, e.g. to get their parent set. When I modify the graph,
>>>>>> say by adding an edge, I create a new graph. However all the nodes
>>>>>> will still refer to the stale graph. It seems I have to reconstruct
>>>>>> all the nodes with the new graph, which is inefficient. The only thing
>>>>>> I can think of is to take all the functionality out of nodes, and put
>>>>>> it in the Graph class, but that is not very object-oriented. Is there
>>>>>> a good way to deal with this?
>>>>>>
>>>>>> Thanks,
>>>>>> �Avi
>>>>>>
>>>>>>
>>>>>
>>>>> --
>>>>> Thanks,
>>>>> -Vlad
>>>>>
>>>>>
>>>>>
>>>>
>>>>
>>>
>>>
>>
>>
>
>

/off-topic

Jung is just very slow. Last time I checked (disclaimer: anecdotal
evidence) it was about 4 times slower than jdsl and 3.5 times slower
than flexigraph, and used about twice memory for graphs than both. This
slowness is apparently a failed attempt to flexibility, i.e. storing
edge lists in Map> hash tables so nodes/edges can
be shared in multiple graphs - I achieve the same flexibility much more
cheaply (also, curious is the fact that the above representation is used
especially for *sparse* graphs, where in fact it's one of the worst
representations for especially sparse graphs). I also find its api
design way too complicated for what it offers - I'm pretty confident
that any algorithm in jung can be expressed at about half the code in
flexigraph, while the latter has a far less api surface.

On the other hand though, Jung is much more comprehensive where it comes
to off-the-self algorithms (surely on of the larger I recall), and also
offers some visualization system, where flexigraph does not. So, for
most applications needing certain algorithms and visualization, jung is
by all means the better choice. If one is after performance, jdsl and
flexigraph and is a good choice (perhaps the former, for the absolute
performance, if one can tolerate a quite significant inflexibility and
high probability of memory leaks without care). The ratio of jdsl code
to flexigraph code is still about 2:1 (I ported several algorithms from
jdsl actually). This leaves flexigraph the niche of developing fast
algorithms (but not the fastest around), for the gain of much higher
flexibility, which can more easily tackle complex algorithms.

I have no experience with Prefuse, I can't comment on that.

I can also add that the two commercial graph toolkits out there, Tom
Sawyer and yWorks, are both quite inferior from a design prespective (I
pointed quite a few major flaws both to yWorks and to TS engineers in
interviews, and both camps attributed them to their inability to fix
their initial design due to customers).

As a bottom line, I can't recommend flexigraph too seriously as of now,
due to the poorer state of documentation with respect to these other
packages (but researchers should cope with that just fine :)). But
anyone should feel free to play with all available libraries and see for
himself which fits his needs best.

Dimitris

O/H Naftoli Gugenheim έγραψε:
> By the way, how would you compare FlexiGraph to Prefuse and Jung?
>
> On Mon, Mar 16, 2009 at 2:19 PM, Andreou Dimitris
> > wrote:
>
> (Duh, Murphy's law, you post a link, and just in time the web
> server goes down. In case you'd like to peek, this works:
> http://139.91.183.8:3026/hudson/job/FlexiGraph/)
>
> O/H Dimitris Andreou ������:
>
> General techniques are described here:
> http://www.cs.cmu.edu/~sleator/papers/making-data-structures-persistent.pdf
>
>
>
> But for the case of a general graph, anything will going to be
> very slow. With node copying, you can easily end up copying
> the entire graph for each update. Fat nodes (explained in
> paper) would slow down the graph more and more for each
> operation. An observation on various work on pointer-based
> persistent data structures is this: the less the bound on
> incoming pointers for any node, the better. (And in a graph, a
> node can have up to N incoming edges, and you may also allow
> parallel edges.....). This is why persistence is quite easy on
> top-down trees, the in-degree of nodes is at most 1.
>
> On a side note, in a graph framework I developed (sorry for
> the self-plug: http://www.csd.uoc.gr/~andreou/flexigraph
>
> ), I chose to
> remove navigational (and node degrees) functionality from
> nodes, so they can be shared amongs graphs. Otherwise when you
> work with subgraphs, you will have to maintain lots and lots
> of node mappings between graphs, to go from a node in one
> graph to the "same" node in another. In any case, I would
> recommend to first think about the use cases you want to
> support, and only under these design restrictions search "for
> an OO way" to design it. Doing it the other way you may end up
> artificially reducing functionality you didn't mean to.
>
> Dimitris
>
> O/H Avi Pfeffer ������:
>
> Hi all,
>
> I have a beginner question on being functional with
> inter-related
> objects. Apologies if this is a FAQ.
>
> I want to create functional graphs. I have a Graph class
> and a Node
> class. A graph contains nodes, and nodes need to access
> the graph that
> contains them, e.g. to get their parent set. When I modify
> the graph,
> say by adding an edge, I create a new graph. However all
> the nodes
> will still refer to the stale graph. It seems I have to
> reconstruct
> all the nodes with the new graph, which is inefficient.
> The only thing
> I can think of is to take all the functionality out of
> nodes, and put
> it in the Graph class, but that is not very
> object-oriented. Is there
> a good way to deal with this?
>
> Thanks,
> �Avi
>
> �
>
>
>
>
>

This suspicion regarding dags indeed seems more plausible, interesting
problem.

O/H Chris Twiner έγραψε:
> I *know* that the approach works for trees, I suspect it or something
> like it may come close to being used for adg but I've no evidence of
> it other than similar graph editors. As I said I haven't got that far
> with them.
>
> I would suspect however that asking these questions to purely
> functional programming lists / groups / sites may gain more responses.
>
> On Mon, Mar 16, 2009 at 10:13 PM, Dimitris Andreou
> wrote:
>
>> I'm afraid I have to repeat my question: are you talking about *trees* or
>> about *graphs*? The original poster talked about graphs. In your links I see
>> "tree" being mentioned several tens of times, while "graph" only one (a
>> vague "graph editor" reference actually), so I think there is a confusion
>> here. Many efficient functional (persistent) tree data structures indeed
>> exist, but none for graphs as far as I know.
>>
>> O/H Chris Twiner έγραψε:
>>
>>> The structure itself manages the relations, you rotate the structure
>>> to the required point, split it, and zip with new nodes. No copying
>>> should take place but for the place you splice. I think that XMonad
>>> is perhaps the best known example of it.
>>>
>>>
>>> http://www.st.cs.uni-sb.de/edu/seminare/2005/advanced-fp/docs/huet-zippe...
>>> and
>>> http://cgi.cse.unsw.edu.au/~dons/blog/2007/05/17
>>>
>>> are less convoluted to read.
>>>
>>> On Mon, Mar 16, 2009 at 9:38 PM, Dimitris Andreou
>>> wrote:
>>>
>>>
>>>> From a cursory look (strange page btw), it seems that zippers weren't
>>>> meant
>>>> for general graphs but only for trees. I fail to see how zippers could be
>>>> used to reuse any substructure of a graph that is, for example, a
>>>> strongly
>>>> connected component. In such a graph, any update would incur a full copy
>>>> of
>>>> all existing/remaining edges, or do I miss something?
>>>>
>>>> O/H Chris Twiner έγραψε:
>>>>
>>>>
>>>>> Zippers (http://en.wikibooks.org/wiki/Haskell/Zippers) work well for
>>>>> functional reuse of graphs. Unfortunately they dont lend themselves
>>>>> to any approach where each node must know all about itself (like a DOM
>>>>> node for example).
>>>>>
>>>>> The simplest approach I could find was to do child only relationships
>>>>> and maintain a seperate map of child to parent. The map still needs
>>>>> to be updated for each operation, but it should be less costly (only
>>>>> to the top graph node) than updating an entire sub tree for parent
>>>>> changes, however the cost for adding child trees was still significant
>>>>> enough (out of one cost into another).
>>>>>
>>>>> I can't say I got far with either approach however, but the zippers
>>>>> are really elegant and allow alot of graph re-use. Perhaps the "or"
>>>>> post from earlier in the lists can help modelling the data structure
>>>>> in scala.
>>>>>
>>>>> On Mon, Mar 16, 2009 at 7:20 PM, Vlad Patryshev
>>>>> wrote:
>>>>>
>>>>>
>>>>>
>>>>>> I guess this is not a good design solution if nodes know to which
>>>>>> structure
>>>>>> they belong. Imagine you want to build a subgraph, then what? Have a
>>>>>> list
>>>>>> of
>>>>>> graphs to which a node belongs? I'd suggest never to reference the
>>>>>> container.
>>>>>>
>>>>>> 2009/3/16 Avi Pfeffer
>>>>>>
>>>>>>
>>>>>>
>>>>>>> Hi all,
>>>>>>>
>>>>>>> I have a beginner question on being functional with inter-related
>>>>>>> objects. Apologies if this is a FAQ.
>>>>>>>
>>>>>>> I want to create functional graphs. I have a Graph class and a Node
>>>>>>> class. A graph contains nodes, and nodes need to access the graph that
>>>>>>> contains them, e.g. to get their parent set. When I modify the graph,
>>>>>>> say by adding an edge, I create a new graph. However all the nodes
>>>>>>> will still refer to the stale graph. It seems I have to reconstruct
>>>>>>> all the nodes with the new graph, which is inefficient. The only thing
>>>>>>> I can think of is to take all the functionality out of nodes, and put
>>>>>>> it in the Graph class, but that is not very object-oriented. Is there
>>>>>>> a good way to deal with this?
>>>>>>>
>>>>>>> Thanks,
>>>>>>> �Avi
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>> --
>>>>>> Thanks,
>>>>>> -Vlad
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>
>>>
>>
>
>