Opened 13 years ago
Closed 12 years ago
#8330 closed defect (fixed)
BipartiteGraph needs to override methods to add and delete vertices and edges
Reported by: | Ryan Hinton | Owned by: | Ryan Hinton |
---|---|---|---|
Priority: | major | Milestone: | sage-4.4 |
Component: | graph theory | Keywords: | BipartiteGraph |
Cc: | Robert Miller, Jason Grout, Nathann Cohen | Merged in: | sage-4.4.alpha0 |
Authors: | Ryan Hinton | Reviewers: | Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
BipartiteGraph needs to hook delete_vertex() and delete_vertices().
sage: g = BipartiteGraph(graphs.CycleGraph(4)) sage: (g.left, g.right) ([0, 2], [1, 3]) sage: g.delete_vertex(0) sage: g.left [0, 2]
Note vertex 0 still shows up in the left partition.
It should also override add_vertex()
sage: g = BipartiteGraph() sage: g.add_vertex('a') sage: g.left [] sage: g.right # where did it go? []
and add_edge().
sage: g = BipartiteGraph(Graph({'a':['b','c']})) sage: g.left ['a'] sage: g.right ['b','c'] sage: g.add_edge('b', 'c') # violates bipartition, should raise exception
Attachments (2)
Change History (11)
comment:1 Changed 13 years ago by
comment:3 Changed 13 years ago by
Status: | new → needs_review |
---|
Yes, I do mean define these methods. The proposed method definitions just call the corresponding method in Graph, then adjust the partition lists. So it feels to me like a driver "hook" where you call the existing function but add a little extra functionality before or after.
The patch defines the needed methods including doctests that pass.
comment:4 Changed 13 years ago by
Description: | modified (diff) |
---|---|
Status: | needs_review → needs_work |
I just tested graph.py for another potential change, and found that a few doctests fail due to this patch. Specifically, the tests create BipartiteGraphs? (e.g. K23), and the Graph algorithm adds a temp vertex, then deletes it later. But the new delete_vertex() raises an exception when it can't find the temp vertex in its left or right sets.
So we may need to fix add_vertex before this delete_vertex solution will work. Or should we do a soft-fail (print a warning?) instead of raising an exception?
comment:5 Changed 13 years ago by
Cc: | Nathann Cohen added |
---|---|
Description: | modified (diff) |
Summary: | BipartiteGraph needs to hook delete_vertex() and delete_vertices() → BipartiteGraph needs to override methods to add and delete vertices and edges |
changing the ticket to handle add and delete methods for completeness
comment:6 Changed 13 years ago by
Status: | needs_work → needs_review |
---|
Changed 13 years ago by
Attachment: | trac_8330-bipartite-delete-vertex.patch added |
---|
REQUIRES #8421. Implements add/delete vertex/vertices and to_undirected to fix a failing doctest elsewhere.
comment:7 Changed 13 years ago by
Hello !!!
Nice patch, applies and does its job... I fixed one or two things... If you think they are ok, you can set this ticket to "positive review" :-)
Nathann
Changed 13 years ago by
Attachment: | trac_8330-smallfixes.patch added |
---|
comment:8 Changed 12 years ago by
Status: | needs_review → positive_review |
---|
Well, it has been two weeks and I only fixed three lines, so let's say this ticket is positively reviewed ^{};
Nathann
comment:9 Changed 12 years ago by
Merged in: | → sage-4.4.alpha0 |
---|---|
Resolution: | → fixed |
Reviewers: | → Nathann Cohen |
Status: | positive_review → closed |
Merged into 4.4.alpha0:
- trac_8330-bipartite-delete-vertex.patch
- trac_8330-smallfixes.patch
When you say "hook", do you mean "define"?