Class Graph<V,E>

java.lang.Object
  Graph<V,E>

public class Graph<V,E>
extends java.lang.Object

Implements a graph.

Nested Class Summary

class	Graph.Edge Implements an edge in a graph.
class	Graph.Node Implements a node in a graph.

Field Summary

protected java.util.LinkedList<Graph.Edge>	edges The list of edges
protected java.util.LinkedList<Graph.Node>	nodes The list of vertices

Constructor Summary

Graph()
Constructor initializes with empty node and edge lists

Method Summary

Graph.Edge	addEdge(E data, Graph.Node head, Graph.Node tail) Adds an edge
Graph.Node	addNode(V data) Adds a node
java.util.HashSet<Graph.Edge>	BFT(Graph.Node start) Breadth-first traversal of graph
void	check() Checks the consistency of the graph
java.util.HashSet<Graph.Edge>	DFT(Graph.Node start) Depth-first traversal of graph -- public interface
double[]	distances(Graph.Node start) Dijkstra's shortest-path algorithm to compute distances to nodes
java.util.HashSet<Graph.Node>	endpoints(java.util.HashSet<Graph.Edge> edges) Returns nodes that are endpoints of a list of edges
Graph.Edge	getEdge(int i) Accessor for edges
Graph.Edge	getEdgeRef(Graph.Node head, Graph.Node tail) Accessor for specific edge
Graph.Node	getNode(int i) Accessor for nodes
int	numEdges() Accessor for number of edges
int	numNodes() Accessor for number of nodes
java.util.HashSet<Graph.Node>	otherNodes(java.util.HashSet<Graph.Node> group) Returns nodes not on a given list
void	print() Prints a representation of the graph
void	removeEdge(Graph.Edge edge) Removes an edge
void	removeEdge(Graph.Node head, Graph.Node tail) Removes an edge
void	removeNode(Graph.Node node) Removes a node

Methods inherited from class java.lang.Object

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

Field Detail

nodes

protected java.util.LinkedList<Graph.Node> nodes

The list of vertices

edges

protected java.util.LinkedList<Graph.Edge> edges

The list of edges

Constructor Detail

Graph

public Graph()

Constructor initializes with empty node and edge lists

Method Detail

getNode

public Graph.Node getNode(int i)

Accessor for nodes

getEdge

public Graph.Edge getEdge(int i)

Accessor for edges

getEdgeRef

public Graph.Edge getEdgeRef(Graph.Node head,
                             Graph.Node tail)

Accessor for specific edge

numNodes

public int numNodes()

Accessor for number of nodes

numEdges

public int numEdges()

Accessor for number of edges

addNode

public Graph.Node addNode(V data)

Adds a node

addEdge

public Graph.Edge addEdge(E data,
                          Graph.Node head,
                          Graph.Node tail)

Adds an edge

removeNode

public void removeNode(Graph.Node node)

Removes a node

removeEdge

public void removeEdge(Graph.Edge edge)

Removes an edge

removeEdge

public void removeEdge(Graph.Node head,
                       Graph.Node tail)

Removes an edge

otherNodes

public java.util.HashSet<Graph.Node> otherNodes(java.util.HashSet<Graph.Node> group)

Returns nodes not on a given list

endpoints

public java.util.HashSet<Graph.Node> endpoints(java.util.HashSet<Graph.Edge> edges)

Returns nodes that are endpoints of a list of edges

BFT

public java.util.HashSet<Graph.Edge> BFT(Graph.Node start)

Breadth-first traversal of graph

DFT

public java.util.HashSet<Graph.Edge> DFT(Graph.Node start)

Depth-first traversal of graph -- public interface

distances

public double[] distances(Graph.Node start)

Dijkstra's shortest-path algorithm to compute distances to nodes

print

public void print()

Prints a representation of the graph

check

public void check()

Checks the consistency of the graph