#19053: arboricity of a undirected graph
-------------------------------------+-------------------------------------
Reporter: chaoxu | Owner:
Type: enhancement | Status: needs_work
Priority: trivial | Milestone: sage-6.9
Component: graph theory | Resolution:
Keywords: | Merged in:
Authors: Chao Xu | Reviewers: David Coudert
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/chaoxu/arboricity | eee17d1a02db6256fc80c46c915d059196cd6956
Dependencies: #19027 | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by dcoudert):
* status: needs_review => needs_work
* reviewer: => David Coudert
Comment:
* You must add tests for graphs with no vertices or no edges.
{{{
sage: G = Graph()
sage: G.arboricity(True)
---------------------------------------------------------------------------
ZeroDivisionError Traceback (most recent call
last)
<ipython-input-9-065f5ba4c546> in <module>()
----> 1 G.arboricity(True)
/Users/dcoudert/sage/local/lib/python2.7/site-
packages/sage/graphs/graph.pyc in arboricity(self, certificate)
7076 """
7077 from sage.matroids.constructor import Matroid
-> 7078 P = Matroid(self).partition()
7079 if certificate:
7080 return (len(P),[self.subgraph(edges=forest) for forest
in P])
/Users/dcoudert/sage/src/sage/matroids/matroid.pyx in
sage.matroids.matroid.Matroid.partition
(/Users/dcoudert/sage/src/build/cythonized/sage/matroids/matroid.c:63561)()
6713 return True, Y
6714
-> 6715 cpdef partition(self):
6716 r"""
6717 Returns a minimum number of disjoint independent sets that
covers the
/Users/dcoudert/sage/src/sage/matroids/matroid.pyx in
sage.matroids.matroid.Matroid.partition
(/Users/dcoudert/sage/src/build/cythonized/sage/matroids/matroid.c:62657)()
6746 n = self.size()
6747 r = self.rank()
-> 6748 hi = -(-n//r)
6749 lo = hi
6750 X = set()
ZeroDivisionError: integer division or modulo by zero
sage: G.arboricity()
---------------------------------------------------------------------------
ZeroDivisionError Traceback (most recent call
last)
...
ZeroDivisionError: integer division or modulo by zero
sage: G = Graph(1)
sage: G.arboricity(True)
---------------------------------------------------------------------------
ZeroDivisionError Traceback (most recent call
last)
...
ZeroDivisionError: integer division or modulo by zero
sage: G = Graph(2)
sage: G.arboricity(True)
---------------------------------------------------------------------------
ZeroDivisionError Traceback (most recent call
last)
...
ZeroDivisionError: integer division or modulo by zero
sage: G = graphs.PetersenGraph()
sage: G.add_vertex(20)
sage: G.arboricity()
2
}}}
More precisely, start with:
{{{
if self.size()==0:
return (0,[]) if certificate else 0
}}}
* In the list of methods (top of the file), you should write `Return`
instead of `Returns` to be consistent with the method description.
* I tried the method with a GNP graph of order 100 and it's really long.
Unfortunately, we can not CRTL-C the computations, the partition method
does not handle signals :(
David.
--
Ticket URL: <http://trac.sagemath.org/ticket/19053#comment:9>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
