Opened 10 years ago
Closed 10 years ago
#7159 closed defect (fixed)
Graph.merge_vertices, and a bug in edge_boundary
Reported by: | ncohen | Owned by: | rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.2.1 |
Component: | graph theory | Keywords: | |
Cc: | Merged in: | sage-4.2.1.alpha0 | |
Authors: | Nathann Cohen | Reviewers: | Anders Jonsson |
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
This patch adds to the Graph class the function merge_vertices.
It is a very common operation in Graph Theory. In a Graph G, one merges two vertices u and v by deleting them and adding a new vertex, which is linked to any other vertex w such that there was an edge uw or vw in G. This can be done with any number of vertices at a time.
Besides, writing this class I noticed there was an error in function edge_boundary :
the function Graph.edge_boundary([u,v]) returns a list of edges, BUT :
- the edges returned do not always contain u or v as their first element. it can be the second one in undirected graphs
- The edges between u and v are returned, which is not the expected behaviour of this function
This patch fixes this too.
Attachments (3)
Change History (13)
comment:1 Changed 10 years ago by
- Status changed from new to needs_review
comment:2 Changed 10 years ago by
- Status changed from needs_review to needs_work
comment:3 Changed 10 years ago by
- Status changed from needs_work to needs_review
Then I hope you will prefer this new version of the patch !!! I thought edge_boundary behaved a bit more nicely ( and mainly got worried about the directed case, thus overlooking the undirected one ... )
Nathann
Changed 10 years ago by
comment:4 follow-up: ↓ 5 Changed 10 years ago by
By the way, I can not find your email on the internet... It's good to see new people in Sage's graph theory section !! What are you studying ?
comment:5 in reply to: ↑ 4 Changed 10 years ago by
I have looked at your new patch, and it seems good. The only thing I found to object against was
if (v in vertices) and not (u in vertices) and v != vertices[0]:
If edge_boundary works as expected, the second test should not be needed as u and v can never be in vertices at the same time. I attach a patch to remove the unneeded test. It applies on top of your patch.
If you agree with this, you can count this as a positive review.
Replying to ncohen:
By the way, I can not find your email on the internet... It's good to see new people in Sage's graph theory section !! What are you studying ?
I'm a student in mathematics and a bit of computer science. I use Sage for diverse calculations in graph theory, and when I find that Sage can't do all that I want it to, I have to do something about it ;-P
comment:6 Changed 10 years ago by
- Status changed from needs_review to positive_review
- Summary changed from [with patch, needs review] Graph.merge_vertices, and a bug in edge_boundary to Graph.merge_vertices, and a bug in edge_boundary
Amazing... I even forgot that I had already fixed this in the same patch :-p
Thank you for your help !!!
comment:7 Changed 10 years ago by
- Status changed from positive_review to needs_work
I read the trac guidelines more closely and there is a last tiny issue before this patch can be said to be perfect:
"Bug Fixes Must Be Doctested: The patch that fixes an issue must also contain a doctest specifically to test the problem."
So all that is missing is a test that displays the expected behavior of edge_boundary(), and that would fail without your patch. For example something like this:
sage: G=graphs.DiamondGraph() sage: G.edge_boundary([0,1]) [(0, 2, None), (1, 2, None), (1, 3, None)]
comment:8 follow-up: ↓ 9 Changed 10 years ago by
- Status changed from needs_work to needs_review
Perhaps the last one ? :-)
comment:9 in reply to: ↑ 8 Changed 10 years ago by
- Status changed from needs_review to positive_review
Replying to ncohen:
Perhaps the last one ? :-)
Let's hope so :-)
All looks fine to me. Positive review.
comment:10 Changed 10 years ago by
- Merged in set to sage-4.2.1.alpha0
- Resolution set to fixed
- Reviewers set to Anders Jonsson
- Status changed from positive_review to closed
Great minds think alike ;-) I just made a ticket ( #7304 ) for edge contraction, but this ticket is more general, so closing mine as a duplicate.
However, there is something wrong in your patch, as my first try revealed this: