Evolutionary Graph Layouts with Genetic Algorithms *

Static Badge Static Badge Static Badge

Graphs are incredibly useful structures in the field of computer science and mathematics, often employed to represent relational data, such as social networks, the internet, and more. A crucial aspect of using graphs effectively is the ability to visualize them. A good graph drawing should ideally minimize edge crossings, distribute nodes evenly, and reflect symmetries, among other criteria. In this project, we take inspiration from nature. Just as evolution shapes organisms for optimal survival in their environments, we will use genetic algorithms to evolve optimal or aesthetically pleasing graph layouts.

  1. Encoding: Each potential layout of the graph is encoded as a data structure suitable for mutation and crossover.

  2. Initial Population: Start with a randomly generated population of graph layouts.

  3. Selection: Evaluate the fitness of each layout in the population. Fitness might be based on several criteria, such as:

    • Minimizing edge crossings

    • Minimizing the total edge length or variance in edge lengths

    • Maximizing minimum distances between vertices to avoid overlaps

    • etc...

  4. Genetic operations: Implement mutation and crossover, consider also other genetic operations...

  5. Termination: Repeat the selection and genetic operations steps until some termination criteria are met, like a maximum number of generations, a satisfactory fitness level, or no significant improvement over several generations.

Implementation guidelines

  1. Running the program:

    • The program can be ran in different modes (sequential, parallel and distributed) by specifying a parameter.

    • User can specify the parameters: window size (height, width of the visualization), \(|V|\) and \(|E|\) (graph size).

    • The program measures run-time needed to compute a given number of iterations of the genetic algorithm.

  2. Implementation details

    • Graph libraries are off-limits

    • The fitness function must be computed in parallel.

    • Given program parameters \(|V|\) and \(|E|\) generate a random graph.

    • Implement a way to visualize the graph showing the transition from the initial random disposition of nodes, to the final aesthetically pleasant disposition of nodes.

    • The implementation must adapt automatically to the hardware it is being ran on (Physical CPU's, Cores, Memory, etc..);

    • Wherever randomness is used a seed must be provided in order to compare solutions.