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

void	addEdge(Edge e) Add an edge From--edgeNumber-->To to this graph, for some, minumum, edgeNumber.
Edge	addEdge(Node From, Node To) Add an edge From--edgeNumber-->To to this graph, for some, minumum, edgeNumber.
Node	addNode() Create, add, and return a new node in this graph.
Node	addNode(int nodeNumber) Add and return a new node in the graph.
void	addNode(Node node) Add a new node to this graph.
void	addNode(Node node, int nodeNumber) Add a new node with a particular node number to this graph.
java.lang.Object	clone()
Graph	copy() Return a fresh (deep) copy of this graph.
void	deleteEdge(Edge edge)
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.
boolean	hasEdge(Edge e) Return true if this graph has an edge e.
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.
boolean	isSimpleDigraph() Return false if the graph contains 2 edges with the same from node and the same to node
static void	main(java.lang.String[] args)
int	maxNodeNumber() Add a new node to this graph.
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(Edge e, int edgeNumber) Create an edge From--edgeNumber-->To in 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)
(package private) static void	test1()
(package private) static void	test2()
(package private) static void	test3()
(package private) static void	test4()
java.lang.String	toDot()
java.lang.String	toString()
java.lang.String	toString(java.lang.String prefix)
java.lang.String	toString(java.lang.String prefix, boolean complete)

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.

deleteEdge

public void deleteEdge(Edge edge)

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.

isSimpleDigraph

public boolean isSimpleDigraph()

Return false if the graph contains 2 edges with the same from node and the same to node

hasEdge

public boolean hasEdge(Node From,
                       Node To)

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

hasEdge

public boolean hasEdge(Edge e)

Return true if this graph has an edge e.

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,
                    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 void addEdge(Edge e)

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

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.

maxNodeNumber

public int maxNodeNumber()

Add a new node to this graph. Give it 1+ the maximum node number already in the graph.

addNode

public void addNode(Node node,
                    int nodeNumber)

Add a new node with a particular node number to this graph.

Parameters:

node - the node to add

nodeNumber - the number of the node

addNode

public void addNode(Node node)

Add a new node to this graph. Give it 1+ the maximum node number already in the graph.

Parameters:

node - the node to add

addNode

public Node addNode()

Create, add, and return a new node in this graph. Give it 1+ the maximum node number already in the graph.

addNode

public Node addNode(int nodeNumber)

Add and return a new node in the graph.

Parameters:

nodeNumber - the number of the node

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.

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

toDot

public java.lang.String toDot()

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)

test1

static void test1()

test2

static void test2()

test3

static void test3()

test4

static void test4()

main

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