search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.48k stars 488 forks source link

Hypergraph enumeration through Nauty #14474

Closed 6bdad4c1-1e26-4f2f-a442-a01a2292c181 closed 11 years ago

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 11 years ago

This patch implements a very short module which calls the optional spkg Nauty and enumerates hypergraphs up to isomophism.

Brendan McKay is a hero :-P

Nathann

CC: @sagetrac-tmonteil @videlec @nthiery @hivert @dimpase @fchapoton @sagetrac-nborie

Component: graph theory

Author: Nathann Cohen

Reviewer: Dmitrii Pasechnik

Merged: sage-5.10.beta1

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

dimpase commented 11 years ago
comment:3

Can you also demonstrate heroism and update nauty spkg to version 2.5? :)

dimpase commented 11 years ago
comment:4

an interesting "feature" of new doctesting framework? :

$ ../../sage -t --optional --long sage/graphs/hypergraph_generators.py
Running doctests with ID 2013-04-22-15-09-26-c0d8e0e6.
Doctesting 1 file.
sage -t sage/graphs/hypergraph_generators.py
    [0 tests, 0.00 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 0.1 seconds
    cpu time: 0.0 seconds
    cumulative wall time: 0.0 seconds

0 tests! And I have nauty installed just fine, by the way...

dimpase commented 11 years ago
comment:5

Replying to @dimpase:

an interesting "feature" of new doctesting framework? :

$ ../../sage -t --optional --long sage/graphs/hypergraph_generators.py
Running doctests with ID 2013-04-22-15-09-26-c0d8e0e6.
Doctesting 1 file.
sage -t sage/graphs/hypergraph_generators.py
    [0 tests, 0.00 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 0.1 seconds
    cpu time: 0.0 seconds
    cumulative wall time: 0.0 seconds

0 tests! And I have nauty installed just fine, by the way...

Oh, OK, it should be --optional=nauty there... Then it works.

dimpase commented 11 years ago
comment:6

the lines

The Fano Plane, as the only 3-uniform hypergraph with 7 sets and 7 vertices:: 

                sage: fano = hypergraphs.nauty(7,7, uniform = 3, max_intersection =1).next() # optional - nauty 
                sage: print fano # optional - nauty 
                ((0, 1, 2), (0, 3, 4), (0, 5, 6), (1, 3, 5), (2, 4, 5), (2, 3, 6), (1, 4, 6))

are repeated in the file...

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 11 years ago
comment:7

Arg... One should be "regular=3".

Fixed.

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 11 years ago
comment:8

Can you also demonstrate heroism and update nauty spkg to version 2.5? :)

This is now #14475.

Nathann

dimpase commented 11 years ago
comment:9

There are lots of test failures on 

sage -bt --optional=nauty --long sage/graphs/

both with and without the patch, on nauty 2.4 and on 2.5. Without the patch: (nauty 2.4):

sage -t --long sage/graphs/digraph.py  # 1 doctest failed
sage -t --long sage/graphs/digraph_generators.py  # 4 doctests failed
sage -t --long sage/graphs/generic_graph.py  # 38 doctests failed
sage -t --long sage/graphs/genus.pyx  # 1 doctest failed
sage -t --long sage/graphs/graph.py  # 2 doctests failed
sage -t --long sage/graphs/graph_generators.py  # 2 doctests failed
sage -t --long sage/graphs/graph_plot.py  # 3 doctests failed
sage -t --long sage/graphs/hyperbolicity.pyx  # 1 doctest failed
sage -t --long sage/graphs/matchpoly.pyx  # 2 doctests failed
sage -t --long sage/graphs/spanning_tree.pyx  # 13 doctests failed
sage -t --long sage/graphs/base/c_graph.pyx  # 1 doctest failed
sage -t --long sage/graphs/base/dense_graph.pyx  # 1 doctest failed
sage -t --long sage/graphs/base/sparse_graph.pyx  # 1 doctest failed
sage -t --long sage/graphs/generators/basic.py  # 46 doctests failed
sage -t --long sage/graphs/generators/degree_sequence.py  # 7 doctests failed
sage -t --long sage/graphs/generators/families.py  # 16 doctests failed
sage -t --long sage/graphs/generators/platonic_solids.py  # 10 doctests failed
sage -t --long sage/graphs/generators/random.py  # 10 doctests failed
sage -t --long sage/graphs/generators/smallgraphs.py  # 23 doctests failed
sage -t --long sage/graphs/graph_decompositions/vertex_separation.pyx  # 1 doctest failed

With the patch (nauty 2.4):

sage -t --long sage/graphs/digraph.py  # 1 doctest failed
sage -t --long sage/graphs/digraph_generators.py  # 4 doctests failed
sage -t --long sage/graphs/generic_graph.py  # 38 doctests failed
sage -t --long sage/graphs/genus.pyx  # 1 doctest failed
sage -t --long sage/graphs/graph.py  # 2 doctests failed
sage -t --long sage/graphs/graph_generators.py  # 2 doctests failed
sage -t --long sage/graphs/graph_plot.py  # 3 doctests failed
sage -t --long sage/graphs/hyperbolicity.pyx  # 1 doctest failed
sage -t --long sage/graphs/matchpoly.pyx  # 2 doctests failed
sage -t --long sage/graphs/spanning_tree.pyx  # 13 doctests failed
sage -t --long sage/graphs/base/c_graph.pyx  # 1 doctest failed
sage -t --long sage/graphs/base/dense_graph.pyx  # 1 doctest failed
sage -t --long sage/graphs/base/sparse_graph.pyx  # 1 doctest failed
sage -t --long sage/graphs/generators/basic.py  # 46 doctests failed
sage -t --long sage/graphs/generators/degree_sequence.py  # 7 doctests failed
sage -t --long sage/graphs/generators/families.py  # 16 doctests failed
sage -t --long sage/graphs/generators/platonic_solids.py  # 10 doctests failed
sage -t --long sage/graphs/generators/random.py  # 10 doctests failed
sage -t --long sage/graphs/generators/smallgraphs.py  # 23 doctests failed
sage -t --long sage/graphs/graph_decompositions/vertex_separation.pyx  # 1 doctest failed

The patch does not seem to affect these numbers - but you you look into these failures? E.g.

$ sage -bt --optional=nauty --long sage/graphs/digraph.py
...

sage -t --long sage/graphs/digraph.py
**********************************************************************
File "sage/graphs/digraph.py", line 987, in sage.graphs.digraph.DiGraph.is_directed_acyclic
Failed example:
    all( random_acyclic(100, .2).is_directed_acyclic()    # long time
           for i in range(50))                              # long time
Exception raised:
    Traceback (most recent call last):
      File "/usr/local/src/sage/sage-5.9.beta5/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 466, in _run
        self.execute(example, compiled, test.globs)
      File "/usr/local/src/sage/sage-5.9.beta5/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 825, in execute
        exec compiled in globs
      File "<doctest sage.graphs.digraph.DiGraph.is_directed_acyclic[0]>", line 2, in <module>
        for i in range(Integer(50)))                              # long time
      File "<doctest sage.graphs.digraph.DiGraph.is_directed_acyclic[0]>", line 2, in <genexpr>
        for i in range(Integer(50)))                              # long time
    NameError: global name 'random_acyclic' is not defined
**********************************************************************
1 item had failures:
   1 of   2 in sage.graphs.digraph.DiGraph.is_directed_acyclic
    [1 test, 1 failure, 0.01 s]
----------------------------------------------------------------------
sage -t --long sage/graphs/digraph.py  # 1 doctest failed
----------------------------------------------------------------------

The latter works if optional= is removed from the invocation of sage -t.

Tested on OSX 10.6.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 11 years ago
comment:10

I would say that when you type --optional=nauty, ONLY the tests that are flagged with nauty are getting executed... Look at the number of doctests run with those commands :

~/sage$ sage -tp 4 --optional=nauty graphs/digraph.py 
Running doctests with ID 2013-04-25-09-19-33-f65408dd.
Doctesting 1 file using 4 threads.
sage -t graphs/digraph.py
    [0 tests, 0.0 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 0.1 seconds
    cpu time: 0.0 seconds
    cumulative wall time: 0.0 seconds
~/sage$ sage -tp 4 graphs/digraph.py 
Running doctests with ID 2013-04-25-09-19-39-5fd4f5f8.
Doctesting 1 file using 4 threads.
sage -t graphs/digraph.py
    [387 tests, 5.4 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 5.6 seconds
    cpu time: 5.3 seconds
    cumulative wall time: 5.4 seconds

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 11 years ago
comment:11

Try this instead :

sage -tp 4 --optional=sage,nauty -l graphs/

Nathann

dimpase commented 11 years ago
comment:12

Replying to @nathanncohen:

Try this instead :

sage -tp 4 --optional=sage,nauty -l graphs/

OK, good!

dimpase commented 11 years ago

Description changed:

--- 
+++ 
@@ -1,5 +1,5 @@
 This patch implements a very short module which calls the optional spkg Nauty and enumerates hypergraphs up to isomophism.

-Brendan McKay is a hero `:-P`
+`Brendan McKay` is a hero `:-P`

 Nathann
jdemeyer commented 11 years ago

Reviewer: Dmitrii Pasechnik

jdemeyer commented 11 years ago
comment:13

The patch needs a proper commit message.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 11 years ago
comment:14

Attachment: trac_14474.patch.gz

Done !

Nathann

jdemeyer commented 11 years ago

Merged: sage-5.10.beta1