Jump to content

Create animated graph visualizations with Processing

+ 1
  odewahn1's Photo
Posted Jun 16 2010 05:46 PM

Graph visualization is the study of how to turn abstract representations of graphs (think network diagrams of nodes and edges, rather than XY-coordinates) into diagrams. I love graphviz (the program that produced this image), and have used it in several different projects, like this visualization of Senate voting patterns I wrote about in Beautiful Visualization. The chapter describes a series of images that were created from Senate voting data from the 101st session to the 111th session of congress:

Attached Image

While graphviz is great, it mainly produces static output, like a PNG. Very useful, but there are limited opportunities for exploration or further development. In this Answer, I'll show you a Processing sketch that transforms the rather dull output from graphviz into a more interesting, interactive forma that looks like this:



The next few sections walk you through the main steps and key things you need to know.

Get the XY coordinates of the nodes
Most of your work in Graphviz will revolve around generating dot, which is a common way to represent the nodes and edges in the graph. Once you're data is in Dot, you use graphviz to transform it into a picture. The following figure, taken from the Graphviz gallery, should give you the general idea:

Attached Image

Graphviz can create images in a variety of formats, like PNG, SVG, EPS, and others. However, hidden among the various command line options, is a format called "plain." If you tell graphviz to use the "plain" format, it will simply dump all the data to stdout in a simple text format.

For example, if you put the previous dot commands into a file called "test.dot," running the command "dot -Kneato -Tplain < test.dot" (the -Kneato option tells dot to use a particular layout algorithm) will output the following information:

graph 1.000 5.069 3.333
node run  1.472 1.542 0.750 0.500 run solid ellipse black lightgrey
node intr  0.681 0.833 0.750 0.500 intr solid ellipse black lightgrey
node runbl  0.444 1.764 0.873 0.500 runbl solid ellipse black lightgrey
node kernel  2.514 1.917 0.977 0.500 kernel solid ellipse black lightgrey
...
edge run intr 4 1.250 1.347 1.139 1.250 1.014 1.125 0.903 1.042 solid black
edge run kernel 4 1.806 1.667 1.903 1.708 2.014 1.736 2.111 1.778 solid black
edge intr runbl 4 0.611 1.083 0.583 1.222 0.542 1.375 0.500 1.514 solid black
...
stop



Transform into XML

The output from -Tplain gives you all the information you need to find the (X,Y) coordinates of the nodes and edges in the graph. Some simple parsing scripts will let you do pretty much whatever you want with the data. I used Python to combine this positional data with metadata about the Senator, such as his or her name and part affiliation, and then output it in XML, which is a much more pliant format for using in Processing.

Here' for example, is a sample of the XML data I derived from my original dot files for the senate visualization:

<session number="101">
   <nodes>
      <senator id="402990" name="Alan Cranston" party="Democrat" x="0.353016008538" y="0.894622396359" />
      <senator id="403483" name="Alan Dixon" party="Democrat" x="0.485592315902" y="0.637402216208" />
      <senator id="409923" name="Alan Simpson" party="Republican" x="0.928256136606" y="0.375408975239" />
      <senator id="404679" name="Albert Gore" party="Democrat" x="0.551402347919" y="0.848433439701" />
      <senator id="403142" name="Alfonse D'Amato" party="Republican" x="0.584017075774" y="0.416831603183" />
     ...
   </nodes>
   </edges>
      <edge s="402990" e="403483" />
      <edge s="402990" e="404679" />
      <edge s="402990" e="300046" />
      <edge s="402990" e="400692" />
      <edge s="402990" e="400564" />
      ...
   </edges>
</nodes>


You can find the full xml files I used in the visualization here: 101st session, 102nd session, 103rd session, 104th session, 105th session, 106th session, 107th session, 108th session, 109th session.

Load into Processing
Once the data is in XML, you can use Processing's XML library to parse it and bind it to the data structures you'll use. The following method shows how to use the XML library to build a Hashtable of Senator objects (described next) whose key is a unique id for the Senator and an Arraylist of Edge objects. The following code segment shows how:

// Load the data in from an XML file
Hashtable fetchSenators(String url) {
  Hashtable retVal = new Hashtable();
  //Load the file
  XMLElement xml = new XMLElement(this, url);
  XMLElement[] children = xml.getChildren();
  XMLElement[] nodes = children[0].getChildren();
  XMLElement[] edges = children[1].getChildren();  
  for (int i=0; i <  nodes.length; i++) {
    String id = nodes[i].getStringAttribute("id");
    String name = nodes[i].getStringAttribute("name");
    String party = nodes[i].getStringAttribute("party");
    float sx  = nodes[i].getFloatAttribute("x");
    float sy  = nodes[i].getFloatAttribute("y");
    Senator s = new Senator(name, party, sx*WIDTH, sy*HEIGHT);
    retVal.put(id, s);
  }
  //Nore process the egges and make then the current edge list
  current_edges.clear();
  for (int i=0; i <  edges.length; i++) {
    String s = edges[i].getStringAttribute("s");
    String e = edges[i].getStringAttribute("e");
    Edge edge = new Edge(s,e);
    current_edges.add(edge);
  }
  return retVal;
}


Model each Senator with a Vector

The basic position information provided in the XML will allow you to draw any single session. To create the animated transition, you have to also figure out how to make the Senators move from place to place. This is best done by modeling each Senator's motion with a vector that describes their current location, direction of travel, and speed. (There are also a few other attributes, like destination, name, party, and so forth.) Each time through Processing's draw() loop, the Senator advances one more step towards his or her eventual destination point. He or she stops walking when he or she is within 5 pixels of this final destination. The following diagram shows the basic layout and math involved in the model:

Attached Image

For incumbents (Senators who were already in office in the previous session), the transition algorithm is fairly simple: you simply update his or her final destination to the new position in the incoming session. If the Senator is new to the session (or, more precisely, his or her unique identifier is not in the hashtable of current senators), then you set the initial position to the top center of the screen and the destination to his or her incoming position. If a Senator has been voted out of office in a Session (or, more precisely, his or her unique id is in the hashtable of current Senators but NOT in the hashtable of incoming senators), then you set his or her destination to the lower center of the screen. Once you've determined the new destination depending on these three cases, you then recalculate the direction of travel using the formulas described earlier.

I've also embellished the basic animation a bit by adding two "arms," which I modeled as two small circles that are drawn in alternating positions along the Senators diameter. In addition to making the figures look a bit more like people and less like a swarm of dots, I thought it added a self-important waddle that somehow fit the nature of the data. The arms are, of course, totally optional, but I thought it was a nice touch.

Draw the edges (or fake it)
The final step is to draw the edges. This is fairly simple: all you do is iterate through each edge in the arraylist, pull out the id's for the start and end Senator, and then use these as keys into the hashtable to retrieve the X and Y positions for the endpoints. Pretty straightforward. However, because there are a LOT of edges, this approach quickly bogged the program's performance down.

So, as a hack, I modified the program to draw just the edges when the Senators all reach their final destinations. I did this for each session, and saved each image using Processing's "save" command. Here, for example, is the image for the 101st session.) I then loaded the appropriate image in as the background each time the user switches between sessions. The Senators appear to walk around on top of the edges until they take their final places. Although not ideal, this simple trick vastly improved the performance.

Code for the final sketch
So, that's about it. It's a fairly complex script relative to some of the others I've been doing on Answers, but I hope this description is enough to get you through this code. Here it is:

import processing.xml.*;
import java.util.Hashtable;
import java.util.Enumeration;


class Edge {
  String s, e; 
  Edge (String _s, String _e) {
    s = _s;
    e = _e;
  }
}

class Senator {
  String name, party;
  color party_color;
  boolean label_visible = false;
  float ox, oy;  //Origin of the vector
  float dx, dy;  //Destination position
  float theta;  //Angle of travel
  float r; // Current radius
  float x,y;  //Current X and Y positions
  float distance;  //How far they have to travel
  float speed = 4;  //How fast they're moving
  boolean inMotion = true;
  int arm_pos = -1;
  int arm_step = 0;
  float arm1_x, arm1_y, arm2_x, arm2_y;
  float arm_angle =  20.0 + random(10);
  
  Senator (String _name, String _party, float _sx, float _sy) {
     name = _name;
     party = _party;
     ox = _sx;
     oy = _sy;
     x = ox;
     y = oy;
     inMotion = true;
     //Set the color
     if (_party.equals("Democrat")) {
        party_color = #0000FF;
     } else if (_party.equals("Republican")) {
        party_color = color(188,57,57);
     } else {
        party_color = color(68,96,147);
     }
  }
  
  //Advance the senator forward to a new position along his or her current path
  void step() {
    float distance = sqrt( (dy - y)*(dy - y) + (dx - x)*(dx - x)); 
    if ( distance > 5.0) {
       x += speed * cos(theta);
       y += speed * sin(theta);
       //Now compute the locations of the arms
       float angle = 90.0 + arm_angle;
       arm1_x = x + R_BODY/2.0 * cos(theta + arm_pos*(95+arm_angle)/57.3);
       arm1_y = y + R_BODY/2.0 * sin(theta + arm_pos*(95+arm_angle)/57.3);
       arm2_x = x + R_BODY/2.0 * cos(theta - arm_pos*(85+arm_angle)/57.3);
       arm2_y = y + + R_BODY/2.0 * sin(theta - arm_pos*(85+arm_angle)/57.3);
       arm_step += 1;
       if ((arm_step % 5) == 0) {
          arm_pos *= -1;
          arm_step = 0;
       }
    } else {
      inMotion = false;
      arm1_x = x + R_BODY/2.0 * cos(theta + arm_pos*90.0/57.3);
      arm1_y = y + R_BODY/2.0 * sin(theta + arm_pos*90.0/57.3);
      arm2_x = x + R_BODY/2.0 * cos(theta - arm_pos*90.0/57.3);
      arm2_y = y + + R_BODY/2.0 * sin(theta - arm_pos*90.0/57.3);
    }
  }
  
  void setDestination(float _dx, float _dy) {
     dx = _dx;
     dy = _dy;
     // Compute new direction vector based on current location
     theta = atan2(dy - y, dx - x);
     r = 0.0;
     distance = sqrt( (dy - y)*(dy - y) + (dx - x)*(dx - x));
  }
  
}  
  

int WIDTH = 640;
int HEIGHT = 480;
int R_BODY = 15;
int R_ARM = 10;
Hashtable current_field = new Hashtable();
ArrayList current_edges = new ArrayList();

PFont f;
PFont fLabel;
PImage bg; 


String[] sessions = { 
  "session_101.xml",
  "session_102.xml",
  "session_103.xml",
  "session_104.xml",
  "session_105.xml",
  "session_106.xml",
  "session_107.xml",
  "session_108.xml",
  "session_109.xml"
};

String[] bgImg = { 
  "session_0.png",
  "session_1.png",
  "session_2.png",
  "session_3.png",
  "session_4.png",
  "session_5.png",
  "session_6.png",
  "session_7.png",
  "session_8.png"
};

String[] session_labels = {
  "101",
  "102",
  "103",
  "104",
  "105",
  "106",
  "107",
  "108",
  "109"
};

  
public int sessionIdx = 0;  //tells us the current session we need to load



// Load the data in from an XML file
Hashtable fetchSenators(String url) {
  Hashtable retVal = new Hashtable();
  //Load the file
  XMLElement xml = new XMLElement(this, url);
  XMLElement[] children = xml.getChildren();
  XMLElement[] nodes = children[0].getChildren();
  XMLElement[] edges = children[1].getChildren();  
  for (int i=0; i <  nodes.length; i++) {
    String id = nodes[i].getStringAttribute("id");
    String name = nodes[i].getStringAttribute("name");
    String party = nodes[i].getStringAttribute("party");
    float sx  = nodes[i].getFloatAttribute("x");
    float sy  = nodes[i].getFloatAttribute("y");
    Senator s = new Senator(name, party, sx*WIDTH, sy*HEIGHT);
    retVal.put(id, s);
  }
  //Nore process the egges and make then the current edge list
  current_edges.clear();
  for (int i=0; i <  edges.length; i++) {
    String s = edges[i].getStringAttribute("s");
    String e = edges[i].getStringAttribute("e");
    Edge edge = new Edge(s,e);
    current_edges.add(edge);
  }
  return retVal;
}

//Merges the given session into the current field
void loadSession(int session_idx) {
  Enumeration id_list;
  Hashtable new_field = fetchSenators(sessions[session_idx]);
  //Process all the members of the new session
  id_list = new_field.keys();
  while (id_list.hasMoreElements()) {
    String id = (String) id_list.nextElement();
    Senator s = (Senator) new_field.get(id);   
    if (current_field.containsKey(id)) {
       //The senator is already on the field, so just update his destination to the new place
       Senator c = (Senator) current_field.get(id);
       c.setDestination(s.x, s.y);
     } else {
        //The senator is a new senator, so make him enter
        Senator c = new Senator (s.name, s.party, WIDTH/2, 0);
        c.setDestination(s.x, s.y);
        current_field.put(id, c);
     }
  }
  
  // Process all the members in the current session and if they aren't in the new field, make them leave the stage
  id_list = current_field.keys();
  while (id_list.hasMoreElements()) {
    String id = (String) id_list.nextElement();
    Senator s = (Senator) current_field.get(id);   
    if (!new_field.containsKey(id)) {
       s.setDestination(WIDTH/2, HEIGHT);
    }
  }
}
 

void keyPressed() {
  if (key == CODED) {
     switch (keyCode) {
        case (LEFT):
           if (sessionIdx > 0) {
              sessionIdx -= 1;
              loadSession(sessionIdx);
              bg = loadImage(bgImg[sessionIdx]);
           }
           break;
        case (RIGHT):
           if (sessionIdx < (sessions.length-1)) {
              sessionIdx += 1;
              loadSession(sessionIdx);
              bg = loadImage(bgImg[sessionIdx]);
           }
           break;
     }
  }
}
  

void setup() {
  size(640,480);
  f = createFont("Arial", 24, true);
  fLabel = createFont("Arial", 72, true);
  bg = loadImage(bgImg[0]);
  loadSession(0);  
}

//If the user clicks on a senator, then set the flag to display (or remove) the label
void mousePressed() {
  Enumeration id_list = current_field.keys();
  while (id_list.hasMoreElements()) {
    String id = (String) id_list.nextElement();
    Senator s = (Senator) current_field.get(id); 
    float dist = sqrt( (s.x - mouseX)*(s.x - mouseX) + (s.y - mouseY)*(s.y-mouseY));
    if (dist < R_BODY) {
       s.label_visible = !s.label_visible;
    }
  }    
}   
  
void draw() {  
  Enumeration id_list;
  smooth();
  background(bg);
  //Draw the stuff 
  int motion_count = 0;

/*  
  stroke(color(218,218,218));
  for (int i=0; i < current_edges.size(); i++) {
     Edge e = (Edge) current_edges.get(i);
     Senator s_start = (Senator) current_field.get(e.s);
     Senator s_end = (Senator) current_field.get(e.e);
     line(s_start.x, s_start.y, s_end.x, s_end.y);
  }
*/
  
  id_list = current_field.keys();
  while (id_list.hasMoreElements()) {
    String id = (String) id_list.nextElement();
    Senator s = (Senator) current_field.get(id); 
    fill(s.party_color);
    stroke(#000000);
    strokeWeight(2);
    ellipse(s.arm1_x, s.arm1_y, R_ARM, R_ARM);
    ellipse(s.arm2_x, s.arm2_y, R_ARM, R_ARM);
    ellipse(s.x, s.y, R_BODY, R_BODY);
    s.step();
    if (s.inMotion) {
      motion_count += 1;
    }
  }
  //Now see if the mouse it over the person
  textFont(f);
  id_list = current_field.keys();
  while (id_list.hasMoreElements()) {
    String id = (String) id_list.nextElement();
    Senator s = (Senator) current_field.get(id); 
    float dist = sqrt( (s.x - mouseX)*(s.x - mouseX) + (s.y - mouseY)*(s.y-mouseY));
    if ((dist < 5) || s.label_visible) {
       fill(color(0,0,0));
       if ( s.x > WIDTH / 2) {
         textAlign(RIGHT);
       } else {
         textAlign(LEFT);
       }
       text(s.name, s.x, s.y);
    }
  }  
  
  textAlign(LEFT);
  textFont(fLabel);
  fill (#000000);
  text(session_labels[sessionIdx], 10, 80);
 
}



Related:



Tags:
1 Subscribe


0 Replies