Skip to content

Latest commit

 

History

History
111 lines (80 loc) · 8.09 KB

README.md

File metadata and controls

111 lines (80 loc) · 8.09 KB
Raw

Nauty Laman plugin

A plugin for the utility program geng provided with nauty that enables quick generation of nonisomorphic sparse and tight graphs. A graph is (k,l)-sparse if every subgraph with n > N vertices has at most kn-l edges and (k,l)-tight if it is (k,l)-sparse and has exactly kn-l edges.

Installation

  1. Download and build nauty.
  2. Clone this repo.
  3. Provide the path to nauty using NAUTY_DIR, e.g., by modifying the makefile.
  4. Run make.

To build the supplementary program filter_rank:

  1. Download Eigen.
  2. Provide the path to Eigen using EIGEN_DIR, e.g., by modifying the makefile.
  3. Run make.

Usage

The compiled binary gensparseg adds a few new parameters to geng:

  • -K#: generate (k,l)-tight graphs where l = k(k+1)/2. Minimum degree and number of edges will default to k and kn-l, respectively. Sparse graphs can be generated by manually providing the minimum and maximum number of edges (e.g. 0:999). In that case, the minimum degree will default to zero.
  • -L#: provides the l when generating (k,l)-sparse or (k,l)-tight graphs.
  • -H: generate (k,l)-tight graphs constructible by Henneberg type I moves. k defaults to 2 but can be set using -K#. l is always k(k+1)/2.
  • -N#: all (complete graphs) graphs with this number of nodes or fewer are considered (tight) sparse. The default value is max(⌊k⌋,2) or the highest n such that a complete graph on n vertices satisfies the sparsity condition.

Both -K and -L accept rational numbers making it possible to generate, e.g., (3/2,2)-tight graphs (see results below). Note, however, that denominators equal to their numerator are ignored, e.g., -K2/2 is equivalent to -K2. If rational arguments are not needed, define the macro INT_KL before compiling for a small increase (~15% for some inputs) in performance.

Algorithm

For integers k and l satisfying 0 ≤ l < 2k and N ≤ k+1, the pebble game algorithm presented in Lee and Streinu (2008) Pebble game algorithms and sparse graphs is used. For all other cases, a naive method checking the sparsity of every subgraph is used. However, due to how geng generates the graphs, even this naive approach is fast.

Results - counts and execution times

The tables below show the execution time when generating graphs for various numbers of vertices n. All the tests were run on an AMD Ryzen Threadripper 3990X 64-Core Processor. Extensions to entries in OEIS are marked with (new).

Laman graphs

OEIS entry: A227117
Command: gensparseg $n -K2 -u

Laman graphs, minimally rigid graphs in 2D, are exactly the (2,3)-tight graphs.

n 11 12 13 14 (new) 15 (new)
Laman graphs 2 039 273 44 176 717 1 092 493 042 30 322 994 747 932 701 249 291
Execution time 1.8 s 42 s 20 min 10 h 15 days

Laman graphs constructible by Henneberg type I moves

OEIS entry: A273468
Command: gensparseg $n -H -u

n 12 13 14 (new) 15 (new) 16 (new)
H1 Laman graphs 23 352 425 498 028 767 11 836 515 526 310 152 665 647 8 883 427 573 134
Execution time 20 s 8.4 min 4.2 h 5.9 days 290 days*

* Total CPU time of 64 cores.

Bipartite Laman graphs

OEIS entry: A328060
Command: gensparseg $n -bK2 -u

n 15 16 (new) 17 (new) 18 (new) 19 (new)
Bipartite Laman graphs 17 860 267 293 210 063 5 277 557 739 103 177 250 918 2 174 556 695 546
Execution time 46 s 11 min 3.3 h 2.6 days 71 days*

* Total CPU time of 64 cores.

Geiringer graphs

OEIS entry: A328419
Command: gensparseg $n -K3 -u

Geiringer graphs, minimally rigid graphs in 3D, are exactly the (3,6)-tight graphs for n=1..7. For larger n, the former is a proper subset of the latter. The Geiringer graphs can be found by numerically checking the rigidity of the generated (3,6)-tight graphs using ./gensparseg $n -K3 | ./filter_rank -u.

n 6 7 8 9 10 11 12
(3,6)-tight graphs 4 26 375 11 495 613 092 48 185 341 5 116 473 573
Geiringer graphs 4 26 374 11 487 612 884 48 176 183 5 115 840 190*
Execution time 10 ms 740 ms 1.6 min 5.3 h

* Calculated by numerically checking the rigidity of the generated (3,6)-tight graphs.

(3/2,2)-tight graphs

OEIS entry: A233288
Command: gensparseg $n -K3/2L2 -u

Note that gensparseg can generate (3/2,2)-tight graphs also for odd orders n.

n 2 4 6 8 10 12 14 16 18 (new)
(3/2,2)-tight graphs 1 1 2 16 230 6 856 318 162 19 819 281 1 535 380 884
Execution time 10 ms 360 ms 39 s 1.9 h 20 days

Pseudoforests

OEIS entry: A134964
Command: gensparseg $n 0:999 -K1L0 -u

Pseudoforests are the (1,0)-sparse graphs.

n 15 16 17 18 19 20 21
Pseudoforests 282 693 793 697 2 237 982 6 335 978 17 992 622 51 235 887 146 228 734
Execution time 2.1 s 8.0 s 32 s 2.2 min 9.6 min 43 min 3.2 h

Trees

OEIS entry: A000055
Command: gensparseg $n -K1 -u

Trees, minimally rigid graphs in 1D, are exactly the (1,1)-tight graphs. Note that this is a terribly inefficient way of generating trees, consider instead the nauty program gentreeg.

n 17 18 19 20 21 22 23
Trees 48 629 123 867 317 955 823 065 2 144 505 5 623 756 14 828 074
Execution time 2.4 s 9.5 s 40 s 2.8 min 12 min 54 min 4.4 h