DataStructures
Class WeightedGraph

java.lang.Object
  |
  +--DataStructures.WeightedGraph

Direct Known Subclasses:

PositiveWeightedGraph

public class WeightedGraph

extends java.lang.Object

A class implementing a weighted directed graph.

Graphs are created empty, for example:

   WeightedGraph g = new WeightedGraph();
 

after which weighted directed arcs can be added by

   g.add(tail, head, weight) 
 

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

Graph descriptions can be read from and written to files.

Nodes and arcs can be enumerated using an iterator, e.g.

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

The remove method is implemented for arcs but not for nodes. The arcs iterator returns an object in the WeightedGraph.Arc class.

Author:

Peter Williams

See Also:

WeightedGraph.Arc

Inner Class Summary

static class	WeightedGraph.Arc A public class returned by the arcs() iteration over arcs.
protected class	WeightedGraph.Node
protected class	WeightedGraph.Tip

Field Summary

protected LookupTable	nodeMap
protected int	version

Constructor Summary

WeightedGraph()
Constructs an empty weighted graph

Method Summary

void	add(java.lang.Object tail, java.lang.Object head, int weight) Adds a weighted directed arc into the graph.
java.util.Iterator	arcs() Iterates over the arcs in the graph.
boolean	contains(java.lang.Object label) Tests whether a node is present in the graph.
java.util.Iterator	nodes() Iterates 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
void	readGraphTxtFile(java.lang.String fileName) Reads a graph description from the text file fileName.
void	writeGraphTxtFile(java.lang.String fileName) Writes a graph description to the text file fileName.

Methods inherited from class java.lang.Object

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

Field Detail

nodeMap

protected LookupTable nodeMap

version

protected int version

Constructor Detail

WeightedGraph

public WeightedGraph()

Constructs an empty weighted graph

Method Detail

contains

public boolean contains(java.lang.Object 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

add

public void add(java.lang.Object tail,
                java.lang.Object 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 nodes()

Iterates over the nodes in the graph.

Returns:

the iterator.

Throws:

java.util.NoSuchElementException - if the next method is called when there is no next element.

UnsupportedOperatonException - if the remove method is called.

arcs

public java.util.Iterator arcs()

Iterates over the arcs in the graph. The next method returns an object in the WeightedGraph.Arc class.

Returns:

the iterator.

See Also:

WeightedGraph.Arc

readGraphTxtFile

public void readGraphTxtFile(java.lang.String fileName)

Reads a graph description from the text file fileName. 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 the text file fileName.

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.