Search software for reduced prime minimal planar doodles
Updated 18th September, 2023
A tarfile containing the software and a Makefile is available here.
The software is in two parts, a programme doodle and a programme 4-gon. The doodle programme determines, for a given number of crossings, all valid doodle codes. The programme 4-gon takes a doodle code and enumerates all possible planar doodles corresponding to that code. The name 4-gon comes from the fact that the programme starts by creating cellular-divisions of a disc whose 2-cells are all four-sided; i.e. 4-gons.
See section 8 of reference [3] on the doodle page for a high-level description of the algorithm.
The tarfile will extract into a directory 4-gon-Sep-2023 containing a Makefile and two subdirectories src and include. In order to build the software you will need an installation of the OGDF (reference [4]) Dogwood release available here and will need to update the variables
OGDF_BUILD = /home/bart/OGDF/2022.02 OGDF_SOURCE = /home/bart/OGDF/OGDF
in the Makefile to reflect the location of the OGDF library before running make. There is a check-build-mode.cpp source file included with the above tarball and a build statement make check that might be useful in testing the OGDF installation.
You can build both the programmes 4-gon and doodle by just typing make, or you can build them separately, by name. The OGDF build-checking programme check must be built explicitly.
The bulk of the search is carried out by 4-gon, which takes as parameters the number of crossings and a doodle code and determines a list of distinct prime minimal planar doodles with that code. It has the following command-line syntax:
Usage: 4-gon [-<short-option>] [--<long-option>] <num-crossings> <doodle-code>
<short-option>:
b: boundary chords only (used for testing)
c: chords patterns only (used for testing), turns on b
B: omit boundary chords (used for testing)
i: show initial interior vertex choices only
d: draw graphs of valid 4-gon graphs
Q: quiet mode (only write doodles to cout)
T: test mode
X: development mode
#: debug, see #H! for details
<long-option>:
development: same as -X
draw: same as -d
test: same as -T
A simple example run is shown below:
[bart@localhost 4-gon]$ 4-gon 10 8 4
num_crossings = 10 max_code_index = 5, doodle_code: 0 0 0 8 4
num_vertices_in_dual_graph = 11
num_edges_in_infinite_cycle = 4
num_4_gons_in_disc = 6
num_boundary_vertices = 8
num_interior_vertices = 3
num_interior_edges = 8
test block size = 4
num_test_block_places = 23
found 2 distinct doodles
L1 L2 L3 R4 R6 R8, L4 R7 R9 R1 L5 L6 L7 R3 R10 R5 L8 L9 R2 L10/# # # # # # # # # #; 4-connected
L1 L2 L3 R4 R6 R8, L4 R10 R2 L5, L6 R9 R1 L7, R3 R5 R7 L8 L9 L10/# # # # # # # # # #; 4-connected
Other than the Q option, options are only required for testing and require familiarity with the code to make much sense. Quiet mode suppresses the algorithm detail and only displays the doodle results. The code includes a SIGUSR1 handler that produces status update information on the progress of the search in response to a kill -10 signal.
The programme writes the full display information above to an output file 4-gon.out, due to the way the programm doodle works (see below) it appends to any existing file so care should be taken to remove any unwanted old output files.
The doodle programme simply evaluates all possible doodle codes and calls 4-gon for each one.
Usage: doodle-code [-<short-option>] <num-crossings>
<short-option>:
#: debug, see #H! for details
b: use boundary chords only option for 4-gon
B: use omit boundary chords option for 4-gon
c: show codes only, don't call 4-gon
i: show 4-gon interior choices
The c option can be useful for tracking progress of the code or simply investigating doodle codes.
[bart@localhost 4-gon]$ doodle -c 10
doodle code 8 4
doodle code 9 2 1
doodle code 10 0 2