FGL: The cost and propoer way of changing the label at a node.

newer
Folding part of a graph, and FGL's...

older
Internship Opportunity at Galois:...

Jeffrey Brown

6 Aug 2015 6 Aug '15

6:29 p.m.

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?

Attachments:

attachment.html (text/html — 756 bytes)

Show replies by date

Ivan Lazar Miljenovic

6 Aug 6 Aug

6:41 p.m.

New subject: FGL: The cost and propoer way of changing the label at a node.

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

Jeffrey Brown

13 Aug 13 Aug

4:14 p.m.

New subject: 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

Ivan Lazar Miljenovic

5:58 p.m.

New subject: FGL: The cost and propoer way of changing the label at a node.

On 14 August 2015 at 06:14, Jeffrey Brown 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 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

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

Jeffrey Brown

6:03 p.m.

New subject: FGL: The cost and propoer way of changing the label at a node.

Right, of course! Thanks again, Ivan! On Thu, Aug 13, 2015 at 2:58 PM, Ivan Lazar Miljenovic < ivan.miljenovic@gmail.com> wrote:

...

On 14 August 2015 at 06:14, Jeffrey Brown 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 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

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

3570

Age (days ago)

3577

Last active (days ago)

List overview

Download

4 comments

2 participants

participants (2)

Ivan Lazar Miljenovic
Jeffrey Brown