Opened 8 years ago
Closed 8 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 )
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)
Change History (16)
comment:1 Changed 8 years ago by
- Cc chapoton nborie added
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
- Component changed from PLEASE CHANGE to graph theory
comment:3 follow-up: ↓ 8 Changed 8 years ago by
comment:4 follow-up: ↓ 5 Changed 8 years ago by
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 8 years ago by
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 seconds0 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 8 years ago by
- 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 8 years ago by
- Status changed from needs_work to needs_review
Arg... One should be "regular=3".
Fixed.
Nathann
comment:8 in reply to: ↑ 3 Changed 8 years ago by
- 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 8 years ago by
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 8 years ago by
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: ↓ 12 Changed 8 years ago by
Try this instead :
sage -tp 4 --optional=sage,nauty -l graphs/
Nathann
comment:12 in reply to: ↑ 11 Changed 8 years ago by
- Description modified (diff)
- Status changed from needs_review to positive_review
comment:13 Changed 8 years ago by
- Reviewers set to Dmitrii Pasechnik
The patch needs a proper commit message.
Changed 8 years ago by
comment:14 Changed 8 years ago by
Done !
Nathann
comment:15 Changed 8 years ago by
- Merged in set to sage-5.10.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
Can you also demonstrate heroism and update nauty spkg to version 2.5? :)