3. Test Support

Introduction

A major component of adding support for .g6 graph input files (Epic #10) was the restoration of the Test All Graphs functionality (Issue #22). Epic #49 entailed further refinement and expansion of the Test All Graphs functionality, including the automation of various workflows. The TestSupport directory contains the planaritytesting Python package, which is comprised of modules that provide this automation support.

Global Requirements

1. Python 3.12+ must be installed on the system; this can be verified from the command line using python --version, python3 --version, or python3.12 --version.
2. Download and install Nauty so that you have a correctly configured instance of the geng executable

N.B. All usage examples are with cwd as edge-addition-planarity-suite/TestSupport/planaritytesting/

Graph Generation Orchestrator

The first iteration of the graph_generation_orchestrator.py module was introduced in PR #63 to automate the generation of graphs using Nauty's geng (Issue #61). This module uses the multiprocessing and subprocess modules to to create a pool of threads (specifically the number of threads is how many cores the PC on which you are executing the code has) and to run a blocking process on each thread that calls the Nauty geng executable appropriate parameterization so that for the desired graph order, the graphs for each possible edge-count are output to separate files. This module was subsequently revised in PR #74.

Script Requirements

• Correctly configured Nauty geng executable (see Global Requirements)

Usage

graph_generation_orchestrator.py help message

% python3 graph_generation_orchestrator.py -h
usage: python graph_generation_orchestrator.py [options]

Graph Generation Orchestrator
Orchestrates calls to nauty's geng to generate graphs for a given order, separated out into files for each edge count. The output files will have paths:
	{output_dir}/{order}/n{order}.m{num_edges}(.canonical)?.g6

options:
  -h, --help            show this help message and exit
  -g PATH_TO_GENG_EXECUTABLE, --gengpath PATH_TO_GENG_EXECUTABLE
  -l, --canonicalfiles  Generate canonical .g6 files
  -n N, --order N
  -o G6_OUTPUT_DIR, --outputdir G6_OUTPUT_DIR
                        If no output directory provided, defaults to
                        	TestSupport/results/graph_generation_orchestrator/{order}

Example runs of graph_generation_orchestrator.py

One must specify at least the desired order of generated graphs using -n. The default output directory is within TestSupport/results/graph_generation_orchestrator/:

% python3 graph_generation_orchestrator.py -g ../../../nauty/geng -n 5           
% ls ../results/graph_generation_orchestrator/5
n5.m0.g6	n5.m2.g6	n5.m5.g6	n5.m8.g6
n5.m1.g6	n5.m3.g6	n5.m6.g6	n5.m9.g6
n5.m10.g6	n5.m4.g6	n5.m7.g6

If you choose to override the output_dir using -o flag:

% python3 graph_generation_orchestrator.py -g ../../../nauty/geng -n 5 -o ~/graphs
% ls ~/graphs/5
n5.m0.g6	n5.m2.g6	n5.m5.g6	n5.m8.g6
n5.m1.g6	n5.m3.g6	n5.m6.g6	n5.m9.g6
n5.m10.g6	n5.m4.g6	n5.m7.g6

To generate canonical .g6 output files, use the -l flag:

% python3 graph_generation_orchestrator.py -g ../../../nauty/geng -n 5 -l
(virtualenv) wbkboyer@Wandas-MBP planaritytesting % ls ../results/graph_generation_orchestrator/5
n5.m0.canonical.g6	n5.m3.canonical.g6	n5.m7.canonical.g6
n5.m0.g6		n5.m3.g6		n5.m7.g6
n5.m1.canonical.g6	n5.m4.canonical.g6	n5.m8.canonical.g6
n5.m1.g6		n5.m4.g6		n5.m8.g6
n5.m10.canonical.g6	n5.m5.canonical.g6	n5.m9.canonical.g6
n5.m10.g6		n5.m5.g6		n5.m9.g6
n5.m2.canonical.g6	n5.m6.canonical.g6
n5.m2.g6		n5.m6.g6

Algorithm Testing Orchestrator

The first iteration of the planarity_testAllGraphs_orchestrator.py module was introduced in PR #63 to automate running the planarity Test All Graphs functionality for each graph algorithm command specifier on all graphs of a given order (Issue #62), and was subsequently revised in PR #74. The planarity_testAllGraphs_orchestrator.py module follows the same pattern as graph_generation_orchestrator.py in leveraging the multiprocessing and subprocess Python modules to call an executable, in this case to call the planarity executable with parameterization:

planarity -t {command} {infile} {outfile}

Script Requirements

1. The compiled planarity executable
2. The results of having run the graph_generation_orchestrator.py for the graph orders for which you wish to run all supported graph algorithms

Usage

planarity_testAllGraphs_orchestrator.py help message

% python3 planarity_testAllGraphs_orchestrator.py -h
usage: python planarity_testAllGraphs_orchestrator.py [options]

Planarity testAllGraphs execution orchestrator

Orchestrates calls to planarity's Test All Graphs functionality.
Expects input directory to contain a subdirectory whose name is the order containing .g6 files to be tested. Each .g6 file contains all graphs of the given order with a specific number of edges:
	{input_dir}/{order}/n{order}.m{num_edges}(.makeg)?(.canonical)?.g6

Output files will have paths:
	{output_dir}/{order}/{command}/n{order}.m{num_edges}(.makeg)?(.canonical)?.{command}.out.txt

options:
  -h, --help            show this help message and exit
  -p PATH_TO_PLANARITY_EXECUTABLE, --planaritypath PATH_TO_PLANARITY_EXECUTABLE
  -l, --canonicalfiles  Indicates .g6 input files are in canonical form
  -m, --makegfiles      Indicates .g6 input files were generated by makeg
  -n N, --order N
  -i DIR_CONTAINING_G6_FILES, --inputdir DIR_CONTAINING_G6_FILES
                        If no input directory provided, defaults to
                        	TestSupport/results/graph_generation_orchestrator/{order}
  -o DIR_FOR_RESULTS, --outputdir DIR_FOR_RESULTS
                        If no output directory provided, defaults to
                        	TestSupport/results/planarity_testAllGraphs_orchestrator/{order}

Example run of planarity_testAllGraphs_orchestrator.py

One must specify at least the desired order of generated graphs using -n. The default input directory is TestSupport/results/graph_generation_orchestrator/{order}, and the default output directory is TestSupport/results/planarity_testAllGraphs_orchestrator/, under which a subdirectory labelled with the chosen graph order is created and to which files are output:

% python3 planarity_testAllGraphs_orchestrator.py -p ../../Release/planarity -n 5
% ls ../results/planarity_testAllGraphs_orchestrator/5/2
n5.m0.2.out.txt		n5.m3.2.out.txt		n5.m7.2.out.txt
n5.m1.2.out.txt		n5.m4.2.out.txt		n5.m8.2.out.txt
n5.m10.2.out.txt	n5.m5.2.out.txt		n5.m9.2.out.txt
n5.m2.2.out.txt		n5.m6.2.out.txt
% cat ../results/planarity_testAllGraphs_orchestrator/5/2/n5.m7.2.out.txt
FILENAME="n5.m7.g6" DURATION="0.000"
-2 4 2 2 SUCCESS

If you specify an input directory other than the default, if the name of the directory is an integer, it must match the value you specified for the graph order (i.e. -n flag) because validation is done to ensure the input directory has the expected contents:

% python3 planarity_testAllGraphs_orchestrator.py -p ../../Release/planarity -n 5 -i ~/graphs/5 -o ~/planarity_testAllGraphs_output
% ls ~/planarity_testAllGraphs_output/5
2	3	4	d	o	p
% ls ~/planarity_testAllGraphs_output/5/3
n5.m0.3.out.txt		n5.m3.3.out.txt		n5.m7.3.out.txt
n5.m1.3.out.txt		n5.m4.3.out.txt		n5.m8.3.out.txt
n5.m10.3.out.txt	n5.m5.3.out.txt		n5.m9.3.out.txt
n5.m2.3.out.txt		n5.m6.3.out.txt
% cat ~/planarity_testAllGraphs_output/5/2/n5.m7.2.out.txt
FILENAME="n5.m7.g6" DURATION="0.000"
-2 4 2 2 SUCCESS

To run planarity Test All Graphs on canonical .g6 files, you must use the -l flag; only files with names like n{order}.m{num_edges}.canonical.g6 will be included in the run, and output files will have filenames of the form n{order}.m{num_edges}.canonical.{command}.out.txt

% python3 planarity_testAllGraphs_orchestrator.py -p ../../Release/planarity -n 5 -l
% ls ../results/planarity_testAllGraphs_orchestrator/5/2
n5.m0.2.out.txt			n5.m4.canonical.2.out.txt
n5.m0.canonical.2.out.txt	n5.m5.2.out.txt
n5.m1.2.out.txt			n5.m5.canonical.2.out.txt
n5.m1.canonical.2.out.txt	n5.m6.2.out.txt
n5.m10.2.out.txt		n5.m6.canonical.2.out.txt
n5.m10.canonical.2.out.txt	n5.m7.2.out.txt
n5.m2.2.out.txt			n5.m7.canonical.2.out.txt
n5.m2.canonical.2.out.txt	n5.m8.2.out.txt
n5.m3.2.out.txt			n5.m8.canonical.2.out.txt
n5.m3.canonical.2.out.txt	n5.m9.2.out.txt
n5.m4.2.out.txt			n5.m9.canonical.2.out.txt

Test Table Generator

test_table_generator.py was introduced in PR #66 to compile the planarity Test All Graphs results for a given graph order and algorithm command specifier (Issue #65). This module was revised in PR #74, and again in PR #90 to optionally incorporate the numInvalidOK for K_{2, 3} search, K_{3, 3} search, and K_4 search derived by performing the edge-deletion analysis on all graphs of each edge-count. PR #115 ensures that "# Invalid OK", "EDA Proc Time", and "EDA Total Time" columns are shown based on the truthiness of self._edge_deletion_analysis_results, which is only a nonempty dict if TestTableGenerator is initialized by TestSupport/planaritytesting/test_table_generation_with_numInvalidOK.py with the EDA results for an order and command.

Script Requirements

• Run planarity_testAllGraphs_orchestrator.py to generate the planarity Test All Graphs output files for a given graph order and for all algorithm command specifiers
  • N.B. Make note of the output directory that you used; the input directory for the TestTableGenerator should be

    {planarity_testAllGraphs_output_dir}/{order}/{command}`
    

    And will contain files with names of the form n{order}.m{num_edges}.{command}.out.txt

Usage

test_table_generator.py help message

 % python3 test_table_generator.py -h
usage: python test_table_generator.py [options]

Test Table Generator
Tabulates results from output files produced by planarity's Test All Graphs functionality.

Expects to be given an input directory containing only the output files produced by running planarity's Test All Graphs for a specific algorithm.

Preferably, this will be the output from having run the Planarity Orchestrator, and will have a path of the form:
	{parent_dir}/{order}/{command}/
And will contain files with the full path:
	{parent_dir}/{order}/{command}/n{order}.m{numEdges}(.makeg)?(.canonical)?.{command}.out.txt

Will output one file per graph algorithm containing the tabulated data compiled from the planarity Test All Graphs output files:
	{output_dir}/n{order}.mALL(.makeg)?(.canonical)?.{command}.out.txt

options:
  -h, --help            show this help message and exit
  -i INPUT_DIR, --inputdir INPUT_DIR
  -o OUTPUT_DIR, --outputdir OUTPUT_DIR
  -c ALGORITHM_COMMAND, --command ALGORITHM_COMMAND
                        One of (pdo234); defaults to '3'
  -n ORDER, --order ORDER
                        Order of graphs for which you wish to compile results of having run planarity with given command specifier. Defaults to N = 11
  -l, --canonicalfiles  Planarity output files must contain 'canonical' in name
  -m, --makegfiles      Planarity output files must contain 'makeg' in name

Example run of test_table_generator.py

Using defaults based on -c and -n flags:

% python3 test_table_generator.py -c 3 -n 5
% cat ./TestSupport/tables/5/n5.mALL.3.out.txt
| Input filename | # Edges | # Graphs | # OK | # NONEMBEDDABLE |Error flag| Duration |
|================|=========|==========|======|=================|==========|==========|
|n5.m0.g6        |0        |1         |1     |0                |SUCCESS   |0.0       |
|n5.m1.g6        |1        |1         |1     |0                |SUCCESS   |0.0       |
|n5.m2.g6        |2        |2         |2     |0                |SUCCESS   |0.0       |
|n5.m3.g6        |3        |4         |4     |0                |SUCCESS   |0.0       |
|n5.m4.g6        |4        |6         |6     |0                |SUCCESS   |0.0       |
|n5.m5.g6        |5        |6         |6     |0                |SUCCESS   |0.0       |
|n5.m6.g6        |6        |6         |6     |0                |SUCCESS   |0.0       |
|n5.m7.g6        |7        |4         |4     |0                |SUCCESS   |0.0       |
|n5.m8.g6        |8        |2         |2     |0                |SUCCESS   |0.0       |
|n5.m9.g6        |9        |1         |1     |0                |SUCCESS   |0.0       |
|n5.m10.g6       |10       |1         |1     |0                |SUCCESS   |0.0       |
|================|=========|==========|======|=================|==========|==========|
|TOTALS                    |34        |34    |0                |11        |0.0       |

If you specify the input_dir using -i and to override the output_dir using -o:

% python3 test_table_generator.py -i ~/planarity_testAllGraphs_output/5/3 -o ~/planarity_tables
% cat ~/planarity_tables/5/n5.mALL.3.out.txt 
| Input filename | # Edges | # Graphs | # OK | # NONEMBEDDABLE |Error flag| Duration |
|================|=========|==========|======|=================|==========|==========|
|n5.m0.g6        |0        |1         |1     |0                |SUCCESS   |0.0       |
|n5.m1.g6        |1        |1         |1     |0                |SUCCESS   |0.0       |
|n5.m2.g6        |2        |2         |2     |0                |SUCCESS   |0.0       |
|n5.m3.g6        |3        |4         |4     |0                |SUCCESS   |0.0       |
|n5.m4.g6        |4        |6         |6     |0                |SUCCESS   |0.0       |
|n5.m5.g6        |5        |6         |6     |0                |SUCCESS   |0.0       |
|n5.m6.g6        |6        |6         |6     |0                |SUCCESS   |0.0       |
|n5.m7.g6        |7        |4         |4     |0                |SUCCESS   |0.0       |
|n5.m8.g6        |8        |2         |2     |0                |SUCCESS   |0.0       |
|n5.m9.g6        |9        |1         |1     |0                |SUCCESS   |0.0       |
|n5.m10.g6       |10       |1         |1     |0                |SUCCESS   |0.0       |
|================|=========|==========|======|=================|==========|==========|
|TOTALS                    |34        |34    |0                |11        |0.0       |

If you wish to generate the test tables for canonical .g6 files, you must use the -l flag:

% python3 test_table_generator.py -n 5 -c 3 -l
(virtualenv) wbkboyer@Wandas-MBP planaritytesting % cat ../tables/5/n5.mALL.canonical.3.out.txt
|   Input filename    | # Edges | # Graphs | # OK | # NONEMBEDDABLE |Error flag| Duration |
|=====================|=========|==========|======|=================|==========|==========|
|n5.m0.canonical.g6   |0        |1         |1     |0                |SUCCESS   |0.0       |
|n5.m1.canonical.g6   |1        |1         |1     |0                |SUCCESS   |0.0       |
|n5.m2.canonical.g6   |2        |2         |2     |0                |SUCCESS   |0.0       |
|n5.m3.canonical.g6   |3        |4         |4     |0                |SUCCESS   |0.0       |
|n5.m4.canonical.g6   |4        |6         |6     |0                |SUCCESS   |0.0       |
|n5.m5.canonical.g6   |5        |6         |6     |0                |SUCCESS   |0.0       |
|n5.m6.canonical.g6   |6        |6         |6     |0                |SUCCESS   |0.0       |
|n5.m7.canonical.g6   |7        |4         |4     |0                |SUCCESS   |0.0       |
|n5.m8.canonical.g6   |8        |2         |2     |0                |SUCCESS   |0.0       |
|n5.m9.canonical.g6   |9        |1         |1     |0                |SUCCESS   |0.0       |
|n5.m10.canonical.g6  |10       |1         |1     |0                |SUCCESS   |0.0       |
|=====================|=========|==========|======|=================|==========|==========|
|TOTALS                         |34        |34    |0                |11        |0.0       |

Graph6 File Diff Finder

The creation of the Test Table Generator allowed us to create new versions of the tables for N=11 to reproduce the results produced by previous versions of the edge-addition-planarity-suite. This revealed an issue with the K_{3, 3} search graph algorithm extension: the planarity Test All Graphs result summary tables created using the current edge-addition-planarity-suite highlighted that there were 100 more 11-vertex 20-edge graphs labelled as K_{3, 3}-free than by the version 2.0 code (Epic #42).

After determining that the current edge-addition-planarity-suite code produced the same OK/NONEMBEDDABLE results as the version 2.0 code on the same individual graphs generated by v2.0's embedded makeg machinery (Commit #82233), the investigation of which was documented in this comment, we hypothesized that the 100 additional OKs produced by the edge-addition-planarity-suite on the new Nauty geng .g6 file vs. on the makeg .g6 file for K_{3, 3} search may be explained by duplicate graphs (see this comment for full reasoning).

The g6_diff_finder.py introduced in PR #72 to satisfy the requirements of Issue #75 was developed with the intent of comparing the .g6 graph input files produced by Nauty's geng vs. those that were produced in-memory by the makeg machinery and answered the questions stated in this comment; since

1. There were no duplicates in the .g6 files produced by either the old (embedded makeg) or new (external Nauty geng application) graph generation mechanisms
2. There were graphs generated by Nauty geng that were not produced by makeg, and graphs produced by makeg that were not produced by Nauty geng
3. There were graphs that were generated by both Nauty geng and makeg but which appeared on different line numbers in their respective .g6 output files

We concluded that the discrepancies in K_{3, 3} search results must be on the graphs in those set-differences, since planarity produces the same results on the same input graphs.

Although the original context was comparing Nauty geng .g6 and makeg .g6 files, the discovery of the -l flag to generate graphs by their canonical labelling (see the Nauty main page), allowed us to run the g6_diff_finder.py as a script to manually compare geng .g6, geng canonical .g6, makeg .g6, and makeg canonical .g6 files.

Script requirements

Requires two .g6 input files as comparands. The expected use case is that one is comparing .g6 files containing all graphs for a specific order (and possibly for only one edge-count) that were generated by different mechanisms, for example comparing geng .g6 vs. geng canonical .g6 graphs, since comparing .g6 files for two different graph orders or for a specific graph order but two different edge-counts is not useful.

Usage

g6_diff_finder.py help message

% python3 g6_diff_finder.py -h
usage: python g6_diff_finder.py [options]

Tool to help interrogate and compare two .g6 files.
- Determines if there are duplicates in the first and second comparand .g6 files; outputs to files with paths:
	{first_comparand_infile_dir}/results/{first_comparand_infile_name}.duplicates.out.txt
	{second_comparand_infile_dir}/results/{second_comparand_infile_name}.duplicates.out.txt
- Determines if there any graphs that appear in the first .g6 file that do not appear in the second .g6 file, and vice versa; outputs to files with paths:
	{first_comparand_infile_dir}/results/graphs_in_{first_comparand_infile_name}_not_in_{second_comparand_infile_name}.g6
	{second_comparand_infile_dir}/results/graphs_in_{second_comparand_infile_name}_not_in_{first_comparand_infile_name}.g6
- Records graphs that occur in both files but which appear on different line numbers; outputs to a file with path:
	{first_comparand_infile_dir}/results/graphs_in_{first_comparand_infile_name}_and_{second_comparand_infile_name}.txt

options:
  -h, --help            show this help message and exit
  --first_comparand FIRST_COMPARAND.g6, -f FIRST_COMPARAND.g6
                        The first .g6 file to compare.
  --second_comparand SECOND_COMPARAND.g6, -s SECOND_COMPARAND.g6
                        The second .g6 file to compare.

Example run of g6_diff_finder.py

For graph order N=7 and edge-count M=15, one compares the geng .g6 and geng canonical .g6 input files as follows:

% python3 g6_diff_finder.py -f n7.m15.g6 -s n7.m15.canonical.g6 
% ls TestSupport/results/graph_generation_orchestrator/example 
n7.m15.canonical.g6	n7.m15.g6		results
% ls TestSupport/results/graph_generation_orchestrator/example/results
graphs_in_n7.m15.canonical_not_in_n7.m15.g6	graphs_in_n7.m15_not_in_n7.m15.canonical.g6

When running the g6_diff_finder.py as a script, logs are output to TestSupport/g6_diff_finder_logs/G6DiffFinder.log:

% cat TestSupport/g6_diff_finder_logs/G6DiffFinder.log 
2024-07-24 15:34:48,158 - [INFO] - g6_diff_finder._populate_comparand_dict - Populating comparand dict from infile path 'n7.m15.g6'.
2024-07-24 15:34:48,158 - [INFO] - g6_diff_finder._populate_comparand_dict - Populating comparand dict from infile path 'n7.m15.canonical.g6'.
2024-07-24 15:34:48,158 - [INFO] - g6_diff_finder._output_duplicates - No duplicates present in 'n7.m15.g6'.
2024-07-24 15:34:48,158 - [INFO] - g6_diff_finder._output_duplicates - No duplicates present in 'n7.m15.canonical.g6'.
2024-07-24 15:34:48,158 - [INFO] - g6_diff_finder._graph_set_diff - Outputting graphs present in 'n7.m15' that aren't in 'n7.m15.canonical' to 'graphs_in_n7.m15_not_in_n7.m15.canonical.g6'.
2024-07-24 15:34:48,158 - [INFO] - g6_diff_finder._graph_set_diff - Outputting graphs present in 'n7.m15.canonical' that aren't in 'n7.m15' to 'graphs_in_n7.m15.canonical_not_in_n7.m15.g6'.
2024-07-24 15:34:48,159 - [INFO] - g6_diff_finder.graph_set_intersection_with_different_line_nums - No graphs present in both 'n7.m15' and 'n7.m15.canonical' that appear on different lines.

Graph Generation and Results Comparison Driver

After implementing the G6DiffFinder and using it to manually compare the .g6 files generated by Nauty's geng vs. makeg, it became necessary to automate the systematic detection of discrepancies in the planarity testAllGraphs() OK/NONEMBEDDABLE counts for each graph algorithm command on the geng .g6, geng canonical .g6, makeg .g6, and makeg canonical .g6 files for each edge-count to determine if there was a smaller order and edge-count than N=8 and M=15 where K_{3, 3} search erroneously reported OK (i.e. K_{3, 3} search results did not diverge before N=8 and M=15 when run on geng .g6 vs. makeg .g6). The specification was given in Issue #76 and the g6_generation_and_comparison_driver.py was introduced in PR #72.

Script Requirements

• Correctly configured Nauty geng executable (see Global Requirements)
• The compiled planarity executable

N.B. The optional parameter for the path to the planarity-backup executable should not generally be used, as it requires one to take the edge-addition-planarity-suite v2.0 code and graft in the G6WriteIterator machinery so that one may write the graphs produced by the embedded makeg machinery (Commit #82233) to file. This was initially introduced to verify that the current edge-addition-planarity-suite produced the same results as v2.0 on the same input.

Usage

g6_generation_and_comparison_driver.py help message

% python3 g6_generation_and_comparison_driver.py -h
usage: python g6_generation_and_comparison_driver.py [options]

G6 File Generation and Comparison Tool

For each graph order in the specified range, a child directory of the output directory will be created named 'n{order}'. This directory will contain subdirectories:
- graphs/
	- For each edge-count from 0 to (N * (N - 1)) / 2, a directory is created to contain:
	n{order}.m{num_edges}.g6
	n{order}.m{num_edges}.canonical.g6
	n{order}.m{num_edges}.makeg.g6 (req. planarity-backup 	path)
	n{order}.m{num_edges}.makeg.canonical.g6 (req. planarity-backup path)
	- results/ which will contain the diffs of these .g6  files, pairs of files:
		- graphs_in_{first_infile}_not_in_{second_infile}.g6
		- graphs_in_{second_infile}_not_in_{first_infile}.g6
	These pairs should contain the same number of graphs
- planarity_results/
	- For each graph algorithm command specifier, there will be a subdirectory containing one subdirectory for each edge-count (0 to (N * (N - 1)) / 2), which will contain files:
	n{order}.m{num_edges}.{command}.out.txt
	n{order}.m{num_edges}.canonical.{command}.out.txt
	n{order}.m{num_edges}.makeg.{command}.out.txt
	n{order}.m{num_edges}.makeg.canonical.{command}.out.txt
- g6_diff_finder_logs/
	- Will contain logs for each of the following comparisons:
	G6DiffFinder.n{order}.geng_vs_geng-canonical.log
	G6DiffFinder.n{order}.geng_vs_makeg.log
	G6DiffFinder.n{order}.geng_vs_makeg-canonical.log
	G6DiffFinder.n{order}.geng-canonical_vs_makeg-canonical.log
	G6DiffFinder.n{order}.makeg_vs_makeg-canonical.log

options:
  -h, --help            show this help message and exit
  -g PATH_TO_GENG_EXECUTABLE, --gengpath PATH_TO_GENG_EXECUTABLE
                        Path to nauty geng executable
  -n X[,Y], --orders X[,Y]
                        Order(s) of graphs for which you wish to generate .g6 files
  -p PATH_TO_PLANARITY_EXECUTABLE, --planaritypath PATH_TO_PLANARITY_EXECUTABLE
                        Path to planarity executable
  -b PATH_TO_PLANARITY_BACKUP_EXECUTABLE, --planaritybackuppath PATH_TO_PLANARITY_BACKUP_EXECUTABLE
                        Path to planarity-backup executable (optional; not public!)
  -o OUTPUT_DIR_PATH, --outputdir OUTPUT_DIR_PATH
                        Parent directory under which subdirectories will be created for output results. If none provided, defaults to:
                        	TestSupport/results/g6_generation_and_comparison_driver/

Example run of g6_generation_and_comparison_driver.py

To determine for which order and edge-count any of the graph algorithm commands produced different OK/NONEMBEDDABLE counts when run on geng .g6 vs. geng canonical .g6 graph input files, for example for orders N \in [5, 8], one need only specify the desired orders and the path to the geng executable:

% python3 g6_generation_and_comparison_driver.py -n 5,8 -g ../../../nauty/geng 

Then, one can check the log files for each order to view the discrepancies found; for example, for N=6 and M=13, we can see that there were discrepancies between the results for K_{3, 3} search when run on the geng .g6 graphs and geng canonical .g6 graphs:

% cat TestSupport/results/g6_generation_and_comparison_driver/6/planarity_results/n6.planarity_discrepancies.txt
Discrepancies in planarity output results for order 6 by edge-count and algorithm specifier:
======
{
    "13": {
        "3": {
            "geng_g6": {
                "numGraphs": "2",
                "numOK": "1",
                "numNONEMBEDDABLE": "1"
            },
            "geng_canonical_g6": {
                "numGraphs": "2",
                "numOK": "0",
                "numNONEMBEDDABLE": "2"
            }
        }
    }
}

Edge-Deletion Analyzer

G6GenerationAndComparisonDriver allowed us to determine for each desired graph order if there were discrepancies in the results obtained by testAllGraphs() for any of the graph algorithm commands when comparing the output across geng .g6, geng canonical .g6, makeg .g6, and makeg canonical .g6 files for each edge-count. Although this tool helped us to manually find a smaller graph (N=6 and M=13) on which K_{3, 3} search erroneously reported OK (see this comment), it highlighted the need for a tool to identify which graphs in particular in a .g6 input file were erroneously reported by K_{3, 3} search as K_{3, 3}-free.

Issue #77 outlines the requirements of this tool, which automate the steps performed in this comment on two candidate graphs identified in this comment. The EdgeDeletionAnalyzer was introduced in PR #78, and subsequently expanded to support testing K_{2, 3} search and K_4 search (see Issue #79 and PR #87))

Script Requirements

1. The compiled planarity executable
2. A .g6 graph input file

Usage

edge_deletion_analysis.py help message

% python3 edge_deletion_analysis.py -h
usage: python edge_deletion_analysis.py [options]

Edge deletion analysis tool

When given an input file, determine the type of input. If the file is a not a .g6 file, an error is raised. Otherwise, iterate over each line and create a separate .g6 file:
	{input_file.stem}.{line_num}.g6
And perform the following steps on each graph:
1. Runs
	planarity -t -ta {input_file} {infile_stem}.AdjList.out.txt
to transform the graph to adjacency list
2. Runs
	planarity -s -{extension_choice} {infile_stem}.AdjList.out.txt {infile_stem}.AdjList.s.{extension_choice}.out.txt
and report whether a subgraph homeomorphic to K_{2, 3} (extension choice is 2), K_{3, 3} (extension choice is 3), or K_4 (extension choice is 4) was found (NONEMBEDDABLE) or not (OK).
3. If no subgraph homeomorphic to the target homeomorph was found (i.e. previous test yielded OK), run
	planarity -s -p {infile_stem}.AdjList.out.txt {infile_stem}.AdjList.s.[po].out.txt {infile_stem}.AdjList.s.[po].obstruction.txt
Where we run planarity if the extension choice is 3 or outerplanarity if the extension choice is 2 or 4.
	a. If the graph is reported as planar/outerplanar, then we can be sure the target homeomorph will not be present in the graph and execution terminates.
	b. If the graph was reported as nonplanar/nonouterplanar, examine the obstruction in 
		{input_file}.AdjList.s.[po].obstruction.txt:
		i. If the obstruction is homeomorphic to K_{2, 3}/K_{3, 3}/K_4, then report that the original graph contains the target homeomorph that was not found by the respective graph search extension.
		ii. If the obstruction is homeomorphic to the other forbidden minor (K_4 for K{2, 3}, K_5 for K_{3, 3}, or K_{2, 3} for K_4) then perform the edge-deletion analysis to determine if the original graph contains a subgraph homeomorphic to the target homeomorph thatwasn't found by the corresponding graph search extension, or if the original graph doesn't contain the target homeomorph (with high confidence).

options:
  -h, --help            show this help message and exit
  -p PATH_TO_PLANARITY_EXECUTABLE, --planaritypath PATH_TO_PLANARITY_EXECUTABLE
                        Path to planarity executable
  -i PATH_TO_GRAPH(s), --inputfile PATH_TO_GRAPH(s)
                        Path to graph(s) to analyze
  -o OUTPUT_DIR_PATH, --outputdir OUTPUT_DIR_PATH
                        Parent directory under which subdirectory named after {infile_stem} will be created for output results. If none provided, defaults to:
                        	TestSupport/results/edge_deletion_analysis/{infile_stem}
  -c ALGORITHM_COMMAND, --command ALGORITHM_COMMAND
                        Graph algorithm command specifier, either 2 (K_{2, 3} search), 3 (K_{3, 3} search), or 4 (K_4 search)

Example run of edge_deletion_analysis.py

For N = 6 and M = 13, we report one OK for both geng .g6 and makeg .g6, but for the geng canonical .g6 and makeg canonical .g6 both report both graphs are NONEMBEDDABLE. Therefore, we choose to run the edge-deletion analysis on n6.m13.g6 to determine which of the two graphs was erroneously reported as OK by K_{3, 3} search:

% cat n6.m13.g6
EV~w
E]~w
% python3 edge_deletion_analysis.py -p ../../Release/planarity -i ../results/graph_generation_orchestrator/6/n6.m13.g6 -c 3 
2024-07-29 13:00:54,649 - [ERROR] - edge_deletion_analysis.analyze_transformed_graph - In '/Users/wbkboyer/git/edge-addition-planarity-suite-fork/TestSupport/results/edge_deletion_analysis/n6.m13/3/n6.m13.g6.1/n6.m13.g6.1.AdjList.out.txt', edge-deletion analysis determined that there is a K_{3, 3} that was not found by K_{3, 3} search.

Since the default output directory was used, one may look at the logs with path TestSupport/results/edge_deletion_analysis/n6.m13/3/edge_deletion_analysis-n6.m13.3.log to see the steps performed by the edge-deletion analysis to determine that the first graph in the file EV~w was erroneously reported as not containing a subgraph homeomorphic to K_{3, 3} by K_{3, 3} search.

Results of Edge-Deletion Analyses

Once the EdgeDeletionAnalyzer was implemented, we sought to answer the question "for each of K_{3, 3} search, K_{2, 3} search, and K_4 search, how many graphs can we detect by edge deletion analysis that are erroneously reported as not containing a subgraph homeomorphic to the target graph?"

Issue #80 provides the specification for the test_table_generation_with_numInvalidOK.py tool, which was introduced in PR #90. This tool allows the user to specify the graph algorithm commands for which they wish to generate the Test Tables from the planarity output results with the -c flag; if the commands specified include 2, 3, and/or 4, then edge-deletion analysis will first be run on each of these .g6 infiles to determine the lower bound on the numInvalidOKs for K_{3, 3} search, K_{2, 3} search, and/or K_4 search.

This script was refactored to per Issue #108 with PR #114 so that when a single graph order and command specifier are given, intermediate results for previously processed edge-counts are stored in a file TestSupport/results/test_table_generation_with_numInvalidOK/N_{order}-C_{command}.json which has the form:

{
    <graph order N>:
    {
        "<command specifier C>":
        {
            "<infile_name for M=0>":
            {
                "numInvalidOK": numInvalidOK,
                "proc_time_s": proc_time_s,
                "tot_time_s": tot_time_s
            }
            "<infile_name for M=1>":
            {
                "numInvalidOK": numInvalidOK,
                "proc_time_s": proc_time_s,
                "tot_time_s": tot_time_s
            }
            ...
            "<infile_name for M=maxProcessedEdgeCount>":
            {
                "numInvalidOK": numInvalidOK,
                "proc_time_s": proc_time_s,
                "tot_time_s": tot_time_s
            }
        }
    }
}

So that in case of unexpected program termination, one may resume processing at the edge-count follow that which had been successfully processed and stored. Additionally, when a user specifies a single order and command, users may provide an edgecount_limit with the -e flag so that processing is done only up to and including that edge-count.

Script Requirements

1. The compiled planarity executable
2. The .g6 files produced by the graph_generation_orchestrator.py for each graph order
3. The results of having run the planarity_testAllGraphs_orchestrator.py on the aforementioned .g6 files (i.e. those generated for each order, partitioned by edge-count)

Usage

test_table_generation_with_numInvalidOK.py help message

% python3 test_table_generation_with_numInvalidOK.py -h
usage: python test_table_generation_with_numInvalidOK.py [options]

Test Table Generation including numInvalidOKs

For each specified graph order:
1. For each edgecount from 0 to (N * (N - 1))/2, runs the EdgeDeletionAnalyzer for K_{2, 3} search, K_{3, 3} search, and K_4 search to determine the numInvalidOKs for those graph algorithm extensions.
2. For each of the supported graph algorithms, Tabulates results from running planarity's Test All Graphs functionality, incorporating the numInvalidOKs if applicable.

options:
  -h, --help            show this help message and exit
  -p PATH_TO_PLANARITY_EXECUTABLE, --planaritypath PATH_TO_PLANARITY_EXECUTABLE
                        Path to planarity executable. Defaults to:
                        	{planarity_project_root}/Release/planarity
  -n X[,Y], --orders X[,Y]
                        Order(s) of graphs for which you wish to generate Test Tables; for commands ('2', '3', '4'), will include numInvalidOKs derived by edge-deletion analysis.
  -e M, --edgecountlimit M
                        If only a single graph order and graph search algorithm are specified, perform EDA for edge-counts up to and including this value.
  -c GENTABLECOMMANDS [GENTABLECOMMANDS ...], --gentablecommands GENTABLECOMMANDS [GENTABLECOMMANDS ...]
                        List of algorithm command specifiers for which you wish to generate test tables. Defaults to ('p', 'd', 'o', '2', '3', '4')
  -g PATH_TO_GRAPH_PARENT_DIR, --graphdir PATH_TO_GRAPH_PARENT_DIR
                        Path to parent directory containing subdirectories for each graph order, the contents of which are assumed to be .g6 files (one for each number of edges from 0 to (N * (N - 1))/2). Defaults to:
                        	TestSupport/results/graph_generation_orchestrator/
  -t PATH_TO_PLANARITY_OUTPUT, --planarityoutputdir PATH_TO_PLANARITY_OUTPUT
                        Path to parent directory containing subdirectories for each graph order, the contents of which are subdirectories for each graph algorithm extension (i.e. ('p', 'd', 'o', '2', '3', '4')). Each of these directories contains the results of running planarity Test All Graphs for the given command on all graphs of a given order and number of edges. Defaults to:
                        	TestSupport/results/planarity_testAllGraphs_orchestrator/
                        The directories will have the form:
                        	{planarity_output_dir}/{order}/{command}/
                        And will contain files with names of the form:
                        	n{order}.m{num_edges}(.makeg)?(.canonical)?.{command}.out.txt
  -o OUTPUT_DIR_PATH, --outputdir OUTPUT_DIR_PATH
                        Parent directory under which subdirectory named after each{order} will be created for output results. If none provided, defaults to:
                        	TestSupport/tables/
                        For each chosen order, output file paths have the form:
                        	{output_dir}/{order}/n{order}.mALL.{command}.out.txt
  -l, --canonicalfiles  Indicates .g6 input files are in canonical form
  -m, --makegfiles      Indicates .g6 input files were generated by makeg

Example run of test_table_generation_with_numInvalidOK.py

If you wish to determine the numInvalidOKs for each graph order N \in [5, 7] for K_{3, 3} search and have already run the graph_generation_orchestrator.py for orders 5 through 7, as well as the planarity_testAllGraphs_orchestrator.py, you only need to use the -n flag to specify the range of orders and the -c flag to specify the algorithm command specifier (i.e. "3"); for example, prior to the fix for K_{3, 3} search Issue #105, a sample run would look like:

% python3 test_table_generation_with_numInvalidOK.py -n 5,7 -c 3
2024-07-29 15:20:03,792 - [ERROR] - edge_deletion_analysis.analyze_transformed_graph - In '/Users/wbkboyer/git/edge-addition-planarity-suite-fork/TestSupport/results/edge_deletion_analysis/n6.m13/3/n6.m13.g6.1/n6.m13.g6.1.AdjList.out.txt', edge-deletion analysis determined that there is a K_{3, 3} that was not found by K_{3, 3} search.
2024-07-29 15:20:09,372 - [ERROR] - edge_deletion_analysis.analyze_transformed_graph - In '/Users/wbkboyer/git/edge-addition-planarity-suite-fork/TestSupport/results/edge_deletion_analysis/n7.m13/3/n7.m13.g6.40/n7.m13.g6.40.AdjList.out.txt', edge-deletion analysis determined that there is a K_{3, 3} that was not found by K_{3, 3} search.
2024-07-29 15:20:10,055 - [ERROR] - edge_deletion_analysis.analyze_transformed_graph - In '/Users/wbkboyer/git/edge-addition-planarity-suite-fork/TestSupport/results/edge_deletion_analysis/n7.m14/3/n7.m14.g6.11/n7.m14.g6.11.AdjList.out.txt', edge-deletion analysis determined that there is a K_{3, 3} that was not found by K_{3, 3} search.
2024-07-29 15:20:10,160 - [ERROR] - edge_deletion_analysis.analyze_transformed_graph - In '/Users/wbkboyer/git/edge-addition-planarity-suite-fork/TestSupport/results/edge_deletion_analysis/n7.m14/3/n7.m14.g6.15/n7.m14.g6.15.AdjList.out.txt', edge-deletion analysis determined that there is a K_{3, 3} that was not found by K_{3, 3} search.
2024-07-29 15:20:10,265 - [ERROR] - edge_deletion_analysis.analyze_transformed_graph - In '/Users/wbkboyer/git/edge-addition-planarity-suite-fork/TestSupport/results/edge_deletion_analysis/n7.m14/3/n7.m14.g6.28/n7.m14.g6.28.AdjList.out.txt', edge-deletion analysis determined that there is a K_{3, 3} that was not found by K_{3, 3} search.
2024-07-29 15:20:10,555 - [ERROR] - edge_deletion_analysis.analyze_transformed_graph - In '/Users/wbkboyer/git/edge-addition-planarity-suite-fork/TestSupport/results/edge_deletion_analysis/n7.m14/3/n7.m14.g6.54/n7.m14.g6.54.AdjList.out.txt', edge-deletion analysis determined that there is a K_{3, 3} that was not found by K_{3, 3} search.
2024-07-29 15:20:10,610 - [ERROR] - edge_deletion_analysis.analyze_transformed_graph - In '/Users/wbkboyer/git/edge-addition-planarity-suite-fork/TestSupport/results/edge_deletion_analysis/n7.m14/3/n7.m14.g6.56/n7.m14.g6.56.AdjList.out.txt', edge-deletion analysis determined that there is a K_{3, 3} that was not found by K_{3, 3} search.
2024-07-29 15:20:10,727 - [ERROR] - edge_deletion_analysis.analyze_transformed_graph - In '/Users/wbkboyer/git/edge-addition-planarity-suite-fork/TestSupport/results/edge_deletion_analysis/n7.m15/3/n7.m15.g6.3/n7.m15.g6.3.AdjList.out.txt', edge-deletion analysis determined that there is a K_{3, 3} that was not found by K_{3, 3} search.
2024-07-29 15:20:10,911 - [ERROR] - edge_deletion_analysis.analyze_transformed_graph - In '/Users/wbkboyer/git/edge-addition-planarity-suite-fork/TestSupport/results/edge_deletion_analysis/n7.m15/3/n7.m15.g6.23/n7.m15.g6.23.AdjList.out.txt', edge-deletion analysis determined that there is a K_{3, 3} that was not found by K_{3, 3} search.
2024-07-29 15:20:10,971 - [ERROR] - edge_deletion_analysis.analyze_transformed_graph - In '/Users/wbkboyer/git/edge-addition-planarity-suite-fork/TestSupport/results/edge_deletion_analysis/n7.m15/3/n7.m15.g6.25/n7.m15.g6.25.AdjList.out.txt', edge-deletion analysis determined that there is a K_{3, 3} that was not found by K_{3, 3} search.
2024-07-29 15:20:11,148 - [ERROR] - edge_deletion_analysis.analyze_transformed_graph - In '/Users/wbkboyer/git/edge-addition-planarity-suite-fork/TestSupport/results/edge_deletion_analysis/n7.m16/3/n7.m16.g6.8/n7.m16.g6.8.AdjList.out.txt', edge-deletion analysis determined that there is a K_{3, 3} that was not found by K_{3, 3} search.

To examine the results for the edge-deletion analysis, you can traverse the output directory (defaults to TestSupport/results/edge_deletion_analysis) and find the subdirectory corresponding to the order and edge-count where K_{3, 3} search erroneously reported OK. For example, for N=6 and M=13 the full logs for all graphs in n6.m13.g6 are in TestSupport/results/edge_deletion_analysis/n6.m13/3/edge_deletion_analysis-n6.m13.3.log. This directory only contains one subdirectory, n6.m13.g6.1, since only the graph on the first line of the input file (i.e. EV~w) contained a K_{3, 3} homeomorph that was not detected by K_{3, 3} search.

Now, the table produced (i.e. TestSupport/tables/6/n6.mALL.3.out.txt) will include the # Invalid OK column:

| Input filename | # Edges | # Graphs | # OK | # NONEMBEDDABLE |Error flag| Duration | # Invalid OK | EDA Proc Time | EDA Total Time |
|================|=========|==========|======|=================|==========|==========|==============|===============|================|
|n6.m0.g6        |0        |1         |1     |0                |SUCCESS   |0.0       |0             |0.016          |0.021           |
|n6.m1.g6        |1        |1         |1     |0                |SUCCESS   |0.0       |0             |0.000          |0.021           |
|n6.m2.g6        |2        |2         |2     |0                |SUCCESS   |0.0       |0             |0.000          |0.043           |
|n6.m3.g6        |3        |5         |5     |0                |SUCCESS   |0.0       |0             |0.031          |0.111           |
|n6.m4.g6        |4        |9         |9     |0                |SUCCESS   |0.0       |0             |0.000          |0.193           |
|n6.m5.g6        |5        |15        |15    |0                |SUCCESS   |0.0       |0             |0.094          |0.328           |
|n6.m6.g6        |6        |21        |21    |0                |SUCCESS   |0.0       |0             |0.109          |0.433           |
|n6.m7.g6        |7        |24        |24    |0                |SUCCESS   |0.016     |0             |0.094          |0.506           |
|n6.m8.g6        |8        |24        |24    |0                |SUCCESS   |0.0       |0             |0.172          |0.516           |
|n6.m9.g6        |9        |21        |20    |1                |SUCCESS   |0.0       |0             |0.125          |0.434           |
|n6.m10.g6       |10       |15        |14    |1                |SUCCESS   |0.016     |0             |0.109          |0.381           |
|n6.m11.g6       |11       |9         |7     |2                |SUCCESS   |0.0       |0             |0.062          |0.354           |
|n6.m12.g6       |12       |5         |3     |2                |SUCCESS   |0.0       |0             |0.062          |0.203           |
|n6.m13.g6       |13       |2         |1     |1                |SUCCESS   |0.016     |1             |0.031          |0.177           |
|n6.m14.g6       |14       |1         |0     |1                |SUCCESS   |0.0       |0             |0.000          |0.016           |
|n6.m15.g6       |15       |1         |0     |1                |SUCCESS   |0.0       |0             |0.000          |0.015           |
|================|=========|==========|======|=================|==========|==========|==============|===============|================|
|TOTALS                    |156       |147   |9                |16        |0.048     |1             |0.906          |3.751           |

Running Memory Checks

Introduction

To ensure higher code quality, we added an epic to #59. The intent was to perform memory leak and overrun checks on all functions available from the command line. This currently includes:

• RandomGraphs - planarity -r [-q] C K N
• RandomMaxPlanarGraphGenerator - planarity -rm [-q] N O [O2]
• SpecificGraph - planarity -s [-q] C I O [O2]
• RandomNonplanarGraphGenerator - planarity -rn [-q] N O [O2]
• TransformGraph - planarity -t [-q] -t(gam) I O
• TestAllGraphs - planarity -t [-q] C I O

Where:

• N corresponds to the desired graph order,
• K corresponds to the number of graphs to generate
• I corresponds to the graph input file
  • N.B. TestAllGraphs only supports .g6 infiles, where SpecificGraph and TransformGraph may accept other graph input formats
• O and O2 corresponds to the output file(s) to which the results of the command shall be written
• C corresponds to one of:
  • Planar embedding and Kuratowski subgraph isolation (-p)
  • Planar graph drawing by visibility representation (-d)
  • Outerplanar embedding and obstruction isolation (-o)
  • Search for subgraph homeomorphic to K_{2,3} (-2)
  • Search for subgraph homeomorphic to K_{3,3} (-3)
  • Search for subgraph homeomorphic to K_4 (-4)

Automating memory checking on MacOS using leaks

The planarity_leaks_orchestrator.py in the TestSupport/planaritytesting/leaksorchestrator subpackage automates using the leaks utility available on MacOS to check the above planarity endpoints for memory issues.

Preconditions

You must have:

• Python 3.12 installed,
• Be running on MacOS 14.5+
• Have Xcode command line tools installed, including clang
• Have access to the leaks and script commands
• Have compiled the edge-addition-planarity-suite with -g compiler flag and preferably without -O<optimization level> (see this comment for why)
  • N.B. If you choose -p Debug/planarity, you'll have to comment out lines 76-79 in commandLine() of c/planarityCommandLine.c and recompile, otherwise the processes will hang waiting for the user to enter a character to end the debug session. This was added to keep the terminal window open when debugging in VSCode (see this commit)

How to run the PlanarityLeaksOrchestrator

One must ensure that no memory issues have been introduced after modifying any of the existing endpoints listed in the introduction, one must run the jobs affected by one's changes before submitting a PR.

1. Run

   git update-index --assume-unchanged TestSupport/planaritytesting/leaksorchestrator/planarity_leaks_config.ini
   

   (See git update-index --assume-unchanged and git update-index - Using "Assume Unchanged" Bit for justification)

2. Modify the default config in TestSupport/planaritytesting/leaksorchestrator/planarity_leaks_config.ini so that:

   • The jobs you wish to run have enabled set to True (the jobs unaffected by your modifications may have enabled set to False),
   • For RandomGraphs, SpecificGraph, and TestAllGraphs jobs, you specify the commands_to_run as a comma-separated list, some subset of p, d, o, 2, 3, 4
     • Leaving commands_to_run empty means you default to running all the various algorithm command specifiers
   • For SpecificGraph, TransformGraph, and TestAllGraphs jobs, specify an infile_path corresponding to a .g6 graph input file
   • For TransformGraph job, you specify the output_formats_to_test as a comma-separated list, some subset of g, a, m
     • Leaving output_formats_to_test empty means you default to transforming your input graph to each of the possible output formats

3. Run the planarity_leaks_orchestrator.py as a script; for example, running from within cwd = TestSupport/planaritytesting/leaksorchestrator/:

   python3 planarity_leaks_orchestrator.py -p ../../../Debug/planarity >/dev/null 2>&1
   

   This will run all enabled jobs on the planarity executable specified after -p (if you exclude -p, defaults to Release/planarity, which assumes you have compiled the planarity executable from your VSCode development environment (see #16 - Adding VSCode support to enable debugging and #54 - Create release and debug builds on supported platforms and gather timing info)

   N.B. It is recommended to "throw away" console output by piping to >/dev/null 2>&1 so that you don't clutter your terminal; the leaks logs are still output to subdirectories of the output_dir

-h output for planarity_leaks_orchestrator.py

% python3 planarity_leaks_orchestrator.py -h
usage: python planarity_leaks_orchestrator.py [options]

Planarity leaks analysis
Automates runs of leaks on MacOS to identify memory issues for the following:
- Random graphs with one small graph,
- Random max planar graph generator,
- Random nonplanar graph generator,
- Specific Graph (will only run on first graph in input file)
- Graph Transformation tool
- Test All Graphs

	N.B. One must run the planarity_leaks_config_manager.py script, and update default configuration values. For example, you must provide an infile_name for the SpecificGraph job, and any jobs you wish to run must have 'enabled' set to True.

If an output directory is specified, a subdirectory will be created to contain the results:
	{output_dir}/{test_timestamp}/
If an output directory is not specified, defaults to:
	TestSupport/results/planarity_leaks_orchestrator/{test_timestamp}/

options:
  -h, --help            show this help message and exit
  -p PATH_TO_PLANARITY_EXECUTABLE, --planaritypath PATH_TO_PLANARITY_EXECUTABLE
                        Must be a path to a planarity executable that was compiled with -g; defaults to:
                        	{planarity_project_root}/Release/planarity
  -c PATH_TO_CONFIG_FILE, --configfile PATH_TO_CONFIG_FILE
                        Optional path to planarity leaks orchestrator config file;defaults to:
                        	{planarity_project_root}/TestSupport/planaritytesting/leaksorchestrator/planarity_leaks_config.ini
  -o DIR_FOR_RESULTS, --outputdir DIR_FOR_RESULTS
                        If no output directory provided, defaults to
                        	{planarity_project_root}/TestSupport/results/planarity_leaks_orchestrator/

Adding memory checks for new planarity endpoints

When one adds a new graph algorithm endpoint to planarity, it is necessary to make the following changes to TestSupport/planaritytesting/leaksorchestrator/planarity_leaks_config_manager.py and TestSupport/planaritytesting/leaksorchestrator/planarity_leaks_orchestrator.py to perform memory checks on the new endpoint, which must accompany the other changes in your PR.

Updating planarity_leaks_config_manager.py

The planarity_leaks_config_manager.py script is used to generate planarity_leaks_config.ini, which is consumed by the planarity_leaks_orchestrator.py to indicate the parameters for your new job.

1. In planarity_leaks_config_manager.py, add a new function:

   def initialize_test_<FUNCTION TO TEST>(config_path: Path) -> None:
       <FUNCTION TO TEST>_config = configparser.ConfigParser()
       <FUNCTION TO TEST>_config.read(config_path)
   
       <FUNCTION TO TEST>_config["<JOB NAME>"] = {
           "enabled": "False",
           "perform_full_analysis": "True",
           <OTHER REQUIRED PARAMETERS>
       }
   
       with open(config_path, "w", encoding="utf-8") as config_file:
           <FUNCTION TO TEST>_config.write(config_file)
   

   Where <OTHER REQUIRED PARAMETERS> are key-value pairs corresponding to parameters required for your new job in planarity_leaks_orchestrator.py. For example, test_random_graphs requires num_graphs, order, and commands_to_run.
   • N.B. It is recommended that you leave lists empty and default to running jobs for all possible values; e.g. leaving commands_to_run empty means one wants to run a given planarity endpoint with all algorithm command specifiers p, d, o, 2, 3, 4 by default.
2. Invoke your new function within def initialize_planarity_leaks_orchestrator_config(config_path: Path) -> None so that when one runs the script from the command line, configuration for your new job will be written to planarity_leaks_config.ini

Updating the repository's base planarity_leaks_config.ini to include the defaults for your new job

After updating planarity_leaks_config_manager.py to include the specification for the config for the new endpoint, it is necessary to run planarity_leaks_config_manager.py to re-initialize planarity_leaks_config.ini so that it will contain the config section corresponding to the new job; assuming that you are working on a feature branch of a fork of the edge-addition-planarity-suite repository and are in the final stages of submitting a PR:

1. Save a copy of the old .ini file to preserve job parameters that you can manually add back to the config file after updating the default .ini file and stash it
2. Run

   git update-index --no-assume-unchanged TestSupport/planaritytesting/leaksorchestrator/planarity_leaks_config.ini
   

3. Run the planarity_leaks_config_manager.py to create the new default planarity_leaks_config.ini
4. Stage the planarity_leaks_config.ini and commit with a message indicating defaults were updated in the .ini file
5. Run

   git update-index --assume-unchanged TestSupport/planaritytesting/leaksorchestrator/planarity_leaks_config.ini
   

6. Pop the stash containing the backup of the old planarity_leaks_config.ini and manually copy job parameters (e.g. infile_path) from the backup into the refreshed planarity_leaks_config.ini before deleting the backup.

Adding function to PlanarityLeaksOrchestrator class in planarity_leaks_orchestrator.py

When planarity_leaks_orchestrator.py is run as a script from the command line, it uses the configparser module to read the values from the config file specified by command line parameter -c (defaults to TestSupport/planaritytesting/leaksorchestrator/planarity_leaks_config.ini). We iterate over the configparser.ConfigParser().sections() (one section per job), and read the expected values before invoking the corresponding function within the PlanarityLeaksOrchestrator class.

1. In the PlanarityLeaksOrchestrator class, add your new function:

   def test_<SNAKE-CASE PLANARITY ENDPOINT NAME>(self, <OTHER PARAMETERS>) -> None:
       ...
   

   If you wish to run the same planarity endpoint with multiple values (e.g. contents of list commands_to_run), it is recommended that you create an "internal" function _test_<SNAKE-CASE PLANARITY ENDPOINT NAME>() that you call using starmap_async() on a multiprocessing pool which will set up the args required for your leaks run, and calls _run_leaks()
2. In the body of the if __name__ == "__main__": conditional within the loop to iterate over each section in the configparser.ConfigParser() initialized from the contents of the file corresponding to the config_file Path, add an elif statement with your <JOB NAME>. Inside this scope, extract the values from the config using configparser's builtin converters, such as getint() and getboolean(), or the custom getlist() converter defined in this project.

N.B. If your config contains more exotic types, you'll need to implement your own converter for handling parsing the config file and add it to the converters kwargs in both planarity_leaks_config_manager.py and planarity_leaks_orchestrator.py instantiations of configparser.ConfigParser(); see configparser - Customizing Parser Behaviour and various StackOverflow answers