sandmark.util.graph
Class Graph

java.lang.Object
  |
  +--sandmark.util.graph.Graph

All Implemented Interfaces:

java.lang.Cloneable

public class Graph

extends java.lang.Object

implements java.lang.Cloneable

Simple graph package. The following data structure is used:

      Nodes
     +-----+
  1  |     |
     +-----+
  2  |     |
     +-----+           +------+
  3  |   +-+---------> |  3   | (sandmark.util.graph.Node)
     +-----+           +------+
  4  |     |
     +-----+
  5  |     |
     +-----+
  6  |     |
     +-----+
 

      Edges
     +-----+
  1  |     |
     +-----+
  2  |     |             1   2   3   4   5   6
     +-----+           +---+---+---+---+---+---+
  3  |   +-+---------> |   |   |   | + |   |   |
     +-----+           +---+---+---+-+-+---+---+
  4  |     |                         |
     +-----+                         |
  5  |     |                         v
     +-----+                   +---+---+---+
  6  |     |                   | + | + | 4 |   (sandmark.util.graph.Edge)
     +-----+                   +-+-+-+-+---+
                                 |   |
                                 |   |
                                 v   v
                               +--+ +--+
                               |3 | |3 |  (sandmark.util.graph.Node)
                               +--+ +--+
 

Nodes is a sandmark.util.SparseVector, indexed by node-number, and containing sandmark.util.graph.Node's. Each node has a number, starting at 1.

Edges is another sandmark.util.SparseVector, indexed by source-node number and containing yet another sandmark.util.SparseVector, which we'll call the 'OutgoingEdgesVector' here. This vector is indexed by EdgeNumber. The graphs we create typically have low out-degree (maybe 2), in which case the OutgoingEdgesVector will only have two elements, numbered 1 to 2.

Each element in the OutgoingEdgesVector is a sandmark.util.graph.Edge object which points to two sandmark.util.graph.Node objects, the source and the sink nodes. sandmark.util.graph.Edge also contains the EdgeNumber.

In the example above we have only one node, node number 3, which has only one outgoing edge (on EdgeNumber 4), to itself. Note that sandmark.util.graph.Graph is really a multi-graph: we can have multiple edges between the same two nodes.

Both nodes and edges can have data associated with them.

Certain operations are expensive, in particular iterating through a node's incoming edges.

Nested Class Summary

(package private) class	Graph.AllEdges
(package private) class	Graph.AllNodes
(package private) class	Graph.Incoming
(package private) class	Graph.OutgoingClassEdges

Field Summary

protected Dfs	dfs
protected java.lang.String[]	edgeNames
protected SparseVector	edges
protected SparseVector	nodes
protected java.lang.String	theHeader
protected Node	theRoot

Constructor Summary

Graph()
Create a new graph.

Graph(int nodeCount)
Create a new graph of at least nodeCount nodes.

Method Summary

Edge	addEdge(Node From, Node To) Add an edge From--edgeNumber-->To to this graph, for some, minumum, edgeNumber.
Node	addNode() Add and return a new node in this graph.
Node	addNode(int nodeNumber) Add and return a new node in the graph.
java.lang.Object	clone()
Graph	copy() Return a fresh (deep) copy of this graph.
void	deleteNode(Node node) Delete a node and any incident edges from this graph.
void	deleteNodes(java.util.HashSet nodeSet) Delete a set of nodes and any incident edges from this graph.
Dfs	DFS() Return the Dfs-object associated with this graph.
Dfs	DFS(Node root)
java.util.Iterator	forAllEdges() Iterate over all edges in the graph, in no particular order.
java.util.Iterator	forAllNodes() Iterate over all nodes in the graph, in no particular order.
Edge	getEdge(Node From, int edgeNumber) If there's an edge From--edgeNumber-->To in this graph, return To, else return null.
Edge	getEdge(Node From, Node To, int edgeNumber) Return the edge From--edgeNumber-->To or null, if it doesn't exist.
java.lang.String	getEdgeName(int edgeNumber) Each outgoing edge has a number.
java.lang.String[]	getEdgeNames() Each outgoing edge has a number.
att.grappa.Graph	getGrappa()
boolean	hasEdge(Node From, Node To) Return true if there's an edge from node From to node To in this graph.
boolean	hasNode(Node node) Return true if there is a node 'node' in this graph.
java.lang.String	header() Return the string header of this graph.
java.util.Iterator	incomingEdges(Node To) Generate all the incoming edges to node To in this Graph.
static void	main(java.lang.String[] args)
java.lang.String	name() Return a unique name for this graph.
int	nodeCount() Return the number of nodes in this graph.
Node[]	nodes() Return an array of the nodes of this graph.
int	outDegree() Return the maximum outdegree of any node in this graph.
java.util.Iterator	outgoingClassEdges(Node From, int Class) Generate all edges of type Class (sandmark.util.graph.Edge.TREE, sandmark.util.graph.Edge.BACK, sandmark.util.graph.Edge.FORWARD, or sandmark.util.graph.Edge.CROSS) starting in node From.
java.util.Iterator	outgoingClassEdges(Node From, int[] Class) Generate all edges whose type is one of the ones (sandmark.util.graph.Edge.TREE, sandmark.util.graph.Edge.BACK, sandmark.util.graph.Edge.FORWARD, or sandmark.util.graph.Edge.CROSS) given in Class, starting in node From.
java.util.Iterator	outgoingEdges(Node From) Given the node From, Generate all edges From--edgeNumber-->To in this graph.
void	print()
void	process() Perform a depth-first search of this graph, classifying each edge as sandmark.util.graph.Edge.TREE, sandmark.util.graph.Edge.BACK, sandmark.util.graph.Edge.FORWARD, or sandmark.util.graph.Edge.CROSS.
void	process(Node root)
Node	root() Return the root node of this graph.
Edge	setEdge(Edge e) Add the edge e to this graph.
Edge	setEdge(Node From, Node To, int edgeNumber) Create an edge From--edgeNumber-->To in this graph.
void	setEdgeNames(java.lang.String[] e) Each outgoing edge has a number.
void	setHeader(java.lang.String h) Set the string header of this graph.
void	setRoot(Node node) Set the root node of this graph.
void	show(java.lang.String header)
java.lang.String	toString()
java.lang.String	toString(java.lang.String prefix)
java.lang.String	toString(java.lang.String prefix, boolean complete)
void	view()

Methods inherited from class java.lang.Object

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

Field Detail

theRoot

protected Node theRoot

dfs

protected Dfs dfs

theHeader

protected java.lang.String theHeader

edgeNames

protected java.lang.String[] edgeNames

nodes

protected SparseVector nodes

edges

protected SparseVector edges

Constructor Detail

Graph

public Graph()

Create a new graph.

Graph

public Graph(int nodeCount)

Create a new graph of at least nodeCount nodes.

Method Detail

clone

public java.lang.Object clone()
                       throws java.lang.CloneNotSupportedException

Overrides:

clone in class java.lang.Object

java.lang.CloneNotSupportedException

copy

public Graph copy()

Return a fresh (deep) copy of this graph.

deleteNode

public void deleteNode(Node node)

Delete a node and any incident edges from this graph.

deleteNodes

public void deleteNodes(java.util.HashSet nodeSet)

Delete a set of nodes and any incident edges from this graph.

nodeCount

public int nodeCount()

Return the number of nodes in this graph.

outDegree

public int outDegree()

Return the maximum outdegree of any node in this graph.

root

public Node root()

Return the root node of this graph.

setRoot

public void setRoot(Node node)

Set the root node of this graph.

header

public java.lang.String header()

Return the string header of this graph. Used when printing the graph.

setHeader

public void setHeader(java.lang.String h)

Set the string header of this graph. Used when printing the graph.

getEdgeName

public java.lang.String getEdgeName(int edgeNumber)

Each outgoing edge has a number. getEdgeName returns the string name associated with this number. Default is "e1" for edge number 1.

getEdgeNames

public java.lang.String[] getEdgeNames()

Each outgoing edge has a number. getEdgeNames returns the array of string names associated with each number. Default is "e1" for edge number 1, etc.

setEdgeNames

public void setEdgeNames(java.lang.String[] e)

Each outgoing edge has a number. setEdgeNames gives a new array of string names to be associated with each edge number.

forAllNodes

public java.util.Iterator forAllNodes()

Iterate over all nodes in the graph, in no particular order.

forAllEdges

public java.util.Iterator forAllEdges()

Iterate over all edges in the graph, in no particular order.

hasEdge

public boolean hasEdge(Node From,
                       Node To)

Return true if there's an edge from node From to node To in this graph.

setEdge

public Edge setEdge(Node From,
                    Node To,
                    int edgeNumber)

Create an edge From--edgeNumber-->To in this graph.

setEdge

public Edge setEdge(Edge e)

Add the edge e to this graph.

getEdge

public Edge getEdge(Node From,
                    Node To,
                    int edgeNumber)

Return the edge From--edgeNumber-->To or null, if it doesn't exist.

addEdge

public Edge addEdge(Node From,
                    Node To)

Add an edge From--edgeNumber-->To to this graph, for some, minumum, edgeNumber.

getEdge

public Edge getEdge(Node From,
                    int edgeNumber)

If there's an edge From--edgeNumber-->To in this graph, return To, else return null.

outgoingEdges

public java.util.Iterator outgoingEdges(Node From)

Given the node From, Generate all edges From--edgeNumber-->To in this graph.

hasNode

public boolean hasNode(Node node)

Return true if there is a node 'node' in this graph.

addNode

public Node addNode()

Add and return a new node in this graph.

addNode

public Node addNode(int nodeNumber)

Add and return a new node in the graph.

nodes

public Node[] nodes()

Return an array of the nodes of this graph.

outgoingClassEdges

public java.util.Iterator outgoingClassEdges(Node From,
                                             int Class)

Generate all edges of type Class (sandmark.util.graph.Edge.TREE, sandmark.util.graph.Edge.BACK, sandmark.util.graph.Edge.FORWARD, or sandmark.util.graph.Edge.CROSS) starting in node From.

outgoingClassEdges

public java.util.Iterator outgoingClassEdges(Node From,
                                             int[] Class)

Generate all edges whose type is one of the ones (sandmark.util.graph.Edge.TREE, sandmark.util.graph.Edge.BACK, sandmark.util.graph.Edge.FORWARD, or sandmark.util.graph.Edge.CROSS) given in Class, starting in node From.

process

public void process()

Perform a depth-first search of this graph, classifying each edge as sandmark.util.graph.Edge.TREE, sandmark.util.graph.Edge.BACK, sandmark.util.graph.Edge.FORWARD, or sandmark.util.graph.Edge.CROSS.

process

public void process(Node root)

DFS

public Dfs DFS()

Return the Dfs-object associated with this graph.

DFS

public Dfs DFS(Node root)

incomingEdges

public java.util.Iterator incomingEdges(Node To)

Generate all the incoming edges to node To in this Graph. Inefficient implementation.

getGrappa

public att.grappa.Graph getGrappa()

view

public void view()

toString

public java.lang.String toString(java.lang.String prefix,
                                 boolean complete)

toString

public java.lang.String toString(java.lang.String prefix)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

print

public void print()

name

public java.lang.String name()

Return a unique name for this graph.

show

public void show(java.lang.String header)

main

public static void main(java.lang.String[] args)