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:

Status badges

Description (last modified by Ryan Hinton)

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)

trac_8330-bipartite-delete-vertex.patch (13.6 KB) - added by Ryan Hinton 13 years ago.
REQUIRES #8421. Implements add/delete vertex/vertices and to_undirected to fix a failing doctest elsewhere.
trac_8330-smallfixes.patch (1.5 KB) - added by Nathann Cohen 13 years ago.

Download all attachments as: .zip

Change History (11)

comment:1 Changed 13 years ago by Jason Grout

When you say "hook", do you mean "define"?

comment:2 Changed 13 years ago by Robert Miller

#1941 is relevant.

comment:3 Changed 13 years ago by Ryan Hinton

Status: newneeds_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 Ryan Hinton

Description: modified (diff)
Status: needs_reviewneeds_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 Ryan Hinton

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 Ryan Hinton

Status: needs_workneeds_review

Changed 13 years ago by Ryan Hinton

REQUIRES #8421. Implements add/delete vertex/vertices and to_undirected to fix a failing doctest elsewhere.

comment:7 Changed 13 years ago by Nathann Cohen

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 Nathann Cohen

Attachment: trac_8330-smallfixes.patch added

comment:8 Changed 12 years ago by Nathann Cohen

Status: needs_reviewpositive_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 John Palmieri

Merged in: sage-4.4.alpha0
Resolution: fixed
Reviewers: Nathann Cohen
Status: positive_reviewclosed

Merged into 4.4.alpha0:

  • trac_8330-bipartite-delete-vertex.patch
  • trac_8330-smallfixes.patch
Note: See TracTickets for help on using tickets.