Skip to content
Genetic Algorithm Path Search
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
src
.gitignore
.travis.yml
License.txt
README.md
pom.xml
todo-thanks.txt
visShowcase.PNG
visShowcase.jpg

README.md

Build Status Tests

GAPS (Genetic Algorithm Path Search)

For a more detailed description, please see Wiki page
See the project in action
And because we shouldn't take anyone's word for it, latest build information

What is GAPS?

A webapp started as a small side project doing path searches in graphs using genetic algorithms

How does it work?

For a description on genetic algorithms, Wikipedia has it (loosely) covered. For graph theory, Wikipedia has it covered again. Putting the two and two together, and combining some great frameworks and technologies (see Thanks section), GAPS was born.

Just like any standard genetic algorithm. Picks a random number of initial paths, then it combines and mutates them until a good solution / stop condition is reached.

How well does it perform?

For small graphs (30 - 100 nodes, 100 - 1000 edges), in ~10% of cases it outperforms JGraphT's KShortestPath algorithm when it concerns path costs. In terms of runtime performance, it is slower, however, there's a chance of finding better paths.

In most cases, it loses to JGraphT, but barely, usually either tied up, or coming close behind.

What are the limits?

Starting from around 100 nodes / 1000 edges, it becomes a bit sluggish client-side due to graph rendering issues. However, if installed and run client-side (web interface is just a wrapper, websocket service means you can use GAPS simply as an API), it performs well even for very large graphs (100k nodes, 1M edges).

What are the future plans?

Please check the issues page for a list of upcoming features.

Special thanks

JGAP helped a lot to get stuff off the ground quickly, and the possibilities of customization are practically endless.

JGraphT, awesome framework for dealing with graphs.

Binary Cart, one of the best bootstrap templates out there, keep it up guys! 👍

Bootstrap - no explanation needed, it just works!

AngularJS was love at first sight, and a lasting relationship since then, 'nuff said

Vis.js, Because rendering graphs and visualizing data in the browser should be this easy

Angular UI notification because users should always be in the loop

Bootstrap slider and Bootstrap toggle two of the few plugins out there that actually work without extensive hacking or adaptation. Nice work!

Also, special special thanks to Pedro Serra for being that wall I could bounce ideas from, and generally for listening to me being geek for hours (ok, minutes at most) on end

You can’t perform that action at this time.