CS 261 Lab J - Graph Layouts

Due Wed Nov 26 at 12:00pm

Overview

As we discussed in class, Graphs are a general data structure that can be used for lots of different purposes. One of the interesting features of graphs is that they do not suggest a single spatial layout: the nodes and edges of a graph can be drawn wherever we want without losing any information in the visualization (compare to binary trees, where it mattered whether we drew a branch on the left or right side of its parent!).

Nevertheless, there are certain ways of drawing the graph that are more sensible or aesthetically pleasing: maybe we want to minimize line crossings, or keep similar nodes next to one another. But getting a computer to automatically produce aesthetically pleasing graph visualizations can be quite challenging and algorithmically intensive!

In this lab, you will be implementing a simple force-directed layout algorithm to organize and visualize a randomly generated graph, such that you can take the figure on the left and turn it into the figure on the right:

This lab will be completed in pairs. Partner assignments for this lab can be found on Moodle

Objectives

Necessary Files

You will need to download the copy of the GraphLab.zip file. This file contains two classes you will need to import into Eclipse.

Preliminary Information

Force-Directed Layouts

While there are many different algorithms for automatically laying out graphs, this lab will focus on a force-directed layout algorithm. These algorithsm treat the graph as under a set of physical "forces" (think gravity or magnetism) that move the nodes around the graph until they've settled into an equilibrium state--indeed, such algorithms are also known as spring-and-damper algorithms. Because these algorithms model physical forces, we can often borrow simple algorithms from physics such as Columb's Law (the "inverse square law") and Hooke's Law to implement them. You can look at an example force-directed layout (using a different algorithm though) here.

Force-directed layout algorithms are fairly simple to implement, yet produce interesting behaviors and nice layouts. However, they have a bad habit of not being particularly efficient. Because each node influences every other node, they can often be O(n^2) or even O(n^3) (where n may be the number of nodes or edges).

The algorithm you will be implementing works as follows:

Thus you can imagine a pair of adjacent nodes as repelling magnets connected by a spring. The magnets will try and push each other away, but eventually the tension of the spring will be greater than the repelling force, so that they won't be able to move further away. The entire graph is treated as a bunch of these magnets connected by springs, and the algorithm involves figuring out how far away everyone wants to be from everyone else, thereby producing a nice graph.

If you have any questions on this basic idea, please ask for clarification!

As a rough pseucode of the process:

Notes on Vectors

The algorithm you are implementing discusses these physical forces in terms of vectors. If you've never encounted vectors, there is a pretty good introduction here.

The basic idea is that a vector is a pair of numbers that represents a displacement from the current position. For example, the vector (5,2) represents a "move" from the current spot 5 units along the x-axis, and 2 units along the y-axis.

Vectors can be added and subtracted--simply add or subtract the x-component and the y-component separately. So (5,2) + (1,2) = (5+1,2+2) = (6,4), and (5,2) - (1,2) = (5-1,2-2) = (4,0). Remember that it is okay for a vector to have a negative component!

We can also multiply and divide vectors by a scalar--that is, but a single regular number. To do this, simply multiply or divide the x-component and y-component by that number. So (5,2)*3 = (5*3,2*3) = (15,6), and (5,2)/10 = (5/10,2/10) = (0.5,0.2). (We will be working with double-precision vectors!)

Finally, we can also talk about the length or magnitude of a vector. This measures how "long" the displacement is. We write length with a pair of bars around the vector: |v|, where v = (5,2). |v| does not mean the absolute value of the vector! We calculate the length of a displacement by using the distance formula: you can consider the (x,y) pair of the vector as representing it's "end point" when displaced from the origin (0,0), so that the length of the vector is the length of the line from (0,0) to (x,y). Thus \(\mathtt{|(5,2)| = \sqrt{(5-0)^2+(2-0)^2} = 5.385}\).

Since vectors are represented by a pair of numbers, it makes sense to use a Point object to hold those numbers (though sadly, such objects don't have nice add or subtract methods!) For this lab, we'll be working with vectors in double precision, so you'll want to use the Point2D.Double class.

Assignment Details

For this assignment, you will be implementing the Fruchterman-Reingold algorithm. This is one of the simplest and earliest force-directed layout algorithms. It has the benefits of working well on small to medium-sized graphs and converging relatively quickly (within 100 iterations usually). In this model, each node applies a repelling force upon every other node inversely proportional to the square of the distance between them (e.g., like magnetism or gravity). Simpler, edges act as springs that apply an attracting force between nodes that is proportional to the square of the distance between them (again, like magnetism or gravity).

The pseudocode for this algorithm can be found on page 4 of the original paper (and it's really neat to look at the original paper!). The algorithm has also been copied below with some fixed typos for your convenience.

Fruchterman-Reingold Algorithm

1.  area := W * L; { W and L are the width and length of the frame }
2.  G := (V, E); { the vertices are assigned random initial positions }
3.  k := \(\sqrt{area\;/\;|V|}\);
4.  function \(f_a(z)\) := begin return \(z^2 \;/\; k \) end;
5.  function \(f_r(z)\) := begin return \(k^2 \;/\; z \) end;

6.  for i := 1 to iterations do begin
7.      { calculate repulsive forces }
8.      for v in V do begin
9.          { each vertex has two vectors: .pos and .disp }
10.         v.disp := 0;
11.         for u in V do
12.             if (u \(\neq\) v) then begin
13.                 { \(\Delta\) is short hand for the difference vector between the positions of the two vertices }
14.                 \(\Delta\) := v.pos - u.pos;
15.                 v.disp := v.disp + (\(\Delta\;/\;|\Delta|\)) * \(f_r(|\Delta|)\)
16.             end
17.     end
    
18.     { calculate attractive forces }
19.     for e in E do begin
20.         { each edge is an ordered pair of vertices .v and .u }
21.         \(\Delta\) := e.v.pos - e.u.pos
22.         e.v.disp := e.v.disp - (\(\Delta\;/\;|\Delta|\)) * \(f_a(|\Delta|)\)
23.         e.u.disp := e.u.disp + (\(\Delta\;/\;|\Delta|\)) * \(f_a(|\Delta|)\)
24.     end

25.     { limit the maximum displacement to the temperature i }
26.     { and then prevent from being displaced outside frame }
27.     for v in V do begin
28.         v.pos := v.pos + (v.disp / |v.disp|) * min(|v.disp|, t);
29.         v.pos.x := min(W/2, max(-W/2, v.pos.x));
30.         v.pos.y := min(L/2, max(-L/2, v.pos.y));
31.     end
32.     { reduce the temperature as the layout approaches a better configuration }
33.     t := cool(t);
34. end

This algorithm does not always use the same variable names as the provided class; translating between those variables is part of the assignment!

As stated above, you will have to make a number of modifications to this algorithm to allow it to work with the provided UI system:

Implementing this algorithm within the provided code and UI is the full extent of this lab! There are a couple of other extensions below however, in case you get done early.

Extensions

As always, there are lots of good extensions you might consider if you have time. You can earn up to 2 points of extra credit for these.

Submitting

Make sure your name is in a class comment at the top of your VisualGraph class and upload all the classes to the LabJ submission folder on vhedwig. Make sure you upload your work to the correct folder! The lab is due at noon on the day after the lab (since we don't have class!)

After you have submitted your solution, log onto Moodle and submit the Lab J Partner Evaluation. Both partners need to submit evaluations.

Grading

This assignment will be graded out of 20 points: