Subdivide edges in a graph

[ncohen]

It is often useful to subdivide the edges of a graph, so there should be a function in Sage for this.

When an edge e between u and v is subdivided in a DiGraph?, perhaps the best thing to do would be to name the new vertices as (e, 0), (e, 1), (e, 2), etc ...

We are left with a similar problem concerning the Graphs and here I have to admit I do not know which name to use without inducing some orientation..

This being said, it has to be done ! :-)

[ncohen]

Here it is !!!

Nathann

[jason]

In the docs, you say that the following are valid forms:

G.add_edge( 1, 2, 8 )

G.add_edge( (1, 2), 8 )

However, reading the code seems to indicate that it should be subdivide_edge, not add_edge.

[ncohen]

Indeed. Fixed :-)

Nathann

[ncohen]

I just applied this patch on top of #7608, and there was nothing wrong to report :-)

[rlm]

"If the given edge is labelled with l, all the edges created by the subdivision will have the same label."

... You should also specify what happens to labels when l is not given. In addition, you should have all these cases doctested.

[rlm]

... You should also specify what happens to labels when l is not given. In addition, you should have all these cases doctested.

That said, all tests pass. So once the above is addressed, I'll probably be happy.

[ncohen]

What about this ? :-)

Nathann

[rlm]

I don't think this quite works as advertised. If I have edge (u, v, 1) and I do G.subdivide_edge((u, v, 2), 5), then the edge (u, v, 1) is never deleted.

Is the input label the new label, or the label of the existing edge?

Maybe there should be a new_label argument instead? I'm not sure the best way to approach this, and I'm interested in your opinion.

[ncohen]

Oh... The behaviour I had in mind was rather to raise an ValueError? excetion saying : edge(u,v,2) does not exist. I really think of this as a topological method, so the user is expected to relabel his edges later if there is any need of it. I really wanted the edge to be "split" into several parts, all bearing the same label.

What would you think about it ? I'll update the patch to match this behaviour, just because it is easy to do so, though if you don't like it we can still remove it ! :-)

Nathann

[rlm]

Apply after trac_7378.patch

[rlm]

Replying to ncohen:

I really wanted the edge to be "split" into several parts, all bearing the same label.

Thanks for clarifying. I've tried to make this clear in the documentation. If you approve of my referee patch, please set the ticket to positive review.

[ncohen]

Thank youuuuuuuuuuu !!! :-)

Nathann

[ncohen]

wrong alert, positive review ! :-)

Nathann