Using external program LKH from GAP

[BuddhiniAnge]

I'm getting the following error when executing the algorithm known as LKH, saying that "no first choice found for 'Process' on 5 arguments....", at the lines indicated by the white star. Can someone please explain the meaning of this error? What could be the reason to it?

Thanks a lot in advance.

[stevelinton]

It looks like your function IrredUndir.... is returning a list of generating sets, whereas CayleyGraph wants a single generating set.

[ChrisJefferson]

I think the problem is GAP is trying to run the external program "LKH". Did you get this code from someone? Did they tell you how to correctly install LKH?

[BuddhiniAnge]

For the LKH file it was mentioned that, "The program LKH (version 2.0.7) must be installed and be available to GAP. It can be downloaded for academic and noncommercial use from http://www.akira.ruc.dk/~keld/research/LKH/".

Now actually the version 2.0.9 is present and when I download it and run the following window appears.

But I can't understand how to make it available to GAP.

[olexandr-konovalov]

@BuddhiniAnge the page http://www.akira.ruc.dk/~keld/research/LKH/ does not mention GAP at all. Could there be any other place with instructions regarding "must be available to GAP"? From what I can see, the file is saved in Downloads under lkh(1).exe name, that's not enough to install it. It should not have (1) in the name and should be placed somewhere in the search path. Perhaps you need to download the source for LKH, unpack it and look for the installation instructions for LKH for Windows.

In addition, if you use GAP on Windows, you should be able to copy text from the terminal and paste it into the description of the issue. A screenshot with a small font is not easily readable, and it requires others to retype your code manually instead of copying and pasting.

P.S. You can also use terminal settings to permanently increase the font size in the terminal.

[hulpke]

This looks as @BuddhiniAnge is trying to reproduce work from https://arxiv.org/pdf/1805.00149.pdf This refers to extra files that are not part of the GAP distribution and could be only available from the authors of this paper. Also, such interfaces often rely on Unix features and thus might not run under Windows.

[olexandr-konovalov]

Good find @hulpke!!! So, https://arxiv.org/abs/1805.00149 has the link to "ancillary files": https://arxiv.org/src/1805.00149v1/anc and there one should be able to find all files referenced in the paper (individually or downloading all in one tar.gz file), including LKH.gap with further comments.

I can not say whether it is working on Windows, or could be adjusted to work on Windows - one nees to try first. LKH.gap has the line

Filename( DirectoriesSystemPrograms(), "LKH"), 

and that means that you need to call in GAP DirectoriesSystemPrograms(); which will tell you the directory in which you need to put LKH.exe. @BuddhiniAnge could you try that? This is what "be available to GAP" means in this case.

If this will not work, as an alternative, it may be useful to create a Docker container which will contain GAP, LKH and the code from this paper (or newer, if the authors have one) and will be available on mybinder.org so that a reader could explore examples from the paper in a GAP Jupyter notebook which do not require much computational power.

@BuddhiniAnge to see how this will work, you may click on "launch binder" button at https://github.com/alex-konovalov/gap-teaching. Eventually you will see the screen like this one:

and you can click on links to ipynb files to explore them. One of them is a reproduction of a computational experiment, another is a clean notebook, and another contains material for a lecture. Sorry that there is no detailed README there yet, but my intention is to put there details which may help researchers to provide their results in a similar way.

If you need a tutorial on using Jupyter, you can find some at https://jupyter.org/try. The interface is the same for all kernels - Python, R, GAP etc. An introduction could be also viewed on GitHub here.

[olexandr-konovalov]

@BuddhiniAnge LKH compiles under macOS, but then gap -A 4-5-Valence2.gap gives me an error:

$ gap -A 4-5-Valence2.gap 
 ┌───────┐   GAP 4.9.2 of 04-Jul-2018
 │  GAP  │   https://www.gap-system.org
 └───────┘   Architecture: x86_64-apple-darwin16.7.0-default64
 Configuration:  gmp 6.1.2, readline
 Loading the library and packages ...
 Packages:   GAPDoc 1.6.1.dev, PrimGrp 3.3.1, SmallGrp 1.3, TransGrp 2.0.2
 Try '??help' for help. See also '?copyright', '?cite' and '?authors'
─────────────────────────────────────────────────────────────────────────────
Loading  GRAPE 4.8 (GRaph Algorithms using PErmutation groups)
by Leonard H. Soicher (http://www.maths.qmul.ac.uk/~lsoicher/).
Homepage: http://www.maths.qmul.ac.uk/~lsoicher/grape/
─────────────────────────────────────────────────────────────────────────────

k = 4.

    GBar = C4 = SmallGroup(4, 1), S0Bar = [ f1 ]
        trying 1 of 1: all extensions of S0Bar are ok   

    GBar = C2 x C2 = SmallGroup(4, 2), S0Bar = [ f1, f1*f2 ]
        trying 1 of 1: all extensions of S0Bar are ok   

-------------------------------------------------------------------- 
...
more lines
...
-------------------------------------------------------------------- 

k = 8.

    GBar = C8 = SmallGroup(8, 1), S0Bar = [ f1 ]
        trying 2 of 3 (a = f2)     
            GCD of voltages is 6 for twist(S0Bar) = [ -1 ] and twist(a) = 1.
            Prime divisors are [ 2, 3 ]
                p = 2 is not larger than the largest prime divisor 2 of k = 8
                p = 3: we call LKH
                        There are 1 lifts of SBar to G = C3 : C8
                            1. S = [ f1, f2*f4 ]
oLKH.tsp

*** Error ***
Unknown keyword: OLKH.TSP
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `ReadAll' on 1 arguments
The 1st argument is 'fail' which might point to an earlier problem
 at /Users/alexk/gap-4.9.2/lib/methsel2.g:250 called from
ReadAll( LKHtoGAP ) at LKH.gap:143 called from
LKH( CayGS, [  ], [  ] ) at CallLKHOnLiftsOfSBar.gap:115 called from
CallLKHOnLiftsOfSBar( GBar, SBar, twist, p 
 ); at 4-5-Valence2.gap:153 called from
<function "unknown">( <arguments> )
 called from read-eval loop at 4-5-Valence2.gap:169
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> 

[olexandr-konovalov]

It works with GAP 4.8 - the authors used GAP 4.8.7, I have GAP 4.8.10. For example, ~/gap4r8p10/bin/gap.sh 4-5-Valence2.gap finished with

k = 47.

    GBar = C47 = SmallGroup(47, 1), S0Bar = [ f1 ]
        trying 22 of 22: all extensions of S0Bar are ok   

-------------------------------------------------------------------- 
-------------------------------------------------------------------- 
Success: found hamiltonian cycles in Cay(G,S) whenever SBar is a redundant ex\
gap>

in about 20 minutes.

[olexandr-konovalov]

I've changed the title of this issue to be more specific. It's worrying that the code does not run in the most recent GAP release. Did we break it by our changes? Do authors know this already and have a new version in place?

[ChrisJefferson]

It seems to work fine on the master branch (on linux), so it might be we've fixed it for 4.10.

[olexandr-konovalov]

@ChrisJefferson - that's good, since Jupyter kernel requires at least GAP 4.9.2.

[BuddhiniAnge]

Thank you very much.

The LKH.gap contains the line "Filename( DirectoriesSystemPrograms(), "LKH")". When I call DirectoriesSystemPrograms(); it gives me the below content.

gap> DirectoriesSystemPrograms(); [ dir("/i686-pc-cygwin-gcc-default32/"), dir("/cygdrive/c/watcom-1.3/binnt/"), dir("/cygdrive/c/watcom-1.3/binw/"), dir("/cygdrive/c/Program Files (x86)/Intel/iCLS Client/"), dir("/cygdrive/c/Program Files/Intel/iCLS Client/"), dir("/cygdrive/c/Windows/system32/"), dir("/cygdrive/c/Windows/"), dir("/cygdrive/c/Windows/System32/Wbem/"), dir("/cygdrive/c/Windows/System32/WindowsPowerShell/v1.0/"), dir("/cygdrive/c/Program Files/Intel/Intel(R) Management Engine Components/DAL/"), dir("/cygdrive/c/Program Files (x86)/Intel/Intel(R) Management Engine Components/DAL/"), dir("/cygdrive/c/Program Files/Intel/Intel(R) Management Engine Components/IPT/"), dir("/cygdrive/c/Program Files (x86)/Intel/Intel(R) Management Engine Components/IPT/"), dir("/cygdrive/c/Program Files/MATLAB/R2014a/runtime/win64/"), dir("/cygdrive/c/Program Files/MATLAB/R2014a/bin/"), dir("/cygdrive/c/Program Files/MATLAB/R2014a/polyspace/bin/"), dir("/cygdrive/c/Program Files (x86)/MiKTeX 2.9/miktex/bin/"), dir("/cygdrive/c/Program Files (x86)/Universal Extractor/"), dir("/cygdrive/c/Program Files (x86)/Universal Extractor/bin/"), dir("/cygdrive/c/Users/kasuni/AppData/Local/atom/bin/") ]

Which location should I choose to place LKH.exe file?

[olexandr-konovalov]

@BuddhiniAnge for a quick check, please try to put it into bin/i686-pc-cygwin-gcc-default32 directory of your installation. This is not sustainable (if it will work only in THIS installation of GAP) but will get us an idea whether it's usable on Windows or not.

[BuddhiniAnge]

I did. Then I tried to run 4-5-Valence2.gap and I receive the same error mentioned above when k=8. (I have GAP 4.8.10 installed now and LKH 2.0.9 version).

In bin/i686-pc-cygwin-gcc-default32 there is another folder named "extern". Do you think it will work if I put inside that folder? So far I only tried by putting it in bin/i686-pc-cygwin-gcc-default32 where there are other .exe files named "cygstart", "gap" and the folder "extern" and several other files.

[BuddhiniAnge]

It gives the same error at k=8, even when I place LKH .exe file inside the folder "extern".

What can I do now? Please advice.

Thanks a lot.

[olexandr-konovalov]

1. bin/i686-pc-cygwin-gcc-default32 is better. extern is for builds of some external code that is redistributed with GAP.

2. This is encouraging - seems that the GAP-LKH interface is working under Windows.

3. on macOS, 4-5-Valence2.gap runs in GAP 4.8.10 - I am already at k=36. a) Try GAP 4.8.7 which is the version used by authors: you can get it from http://www.gap-system.org/Releases/4.8.7.html b) This may be a problem that depends on some randomness, and maybe on Windows you have different random state and it produces different output which triggers an error. Do you read 4-5-Valence2.gap in a clean new GAP session? c) Could this be because of changes in the GRAPE package?

[BuddhiniAnge]

Yes I read it in a clean new session.

Ok, I will try it in GAP 4.8.7 version.

[BuddhiniAnge]

I tried it in GAP 4.8.7. It still gives the same error at k=8.

[olexandr-konovalov]

Got it by looking at LKH.gap around line 143 specified below:

*** Error ***
Unknown keyword: OLKH.TSP
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `ReadAll' on 1 arguments
The 1st argument is 'fail' which might point to an earlier problem
 at /Users/alexk/gap-4.9.2/lib/methsel2.g:250 called from
ReadAll( LKHtoGAP ) at LKH.gap:143 called from
LKH( CayGS, [  ], [  ] ) at CallLKHOnLiftsOfSBar.gap:115 called from
CallLKHOnLiftsOfSBar( GBar, SBar, twist, p 
 ); at 4-5-Valence2.gap:153 called from
<function "unknown">( <arguments> )
 called from read-eval loop at 4-5-Valence2.gap:169
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> LKHtoGAP;
fail
brk> LKHtoGAPfile;
"/var/folders/cl/gp9_ksln7x9ddcddld4wkyv40000gq/T//tmSiMkzh/LKHtoGAP.txt"
brk> LKHparfile;
"/var/folders/cl/gp9_ksln7x9ddcddld4wkyv40000gq/T//tmSiMkzh/GAPtoLKH.par"

Now it happens that the first file does not exist on my system, and the .par file looks like this:

PROBLEM_FILE = /var/folders/cl/gp9_ksln7x9ddcddld4wkyv40000gq/T//tmSiMkzh/GAPt\
oLKH.tsp
TOUR_FILE = /var/folders/cl/gp9_ksln7x9ddcddld4wkyv40000gq/T//tmSiMkzh/LKHtoGA\
P.txt

Those line breaks were added because of the text printed to thee files being too wide. One should change the way how the input files for LKH are produced in LKH.gap. At the moment they are printed with

    PrintTo(LKHparfile, 
        "PROBLEM_FILE = ", LKHtspfile, "\n",
        "TOUR_FILE = ", LKHtoGAPfile, "\n"
        );

and in many other places in the code PrintTo is used too. This relies on the screen width, and does not give you a reproducible behaviour.

For example, I used mouse just to increase the width of the terminal window, and the problem disappeared, but, quoting @mikecroucher, "how reproducible is a mouse click?" (see http://mikecroucher.github.io/MLPM_talk/).

A slightly more reproducible approach would be to call SizeScreen([100,]); to expand the line width from default 80 to 100 (or a larger number). I suggest you can try this now as a quick workaround: enter SizeScreen([100,]); before reading the GAP input file. But then, what if someone will have the path which go above 100 characters? Then the problem will appear again.

A proper way would be to change the code to use streams to produce these file and use SetPrintFormattingStatus to avoid line breaks, as explained at https://www.gap-system.org/Manuals/doc/ref/chap10.html#X8663FCD57E8BC390. We need to alert the authors of the code about this.

Good news are that there is no regression in GAP 4.9 in this case. We simply hit the situation when the path to a temporary file became too long.

[BuddhiniAnge]

I tried.

gap> SizeScreen(); [ 191, 58 ] gap> Read("C:/Users/acer/Desktop/Test4/4-5-Valence2.gap"); ──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── Loading GRAPE 4.7 (GRaph Algorithms using PErmutation groups) by Leonard H. Soicher (http://www.maths.qmul.ac.uk/~leonard/). Homepage: http://www.maths.qmul.ac.uk/~leonard/grape/ ────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────

k = 4.

GBar = C4 = SmallGroup(4, 1), S0Bar = [ f1 ]
    trying 1 of 1: all extensions of S0Bar are ok

GBar = C2 x C2 = SmallGroup(4, 2), S0Bar = [ f1, f1*f2 ]
    trying 1 of 1: all extensions of S0Bar are ok

and then for k=8 I get an error still.

k = 8.

GBar = C8 = SmallGroup(8, 1), S0Bar = [ f1 ]
    trying 2 of 3 (a = f2)
        GCD of voltages is 6 for twist(S0Bar) = [ -1 ] and twist(a) = 1.
        Prime divisors are [ 2, 3 ]
            p = 2 is not larger than the largest prime divisor 2 of k = 8
            p = 3: we call LKH
                    There are 1 lifts of SBar to G = C3 : C8

Error, no method found! For debugging hints type ?Recovery from NoMethodFound Error, no 1st choice method found for `ReadAll' on 1 arguments called from ReadAll( LKHtoGAP ) at C:/Users/acer/Desktop/Test4/LKH.gap:143 called from LKH( CayGS, [ ], [ ] ) at C:/Users/acer/Desktop/Test4/CallLKHOnLiftsOfSBar.gap:115 called from CallLKHOnLiftsOfSBar( GBar, SBar, twist, p ); at C:/Users/acer/Desktop/Test4/4-5-Valence2.gap:153 called from <function "unknown">( ) called from read-eval loop at line 169 of C:/Users/acer/Desktop/Test4/4-5-Valence2.gap you can 'quit;' to quit to outer loop, or you can 'return;' to continue brk> quit;

This was tried in GAP 4.8.7 without changing the screen size since it is 191 already.

I also tried it by 1). Changing the screensize to 100 as mentioned above. 2). Screensize to 300 3). Tried the above screen sizes in GAP 4.9.2

But still I'm getting the error.

[BuddhiniAnge]

I tried SetPrintFormattingStatus in LKH befor8e the very first PrintTo line and I am getting the below error.

k = 8.

GBar = C8 = SmallGroup(8, 1), S0Bar = [ f1 ]
    trying 2 of 3 (a = f2)
        GCD of voltages is 6 for twist(S0Bar) = [ -1 ] and twist(a) = 1.
        Prime divisors are [ 2, 3 ]
            p = 2 is not larger than the largest prime divisor 2 of k = 8
            p = 3: we call LKH
                    There are 1 lifts of SBar to G = C3 : C8

Error, Only the string "stdout" is recognized by this method. called from SetPrintFormattingStatus( LKHparfile, false ); at C:/Users/acer/Desktop/Test4/LKH.gap:50 called from LKH( CayGS, [ ], [ ] ) at C:/Users/acer/Desktop/Test4/CallLKHOnLiftsOfSBar.gap:115 called from CallLKHOnLiftsOfSBar( GBar, SBar, twist, p ); at C:/Users/acer/Desktop/Test4/4-5-Valence2.gap:153 called from <function "unknown">( ) called from read-eval loop at line 169 of C:/Users/acer/Desktop/Test4/4-5-Valence2.gap you can 'quit;' to quit to outer loop, or you can 'return;' to continue

Do I have to use SetPrintFormattingStatus before all the PrintTo and AppendTo lines and check?

[DaveWitteMorris]

If SetPrintFormattingStatus is not used, then the line that causes the error is ReadAll( LKHtoGAP ). This is supposed to read the output file that has been created by LKH.exe, but it seems that LKH.exe has not created the file. I don't know anything about Windows, but, to debug the problem, it might be helpful to see any error messages that have been written by LKH.exe. This program is called by the code in lines 132-138 of LKH.gap:

    Process(
        LKHTempDir, 
        Filename( DirectoriesSystemPrograms(), "LKH"), 
        InputTextUser(), 
        LKHstdoutStream,
        [LKHparfile]
        );

In this code block, you could replace LKHstdoutStream with OutputTextUser(). After this change, I think that any messages from LKH.exe will be printed on your terminal. If LKH.exe is working correctly, then it should give you messages that start something like this:

PARAMETER_FILE = /tmp/tm6fPdRa/GAPtoLKH.par
Reading PROBLEM_FILE: "/tmp/tm6fPdRa/GAPtoLKH.tsp" ... done
ASCENT_CANDIDATES = 23
BACKBONE_TRIALS = 0
BACKTRACKING = NO
# CANDIDATE_FILE =
CANDIDATE_SET_TYPE = ALPHA
EXCESS = 0.0416667

and end something like this:

* 1: Cost = 0, Time = 0.00 sec. 
Run 9: Cost = 0, Time = 0.00 sec. 

* 1: Cost = 0, Time = 0.00 sec. 
Run 10: Cost = 0, Time = 0.00 sec. 

Successes/Runs = 0/10 
Cost.min = 0, Cost.avg = 0.00, Cost.max = 0
Trials.min = 24, Trials.avg = 24.0, Trials.max = 24
Time.min = 0.00 sec., Time.avg = 0.00 sec., Time.max = 0.00 sec.

[BuddhiniAnge]

When I tried by using the line OutputTextUser() it gave me the below error when it came to k=8 in 4-5-Valence2.gap.

At k=8, it started as,

k = 8.

GBar = C8 = SmallGroup(8, 1), S0Bar = [ f1 ]
    trying 2 of 3 (a = f2)
        GCD of voltages is 6 for twist(S0Bar) = [ -1 ] and twist(a) = 1.
        Prime divisors are [ 2, 3 ]
            p = 2 is not larger than the largest prime divisor 2 of k = 8
            p = 3: we call LKH
                    There are 1 lifts of SBar to G = C3 : C8

PARAMETER_FILE = c:/WINDOWS/Temp/tmj7rS0s/GAPtoLKH.par Reading PROBLEM_FILE: "c:/WINDOWS/Temp/tmj7rS0s/GAPtoLKH.tsp" ... done ASCENT_CANDIDATES = 23 BACKBONE_TRIALS = 0 BACKTRACKING = NO

CANDIDATE_FILE =

CANDIDATE_SET_TYPE = ALPHA

EDGE_FILE =

EXCESS = 0.0416667 EXTRA_CANDIDATES = 0 EXTRA_CANDIDATE_SET_TYPE = QUADRANT GAIN23 = YES

and ended as,

SUBPROBLEM_SIZE =

SUBPROBLEM_TOUR_FILE =

SUBSEQUENT_MOVE_TYPE = 5 SUBSEQUENT_PATCHING = YES

TIME_LIMIT =

TOUR_FILE = c:/WINDOWS/Temp/tmj7rS0s/LKHtoGAP.txt TRACE_LEVEL = 1

Cand.min = 4, Cand.avg = 4.0, Cand.max = 4 Preprocessing time = 0.00 sec. Error, no method found! For debugging hints type ?Recovery from NoMethodFound Error, no 1st choice method found for `ReadAll' on 1 arguments called from ReadAll( LKHtoGAP ) at C:/Users/acer/Desktop/Test4/LKH.gap:143 called from LKH( CayGS, [ ], [ ] ) at C:/Users/acer/Desktop/Test4/CallLKHOnLiftsOfSBar.gap:115 called from CallLKHOnLiftsOfSBar( GBar, SBar, twist, p ); at C:/Users/acer/Desktop/Test4/4-5-Valence2.gap:153 called from <function "unknown">( ) called from read-eval loop at line 169 of C:/Users/acer/Desktop/Test4/4-5-Valence2.gap you can 'quit;' to quit to outer loop, or you can 'return;' to continue brk> quit;

Could it be because I'm using the LKH 2.0.9 which is available now and not the LKH 2.0.7 which was mentioned in the algorithm?

[DaveWitteMorris]

According to the documentation of LKH.exe, the differences between LKH 2.0.9 and LKH 2.0.7 should not be an issue for LKH.gap, so it is unlikely to be the problem. (But I will take a look at this if there is no other explanation.)

I am surprised that this latest output has no error message. The output from LKH.exe is correct, but should have continued something like:

* 1: Cost = 0, Time = 0.00 sec. 
Writing TOUR_FILE: "/tmp/tm21oTq0/LKHtoGAP.txt" ... done
Run 1: Cost = 0, Time = 0.01 sec. 

* 1: Cost = 0, Time = 0.00 sec. 
Run 2: Cost = 0, Time = 0.01 sec. 

Instead, the program seems to silently stop before starting to look for any hamiltonian cycles.

Perhaps the input files to LKH.exe are incorrect. These are temporary files, so they will be deleted when you quit GAP. Try running the program again. Then, before you quit GAP, look at the GAPtoLKH.par file and the GAPtoLKH.tsp file. To know what directory these are in, you will need to look at the output from LKH.exe, because these are "PARAMETER_FILE" and "PROBLEM_FILE". (In your latest output, the directory is c:/WINDOWS/Temp/tmj7rS0s/, but this has presumably been deleted.)

The .par file should have just two lines, something like:

PROBLEM_FILE = /tmp/tm21oTq0/GAPtoLKH.tsp
TOUR_FILE = /tmp/tm21oTq0/LKHtoGAP.txt

Judging from the LKH.exe output, I think this file will be correct. (It had an incorrect linebreak when the terminal width was too small.)

The .tsp file should be exactly:

TYPE : HCP
DIMENSION : 24
EDGE_DATA_FORMAT : EDGE_LIST
EDGE_DATA_SECTION
1 2
1 10
1 13
1 23
2 3
2 20
2 21
3 6
3 11
3 12
4 6
4 7
4 17
4 18
5 8
5 9
5 18
5 20
6 8
6 22
7 9
7 14
7 24
8 10
8 24
9 13
9 19
10 14
10 19
11 14
11 15
11 23
12 16
12 17
12 24
13 15
13 16
14 16
15 17
15 21
16 18
17 20
18 21
19 21
19 22
20 22
22 23
23 24
-1

The temporary directory is also supposed to have a file called LKHtoGAP.txt but it seems clear that LKH.exe is not creating this file for you. It would be very interesting to see what is in this file if, by some miracle, it does actually exist.

[BuddhiniAnge]

Dear Professor,

I tried again and this is the output in GAP.

gap> SizeScreen(); [ 191, 58 ] gap> Read("C:/Users/kasuni/Desktop/Test1/4-5-Valence2.gap"); ──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── Loading GRAPE 4.7 (GRaph Algorithms using PErmutation groups) by Leonard H. Soicher (http://www.maths.qmul.ac.uk/~leonard/). Homepage: http://www.maths.qmul.ac.uk/~leonard/grape/ ────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────

k = 4.

GBar = C4 = SmallGroup(4, 1), S0Bar = [ f1 ]
    trying 1 of 1: all extensions of S0Bar are ok

GBar = C2 x C2 = SmallGroup(4, 2), S0Bar = [ f1, f1*f2 ]
    trying 1 of 1: all extensions of S0Bar are ok

---

---

k = 5.

GBar = C5 = SmallGroup(5, 1), S0Bar = [ f1 ]
    trying 1 of 1: all extensions of S0Bar are ok

---

---

k = 6.

GBar = C6 = SmallGroup(6, 2), S0Bar = [ f1 ]
    trying 2 of 2: all extensions of S0Bar are ok

GBar = S3 = SmallGroup(6, 1), S0Bar = [ f1, f1*f2 ]
    trying 2 of 2: all extensions of S0Bar are ok

---

---

k = 7.

GBar = C7 = SmallGroup(7, 1), S0Bar = [ f1 ]
    trying 2 of 2: all extensions of S0Bar are ok

---

---

k = 8.

GBar = C8 = SmallGroup(8, 1), S0Bar = [ f1 ]
    trying 2 of 3 (a = f2)
        GCD of voltages is 6 for twist(S0Bar) = [ -1 ] and twist(a) = 1.
        Prime divisors are [ 2, 3 ]
            p = 2 is not larger than the largest prime divisor 2 of k = 8
            p = 3: we call LKH
                    There are 1 lifts of SBar to G = C3 : C8

PARAMETER_FILE = c:/WINDOWS/Temp/tmxRdFxZ/GAPtoLKH.par Reading PROBLEM_FILE: "c:/WINDOWS/Temp/tmxRdFxZ/GAPtoLKH.tsp" ... done ASCENT_CANDIDATES = 23 BACKBONE_TRIALS = 0 BACKTRACKING = NO

CANDIDATE_FILE =

CANDIDATE_SET_TYPE = ALPHA

EDGE_FILE =

EXCESS = 0.0416667 EXTRA_CANDIDATES = 0 EXTRA_CANDIDATE_SET_TYPE = QUADRANT GAIN23 = YES GAIN_CRITERION = YES INITIAL_PERIOD = 100 INITIAL_STEP_SIZE = 1 INITIAL_TOUR_ALGORITHM = WALK

INITIAL_TOUR_FILE =

INITIAL_TOUR_FRACTION = 1.000

INPUT_TOUR_FILE =

KICK_TYPE = 0 KICKS = 1

MAX_BREADTH =

MAX_CANDIDATES = 0 MAX_SWAPS = 24 MAX_TRIALS = 24

MERGE_TOUR_FILE =

MOVE_TYPE = 5

NONSEQUENTIAL_MOVE_TYPE = 5

OPTIMUM =

OUTPUT_TOUR_FILE =

PATCHING_A = 1 PATCHING_C = 0

PI_FILE =

POPMUSIC_INITIAL_TOUR = NO POPMUSIC_MAX_NEIGHBORS = 5 POPMUSIC_SAMPLE_SIZE = 10 POPMUSIC_SOLUTIONS = 50 POPMUSIC_TRIALS = 1

POPULATION_SIZE = 0

PRECISION = 100 PROBLEM_FILE = c:/WINDOWS/Temp/tmxRdFxZ/GAPtoLKH.tsp RECOMBINATION = IPT RESTRICTED_SEARCH = YES RUNS = 10 SEED = 1 STOP_AT_OPTIMUM = YES SUBGRADIENT = YES

SUBPROBLEM_SIZE =

SUBPROBLEM_TOUR_FILE =

SUBSEQUENT_MOVE_TYPE = 5 SUBSEQUENT_PATCHING = YES

TIME_LIMIT =

TOUR_FILE = c:/WINDOWS/Temp/tmxRdFxZ/LKHtoGAP.txt TRACE_LEVEL = 1

Cand.min = 4, Cand.avg = 4.0, Cand.max = 4 Preprocessing time = 0.00 sec. Error, no method found! For debugging hints type ?Recovery from NoMethodFound Error, no 1st choice method found for `ReadAll' on 1 arguments called from ReadAll( LKHtoGAP ) at C:/Users/kasuni/Desktop/Test1/LKH.gap:143 called from LKH( CayGS, [ ], [ ] ) at C:/Users/kasuni/Desktop/Test1/CallLKHOnLiftsOfSBar.gap:115 called from CallLKHOnLiftsOfSBar( GBar, SBar, twist, p ); at C:/Users/kasuni/Desktop/Test1/4-5-Valence2.gap:153 called from <function "unknown">( ) called from read-eval loop at line 169 of C:/Users/kasuni/Desktop/Test1/4-5-Valence2.gap you can 'quit;' to quit to outer loop, or you can 'return;' to continue

I checked the files in temporary directory. The .par file consisted of the below two lines,

PROBLEM_FILE = c:/WINDOWS/Temp/tmxRdFxZ/GAPtoLKH.tsp TOUR_FILE = c:/WINDOWS/Temp/tmxRdFxZ/LKHtoGAP.txt

and the .tsp file consisted of the following.

TYPE : HCP DIMENSION : 24 EDGE_DATA_FORMAT : EDGE_LIST EDGE_DATA_SECTION 1 2 1 10 1 13 1 23 2 3 2 20 2 21 3 6 3 11 3 12 4 6 4 7 4 17 4 18 5 8 5 9 5 18 5 20 6 8 6 22 7 9 7 14 7 24 8 10 8 24 9 13 9 19 10 14 10 19 11 14 11 15 11 23 12 16 12 17 12 24 13 15 13 16 14 16 15 17 15 21 16 18 17 20 18 21 19 21 19 22 20 22 22 23 23 24 -1

It was as you have mentioned. The temporary directory was named as "tmxRdFxZ" and it had a text file called "LKHstdout.txt" which was empty. The temporary directory had only these three .par,.tsp,.txt files.

[BuddhiniAnge]

Can you mention the operating system you are using? Is it macOS? Does it run without any error in that? If so could it be because I'm trying to run it in Windows..

[DaveWitteMorris]

I usually use macOS, but I have also used this program on linux. It worked fine on both (and I also tested version 2.0.9 today), so the problem may have something to do with using Windows, but I do not see what the issue is. The program in LKH.gap is creating the correct files, and LKH.exe seems to be finding those files, so I do not understand why LKH.exe is not trying to find a hamiltonian cycle.

I think you should test your installation of LKH.exe. (If LKH does not work from the command line, then we cannot expect it to work with GAP.) As a simple test, before you close GAP (so before the temporary directory disappears), you could type LKH at the command line. It will ask for a PARAMETER FILE, and you could type in the the path to the GAPtoLKH.par file. This is using the same files that GAP created, so it is not a completely independent test. If that doesn't work, we can make some other small files to try that are created directly and do not come from GAP.

It would be good to get the program working for you on windows, but we may need to do as @alex-konovalov suggested, and create a Docker container to use with Jupyter. That is not something I have ever done, but it is not supposed to be difficult. Unfortunately, I probably would not have time to do that very soon.

[olexandr-konovalov]

@DaveWitteMorris thank you for your comments - delighted to hear from one of the two authors of the preprint in question! I will be happy to help to create a reproducible experiment with Docker & Jupyter - this is an interesting example, a good test case, and this may be useful for potential reviewers of your paper. Do you have already a source code repository with your code, or can we establish it? E.g. to start with, I can create one, put there files from https://arxiv.org/src/1805.00149v1/anc, and give you write access there.

[olexandr-konovalov]

@BuddhiniAnge:

1) you can call SizeScreen with larger parameter than the actual screen width. Although it seems to me unlikely that the new problem is related to that.

2) You wrote I tried SetPrintFormattingStatus in LKH befor8e the very first PrintTo line - can't see your changes, so maybe I am wrong, but I am afraid that was not correct. You need to rework the way how files are produced. Instead of calling PrintTo on a file, one has to call it on another object, called a stream. Please see examples in the Manual. It will be useful to do this everywhere in the supplementary code for the paper - if we will have the repository, I will be able to submit a pull request. This will be helpful to run it everywhere, not only with Jupyter but in batch computations as well.

[BuddhiniAnge]

I tried to create a docker container as mentioned. First I got a docker and run the command "docker pull gapsystem/gap-docker" and after that I executed the command to initialize GAP and got GAP running inside the docker. But I don't understand how to get the LKH.exe and the file containing the .gap programs connected to that docker container to execute them. Can someone please guide me to do that?

[olexandr-konovalov]

First, good to know that you have managed to run it on Windows! Second, there are some details in README at https://github.com/gap-system/gap-docker. Basically,

1. start it with docker run --rm -i -t --net="host" gapsystem/gap-docker to get network access
2. download there (using curl or wget) archive with LKH source, compile KLH (the LKH.exe is for Windows, it will not work in the container!) and make it available to GAP (i.e. LKH should be in the $PATH)
3. Download files from https://arxiv.org/src/1805.00149v1/anc (there is all-in-one archive there)
4. Call gap to start GAP

Steps 2 and 3 require some skills with using UNIX Shell. Furthermore, every time you start the container, you will have to add there LKH and .gap files again. My intention was to create a new container which will already have them, so for these experiments it will be usable from the start. @DaveWitteMorris, if you don't have a repository yet, I can create it and invite you as a collaborator to give you full access.

[BuddhiniAnge]

buddhini@matsp14 MINGW64 /c/Program Files/Docker Toolbox $ docker run --rm -i -t --net="host" gapsystem/gap-docker Unable to find image 'gapsystem/gap-docker:latest' locally latest: Pulling from gapsystem/gap-docker 124c757242f8: Pull complete 9d866f8bde2a: Pull complete fa3f2f277e67: Pull complete 398d32b153e8: Pull complete afde35469481: Pull complete 51f2eb8e6cfa: Pull complete c5e4453b072b: Pull complete 1a9251127845: Pull complete 6ff22edaf5dc: Pull complete cae5a84a4080: Pull complete 03ccb67f519b: Pull complete 4dd9ae972a43: Pull complete 3dd0dd5954f9: Pull complete 4b3c754d8070: Pull complete 09dc3d49f3d2: Pull complete ecddf80dbfe7: Pull complete 60968f520a41: Pull complete d2a38d21534a: Pull complete ac5e64886d50: Pull complete Digest: sha256:5c85c6d9c597058d9c81a45580cc832e7d7367dd7a30cfc0891420c9c87353fc Status: Downloaded newer image for gapsystem/gap-docker:latest gap@default:~$ curl http://www.akira.ruc.dk/~keld/research/LKH/ --output LKH-2.0 .9.tgz bash: curl: command not found gap@default:~$

When I try to download using curl after starting the docker with network access I get the above error. Is there something missing in my commands?

Thanks a lot in advance.

[BuddhiniAnge]

In the above none of the commands were cut across by a line, even though it is in the above preview. But instead there are two lines -- infront of "output".

[DaveWitteMorris]

@alex-konovalov The files are not yet in a repository, so please do create one, as you suggested. I have been busy, but I should have some time to work on this in the next couple of weeks.

[BuddhiniAnge]

Dear Professor,

Can you please mention the versions of MacOs and Linux on which the results were successfully tested?

Thank you very much.

And thank you very much for everyone for the valuable help.

[olexandr-konovalov]

@DaveWitteMorris I've created the repository at https://github.com/alex-konovalov/hamiltonian-cayley-graphs and invited you there as collaborator, so you will have write access to this repository after accepting the invitation. The original code and log files are there in the gap directory, and the instructions how to launch it on Binder are in the README file.

The setup needed for containerisation is based on two files:

• https://github.com/alex-konovalov/gap-docker-lkh/blob/master/Dockerfile to add LKH installation to the Docker container with the latest GAP release.
• https://github.com/alex-konovalov/hamiltonian-cayley-graphs/blob/master/Dockerfile to build the container to be launched on Binder (see Binder docs here for details).

At the moment, the repository has only one Jupyter notebook with the "4-5-Valence2" example. One can see it statically rendered on Github at https://github.com/alex-konovalov/hamiltonian-cayley-graphs/blob/master/gap/4-5-Valence2.ipynb, or one can launch it on Binder, clean all output and then re-run it from scratch. @BuddhiniAnge, I hope you will now be able to run the code requiring LKH on Binder, but remember that you will need to save your results, since these Binder instances are not persistent and will disappear after you disconnect.

I think that this issue may now be closed and @DaveWitteMorris, @BuddhiniAnge and me can continue discussion at https://github.com/alex-konovalov/hamiltonian-cayley-graphs where we may create more focused separate issues. I have some suggestions regarding code refactoring, tests, etc.

[olexandr-konovalov]

I am going to close this issue, and we can continue discussion at https://github.com/alex-konovalov/hamiltonian-cayley-graphs - please create new issues there if you will have any questions/suggestions etc. @BuddhiniAnge would be good to know if you have managed to perform calculations by launching the project on Binder.