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

[Ivan Lazar Miljenovic]

On 14 August 2015 at 06:14, Jeffrey Brown <jeffbrown.the at gmail.com> wrote:
> 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.

If you're doing it as a batch, then it might be worth using emap;
otherwise, for a single edge do the same procedure: for an edge
(u,v,l), match on `u`, adjust the `(l,v)` in the fourth field of the
Context and put it back with &.

>
> On Thu, Aug 6, 2015 at 3:41 PM, Ivan Lazar Miljenovic
> <ivan.miljenovic at 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 <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
>> http://IvanMiljenovic.wordpress.com
>
>



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