org.quilt.graph
Class Directed

java.lang.Object
  |
  +--org.quilt.graph.Directed

Direct Known Subclasses:

ControlFlowGraph

public class Directed

extends java.lang.Object

A graph consisting of vertices connected by directed, weighted edges. The graph is guaranteed to have at least an entry and an exit point and to always be well-formed, in the sense that

• there will be a path from the entry vertex to any other vertex in the graph, and
• there will be a path from any vertex in the graph to the exit vertex

These graphs may be nested. In such a case

• both graphs will be well-formed
• the entry and exit points of the subgraph are in the graph
• all paths from the entry point of the parent to a point in the subgraph will pass through the entry point of the subgraph
• all paths from a vertex within the subgraph to a vertex in the parent graph will pass through the exit vertex of the subgraph

Author:

Jim Dixon

Field Summary

protected static int

graphIndex Index of most recently built graph.

Constructor Summary

	Directed() Builds a root directed graph with two vertices and two edges.
protected	Directed(Directed parent) Subgraph constructor; will have depth one more than parent.

Method Summary

int	anotherEdge(Edge e) Step edge count.
int	anotherVertex(Vertex v) Step count of vertices .
static void	checkForNull(java.lang.Object o, java.lang.String what)
Entry	closestEntry(Directed g) If the edge points towards a vertex in a graph which is enclosed within the current graph, return a reference to the closest Entry.
protected static Directed	connectSubgraph(Directed subgraph, Edge e, int n) Inserts a subgraph into an edge, putting the entry and exit points on the edge presented.
int	getDepth()
Entry	getEntry()
Exit	getExit()
int	getIndex()
Directed	getParent()
Vertex	insertVertex(Edge e) Create a new Vertex with a Unary connector and insert into this graph's edge e.
protected Vertex	insertVertex(Vertex v, Edge e) Insert a (new) Vertex into the graph along the edge provided.
int	size()
Directed	subgraph(Edge e, int n) Constructs a subgraph and inserts it into the parent graph on the edge presented.

Methods inherited from class java.lang.Object

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

Field Detail

graphIndex

protected static int graphIndex

Index of most recently built graph.

Constructor Detail

Directed

public Directed()

Builds a root directed graph with two vertices and two edges. The two vertices are Entry and Exit types. There is an edge from entry to exit and another from exit back to entry. Each is constained in a UnaryConnector. Vertices are added to the graph by inserting them along the entry-to-exit edge.

See Also:

Connector, Edge

Directed

protected Directed(Directed parent)

Subgraph constructor; will have depth one more than parent.

Parameters:

parent - Graph in which this is a subgraph.

Method Detail

getParent

public Directed getParent()

Returns:

The parent graph to this graph, or null if there is none.

getIndex

public int getIndex()

Returns:

The zero-based index of this graph.

connectSubgraph

protected static final Directed connectSubgraph(Directed subgraph,
                                                Edge e,
                                                int n)

Inserts a subgraph into an edge, putting the entry and exit points on the edge presented. On exit the original edge has been retargeted to the Entry of the subgraph.

Parameters:

e - An edge in the parent graph.

Returns:

A reference to the subgraph.

subgraph

public Directed subgraph(Edge e,
                         int n)

Constructs a subgraph and inserts it into the parent graph on the edge presented. This is a wrapper around the method that does the connecting; when extending the class, override the wrapper.

Parameters:

e - An edge in the parent graph.

Returns:

A reference to the subgraph.

getDepth

public int getDepth()

Returns:

The depth of this graph.

getEntry

public Entry getEntry()

Returns:

The entry vertex of this graph.

getExit

public Exit getExit()

Returns:

The exit vertex of this graph.

checkForNull

public static void checkForNull(java.lang.Object o,
                                java.lang.String what)

anotherEdge

public int anotherEdge(Edge e)

Step edge count.

Parameters:

e - Edge being added. Ignored at the moment.

anotherVertex

public int anotherVertex(Vertex v)

Step count of vertices .

Parameters:

v - Vertex being added. Being ignored at the moment.

insertVertex

protected final Vertex insertVertex(Vertex v,
                                    Edge e)

Insert a (new) Vertex into the graph along the edge provided. After this operation the target of the edge will be the new vertex.

Parameters:

v - Vertex to be inserted.

e - Edge it is to be inserted along.

insertVertex

public Vertex insertVertex(Edge e)

Create a new Vertex with a Unary connector and insert into this graph's edge e.

size

public int size()

closestEntry

public Entry closestEntry(Directed g)

If the edge points towards a vertex in a graph which is enclosed within the current graph, return a reference to the closest Entry. The vertex might be within a nested subgraph. If it is not in a descendent graph, return null.

Parameters:

g - Candidate lower-level graph.

Returns:

A reference to the nearest Entry point or null.