wbkboyer
commented
6 months ago Initial investigation has yielded interesting results. I started by using the Nauty makeg in older planarity code to generate the exact sequence of OK (K{3,3}-free) and NONEMBEDDABLE (containing K{3,3}) results.
Then, I tested the same sequence of OK and NONEMBEDDABLE results coming from the current version of planarity running over a .g6 file generated by the current Nauty&Traces version 2.8000 (32 bits) geng program:
> geng 11 20:20 > n11.m20.g6I got the following results:
> planarity -t -3 n11.m20.g6 n11.m20.g6.t.3.out.txt
Start testing all graphs in "n11.m20.g6".
Num OK disagreements = 2200162, Num NONEMBEDDABLE disagreements = 2200062
Done testing all graphs (65.363 seconds).With output file:
FILENAME="n11.m20.g6" DURATION="65.363"
-3 15108047 3500029 11608018 SUCCESSComparing with tables generated back in the 2.0 release of planarity, there's 100 more OKs and 100 less NONEMBEDDABLEs. However, there are also 4.4 million disagreements, which suggests that the old makeg program did not generate graphs in the same order as the new geng program.
After adding the G6WriteIterator code into the old planarity project, I was able to write the graphs generated by the makeg functionality of the old planarity codebase to a .g6 output file. When the new planarity project is run on this .g6 file, we now report the same results as were produced by the old version of planarity:
Old planarity code:
> planarity -gen -3 11 20 20
...
Begin Stats for Algorithm K3,3 Search
Status=SUCCESS
maxn=11, mine=20, maxe=20, arcCapacity=40
# Edges # Graphs no K3,3 with K3,3
------- ---------- ---------- ----------
20 15108047 3499929 11608118
TOTALS 15108047 3499929 11608118
End Stats for Algorithm K3,3 Search
Total time = 69.010 secondsCurrent planarity code running command:
planarity -t -3 n11.m20.oldgeng.g6 n11.m20.oldgeng.g6.t.3.out.txtProduces output file:
FILENAME="n11.m20.oldgeng.g6" DURATION="65.481"
-3 15108047 3499929 11608118 SUCCESSThese results suggest that the old makeg may have had a bug in generating graphs that has been fixed by the newer geng program. Less likely, perhaps there is a bug in the newer geng program. To test these hypotheses, Since the makeg and geng programs generated the same total number of 11-vertex 20-edge graphs, I will be pursuing the following next steps:
- Are there duplicates in the old
.g6file?- This could explain why we have 100 more
OKs and 100 lessNONEMBEDDABLEs in the output of running planarity on the new file: there are 50 graphs that do contain aK_{3, 3}that are duplicated, then that would indicate we overcount theNONEMBEDDABLEs by 50 and undercount theOKs by 50, which would mean the old planarity results are incorrect
- This could explain why we have 100 more
- Are there duplicates in the new
.g6file?- This could also explain why we have 100 more
OKs and 100 lessNONEMBEDDABLEs in the output of running planarity on the new file: if there are 50 graphs that do not contain aK_{3, 3}that are duplicated, then that would indicate we overcount theOKs by 50 and undercount theNONEMBEDDABLEs by 50, which explain why the new planarity results are incorrect vs. the old
- This could also explain why we have 100 more
- Find the graphs that are different between the old and new
.g6files. Specifically, search for graphs that appear in the new.g6file that didn't appear in the old one, and search for graphs that appear in the old.g6file but don't appear in the new one.- The main hypothesis is that the old file contains 50 duplicates that contain a
K_{3,3}and the new file instead contains 50 new graphs that are allK_{3,3}-free. If the new graphs can be wrangled and then the old planarity code also reports them asK_{3,3}-free, then we we can safely conclude that no bug has been introduced into theK_{3,3}search algorithm but rather that the new numbers in theK_{3,3}table reflect appropriate output from the newergengin the current Nauty suite.
- The main hypothesis is that the old file contains 50 duplicates that contain a
john-boyer-phd
Comparing results of current code to results from version 2.0 code, there seem to be 100 11-vertex 20-edge graph that are now reported to be
K_{3,3}-free but didn't used to be. ForK_{3,3}graphs, the old table reported 3,499,929 but now we report 3,500,029 (the numbers containingK_{3,3}are similarly adjusted down by 100 in the current code). So, the code used to find aK_{3,3}and verify the result in those 100 graphs, and now it doesn't.This will involve several steps:
OKandNONEMBEDDABLEresults as a string of 0 and 1 values for all 11-vertex 20-edge graphs.K_{3,3}-free) result in the new code that is not an OK in the results string, increment a counter. Also, if there are anyNONEMBEDDABLEresults in the new code that correlate with an OK in the results string, then increment a second counter. See whether the counter differences match the total difference of 100. (The total differences matches but the separate differences betweenOKcounts andNONEMBEDDABLEcounts is much higher than expected becausemakegandgengproduce different graphs).makegorgengis erroneously producing any duplicate graphs. (Both were found to be generating unique graphs, just some different graphs).g6files, namely one representing the output ofmakegand the other representing the output ofgeng.makegversusgengon the smallest orders of graph (N= 6, 7, 8 etc.) to find the smallest order of graphs in which the number of OKs and NONEBMEDDABLES forK_{3,3}search is different between themakegversusgengfiles.K_{3,3}) to find the minimum M for which the number of OKs and NONEBMEDDABLES forK_{3,3}search is different between themakegversusgengfiles. (That was discovered to be N=8, M=15, which had a difference of one OK versus NONEMBEDDABLE forK_{3,3}search between themakegversusgengfiles).makegversusgengfiles for N=8, M=15).K_{3,3}search indicates have aK_{3,3}homeomorph (It was determined that this leaves 34 graphs thatK_{3,3}search indicates areK_{3,3}-free).K_{3,3}-free because they are planar. (It was found that only 2 of the graphs that were reportedlyK_{3,3}-free are also reported to be non-planar).K_5in both cases).K_{3,3}once theK_5was planarized by the removal of an edge incident to one of the 5 degree 4 vertices. (It was determined that one of the graphs reported to beK_{3,3}-free by theK_{3,3}search did in fact have a subgraph homeomorphic toK_{3,3}once a particular edge was removed to break up a subgraph homeomorphic toK_5in the graph).makegversusgeng, it turns out that most of the graphs generated by canonicalgengare different than those ofgeng, and most of the canonicalmakeggraphs are different than both thegengand canonicalgengfiles. So there are three sources of mostly different graphs for the samenandmvalues, which enables us to search for more error graphs that are potentially smaller than the n=8, m=15 graph already found to produce a problem for theK_{3,3}search. The following tasks are intended to automate finding the smallest example possible of an error graph.gengversus canonicalgengoutputs. First piece of good news: There were no differences of algorithm behavior for any of the algorithms other than theK_{3.3}search. Furthermore, forK_{3.3}search, there was an output difference for n=6, m=13, for which there are only two graphs. For canonicalgengoutput, aK_{3.3}homeomorph is found in both graphs, but in only one of the graphs in the non-canonicalgengoutput. We know that theOKresult on one of the non-canonicalgenggraphs is in error because it is just an alternative adjacency matrix representation of one of the graphs in the canonicalgengoutput, both of which contain a subgraph homeomorphic toK_{3,3}. We should be able to easily identify that 6-vertex 13-edge graph and then show aK_{3,3}in it.K_{3,3}analysis program to find aK_{3,3}in the 6-vertex 13-edge graph from thegengoutput that is reported to beK_{3,3}-free by theK_{3,3}search implementation. Post a comment indicating the.g6and adjacency list formats of the graph and the adjacency list formatted version of theK_{3,3}it contains.