EvoGraph Web Demo

About EvoGraph

The purpose of EvoGraph is to answer the following question:

What is the best way to represent an undirected graph on a 2D plane?

This is an NP-Complete problem. EvoGraph uses stochastic search algorithms in order to evolve a solution. Consider a graph instance to be the representation of a particular graph on a 2D plane or canvas, i.e. each node has both x and y coordinates. We measure the quality of a graph instance by calculating its fitness, a value that we seek to minimize.

Fitness Function

Our fitness function is the sum of penalties induced by five independent criteria:

• Edge Crossings: This is simply the number of times two edges intersect.
• Edge Fitness: The quality of a given edge. We determine this to be its deviation from a certain calculated Optimal Edge Length, which is a function of the canvas size, the number of nodes, and the number of edges.
• Angular Resolution: This is essentially the quality of a node's outgoing edges in terms of the angles they make. Edge angles strive to be equally separated, and they are penalized for being too sharp.
• Node Separation: Nodes that are not connected should not be too close to each other.
• Edge Tunneling: Nodes are penalized for being too close to or overlapping edges.

Algorithms

EvoGraph uses five stochastic search algorithms that you can select from. Each one has strengths and weaknesses. The first four work for all graphs:

• Genetic Algorithm
• Age Layered Population Structure (ALPS)
• Simulated Annealing
• Hill Climber

Human In The Loop

At any time when the algorithm is not running, you can drag and drop any node of the graph in order to try and "help" the process. The fitness of the shown graph instance will be recalculated and stored in memory. If the fitness of the graph is worse than it was before, the changes will likely be discarded after the next iteration.

About the Web Demo

The EvoGraph web demo uses HTML5 canvas tools and may not work on all browsers. Since it runs the optimization algorithms in your browser with javascript, the performance is limited by that of your machine. Therefore it may not be suitable for mobile devices and older computers.