Overview

Task statement

There's an undirected unweighted graph (farm by subject) described in the file with flow size (ants number's). We had to read it, write it back to output, valid it, find minimum-cost flow - disjoint path (by connects and nodes) - best combinations of ways for transfer ants between start and end, and print the final path of ants (for every ant).

Here you may find full subject. (Sorry for Google, but by law, I can't upload tasks.)

We are also given a map generator. To complete the project, we need to solve the --big-superposition (random map : from 2.5 to 5.5 thousands nodes and random connects) maps in no more than 3 seconds (on school imac's) and find a solution no more than 3 moves worse than expected (the generator displays this expectation as a comment).

That part of the students who make the “quick” lemin as a bonus part usually fit into 0.3-1.0 seconds.

My solve

My lemin always finds the best possible solution for a given graph.

In addition, the average runtime of the program for --big-superposition is about 0.01 seconds:

> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.01s user 0.00s system 78% cpu 0.009 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.02s user 0.00s system 89% cpu 0.018 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.01s user 0.00s system 81% cpu 0.008 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.01s user 0.00s system 81% cpu 0.008 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.01s user 0.00s system 70% cpu 0.011 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.01s user 0.00s system 88% cpu 0.015 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.01s user 0.00s system 88% cpu 0.015 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.00s user 0.00s system 75% cpu 0.007 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.00s user 0.00s system 76% cpu 0.007 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.01s user 0.00s system 79% cpu 0.007 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.01s user 0.00s system 89% cpu 0.017 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.01s user 0.00s system 89% cpu 0.017 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.01s user 0.00s system 90% cpu 0.017 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.00s user 0.00s system 70% cpu 0.006 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.00s user 0.00s system 72% cpu 0.005 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.00s user 0.00s system 72% cpu 0.005 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.01s user 0.00s system 89% cpu 0.017 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.01s user 0.00s system 89% cpu 0.017 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.01s user 0.00s system 91% cpu 0.017 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.00s user 0.00s system 76% cpu 0.007 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.01s user 0.00s system 59% cpu 0.010 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.01s user 0.00s system 87% cpu 0.013 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.01s user 0.00s system 78% cpu 0.009 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.01s user 0.00s system 61% cpu 0.011 total
> ./test_maps/generator --big-superposition > map ; time ./lem-in < map > res
./lem-in < map > res  0.01s user 0.00s system 87% cpu 0.015 total

It also works pretty well with large enough maps. For example lets test mars_4000_20_20_95_180_5_no_z. Map specifications:

• 23200 nodes
• 583000 connects
• 6.7 MB total size of file

Result:

> time ./lem-in < test_maps/mars_4000_20_20_95_180_5_no_z > res
./lem-in < test_maps/mars_4000_20_20_95_180_5_no_z > res  0.77s user 0.01s system 99% cpu 0.790 total

Also, memory using is optimal too. This is memory using for mars_4000_20_20_95_180_5_no_z: