Force-directed graph layout *

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.

One popular method to achieve this is through force-directed algorithms. The idea behind these algorithms is to treat the graph as a physical system, where nodes repel each other like particles with the same charge, while edges attract their endpoints, similar to springs connecting these particles. By simulating this physical system, the graph settles into a state of minimal energy, resulting in a visually pleasing arrangement.

The Fruchterman & Reingold algorithm is a renowned force-directed graph drawing algorithm. It models the forces in the following manner:

1. Repulsive Forces: Every pair of nodes repels each other, simulating the effect of like charges. This force ensures nodes are not too close to one another.

2. Attractive Forces: Nodes connected by an edge attract each other, akin to a spring's behavior. This force ensures connected nodes remain close.

The algorithm initializes node positions randomly and then refines these positions iteratively based on the combined forces acting upon them. Over time, the magnitude of these adjustments (often termed temperature) decreases, causing the system to cool down and stabilize. The Fruchterman & Reingold algorithm is given in Algorithm 2.

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), C, \(|V|\) and \(|E|\) (graph size).

   • The program measures run-time needed the average time needed to compute one iteration of the algorithm.

2. Implementation details

   • Graph libraries are off-limits

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

   • Implement a way to visualize the graph.

   • Your solution should effectively showcase the transformation of a graph with 1,000 nodes and 1,000 edges from its initial chaotic arrangement to a clearer, minimal energy layout.

   • 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.