arboricity of a undirected graph

[chaoxu]

#19027 implements matroid partition. One can use it directly to find the arboricity of the graph. https://en.wikipedia.org/wiki/Arboricity

Component: graph theory

Author: Chao Xu, Vipul Gupta

Branch/Commit: e611ab4

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/19053

[chaoxu]

Branch: u/chaoxu/arboricity

[nathanncohen]

comment:2

Could you add the new graph function to the index at the top of the file? Sorry for asking this now, before you even set the ticket to needs_review, but that's one of the things that easily goes unnoticed.

(I have plans to make the building of this index a bit easier in the future)

Nathann

P.S.: Thank you very much for thia addition !

---

New commits:

8cd3a4e	add matroid union
2aaeaa6	implements partition and updating documentation
96ae2af	not bases, independent sets
454cb1d	rename SumMatroid, UnionMatroid to MatroidSum, MatroidUnion
a83ef24	fixed bug, need to search for k, no direct formula
aa490c3	add arboricity

[nathanncohen]

Commit: aa490c3

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

dc5cfb5

added index

[sagetrac-git]

Changed commit from aa490c3 to dc5cfb5

[sagetrac-git]

Changed commit from dc5cfb5 to 7bbb2c3

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

7bbb2c3

indent

[nathanncohen]

comment:5

Thank you!

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

eee17d1

Merge branch 'develop' into u/chaoxu/arboricity

[sagetrac-git]

Changed commit from 7bbb2c3 to eee17d1

[dcoudert]

comment:7

Is this ticket ready for review?

[chaoxu]

comment:8

It's ready for review.
In order to have a reasonable performance, it will require this minor change in ticket #19254.
It is probably too slow for any graph with more than 200 edges.

[dcoudert]

comment:9

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

[dcoudert]

Reviewer: David Coudert

[sagetrac-git]

Changed commit from eee17d1 to 6d871af

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

6d871af

Merge branch 'develop' into u/chaoxu/arboricity

[chaoxu]

Changed dependencies from #19027 to #19275

[dcoudert]

comment:12

You have added the dependency to #19275 without merge.
Also you should add a test with G = Graph() and/or G = Graph(2).
David.

[vipul79321]

Changed commit from 6d871af to none

[vipul79321]

Changed branch from u/chaoxu/arboricity to u/gh-vipul79321/ticket19053

[vipul79321]

Changed dependencies from #19275 to none

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

386c96b

Added doctest for empty graph

[sagetrac-git]

Commit: 386c96b

[vipul79321]

comment:15

Replying to @dcoudert:

You have added the dependency to #19275 without merge.
Also you should add a test with G = Graph() and/or G = Graph(2).
David.

After fixing of tickets #19275, #19027, #19254. We can restart the work on this. I have added doctest for G=Graph().
The only remaining issue is of time complexity which heavily depends on the Partition method of Matroids.

[dcoudert]

comment:16

Several comments.

• There is a TAB that must be removed. To know that is suffices to run the tests ./sage -t src/sage/graphs/graph.py

sage -t src/sage/graphs/graph.py
    Error: TAB character found at line 8648
    [1081 tests, 16.44 s]
----------------------------------------------------------------------
sage -t src/sage/graphs/graph.py  # Tab character found
----------------------------------------------------------------------

• At the beginning of the method, use r""" instead of """ to enable latex mode. Then `a` is treated using latex

• small change to unify the style with other methods

-        - ``certificate`` -- boolean (default: ``False``) Whether to return 
-          a certificate.
+        - ``certificate`` -- boolean (default: ``False``); whether to return 
+          a certificate.

• ``(a, F)`` -> `(a, F)`

• I propose to remove the seealso block and to do

-        Represent the graph as a graphical matroid, then apply matroid partition
-        algorithm in the matroids module.
+        Represent the graph as a graphical matroid, then apply matroid
+        :meth:`sage.matroid.partition` algorithm from the matroids module.

• add spaces around ==, so )==G.size() -> ) == G.size()

• g=Graph() -> g = Graph()

• a space is needed after the ,, and the parenthesis are optional here

-          return (len(P),[self.subgraph(edges=forest) for forest in P])
+          return len(P), [self.subgraph(edges=forest) for forest in P]

[sagetrac-git]

Changed commit from 386c96b to e611ab4

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

e611ab4

Updated according to comment 16

[dcoudert]

comment:19

Please add your full name in the Authors field.

[vipul79321]

Changed author from Chao Xu to Chao Xu, Vipul Gupta

[dcoudert]

comment:21

LGTM.

[vbraun]

Changed branch from u/gh-vipul79321/ticket19053 to e611ab4