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:

Status badges

Description (last modified by rhinton)

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 rhinton 11 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 ncohen 11 years ago.

Download all attachments as: .zip

Change History (11)

comment:1 Changed 11 years ago by jason

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

comment:2 Changed 11 years ago by rlm

#1941 is relevant.

comment:3 Changed 11 years ago by rhinton

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

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

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

  • Status changed from needs_work to needs_review

Changed 11 years ago by rhinton

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

comment:7 Changed 11 years ago by ncohen

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 ncohen

comment:8 Changed 11 years ago by ncohen

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

  • 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
Note: See TracTickets for help on using tickets.