DataStructures
Class WeightedGraph

java.lang.Object
  DataStructures.WeightedGraph

All Implemented Interfaces:

java.lang.Iterable<WeightedGraph.Arc>

public class WeightedGraph
extends java.lang.Object
implements java.lang.Iterable<WeightedGraph.Arc>

A class implementing a weighted directed graph and shortest path algorithms for a positively weighted graph.

Graphs are created empty

   WeightedGraph g = new WeightedGraph();
 

after which weighted directed arcs can be added by

   g.addArc(tail, head, weight) 
 

where tail is the String label of the source node of the arc, head is the String label of the destination node of the arc and weight is an integer.

Weighted arcs can iterated over, for example by

   for (WeightedGraph.Arc a : g) {
       System.out.println(a);
   }
 

Nodes can be iterated over, for example by

   for (Iterator i = g.nodes(); i.hasNext();) {
       System.out.println(i.next());
   }
 

Graph descriptions can be read from and written to files.

Author:

Peter Williams

See Also:

WeightedGraph.Arc

Nested Class Summary

static class

WeightedGraph.Arc A public class returned by WeightedGraph.arcs().

Constructor Summary

WeightedGraph()
Constructs an empty weighted graph

Method Summary

void	addArc(java.lang.String tail, java.lang.String head, int weight) Adds a weighted directed arc into the graph.
void	addNode(java.lang.String label) Adds a node into the graph.
java.util.Iterator<WeightedGraph.Arc>	arcs() Returns an iteration over the arcs in the graph.
boolean	contains(java.lang.String label) Tests whether a node is present in the graph.
java.util.Iterator<WeightedGraph.Arc>	iterator() Returns the arcs iterator
java.util.Iterator<java.lang.String>	nodes() Returns an iteration over the nodes in the graph.
int	nrArcs() Returns the number of arcs in the graph
int	nrNodes() Returns the number of nodes in the graph
boolean	pathExists(java.lang.String origin, java.lang.String destination) Tests whether a path exists between two given nodes.
void	readGraphTxtFile(java.lang.String fileName) Reads a graph description from a text file.
java.util.Enumeration	shortestPath(java.lang.String origin, java.lang.String destination) Enumerates the nodes in a shortest path between two given nodes.
int	shortestPathLength(java.lang.String origin, java.lang.String destination) Returns the length of a shortest path between two given nodes.
void	writeGraphTxtFile(java.lang.String fileName) Writes a graph description to a text file.

Methods inherited from class java.lang.Object

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

Constructor Detail

WeightedGraph

public WeightedGraph()

Constructs an empty weighted graph

Method Detail

contains

public boolean contains(java.lang.String label)

Tests whether a node is present in the graph.

Parameters:

label - the label of the node to be searched for.

Returns:

true if the node is present, false otherwise

nrNodes

public int nrNodes()

Returns the number of nodes in the graph

Returns:

the number of nodes

nrArcs

public int nrArcs()

Returns the number of arcs in the graph

Returns:

the number of arcs

addNode

public void addNode(java.lang.String label)

Adds a node into the graph.

Parameters:

label - the label of the node

addArc

public void addArc(java.lang.String tail,
                   java.lang.String head,
                   int weight)

Adds a weighted directed arc into the graph.

Parameters:

tail - the label of the source node

head - the label of the destination node and

weight - the weight attached to the arc.

nodes

public java.util.Iterator<java.lang.String> nodes()

Returns an iteration over the nodes in the graph.

Returns:

an iteration over the nodes in the graph

arcs

public java.util.Iterator<WeightedGraph.Arc> arcs()

Returns an iteration over the arcs in the graph. The next method returns an element of the WeightedGraph.Arc class.

Returns:

an iteration over the arcs in the graph

See Also:

WeightedGraph.Arc

iterator

public java.util.Iterator<WeightedGraph.Arc> iterator()

Returns the arcs iterator

Specified by:

iterator in interface java.lang.Iterable<WeightedGraph.Arc>

Returns:

the iterator.

See Also:

arcs()

pathExists

public boolean pathExists(java.lang.String origin,
                          java.lang.String destination)

Tests whether a path exists between two given nodes.

Parameters:

origin - the node at which to begin,

destination - the node at which to end.

Returns:

true if a path exists, false otherwise.

Throws:

java.util.NoSuchElementException - if either node does not exist.

java.lang.ArithmeticException - if a negatively weighted arc is encountered in the search.

shortestPathLength

public int shortestPathLength(java.lang.String origin,
                              java.lang.String destination)

Returns the length of a shortest path between two given nodes.

Parameters:

origin - the node at which to begin,

destination - the node at which to end.

Returns:

the shortest path length.

Throws:

java.util.NoSuchElementException - if either node does not exist, or if there is no path between them.

java.lang.ArithmeticException - if a negatively weighted arc is encountered in the search.

shortestPath

public java.util.Enumeration shortestPath(java.lang.String origin,
                                          java.lang.String destination)

Enumerates the nodes in a shortest path between two given nodes.

Parameters:

origin - the node at which to begin,

destination - the node at which to end.

Returns:

the enumeration.

Throws:

java.util.NoSuchElementException - if either node does not exist, or if there is no path between them.

java.lang.ArithmeticException - if a negatively weighted arc is encountered in the search.

readGraphTxtFile

public void readGraphTxtFile(java.lang.String fileName)

Reads a graph description from a text file. Entries read from the file are added to the graph.

File entries must be of form

        T H W
 

where T and H are strings and W is an integer. Each entry represents a weighted arc where T is the tail or source node, H is the head or destination node and W is the weight.

All entries must be on separate lines. Empty lines are skipped.

writeGraphTxtFile

public void writeGraphTxtFile(java.lang.String fileName)

Writes a graph description to a text file.

Files are written in the same form in which readGraphTxtFile expects to read them.

Note: it is the applications's responsibility to protect files which ought not to be overwritten.