The program that finds optimal routes in a graph.
Algorithmic project on graph theory. It's something like a logistics planner for an ant farm :) The goal is to move a random number of ants in a labyrinth from the Start room to the End room in a minimum number of moves.
This is the project of the Algorithms branch of the School 42 curriculum.
Detailed description of the task: lem-in.en.pdf
Compile with make. Then run like this:
./lem-in [-p -c -d -s -n -a] < [map]
-p hide discovered paths
-c hide moves count
-d allow duplicate links
-s allow self-links
-n allow negative coordinates
-a extend ants limit to max int (NOT RECOMMENDED)
Use test files in _my_maps directory.
Or generate random maps by the provided generator.dms. You can either generate map into a file:
./generator.dms --big > file
./lem-in < file
Or input the generator's output directly to the lem-in executable like this:
./generator.dms --big | ./lem-in
--help : to read the manual
--flow-one : generates an ant farm with distinctive path and [1] ant in it
--flow-ten : generates an ant farm with a distinctive path and approximately [10] ants in it
--flow-thousand : generates an ant farm with a distinctive path and approximately [100] ants in it
--big : generates a big map (approximately [1000] rooms) to test the time complexity
--big-superposition : generates a big map with overlapping paths
Tested only on Mac OS X.
I find all paths from start to end that don't overlap, because any room can be occupied by only one ant at a time. For that, I use BFS (Breadth-First Search) with a queue. First, I find the shortest route, exclude its rooms from the next searches, and then look for the second shortest route and so on.
When I have the list of routes, I move ants on them one by one. Depending on the number of ants and routes lengths, the program chooses the best route for each ant.
Maps have a very strict form and lem-in doesn't accept any deviations from it. A file should contain 3 sections in this order:
- Number of ants (a positive integer)
- List of rooms in a form:
Name X Y(X and Y are coordinates) - List of links between rooms in a form
room1-room2
More on this in the subject lem-in.en.pdf