Opened 11 years ago
Closed 11 years ago
#8330 closed defect (fixed)
BipartiteGraph needs to override methods to add and delete vertices and edges
Reported by: | rhinton | Owned by: | rhinton |
---|---|---|---|
Priority: | major | Milestone: | sage-4.4 |
Component: | graph theory | Keywords: | BipartiteGraph |
Cc: | rlm, jason, ncohen | 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 11 years ago by
comment:2 Changed 11 years ago by
#1941 is relevant.
comment:3 Changed 11 years ago by
- Status changed from new to 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 11 years ago by
- Description modified (diff)
- Status changed from needs_review to 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 11 years ago by
- Cc ncohen added
- Description modified (diff)
- Summary changed from BipartiteGraph needs to hook delete_vertex() and delete_vertices() to 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 11 years ago by
- Status changed from needs_work to needs_review
Changed 11 years ago by
REQUIRES #8421. Implements add/delete vertex/vertices and to_undirected to fix a failing doctest elsewhere.
comment:7 Changed 11 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 11 years ago by
comment:8 Changed 11 years ago by
- Status changed from needs_review to 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 11 years ago by
- Merged in set to sage-4.4.alpha0
- Resolution set to fixed
- Reviewers set to Nathann Cohen
- Status changed from positive_review to closed
Merged into 4.4.alpha0:
- trac_8330-bipartite-delete-vertex.patch
- trac_8330-smallfixes.patch
When you say "hook", do you mean "define"?