Opened 7 years ago

Closed 7 years ago

#11910 closed defect (fixed)

Connectivity of complete graphs

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.0
Component: graph theory Keywords:
Cc: Merged in: sage-5.0.beta7
Authors: Nathann Cohen Reviewers: Jason Grout, David Coudert
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

Fixes the problem reported at :

http://ask.sagemath.org/question/793/vertex-connecitivity-incomplete-pun-intended?answer=1306#1306

The connectvity of a complete graph is n-1. Currently, an exception is returned

Requires : #11367

Apply : trac_11910.patch

Attachments (1)

trac_11910.patch (4.7 KB) - added by ncohen 7 years ago.

Download all attachments as: .zip

Change History (14)

comment:1 Changed 7 years ago by ncohen

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 7 years ago by jason

  • Reviewers set to Jason Grout

When testing on sage-4.8.alpha3, I get this (presumably from #11367):


sage -t  "devel/sage-main/sage/graphs/generic_graph.py"     
Exception MemoryError: MemoryError() in 'sage.graphs.distances_all_pairs.c_eccentricity' ignored
Exception MemoryError: MemoryError() in 'sage.graphs.distances_all_pairs.c_eccentricity' ignored
**********************************************************************
File "/home/grout/sage-trees/sage-4.8.alpha3/devel/sage-main/sage/graphs/generic_graph.py", line 6805:
    sage: g.vertex_connectivity()
Expected:
    9.0
Got:
    9
**********************************************************************
1 items had failures:
   1 of  21 in __main__.example_84
***Test Failed*** 1 failures.
For whitespace errors, see the file /home/grout/.sage//tmp/generic_graph_22844.py
	 [63.6 s]
 
----------------------------------------------------------------------
The following tests failed:


	sage -t  "devel/sage-main/sage/graphs/generic_graph.py"
Total time for all tests: 63.6 seconds

Other than that, the code looks good. The MemoryErrors? look interesting, though. I don't think it's from this patch, but do you have any idea what it could be from?

comment:3 Changed 7 years ago by jason

  • Status changed from needs_review to needs_work
  • Work issues set to doctest rebase

comment:4 Changed 7 years ago by jason

Interestingly, when I pop the patch and rerun tests, I don't get those memory errors anymore, so maybe it is this patch causing the memory errors. Do you have any clue about what is going on?

comment:5 Changed 7 years ago by ncohen

Hmmmm... O_o

The memory error most probably comes from patch #12052.

Nathann

comment:6 Changed 7 years ago by ncohen

  • Status changed from needs_work to needs_info

Hmmm... Which kind of version are you using ? I applied the patch against alpha4 and there is nothing wrong there ! O_o

Nathann

comment:7 Changed 7 years ago by ncohen

  • Status changed from needs_info to needs_review

comment:8 Changed 7 years ago by dcoudert

  • Reviewers changed from Jason Grout to Jason Grout, David Coudert
  • Status changed from needs_review to needs_work

I have installed the patch with sage 5.0-beta4.

It is working correctly, but I also have a problem with the tests. This is a rounding problem. You should ensure that unweighted connectivity returns an integer.

sage -t  "devel/sage-myclone/sage/graphs/generic_graph.py"
IBM ILOG License Manager: "IBM ILOG Optimization Suite for Academic Initiative" is accessing CPLEX 12 with option(s): "e m b q ".
**********************************************************************
File "/path-to-sage/sage-5.0.beta4/devel/sage-myclone/sage/graphs/generic_graph.py", line 7020:
    sage: g.vertex_connectivity()
Expected:
    9.0
Got:
    9
**********************************************************************
1 items had failures:
   1 of  21 in __main__.example_85
***Test Failed*** 1 failures.
For whitespace errors, see the file /path-to-home/.sage//tmp/generic_graph_2957.py
         [53.6 s]
 
----------------------------------------------------------------------
The following tests failed:


        sage -t  "devel/sage-myclone/sage/graphs/generic_graph.py"
Total time for all tests: 53.6 seconds

comment:9 Changed 7 years ago by ncohen

  • Status changed from needs_work to needs_review

Ahaahh. Actually for once it is the opposite : the function returns an integer, and a float was expected in the doctest... Of course the value returned is always an integer, as it is g.order()-1. Stupid me :-p

Thank you for the review ! Patch updated ! :-)

Nathann

Changed 7 years ago by ncohen

comment:10 follow-up: Changed 7 years ago by dcoudert

  • Status changed from needs_review to positive_review

The patch now pass the tests successfully !

Install ok, docbuild ok, test ok, functionality ok => positive review.

D.

comment:11 in reply to: ↑ 10 Changed 7 years ago by ncohen

Install ok, docbuild ok, test ok, functionality ok => positive review.

Wouhouuuuuuu ! :-)

And it looks like ISGCI (#11880) should be included in Sage in a not so distant future :-)

Thanks !

Nathann

comment:12 Changed 7 years ago by jdemeyer

  • Work issues doctest rebase deleted

comment:13 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.0.beta7
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.