net.goui.util
Class GraphLayout

java.lang.Object
  net.goui.util.GraphLayout

public class GraphLayout

extends java.lang.Object

Author:

David Beaumont, Copyright 2005

Introduction

This class encapsulates the layout of the vertices of a directed acyclic graph (DAG), according to size constraints placed upon the edges between those vertices.

Typically it is not expected that this class will be used directly within an application, but rather that it, and the associated inner classes are extended to implement a more specific and meaningful behaviour.

The vertices within the graph have a position which can either be set explicitly or determined during a layout. The edges have length constraints and a weighting value which is used to determine the correct distribution of any 'spare' space which might exist during a layout procedure. A simple graph might look like this:

        min=100          min=100
      ,>---------> V1 >--------->.
     /    E0               E2     \
   V0                              V3
     \    E1               E3     /
      `>---------> V2 >--------->'
        min=100          min=200
 

Here Vertex V0 connects to Vertices V1 and V2 (via Edges E0 & E1 respectively) which in turn both connect to Vertex V3 via Edges E2 & E3 respectively. We can also see that E0, E1 and E2 have a minimum length of 100 'units' but E3 has a minimum length of 200.

Firstly we must assign a position to Vertex V0 as it is a source in the graph (it only has outgoing edges) because it cannot depend on the position of any other preceding Vertices. For simplicity in this example we will place it at position 0. Note that the position of Vertices must be a non-negative integer, so zero is the minimal value which can be assigned to any source Vertices.

Now we can determine the minimal offset of Vertices V1 and V2 from V0 and in this case it is trivially 100 units. Similarly the offset of V3 from V1 and V2 is 100 and 200 units respectively.

However the minimimal offset of V3 from V0 is not so trivial because there are two paths between them and we must find the longest such path (in terms of units rather than the number of edges in it). By this rule, the minimum offset from Vertex V0 to V3 is 300 units, defined by the sequence of edges (E1, E3).

Suppose now that we were to posistion V3 at 300, its minimum permitted offset from V0. We would now be able to attempt to layout the remaining Vertices according to their minimum size constraints and weighting. Whilst Vertex V2 has only one valid position in which it can be placed (pos=100) we can place Vertex V1 anywhere in the range [100,200] without violating the minimum size constraints of the edges around it. This is where the weighting values come in.

Where a Vertex (or series or Vertices) can be placed freely between two fixed Vertices, we attempt to resize the edges between them so their size is in proportion to their weighting. So if E0 and E2 both have a weight of 1, then the Edges E0 and E2 would obtain a length of 150 units each and Vertex V1 would be positioned at 150. Similarly if the ratio of weighting between E0 and E2 was 2:1, V1 would be positioned at 200. However, if the ratio were any higher, 5:1 for example, then we would not be able to place V2 according to this weighting without violating the minimum size constraint of Edge E2.

Paths

When constructing a more complex graph, it is possible that the position of a Vertex can be defined by several conflicting sets of constraints.

        weight=2        weight=1
      ,>-------->.    ,>-------->.
     /    E0      \  /     E2     \
   V0              V1              V2
     \    E1      /  \     E3     /  
      `>-------->'    `>-------->'   
   |     weight=1        weight=2   |
   v                                v
 pos=0                           pos=300
 

In the example above, if the minimum size of all the edges is zero, then we will seek to position Vertex V1 in accordance with the weights of the edges around it. However between the fixed Vertices V0 (position=0) and V2 (position=300) there are actually 4 possible paths which can be taken that will defined the position of Vertex V1.

• (E0, E2) : Position of V1 = 200
• (E1, E3) : Position of V1 = 100
• (E0, E3) : Position of V1 = 150
• (E1, E2) : Position of V1 = 150

To resolve this issue the concept of a Path within the graph has been defined. A Path is an ordered sequence of adjacent edges and it is only possible to layout Vertices within the graph by laying out a Path which contains them.

This removes any ambiguity about which of the edges should be uesd to define the position of V1 in the above example by requiring that the user of the GraphLayout dexcides for themselves which sequence of edges is used. Thus a layout process can be defined as the cummulative result of laying out a set of Paths in a particular order.

On requirement of using a Path instance is that prior to laying it out, both the end Vertices must have their positions set. This can be done explicitly or can be as the result of the layout of a different Path earlier in the layout process. Once reset() has been called on the GraphLayout instance however, all the Vertices in that graph will have had their positions invalidate, so for the first Path at least, the Vertex positions must be set explicitly.

An example of typical usage would look something like:

 myGraphLayout.reset();

 Edge firstEdge = myPath.getEdge(0);
 Edge lastEdge  = myPath.getEdge(path.getEdgeCount()-1);
 
 Vertex firstVertex = firstEdge.getVertexNeg();
 Vertex lastVertex  = lastEdge.getVertexPos();
 
 firstVertex.setPosition(myFirstPosition);
 lastVertex.setPosition(myLastPosition);
 
 myPath.layout();
 

Or alternatively:

 myGraphLayout.reset();
 
 myPath.setBounds(myFirstPosition,myLastPosition);
 
 myPath.layout();
 

Synchronisation

Note that none of the methods in this class use any form of synchronisation mechanism and it is up to the application using this class to protect the user from any risk of concurrent modification to the graph.

Nested Class Summary

static class	GraphLayout.Edge
static interface	GraphLayout.EdgeConstraint
static class	GraphLayout.Path
static class	GraphLayout.Vertex

Field Summary

static int

INVALID This constant is returned when the position of a Vertex is not known.

Constructor Summary

GraphLayout()
Construct an empty GraphLayout instance.

Method Summary

void	addEdge(GraphLayout.Vertex neg, GraphLayout.Edge edge, GraphLayout.Vertex pos) Add the given edge to the current graph, connected by the given Vertices.
void	reset() This method resets the position of all Vertices and the size of all Edges which are part of this GraphLayout.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

INVALID

public static final int INVALID

This constant is returned when the position of a Vertex is not known.

See Also:

Constant Field Values

Constructor Detail

GraphLayout

public GraphLayout()

Construct an empty GraphLayout instance. Use the addEdge() method to populate this layout with edges and vertices.

Method Detail

reset

public void reset()

This method resets the position of all Vertices and the size of all Edges which are part of this GraphLayout. It should be called prior to initiating any new layout procedure.

Warning This method is unsynchronised and it is up to the user to ensure that concurrent modification of the layout graph does not occur.

addEdge

public void addEdge(GraphLayout.Vertex neg,
                    GraphLayout.Edge edge,
                    GraphLayout.Vertex pos)

Add the given edge to the current graph, connected by the given Vertices. Before an edge can be added to a Path or used during a layout procedure it must be added to the GraphLayout using this method.

Warning This method is unsynchronised and it is up to the user to ensure that concurrent modification of the layout graph does not occur.

Parameters:

neg - The negative (preceding) Vertex for the edge (non null).

edge - The edge to be added to this GraphLayout (non null).

pos - The positive (following) Vertex for the edge (non null).

Throws:

java.lang.IllegalArgumentException - if any of the arguments have already been added to a different GraphLayout instance.

java.lang.NullPointerException - if any of the arguments are null.