Opened 10 years ago

Closed 10 years ago

#8329 closed defect (fixed)

Missing copy() method in BipartiteGraph

Reported by: rhinton Owned by: rhinton
Priority: major Milestone: sage-4.4
Component: graph theory Keywords: BipartiteGraph, copy
Cc: rlm, jason Merged in: sage-4.4.alpha0
Authors: Ryan Hinton Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

BipartiteGraph? is missing a copy() method.

sage: bg = BipartiteGraph(graphs.CycleGraph(4))
sage: type(bg)
<class 'sage.graphs.bipartite_graph.BipartiteGraph'>
sage: bg2 = bg.copy()
sage: type(bg2)
<class 'sage.graphs.graph.Graph'>

The result is not horrendous because the base Graph class has a copy() method. But the result is unexpected: copy() a BipartiteGraph? and you get a Graph?

Attachments (2)

trac_8329-bipartite-graph-copy.patch (2.7 KB) - added by rhinton 10 years ago.
modifies copy() code in generic_graph.py and adds test to BipartiteGraph?
trac_8329-posets-repr.patch (843 bytes) - added by rhinton 10 years ago.
Apply both patches, order does not matter

Download all attachments as: .zip

Change History (20)

comment:1 Changed 10 years ago by rhinton

  • Authors set to Ryan Hinton
  • Status changed from new to needs_review

comment:2 Changed 10 years ago by rhinton

  • Cc jason added; jgrout removed

comment:3 Changed 10 years ago by rhinton

  • Status changed from needs_review to needs_work

Oops, bug in doctest, the patch doesn't work at all.

comment:4 Changed 10 years ago by rhinton

  • Status changed from needs_work to needs_review

New patch (replaced old) should work, including fixed doctest.

comment:5 follow-up: Changed 10 years ago by rlm

This is item 9 on trac #1941.

comment:6 in reply to: ↑ 5 ; follow-up: Changed 10 years ago by rhinton

Right, I had forgotten about this. Obviously I'm fixing methods as I need them. I don't have time right now for the complete overhaul. Is the piecemeal approach OK?

Incidentally, I think I have a decent approach for add_vertex. I was planning on opening another ticket.... :-)

comment:7 in reply to: ↑ 6 ; follow-up: Changed 10 years ago by rlm

Replying to rhinton:

Right, I had forgotten about this. Obviously I'm fixing methods as I need them. I don't have time right now for the complete overhaul. Is the piecemeal approach OK?

I was just linking the tickets to each other. Adding edges to trac I guess... Any way you want to improve bipartite graphs I'll gladly review once I get the time, I just wanted to make sure you were aware of that ticket.

Incidentally, I think I have a decent approach for add_vertex. I was planning on opening another ticket.... :-)

Go for it!

comment:8 Changed 10 years ago by rhinton

Note for someone who is more knowledgeable: the new BipartiteGraph?.copy() method doesn't try to do anything tricky with vertex associations, boundaries, positions, etc. It just tries the Graph constructor. I haven't figured out a way to copy() the Graph part and get out a BipartiteGraph? instance. This way works for me, but I'm not sure if it does all the special stuff that Graph.copy() does.

comment:9 in reply to: ↑ 7 Changed 10 years ago by rhinton

I get it ... adding edges. :-)

Replying to rlm:

Replying to rhinton:

Right, I had forgotten about this. Obviously I'm fixing methods as I need them. I don't have time right now for the complete overhaul. Is the piecemeal approach OK?

I was just linking the tickets to each other. Adding edges to trac I guess... Any way you want to improve bipartite graphs I'll gladly review once I get the time, I just wanted to make sure you were aware of that ticket.

comment:10 Changed 10 years ago by rhinton

  • Cc ncohen added
  • Keywords copy added

The new patch to GenericGraph?.copy() always creates a new object of the same class as the original object -- no special case code for Graph, DiGraph?, or BipartiteGraph?. Any future subclasses will work as well assuming they can handle the same initializer arguments (by passing them to the superclass initializer).

comment:11 Changed 10 years ago by rlm

This patch exposes a bug in another seldom used extension of the Graph class, GraphBundle.

File "/Users/rlmill/sage-4.3.3/devel/sage-main/sage/graphs/graph_bundle.py", line 163:
    sage: B.plot()
Exception raised:
    Traceback (most recent call last):
      File "/Users/rlmill/sage-4.3.3/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/rlmill/sage-4.3.3/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/rlmill/sage-4.3.3/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_5[5]>", line 1, in <module>
        B.plot()###line 163:
    sage: B.plot()
      File "/Users/rlmill/sage-4.3.3/local/lib/python/site-packages/sage/graphs/graph_bundle.py", line 173, in plot
        total_pos = generic_graph_pyx.spring_layout_fast(self, iterations=iters)
      File "generic_graph_pyx.pyx", line 86, in sage.graphs.generic_graph_pyx.spring_layout_fast (sage/graphs/generic_graph_pyx.c:1361)
      File "/Users/rlmill/sage-4.3.3/local/lib/python/site-packages/sage/graphs/graph.py", line 2061, in to_undirected
        return copy(self)
      File "/Users/rlmill/sage-4.3.3/local/lib/python2.6/copy.py", line 79, in copy
        return copier(x)
      File "/Users/rlmill/sage-4.3.3/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 483, in __copy__
        G = self.__class__(self, name=self.name(), pos=copy(self._pos), boundary=copy(self._boundary), implementation=implementation, sparse=sparse)
      File "/Users/rlmill/sage-4.3.3/local/lib/python/site-packages/sage/graphs/graph_bundle.py", line 73, in __init__
        if isinstance(args[0], (list, tuple)):
    IndexError: tuple index out of range

comment:12 Changed 10 years ago by rlm

I will offer the suggestion to disable the failing doctest, for discussion. I don't know of anyone who uses graph bundles in Sage. I've emailed Chris Godsil to see if he ever uses it.

comment:13 Changed 10 years ago by rhinton

Sounds great to me. The new patch disables the "plot" doctest that was failing and adds a "known bugs" warning to the beginning of the graph_bundle.py.

Changed 10 years ago by rhinton

modifies copy() code in generic_graph.py and adds test to BipartiteGraph?

comment:14 Changed 10 years ago by rlm

  • Reviewers set to Robert Miller
  • Status changed from needs_review to positive_review

Anyone queasy about the GraphBundle doctest, Godsil tells me he has a student who is working on a bundle package, which I am assuming actually does something (unlike bundles in Sage). Look for this to appear in Sage at some point soon!

comment:15 Changed 10 years ago by rhinton

  • Cc ncohen removed
  • Status changed from positive_review to needs_work

Found a failing doctest in combinat/posets/posets.py due to this change. Additional patch coming soon.

Changed 10 years ago by rhinton

Apply both patches, order does not matter

comment:16 Changed 10 years ago by rhinton

  • Status changed from needs_work to needs_review

New patch fixes posets doctest failure. Apply both patches; order does not matter.

comment:17 Changed 10 years ago by ncohen

  • Status changed from needs_review to positive_review

Good patch ! Applies fine, does its job.. :-)

Nathann

comment:18 Changed 10 years ago by jhpalmieri

  • Merged in set to sage-4.4.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed

Merged in 4.4.alpha0:

  • trac_8329-bipartite-graph-copy.patch
  • trac_8329-posets-repr.patch
Note: See TracTickets for help on using tickets.