ORIGINAL DRAFT
Among the many data structures available to programmers, the graph can easily represent complex relationships between elements. Constructed with nodes and edges, a graph can model anything from transportation between cities to neurons and synapses in the brain. Swing has components for handling lists, trees and tables, among other things, but nothing for dealing with graphs. This month, we’ll rectify that by developing a JGraph component, complete with customizable models and renderers, and an interface that allows graphs to adjust node positions automatically, using plugable algorithms.
Modeling
To maintain flexibility, we’ll be using a lot of interfaces in our design. We can represent a graph with nodes, so we’ll need interfaces to make sure we can use custom node and edge elements in our model. The whole model will also use a separate interface, to make it possible to create a graph model to suit alternate data requirements. In most cases, you can use the default implementations we’ll provide, but should you need your own, we’ll make sure the coupling is as loose as possible and the contract between elements effectively defined.
Figure 1: Model Classes.
The GraphEdge interface allows us to handle arcs or edges between nodes. We’ll identify the nodes at each end of the edge as the from and to nodes, which we’ll access through the getFrom and getTo methods, respectively. We’ll also be storing a weight value that describes the stress, or tension, between nodes.
public interface GraphEdge
{
public GraphNode getFrom();
public GraphNode getTo();
public double getWeight();
}
The GraphNode interface is only slightly more detailed. Each node has a name, a fixed flag that lets us mark it as not movable, along with the x and y position. We provide read and write accessors for each of these value.
public interface GraphNode
{
public String getName();
public void setName(String name);
public boolean isFixed();
public void setFixed(boolean fixed);
public double getX();
public double getY();
public void setX(double x);
public void setY(double y);
}
The GraphModel provides access to the nodes and edges. We can count the number of elements, add an entry or get an entry, based on its index, in each respective list. While it’s possible to traverse a graph from any node directly, by forcing nodes to be part of a model like this one, it’s much easier to manage drawing and selection operations than it would be if graph traversal was always required.
public interface GraphModel
{
public int getNodeCount();
public GraphNode getNode(int index);
public void addNode(GraphNode node);
public int getEdgeCount();
public GraphEdge getEdge(int index);
public void addEdge(GraphEdge edge);
}
With these interfaces in hand, we can implement the default classes. Since there are close to twenty classes in this project, we’ll only show some of the default implementations. Both the GraphEdge and the GraphNode implementations are trivial. The constructors allow you to set each of the values on creation and the accessors let you set and get the values as we’ve defined above. Since that’s all there is to it, we won’t list those classes here in print, though you can get all the classes online at www.java-pro.com.
Listing 1 shows the DefaultGraphModel class, which is relatively uncomplicated. We use two ArrayList objects for the nodes and edges, respectively. The two methods that retrieve the node or edge counts simply use the List interface size method, and we map directly on to the List add and get methods for the rest of the interface. In Java 1.1 we might have use a Vector to accomplish the same thing, but the Java 1.2 Collections API provides much faster implementations because they are not synchronized by default. ArrayList serves exactly the same purpose as a Vector class, but operates much more quickly.
Rendering
As we did with our model, we want to maximize flexibility in the user interface. To do this, we’ll define two renderer interfaces responsible for drawing nodes and edges. Nodes are drawn locally, wherever the model dictates the location should be. Edges have to be handled differently, using the graph’s whole coordinate system to draw properly between nodes. In other words, we can draw nodes by rendering a JComponent at the current node position, but to draw edges between nodes, we need to have a JComponent that covers the whole drawing area.
As always, we’ll provide default renderers, so you normally won’t have to implement anything special. Should you want to customize the JGraph display, however, the design supports it and puts the power where it belongs, into your hands. Let’s take a look at the interfaces.
Figure 2: Renderer Classes.
The GraphNodeRenderer interface declares a single method called getGraphNodeRendererComponent, which returns a JComponent reference. We could have allowed heavyweight AWT Components to be returned, as most of the Swing interfaces do, but this is not very useful in a lightweight component.While it might make some sense for the node renderer, it quickly becomes obvious that heavyweight components make poor edge renderer since they’ll cover the entire space and obliterate the rest of the display, by virtue of their background fill.
public interface GraphNodeRenderer
{
public JComponent getGraphNodeRendererComponent(
JGraph graph, GraphNode node, boolean hasFocus);
}
The getGraphNodeRendererComponent method is the only method we need. It expects a reference to the JGraph component, the current node to be painted, as well as a boolean flag that tell us whether the node currently has the focus.
The GraphEdgeRenderer interface handles drawing edges. It declares a method called getGraphEdgeRendererComponent, which returns a JComponent object. If you implement your own renderer, make sure the component is not opaque or you’ll end up with a single edge in the display area. The arguments include a reference to the JGraph component, the edge being rendered and a flag indicating whether the stress value should be displayed.
public interface GraphEdgeRenderer
{
public JComponent getGraphEdgeRendererComponent(
JGraph graph, GraphEdge edge, boolean showStress);
}
Now that we’ve defined the interfaces, lets implement the default renderers.
Listing 2 shows the DefaultGraphNodeRenderer. We define a couple of colors, one for fixed nodes and a normal color for all other nodes. I chose an yellowish orange for the node color. Also defined, are a normal and focus border. The normal border is just a raised EtchedBorder and the focus border uses a flat two pixel blue border. The constructor sets the normal border and also makes sure the node is opaque so that the background is always properly drawn.
The getGraphNodeRendererComponent method does the real work. We’re subclassing a JLabel component, so we first set the node’s name as the text value. We also set the background, based on whether the node is fixed or not, and the border, based on whether we have the focus or not.
Listing 3 shows the DefaultGraphEdgeRenderer. We set up a few colors for convenience. These define the text color, used to display the stress value (based on the edge’s weight value), and a normal and stress color for the edge line. We’ll show the edge in red if it’s under greater stress and black as a normal state. We use a couple of instance variables to hold a reference to the edge being drawn and a flag that determines whether stress values should be shown. This is information we receive through the getGraphEdgeRendererComponent method that we want available when we paint the component.
The paintComponent method does most of the work. We first get x and y position information from the two nodes at each end of the edge, using the GraphEdge interface getFrom and getTo methods. We then perform a Pythagorean calculation to get the physical length of the line and subtract the weight we assigned for the edge. From this, we can determine if we’re under stress and decide which color to use. Then we just draw the line. Optionally, we draw the text that represents the calculated stress value if the showStress flag is set.
Automation
If you’ve tried running the graph example that comes with the JDK, you may recall seeing self-adjusting nodes that settle into a usable configuration through convergence. To make it possible to add this kind of intelligence to our JGraph component, we’ll define one last interface called GraphAdjuster and provide several implementations that do interesting things, including the same behavior that the JDK example demonstrates. Our solution allows plug-and-play functionality through these interfaces, so these various behaviors are intended to demonstrate how useful this approach can be.
public interface GraphAdjuster extends Runnable
{
public void adjust();
}
We’ll implement 4 instances of this class. Two of them will scramble and shake the nodes on-demand. We’ll name these ScrambleAdjuster and ShakeAdjuster, respectively. Another adjuster, RandomAdjuster, periodically moves a single node at random and runs as a separate thread. Since we may want to use background threads like this fairly often, I’ve created an AutomaticAdjuster utility class you can use with any GraphAdjuster implementation. Its purpose is to call the adjust method at a predetermined interval you can specify. You can see what that looks like in Listing 4.
The most complicated GraphAdjuster implementation is OrganizeAdjuster, which implements the behavior from the JDK example, running as a background thread. OrganizeAdjuster requires a specialized GraphNode object called OrganizeGraphNode, which extends the DefaultGraphNode, because it needs access to velocity information for each node. While I could have made this part of the interface definition for GraphNode, it didn’t make sense to add a set of attributes with such a specific purpose to the interface, so if you want to use the OrganizeAdjuster, the nodes have to be of this type or nothing useful will happen.
Figure 3: Adjuster Classes.
The GraphAdjuster classes can be simple or complicated. Listing 5 shows the ScrambleAdjuster. The constructor stores a reference to the JGraph object, which we use in the adjust method to get the size of the drawing area. From that, we randomly reposition each node in the model and call the repaint method to refresh the view. The ShakeAdjuster does virtually the same thing, but rather than randomly repositioning the nodes anywhere in the drawing area, the nodes are randomly moved a smaller random distance from their current position.
There isn’t enough room to drill down into the OrganizeAdjuster, so I’ll just mention a few things for clarity. The algorithm comes from the Graph example that ships with the JDK. This implementation, however, is much cleaner than what you’ll see in the example, and intentionally uncoupled from the drawing code. As you can see from our design, this makes it possible to process the nodes without any negative impact on the overall design. I couldn’t resist exploring the JDK example because, for me, the whole graph came to life when this behavior was attached to it.
Composition
Let’s briefly touch on the user interface requirements and then put all this together in the JGraph class. Useful components typically provide mouse and keyboard control. In our case, we want to be able to handle focus events and node selection, as well as the fixed state a node can be in. When a node is considered ‘fixed’ we can avoid moving it, depending on the type of adjuster we’re using. We have to be able to toggle that state, so we’ll use the space bar on a selected node or a right click of the mouse to do this.
To move between node selections, we’ll use the arrow keys to cycle through the nodes in the model. At times, this might seem awkward, because we won’t move in the direction we chose. This is the only way to ensure we can cycle through each node without overcomplicating our problem. We can select nodes with appropriate mouse clicks to make it easier, but it’s important we also implement useful keyboard navigation.
Listing 6 shows the JGraph implementation. We set up a CellRendererPane to use in our drawing. This is a Swing class that makes it possible to handle renderers more effectively. We also set up our default node and edge renderers and the default graph model. A few other instance variables keep track of whether we’ll show the stress values, keep a reference to the currently selected node, store a flag indicating whether the current node is fixed, and keep an index into the node list that we can increment and decrement when we move between nodes.
The JGraph component implements the focus, mouse and keyboard listener interfaces, so we register these in the constructor. Much of our code is dedicated to handling these events. The component returns true in the isFocusTraversable method to tell Swing it can manage the focus. The only thing that changes when we get or lose the focus is handled in the paintComponent method, so all the focusLost and focusGained methods need to do is call repaint.
For keyboard events all we need is the keyPressed method to recognize a few keystrokes. We handle DOWN and RIGHT the same way, moving to the next node, and UP and LEFT the same way by moving to the previous node. All we need to do is increment or decrement the focusIndex value, handling wrap around conditions and repaint when we’re done to refresh the display. If the space key is pressed, we get the current node, based on the focusIndex, and toggle its fixed state, then repaint.
The mouse events are only slightly more complicated because we support dragging nodes around. The mouse pressed event requests the focus and adds a mouse motion listener. It then finds the node closest to the mouse position by walking the list of nodes in the model. If the right mouse button was used, we toggle the fixed state for the node. In either case, we store some critical values to be restored on mouse release and set things up so we can drag the node around before repainting to reflect our changes. The mouseReleased method restores these settings and removes the mouse motion listener before repainting. The mouseDragged method just moves the node to a new position and repaints the display.
Aside from the paint handling, there are only two methods that provide accessors to get and set the model. The paintComponent method does most of the work, with the support of paintNode and paintEdge methods. Each of these calls a renderer with setup information for the node or edge to be painted. It determines what the rendering size is and then uses the CellRendererPane to paint the component. This division of labor makes paintComponent easier to read since it merely draws the background and walks the model list of edges and nodes, delegating the paint operations to the paintNode and paintEdge methods.
You might be wondering about the number of paint events we are relying on and that’s a reasonable concern. For graphs that have a limited set of nodes, this component will perform well, but performance will degrade as the number of nodes and edges grows to a large enough number. Unfortunately, the kinds of optimizations required to focus on drawing performance are varied and make the code much more difficult to read or explain. Combined with the limited time between articles, I wasn’t able to do much work in this area. I though the 19 classes in this article were challenging enough to get just right. I hope you’ll agree that the open architecture provides plenty of value and encourage you to consider making drawing optimizations yourself. If I get enough mail about this, I’ll consider doing it in a future installment.
Figure 4: JGraphTest.
If you pull everything down from www.java-pro.com, you’ll find a JGraphTest class you can run to see how the JGraph component behaves. Figure 4 shows JGraphTest in action. The Scramble button triggers the ScrambleAdjuster and the Shake button triggers the ShakeAdjuster. The Stress check box determines whether the numerical values on each edge are shown. The Random check box determines whether periodic, single-node adjustments are used to help the graph adjustment stay out of local minima conditions (a fancy way of saying it introduces random events to avoid getting stuck). The RandomCheck box starts an AutomaticAdjuster with a RandomAdjuster and calls the quit method when you toggle it off.
The Organize check box determines whether the OrganizeAdjuster is active. This works the same way as the RandomAdjuster, using the AutomaticAdjuster to handle threading. This test configuration will eventually settle into a circle. I toggled off Organize to stop it from moving long enough to get the screen shot, but you can play with this all you like. I think you’ll find it interesting.
I hope you derive some enjoyment from this component as well as an appreciation for using interfaces effectively. In this case, we can swap three kinds of modeling elements, two renderers and any number of adjusters to associated behaviors with our graph. The modeling allows us to display any suitable data source. The renderers allows us to change the look of each element as needed and the adjusters provide a flexible way of handling directly triggered or automated events that move nodes around in the display. Taken with easily extensible default classes, this component represents a solid foundation to fill your graph display needs. I hope it serves you well.
Listing 1
import java.util.*;
public class DefaultGraphModel implements GraphModel
{
protected ArrayList nodes = new ArrayList();
protected ArrayList edges = new ArrayList();
public int getNodeCount()
{
return nodes.size();
}
public GraphNode getNode(int index)
{
return (GraphNode)nodes.get(index);
}
public void addNode(GraphNode node)
{
nodes.add(node);
}
public int getEdgeCount()
{
return edges.size();
}
public GraphEdge getEdge(int index)
{
return (GraphEdge)edges.get(index);
}
public void addEdge(GraphEdge edge)
{
edges.add(edge);
}
}
Listing 2
import java.awt.*;
import javax.swing.*;
import javax.swing.border.*;
public class DefaultGraphNodeRenderer extends JLabel
implements GraphNodeRenderer
{
protected final Color fixedColor =
Color.red;
protected final Color nodeColor =
new Color(250, 220, 100);
protected final Border normalBorder =
new EtchedBorder(EtchedBorder.RAISED);
protected final Border focusBorder =
new LineBorder(Color.blue, 2);
public DefaultGraphNodeRenderer()
{
setBorder(normalBorder);
setOpaque(true);
}
public JComponent getGraphNodeRendererComponent(
JGraph graph, GraphNode node, boolean hasFocus)
{
setText(node.getName());
setBackground(node.isFixed() ? fixedColor : nodeColor);
setBorder(hasFocus ? focusBorder : normalBorder);
return this;
}
}
Listing 3
import java.awt.*;
import javax.swing.*;
import javax.swing.border.*;
public class DefaultGraphEdgeRenderer extends JPanel
implements GraphEdgeRenderer
{
protected final Color textColor = Color.darkGray;
protected final Color normalColor = Color.black;
protected final Color stressColor = Color.red;
protected GraphEdge edge;
protected boolean showStress;
public JComponent getGraphEdgeRendererComponent(
JGraph graph, GraphEdge edge, boolean showStress)
{
this.edge = edge;
this.showStress = showStress;
return this;
}
public void paintComponent(Graphics g)
{
int x1 = (int)edge.getFrom().getX();
int y1 = (int)edge.getFrom().getY();
int x2 = (int)edge.getTo().getX();
int y2 = (int)edge.getTo().getY();
int len = (int)Math.abs(Math.sqrt(
(x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) -
edge.getWeight());
g.setColor((len < 10) ? normalColor : stressColor);
g.drawLine(x1, y1, x2, y2);
if (showStress)
{
g.setColor(textColor);
g.drawString(String.valueOf(len),
x1 + (x2 - x1) / 2, y1 + (y2 - y1) / 2);
}
}
}
Listing 4
public class AutomaticAdjuster extends Thread
{
protected boolean stop = false;
protected GraphAdjuster adjuster;
protected int interval;
public AutomaticAdjuster(GraphAdjuster adjuster)
{
this(adjuster, 100);
}
public AutomaticAdjuster(GraphAdjuster adjuster, int interval)
{
this.adjuster = adjuster;
this.interval = interval;
start();
}
public void run()
{
while (!stop)
{
adjuster.adjust();
try
{
Thread.sleep(interval);
}
catch (InterruptedException e)
{
break;
}
}
}
public void quit()
{
stop = true;
}
}
Listing 5
import java.awt.*;
public class ScrambleAdjuster implements GraphAdjuster
{
protected JGraph graph;
public ScrambleAdjuster(JGraph graph)
{
this.graph = graph;
}
public void adjust()
{
Dimension area = graph.getSize();
GraphModel model = graph.getModel();
for (int i = 0; i < model.getNodeCount(); i++)
{
GraphNode node = model.getNode(i);
node.setX(10 + (area.width - 20) * Math.random());
node.setY(10 + (area.height - 20) * Math.random());
}
graph.repaint();
}
}
Listing 6
import java.util.*;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
public class JGraph extends JPanel
implements MouseListener, MouseMotionListener,
KeyListener, FocusListener
{
protected CellRendererPane rendererPane =
new CellRendererPane();
protected GraphNodeRenderer nodeRenderer =
new DefaultGraphNodeRenderer();
protected GraphEdgeRenderer edgeRenderer =
new DefaultGraphEdgeRenderer();
protected GraphModel model =
new DefaultGraphModel();
protected boolean showStress;
protected GraphNode selection;
protected boolean selectionFixed;
protected int focusIndex = 0;
public JGraph()
{
addKeyListener(this);
addFocusListener(this);
addMouseListener(this);
}
public GraphModel getModel()
{
return model;
}
public void setModel(GraphModel model)
{
this.model = model;
}
public void paintNode(Graphics g, GraphNode node, boolean hasFocus)
{
Component component =
nodeRenderer.getGraphNodeRendererComponent(
this, node, hasFocus);
Dimension size = component.getPreferredSize();
rendererPane.paintComponent(g, component, this,
(int)node.getX() - (size.width / 2),
(int)node.getY() - (size.height / 2),
size.width, size.height);
}
public void paintEdge(Graphics g, GraphEdge edge)
{
Component component = edgeRenderer.getGraphEdgeRendererComponent(
this, edge, showStress);
Dimension size = getSize();
rendererPane.paintComponent(g, component, this,
0, 0, size.width, size.height);
}
public void paintComponent(Graphics g)
{
Dimension size = getSize();
g.setColor(getBackground());
g.fillRect(0, 0, size.width, size.height);
for (int i = 0; i < model.getEdgeCount(); i++)
{
paintEdge(g, model.getEdge(i));
}
for (int i = 0; i < model.getNodeCount(); i++)
{
paintNode(g, model.getNode(i),
hasFocus() && i == focusIndex);
}
}
private double distance(Point point, GraphNode node)
{
double x = point.getX() - node.getX();
double y = point.getY() - node.getY();
return Math.sqrt(x * x + y * y);
}
public boolean isFocusTraversable()
{
return true;
}
public void focusLost(FocusEvent event)
{
repaint();
}
public void focusGained(FocusEvent event)
{
repaint();
}
public void keyTyped(KeyEvent event) {}
public void keyReleased(KeyEvent event) {}
public void keyPressed(KeyEvent event)
{
int code = event.getKeyCode();
if (code == KeyEvent.VK_UP ||
code == KeyEvent.VK_LEFT)
{
focusIndex++;
int max = model.getNodeCount() - 1;
if (focusIndex > max) focusIndex = 0;
repaint();
}
if (code == KeyEvent.VK_RIGHT ||
code == KeyEvent.VK_DOWN)
{
focusIndex--;
int max = model.getNodeCount() - 1;
if (focusIndex < 0) focusIndex = max;
repaint();
}
if (code == KeyEvent.VK_SPACE)
{
GraphNode node = model.getNode(focusIndex);
node.setFixed(!node.isFixed());
repaint();
}
}
public void mouseClicked(MouseEvent event) {}
public void mouseEntered(MouseEvent event) {}
public void mouseExited(MouseEvent event) {}
public void mouseMoved(MouseEvent event) {}
public void mousePressed(MouseEvent event)
{
requestFocus();
addMouseMotionListener(this);
double closest = Double.MAX_VALUE;
Point point = event.getPoint();
for (int i = 0; i < model.getNodeCount(); i++)
{
GraphNode node = model.getNode(i);
double dist = distance(point, node);
if (dist < closest)
{
selection = node;
closest = dist;
focusIndex = i;
}
}
boolean rightButton = SwingUtilities.isRightMouseButton(event);
if (rightButton) selection.setFixed(!selection.isFixed());
selectionFixed = selection.isFixed();
selection.setFixed(true);
selection.setX(point.getX());
selection.setY(point.getY());
repaint();
}
public void mouseReleased(MouseEvent event)
{
removeMouseMotionListener(this);
selection.setX(event.getPoint().getX());
selection.setY(event.getPoint().getY());
selection.setFixed(selectionFixed);
selection = null;
repaint();
}
public void mouseDragged(MouseEvent event)
{
selection.setX(event.getPoint().getX());
selection.setY(event.getPoint().getY());
repaint();
}
}