Opened 6 years ago

Closed 6 years ago

#14474 closed enhancement (fixed)

Hypergraph enumeration through Nauty

Reported by: ncohen Owned by: tbd
Priority: major Milestone: sage-5.10
Component: graph theory Keywords:
Cc: tmonteil, vdelecroix, nthiery, hivert, dimpase, chapoton, nborie Merged in: sage-5.10.beta1
Authors: Nathann Cohen Reviewers: Dmitrii Pasechnik
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by dimpase)

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

Attachments (1)

trac_14474.patch (7.9 KB) - added by ncohen 6 years ago.

Download all attachments as: .zip

Change History (16)

comment:1 Changed 6 years ago by ncohen

  • Cc chapoton nborie added
  • Status changed from new to needs_review

comment:2 Changed 6 years ago by ncohen

  • Component changed from PLEASE CHANGE to graph theory

comment:3 follow-up: Changed 6 years ago by dimpase

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

Last edited 6 years ago by dimpase (previous) (diff)

comment:4 follow-up: Changed 6 years ago by 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...

comment:5 in reply to: ↑ 4 Changed 6 years ago by dimpase

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.

comment:6 Changed 6 years ago by dimpase

  • Status changed from needs_review to needs_work

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

comment:7 Changed 6 years ago by ncohen

  • Status changed from needs_work to needs_review

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

Fixed.

Nathann

comment:8 in reply to: ↑ 3 Changed 6 years ago by ncohen

  • Type changed from PLEASE CHANGE to enhancement

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

This is now #14475.

Nathann

comment:9 Changed 6 years ago by dimpase

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.

comment:10 Changed 6 years ago by ncohen

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

comment:11 follow-up: Changed 6 years ago by ncohen

Try this instead :

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

Nathann

comment:12 in reply to: ↑ 11 Changed 6 years ago by dimpase

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

Replying to ncohen:

Try this instead :

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

OK, good!

comment:13 Changed 6 years ago by jdemeyer

  • Reviewers set to Dmitrii Pasechnik

The patch needs a proper commit message.

Changed 6 years ago by ncohen

comment:14 Changed 6 years ago by ncohen

Done !

Nathann

comment:15 Changed 6 years ago by jdemeyer

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