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 )
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)
Change History (18)
comment:1 Changed 9 years ago by
- Report Upstream set to N/A
- Status changed from new to needs_review
comment:2 Changed 9 years ago by
- 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
Indeed. Fixed :-)
Nathann
comment:4 Changed 9 years ago by
- Description modified (diff)
comment:5 Changed 9 years ago by
- Description modified (diff)
I just applied this patch on top of #7608, and there was nothing wrong to report :-)
comment:6 follow-up: ↓ 7 Changed 9 years ago by
- 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
... 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
- Status changed from needs_work to needs_review
What about this ? :-)
Nathann
comment:9 Changed 9 years ago by
- 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: ↓ 11 Changed 9 years ago by
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
comment:11 in reply to: ↑ 10 Changed 9 years ago by
- 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
- Status changed from needs_review to positive_review
Thank youuuuuuuuuuu !!! :-)
Nathann
comment:13 Changed 9 years ago by
- Status changed from positive_review to needs_work
comment:14 Changed 9 years ago by
- Status changed from needs_work to needs_review
comment:15 Changed 9 years ago by
- Status changed from needs_review to positive_review
wrong alert, positive review ! :-)
Nathann
comment:16 Changed 9 years ago by
- Merged in set to sage-4.5.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
Here it is !!!
Nathann