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, 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).

This is the full subject.

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: