digraphs

Class Digraph

java.lang.Object

digraphs.Digraph

public class Digraph
extends java.lang.Object

A class for representing directed graphs.

Author:

James A. Mason

Field Summary

Fields

Modifier and Type	Field and Description
protected java.util.ArrayList<DigraphEdge>	digraphEdges
protected java.util.ArrayList<DigraphNode>	digraphNodes
protected static java.lang.String	EdgeClassName

Constructor Summary

Constructors

Constructor and Description
Digraph() Initializes a new Digraph with empty lists of nodes and edges.

Method Summary

Modifier and Type	Method and Description
DigraphEdge	addEdgeFromNodeToNode(DigraphNode node1, DigraphNode node2) Adds a new edge of the appropriate DigraphEdge subclass to connect two given nodes, provided the two nodes are nodes of the receiver Digraph.
DigraphEdge	addEdgeFromTo(int nodeIndex1, int nodeIndex2) Adds a new edge of the appropriate DigraphEdge subclass to connect two given nodes indicated by their indices (0, 1, 2, ... ) in the list of DigraphNodes for the Digraph.
DigraphNode	addNode() Adds a new node to the Digraph and returns it.
Digraph	copyDigraph() Returns a copy of the receiver Digraph, without sharing of nodes or edges.
DigraphEdge	edgeAt(int pos) Returns the DigraphEdge at given position in the list of edges; null if no such edge.
java.util.ArrayList<DigraphEdge>	getEdges() Returns the ArrayList of DigraphEdges in the Digraph
java.util.ArrayList<DigraphNode>	getNodes() Returns the ArrayList of DigraphNodes in the Digraph
boolean	isCyclic() Returns true of the Digraph has cycles; false if not
DigraphNode	nodeAt(int pos) Returns the DigraphNode at given position in the list of nodes; null if no such node.
int	numberOfEdges() Returns the number of edges in the Digraph
int	numberOfNodes() Returns the number of nodes in the Digraph
DigraphEdge	removeEdge(DigraphEdge aDigraphEdge) Removes a given edge, provided it is in the Digraph.
DigraphNode	removeNode(DigraphNode aDigraphNode) Removes a given node, provided it is in the Digraph, after first removing all edges in and out of it.
java.util.ArrayList<DigraphNode>	sinks() Returns an ArrayList containing the DigraphNodes in the Digraph that have no outgoing edges.
java.util.ArrayList<DigraphNode>	sources() Returns an ArrayList containing the DigraphNodes in the Digraph that have no incoming edges.
java.lang.String	toString() Returns a string that represents the Digraph in the following form: - the number of nodes in digraphNodes; - a parenthesized list of edge representations, each a parenthesized pair: (fromNodeNumber, toNodeNumber) where fromNodeNumber and toNodeNumber are indices of nodes in digraphNodes.

Methods inherited from class java.lang.Object

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

Field Detail

digraphEdges

protected java.util.ArrayList<DigraphEdge> digraphEdges

digraphNodes

protected java.util.ArrayList<DigraphNode> digraphNodes

EdgeClassName

protected static java.lang.String EdgeClassName

Constructor Detail

Digraph

public Digraph()

Initializes a new Digraph with empty lists of nodes and edges.

Method Detail

addEdgeFromTo

public DigraphEdge addEdgeFromTo(int nodeIndex1,
                                 int nodeIndex2)
                          throws java.lang.ClassNotFoundException,
                                 java.lang.reflect.InvocationTargetException,
                                 java.lang.InstantiationException,
                                 java.lang.IllegalAccessException

Adds a new edge of the appropriate DigraphEdge subclass to connect two given nodes indicated by their indices (0, 1, 2, ... ) in the list of DigraphNodes for the Digraph.

Returns:

the edge added, or null if unsuccessful.

Throws:

java.lang.ClassNotFoundException

java.lang.reflect.InvocationTargetException

java.lang.InstantiationException

java.lang.IllegalAccessException

addEdgeFromNodeToNode

public DigraphEdge addEdgeFromNodeToNode(DigraphNode node1,
                                         DigraphNode node2)
                                  throws java.lang.ClassNotFoundException,
                                         java.lang.reflect.InvocationTargetException,
                                         java.lang.InstantiationException,
                                         java.lang.IllegalAccessException

Adds a new edge of the appropriate DigraphEdge subclass to connect two given nodes, provided the two nodes are nodes of the receiver Digraph.

Parameters:

node1 - the node that the edge is to go from

node2 - the node that the edge is to go to

Returns:

the new edge; or null if unsuccessful

Throws:

java.lang.ClassNotFoundException

java.lang.reflect.InvocationTargetException

java.lang.InstantiationException

java.lang.IllegalAccessException

addNode

public DigraphNode addNode()

Adds a new node to the Digraph and returns it.

copyDigraph

public Digraph copyDigraph()
                    throws java.lang.ClassNotFoundException,
                           java.lang.reflect.InvocationTargetException,
                           java.lang.InstantiationException,
                           java.lang.IllegalAccessException

Returns a copy of the receiver Digraph, without sharing of nodes or edges. Returns null if the receiver Digraph is ill-formed.

Throws:

java.lang.ClassNotFoundException

java.lang.reflect.InvocationTargetException

java.lang.InstantiationException

java.lang.IllegalAccessException

edgeAt

public DigraphEdge edgeAt(int pos)

Returns the DigraphEdge at given position in the list of edges; null if no such edge.

Parameters:

pos - the index of the edge to be found

getEdges

public java.util.ArrayList<DigraphEdge> getEdges()

Returns the ArrayList of DigraphEdges in the Digraph

getNodes

public java.util.ArrayList<DigraphNode> getNodes()

Returns the ArrayList of DigraphNodes in the Digraph

isCyclic

public boolean isCyclic()
                 throws java.lang.ClassNotFoundException,
                        java.lang.reflect.InvocationTargetException,
                        java.lang.InstantiationException,
                        java.lang.IllegalAccessException

Returns true of the Digraph has cycles; false if not

Throws:

java.lang.ClassNotFoundException

java.lang.reflect.InvocationTargetException

java.lang.InstantiationException

java.lang.IllegalAccessException

nodeAt

public DigraphNode nodeAt(int pos)

Returns the DigraphNode at given position in the list of nodes; null if no such node.

Parameters:

pos - the index of the node to be found

numberOfEdges

public int numberOfEdges()

Returns the number of edges in the Digraph

numberOfNodes

public int numberOfNodes()

Returns the number of nodes in the Digraph

removeEdge

public DigraphEdge removeEdge(DigraphEdge aDigraphEdge)

Removes a given edge, provided it is in the Digraph. Also updates the starting and ending nodes of the edge appropriately.

Parameters:

aDigraphEdge - the edge to be removed

Returns:

the edge removed, or null if the edge is not in the Digraph

removeNode

public DigraphNode removeNode(DigraphNode aDigraphNode)

Removes a given node, provided it is in the Digraph, after first removing all edges in and out of it.

Parameters:

aDigraphNode - the node to be removed

Returns:

the node removed, or null if the node is not in the Digraph

sinks

public java.util.ArrayList<DigraphNode> sinks()

Returns an ArrayList containing the DigraphNodes in the Digraph that have no outgoing edges.

sources

public java.util.ArrayList<DigraphNode> sources()

Returns an ArrayList containing the DigraphNodes in the Digraph that have no incoming edges.

toString

public java.lang.String toString()

Returns a string that represents the Digraph in the following form: - the number of nodes in digraphNodes; - a parenthesized list of edge representations, each a parenthesized pair: (fromNodeNumber, toNodeNumber) where fromNodeNumber and toNodeNumber are indices of nodes in digraphNodes.

Overrides:

toString in class java.lang.Object