Algorithm

We use a custom Suurballe algorithm that try to find the best set of Node Disjoint Paths.

Explanation of algorithm (using audit/example01.txt)

https://excalidraw.com/#json=WW3srHsjxB4Kn8x4PIoCl,ahe0HvXoWgBeYRefFrG7KA

Explanation of Dijkstra's Algorithm (for a weighted Graph):

https://excalidraw.com/#json=8QVhn1KQJYsy5KK0KnC0J,OATPKpadBMzYPfOp-GLClQ

min-heap:

https://www.youtube.com/watch?v=AFPzC2RJOMk

Inspiration:

• https://github.com/almayor/lem-in/blob/master/docs/algorithm-explanation.pdf
• https://web.archive.org/web/20230416040506/http://www.macfreek.nl/memory/Disjoint_Path_Finding
• https://github.com/elijahkash/lemin/wiki

Testing your lem-in executable

The repository ships with a small harness in lemin_test/ that compares your solver (lemin) with a reference solver (leminTest) on the same map and checks that both produce the same number of frames/moves. Follow the steps below to plug in your own build and run the suites.

1. Build or copy your solver as lemin.
   Compile your lem-in project however you normally do, then move the resulting binary into the test folder and name it lemin.

   cp /path/to/your/lem-in ./lemin_test/lemin
   # or rebuild this Go version:
   go build -o lemin . && mv -f lemin ./lemin_test/lemin

2. (Optional) Rebuild the reference solver.
   A precompiled leminTest binary already lives in lemin_test/. Rebuild it if you want to ensure it matches your toolchain:

   go build -o leminTest . && mv -f leminTest ./lemin_test/leminTest

3. Launch the automated tutorial run.
   From the project root run:

   ./launch_test.sh

   The script refreshes lemin, jumps into lemin_test/, sources lemin_key.sh, and runs two batches:

   • audit: the canonical 42 maps in lemin_test/audit/
   • lemin: the larger custom maps in lemin_test/cstm/

   After each map finishes you will be prompted to press any arrow key to continue. Each iteration prints the number of frames/moves for leminTest and for your lemin binary, followed by an OK/KO.

4. Run individual tests manually (optional).
   If you prefer to drive the harness yourself:

   cd lemin_test
   source lemin_key.sh
   shopt -s expand_aliases       # needed so the audit/lemin aliases work
   audit                         # run the official 42 maps
   lemin                         # run the heavier custom maps
   ./lemin_test.sh cstm/big_1.txt  # run only one specific map

   Adjust the timeout per map via the TIMEOUT_DURATION variable at the top of lemin_key.sh when testing extremely large graphs.

5. Inspect the diff if you get KO.
   Every run leaves three files inside lemin_test/:

   • leminTest.txt: raw output from the reference solver
   • lemi.txt: raw output from your solver
   • lemin.txt: filtered output used for the comparison (L lines only)
     Use your favorite diff tool (e.g. diff -u leminTest.txt lemi.txt) to understand where the divergence happens.

That is all you need—drop in your executable, refresh the reference binary if desired, and drive the harness either through launch_test.sh or manually for complete control over the maps you exercise.