Opened 10 years ago

Closed 9 years ago

#7378 closed enhancement (fixed)

Subdivide edges in a graph

Reported by: ncohen Owned by: jason
Priority: major Milestone: sage-4.5
Component: graph theory Keywords:
Cc: Merged in: sage-4.5.alpha1
Authors: Nathann Cohen Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by 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 ! :-)

Attachments (2)

trac_7378.patch (5.5 KB) - added by ncohen 9 years ago.
trac_7378-ref.patch (3.0 KB) - added by rlm 9 years ago.
Apply after trac_7378.patch

Download all attachments as: .zip

Change History (18)

comment:1 Changed 9 years ago by ncohen

  • Report Upstream set to N/A
  • Status changed from new to needs_review

Here it is !!!

Nathann

comment:2 Changed 9 years ago by jason

  • Owner changed from rlm to 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.

comment:3 Changed 9 years ago by ncohen

Indeed. Fixed :-)

Nathann

comment:4 Changed 9 years ago by mvngu

  • Description modified (diff)

comment:5 Changed 9 years ago by ncohen

  • Description modified (diff)

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

comment:6 follow-up: Changed 9 years ago by rlm

  • Authors set to Nathann Cohen
  • Status changed from needs_review to needs_work

"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.

comment:7 in reply to: ↑ 6 Changed 9 years ago by 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.

comment:8 Changed 9 years ago by ncohen

  • Status changed from needs_work to needs_review

What about this ? :-)

Nathann

comment:9 Changed 9 years ago by rlm

  • Status changed from needs_review to needs_work

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.

comment:10 follow-up: Changed 9 years ago by 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

Changed 9 years ago by ncohen

Changed 9 years ago by rlm

Apply after trac_7378.patch

comment:11 in reply to: ↑ 10 Changed 9 years ago by rlm

  • Reviewers set to Robert Miller
  • Status changed from needs_work to needs_review

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.

comment:12 Changed 9 years ago by ncohen

  • Status changed from needs_review to positive_review

Thank youuuuuuuuuuu !!! :-)

Nathann

comment:13 Changed 9 years ago by ncohen

  • Status changed from positive_review to needs_work

comment:14 Changed 9 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:15 Changed 9 years ago by ncohen

  • Status changed from needs_review to positive_review

wrong alert, positive review ! :-)

Nathann

comment:16 Changed 9 years ago by rlm

  • Merged in set to sage-4.5.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.