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

Ivan Lazar Miljenovic ivan.miljenovic at gmail.com
Thu Aug 6 22:41:41 UTC 2015

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 <jeffbrown.the at gmail.com> 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 at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

Ivan Lazar Miljenovic
Ivan.Miljenovic at gmail.com

More information about the Haskell-Cafe mailing list