Re: [Haskell-cafe] FGL: The cost and propoer way of changing the label at a node.

What about changing an edge's label? Again all I can think of is to replace the edge with a new one, but that seems likely inefficient, particularly if I wanted to handle a lot of edges as a batch. On Thu, Aug 6, 2015 at 3:41 PM, Ivan Lazar Miljenovic < ivan.miljenovic@gmail.com> wrote:

The easiest way of changing the label of one node is to obtain its Context using `match`, and update the label in the Context and then put it back in the graph with (&).

Ignoring log factors (which are from the graph implementations, not the FGL model) this ends up being O(|degree of node|).

On 7 August 2015 at 08:29, Jeffrey Brown wrote:

...

Is changing the label at a node O(N)?

The only way I can think of to do it is with a map, like the following -- which works, but seems like its speed must be linear in the number of nodes of the graph:

...

:m Data.Graph.Inductive.Example Data.Graph.Inductive.Graph let f c@(adjIn, node, lab, adjOut) = case node of {1 -> (adjIn, node, 'b', adjOut); _ -> c} loop mkGraph [(1,'a')] [(1,1,())] gmap f loop mkGraph [(1,'b')] [(1,1,())]

Is that in fact the right way? Am I somehow missing the point of FGL if I have to do a lot of that?

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

-- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com