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)

trac_7159.patch (3.4 KB) - added by ncohen 10 years ago.
trac_7159-appendix.patch (948 bytes) - added by AJonsson 10 years ago.
Remove no-op tests
trac_7159-appendix-appendix.patch (1.8 KB) - added by ncohen 10 years ago.
Adds one test

Download all attachments as: .zip

Change History (13)

comment:1 Changed 10 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 10 years ago by AJonsson

  • Status changed from needs_review to needs_work

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:

sage: P=graphs.PetersenGraph()
sage: P.merge_vertices([5,7])
sage: P.vertices()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

comment:3 Changed 10 years ago by ncohen

  • 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 ncohen

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

comment:5 in reply to: ↑ 4 Changed 10 years ago by AJonsson

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

Changed 10 years ago by AJonsson

Remove no-op tests

comment:6 Changed 10 years ago by ncohen

  • 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 AJonsson

  • 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)]

Changed 10 years ago by ncohen

Adds one test

comment:8 follow-up: Changed 10 years ago by ncohen

  • Status changed from needs_work to needs_review

Perhaps the last one ? :-)

comment:9 in reply to: ↑ 8 Changed 10 years ago by AJonsson

  • 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 mhansen

  • Authors set to Nathann Cohen
  • 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
Note: See TracTickets for help on using tickets.