CS 261 Lab K - Graph Layouts

Due Wed Apr 24 at 9:00am

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 random graph.

This lab will be completed in pairs. Review the pair programming guidelines!

Objectives

To practice working with graphs and get a sense for how connectivity in undirected graphs works.
To practice converting pseudocode into implemented code.
To practice reading mathematical algorithms.
Gain awareness of the effects and process of translating an algorithm into an actual implementation
- Dan's note: Even with something as simple as this algorithm, turning the paper into Java code is an act of translation--and many things can get lost (or gained!) in translation.

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. Take a moment to read through these classes and see how they work!

VisualGraph is a simple implementation of a simple undirected graph data structure. Each node in this graph does not hold any data, but does have x,y coordinates of where it should appear in a visualization. Edges are defined as a pair of nodes (again, without direction or weight).
GraphVisualization is a regular GUI class that draws a given VisualGraph. Nodes are drawn centered at their x,y coordinates, and edges are drawn between these nodes. This class also supposed user interaction, in that you can drag nodes around on the screen!

Details

The first step in this lab is to import the provided classes and run them. Play around with the given UI; can you place the nodes in a random graph so that the graph is "aesthetically pleasing"? How did you decide where to place the nodes? Can you translate that into a computer algorithm?

Have you actually played with the program? I'll wait...

...

In this lab you will just be implementing a single method: the layout() method of the VisualGraph class. In particular, your method should implement the Fruchterman-Reingold algorithm (rehosted original paper) for performing a force-directed layout.

Force-Directed Layouts

One of the most common types of algoritms for doing graph layouts are force-directed. These algorithms treat the graph as being under a set of physical "forces" that move the nodes around the graph until they've settled into an equilibrium state. For example, we may treat the nodes as circular "magnets" that push each other away, but treat the edges as kinds of "springs" that draw connected nodes back to one another---force-directed layouts are also known as spring-and-damper algorithms.

We let each node push each other a little ways, let each edge pull its nodes a little ways, and keep looping until the graph looks good. Because we're using physical forces as our model (e.g., magnitism, gravity, spring-tension), we can often borrow from simple algorithms like Columb's Law (the "inverse square law") and Hooke's Law to determine how far and in what direction each node should move.

These algorithms are fairly simple to implement but produce interesting behaviors (and nice layouts). However, they have the bad habit of having a high run-time. Because each node influences every other node, they can often be O(n²) or O(n³).

Fruchterman-Reingold

The Fruchterman-Reingold algorithm 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. Simpler, edges act as springs that apply an attracting force between nodes that is proportional to the square of the distance between them.

The pseudocode for this algorithm can be found on page 4 of the original paper and has also been copied below (as an image, because formatting this kind of math in HTML is a pain. Typos are not mine!). Note that you will need to make a couple of modifications to this algorithm!

You will need to make a few modifications to this algorithm.

For one, you will want to remove the loop to apply this algorithm for a number of iterations (line 6). The provided GUI includes a timer that will act as that loop, allowing you to see the graph fix its layout in real-time (rather than just hitting "go" and getting an organized graph).
The "temperature" (t) is used to slow down the algorithm as it gets in to place. It also acts as a limiter on the "speed" at which the graph converges into its desired layout--the smallest this number, the slower the graph will move but the more precise the movements. In my implementation, a value of 1.0 worked well for me for this value, though Dan says 5.0 worked for him. Try out different values and see what happens!
- IMPORTANT NOTE: there is a typo in the original algorithm. Where it says min(v.disp,t), it should say min(|v.disp|,t) (use the magnitude of the displacement!)
- You also do not need to implement a "cooling" function that alters the temperature. Rather, you can just watch the graph settle into place without worrying about whether it stops or not (don't worry: it should. It may "vibrate" at the end, but this is expected).
Note that you will likely need to use a different method to "prevent from displacement outside frame}". For one, our frame goes from (0, 0) to (width, height), not from (-width/2, -height/2) to (width/2, height/2).
Hint: You might need to add another data member or two to the Nodes or Edges to keep track of some information.
Helpful Java components:
- Your numbers will likely work out better if you do your math in double precision. If you'd like to use a Point object with double precision, check out the Point2D.Double class.
- The Math.hypot() method may be your best friend for this lab.

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

Note you may need to "fiddle" with the forces and constants to get something that works nicely for you. Be sure to document in the comments any changes you make!
Try running your algorithm with bigger and bigger graphs (thousands or tens of thousands of nodes--you may need to make the window larger!). What do you notice about the algorithm?
You can continue to drag around nodes as the algorithm works. Watch the rest of the graph follow your node!

A Note about Vectors

The above algorithm treats forces and positions as mathematical vectors. You should have encountered this concept previously in a math course, but if you need a refresher there is a pretty good one here. A few notes:

The vector between two points can be calculated simply by subtracting the x-coordinates and the y-coordinates.
Points (x,y) can directly be treated as vectors if you just think of the vector as coming out of the origin (0,0)
The notation |V| indicates the length (or magnitude) of a vector V
- This notation is also used to talk about the length of a list!
You can calculate the length of a vector using the basic distance formula.
You can add vectors together simply by adding their respective coordinates. (x1, y1) + (x2, y2) = (x1+x2, y1+y2)
You can multiply vectors by scalars (normal numbers) simply by multiplying each component (i.e., the x and the y). This means that if you want to "normalize" the vector (give it a length of 1.0), just divide each coordiante by its length!

If you have any questions on this math, be sure to ask!

Submitting

Submit all of your classes to the LabK submission folder on hedwig. Make sure you upload your work to the correct folder! The lab is due at the start of class on the day after the lab.

Remember to fill out your lab partner evaluation!

Extensions

As always, there are lots of good extensions you might consider if you have time:

Add further refinements to the given algorithm. You might add an attractive force at the center of the graph to try and drag nodes away from the walls. You might even give the walls a repelling force.
You might add in methods to create particular kinds of graphs: trees, meshes, etc. The Fruchterman-Reingold paper and the Kouborov paper (linked below) both have some good examples.
- You should probably add in a button to the JFrame so that you can easily make your new graph!
- Can you read in a graph from a file?!
Try adding different weights to the nodes and edges. Larger nodes should have more repulsion (and might be drawn larger), and heavier edges might have more attraction (and may be drawn thicker or darker).
You might look at different algorithms. Kobourov 2007 has a nice summary of different options. Implemting the Kamada-Kawai algorithm can be really informative about graphs--you'll need to calculate all-pairs-shortest paths and use some partial derivites, but it is highly doable (though likely not in the time allotted for lab).

Grading

This assignment will be graded based on approximately the following criteria:

Nodes repulse one another [25%]
Edges attract connected nodes to one another [25%]
Nodes update their position based on the forces applied to them [20%]
Your algorithm lays out the nodes in an aesthetically pleasing fashion (so works overall) [5%]
Your algorithm works with the provided UI so that you can see the nodes being re-organized [10%]
Your code is well documented and follows the edicts of good style [10%]
You completed your lab partner evaluation [5%]