EvoGraph may not work in all browsers. Try Chrome.

About EvoGraph

The purpose of EvoGraph is to attempt to solve the following problem:

What is the best way to represent a given 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.

In general, each of these criteria aims to be minimized, but you can specify the weights of each one using the sliders in the interface. A low weight indicates that the attribute's penalties count for less in the fitness function.

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

The last algorithm is a an original approach known as the K-Graph Heuristic, and it is intended to be used with complete graphs in order to find its crossing number. The details of this algorithm, along with its efficacy compared to the aforementioned four, are discussed in a paper that is currently pending publication. It will be linked here if and when this occurs.

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.

Open source

The algorithms and java implementations of EvoGraph are an open-source project maintained by Phil Melzer and Abhinav Jauhri. You can find the repository here.