edu.berkeley.guir.lib.graphs
Class Graph

java.lang.Object
  |
  +--edu.berkeley.guir.lib.graphs.Graph

All Implemented Interfaces:

GraphConst, Serializable

public class Graph

extends Object

implements GraphConst, Serializable

A container for a graph.

This software is distributed under the Berkeley Software License.

 Revisions:  - GUIRLib-v1.0-1.0.0, Nov 06 1997, JH
               Created class
             - GUIRLib-v1.0-1.1.0, Feb 24 2000, JH
               Updated for JDK1.3RC1 to use the Collections
             - GUIRLib-v1.2-1.0.0, Jun 22 2000, JH
               Touched for GUIRLib release
             - GUIRLib-v1.3-1.0.0, Aug 11 2000, JH
               Touched for GUIRLib release
             - GUIRLib-v1.4-1.0.0, Aug 31 2000, JH
               Touched for GUIRLib release
 

Since:

1.3RC1

Version:

GUIRLib-v1.4-1.0.0, Aug 31 2000

Author:

Jason Hong ( jasonh@cs.berkeley.edu)

See Also:

Serialized Form

Field Summary

protected HashMap

mapNodes This is the table that contains the Nodes.

Fields inherited from interface edu.berkeley.guir.lib.graphs.GraphConst

DEFAULT_NUMBER_EDGES, DEFAULT_NUMBER_NODES, DEFAULT_PATH_SIZE, DEFAULT_WEIGHT, ERROR, TRUE

Constructor Summary

Graph()
Default constructor.

Method Summary

void	addDirectedEdge(Node nodeFrom, Node nodeTo) Add a directed edge with the default weight (GraphConst.DEFAULT_WEIGHT) from one node to another node.
void	addDirectedEdge(Node nodeFrom, Node nodeTo, float weight) Add a directed edge with the specified weight from one node to another node.
void	addDirectedEdge(String strNodeFrom, String strNodeTo) Add a directed edge with the default weight (GraphConst.DEFAULT_WEIGHT) from one node to another node.
void	addDirectedEdge(String strNodeFrom, String strNodeTo, float weight) Add a directed edge with the specified weight from one node to another node.
void	addNode(Node node) Add the Node if and only if it is not already in the Graph.
void	addNode(String strNodeName) Add a new Node if and only if it is not already in the Graph.
void	addUndirectedEdge(Node nodeFrom, Node nodeTo) Add an undirected edge with the default weight (GraphConst.DEFAULT_WEIGHT) from one node to another node.
void	addUndirectedEdge(Node nodeFrom, Node nodeTo, float weight) Add an undirected edge with the specified weight from one node to another node.
void	addUndirectedEdge(String strNodeFrom, String strNodeTo) Add an undirected edge with the default weight (GraphConst.DEFAULT_WEIGHT) from one node to another node.
void	addUndirectedEdge(String strNodeFrom, String strNodeTo, float weight) Add an undirected edge with the specified weight from one node to another node.
Node	getNode(String strNodeName) Get a Node from this Graph.
float	getWeight(Node nodeFrom, Node nodeTo) Get the weight of the edge between the from-node to the to-node.
float	getWeight(String strNodeFrom, String strNodeTo) Get the weight of the edge between the from-node to the to-node.
boolean	isAdjacent(Node nodeFrom, Node nodeTo) See if you can get from the from-node to the to-node.
boolean	isAdjacent(String strNodeFrom, String strNodeTo) See if you can get from the from-node to the to-node.
boolean	nodeExists(Node node) See if the given Node is in the Graph or not.
boolean	nodeExists(String strNodeName) See if the given Node is in the Graph or not.
int	numberOfEdges() Count the number of Edges in this Graph.
int	numberOfNodes() Count the number of Nodes in this Graph.
void	removeDirectedEdge(Node nodeFrom, Node nodeTo) Remove a directed edge from one node to another.
void	removeDirectedEdge(String strNodeFrom, String strNodeTo) Remove a directed edge from one node to another.
void	removeNode(Node node) Remove this Node from the Graph.
void	removeNode(String strNodeName) Remove this Node from the Graph.
void	removeUndirectedEdge(Node nodeFrom, Node nodeTo) Remove an undirected edge between two nodes.
void	removeUndirectedEdge(String strNodeFrom, String strNodeTo) Remove an undirected edge between two nodes.
static void	setDefaultNumberEdges(int edges) Sets the default number of edges in the Adjacency List of each Node.
static void	setDefaultNumberNodes(int nodes) Sets the default number of maximum nodes in the Graph.
String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

mapNodes

protected HashMap mapNodes

This is the table that contains the Nodes. Each Node itself contains its own adjacency list of inlinks and outlinks.

The key for this table is the name of the Node, and it refers to the actual Node object. (NodeName -> Node)

If this Graph is to be backed by a Database, then modify this variable.

Constructor Detail

Graph

public Graph()

Default constructor.

Method Detail

setDefaultNumberNodes

public static void setDefaultNumberNodes(int nodes)

Sets the default number of maximum nodes in the Graph. The graph will dynamically resize itself if necessary but it is more efficient this way.

Parameters:

iNumEdges - is the number of edges, and must be greater than the default number of edges. If it is less, then it will revert to the default number of edges. Ignores negative values.

setDefaultNumberEdges

public static void setDefaultNumberEdges(int edges)

Sets the default number of edges in the Adjacency List of each Node. The Adjacency List will dynamically resize itself if necessary but it is more efficient this way.

Parameters:

iNumEdges - is the number of edges, and must be greater than the default number of edges. If it is less, then it will revert to the default number of edges. Ignores negative values.

addNode

public void addNode(String strNodeName)

Add a new Node if and only if it is not already in the Graph. If it is already in the Graph, there will be no effect.

Parameters:

strNodeName - is the name of the Node to add to the Graph.

addNode

public void addNode(Node node)

Add the Node if and only if it is not already in the Graph. If it is already in the Graph, there will be no effect. If it is not, it will correctly add in the inlinks and outlinks of this Node to the Graph (creating those Nodes too if necessary).

Parameters:

node - is the Node to add to the Graph.

removeNode

public void removeNode(String strNodeName)

Remove this Node from the Graph. If it is not in the Graph, there will be no effect. The corresponding inlinks and outlinks of the appropriate Node will be updated.

Parameters:

strNodeName - is the name of the Node to remove from the Graph.

removeNode

public void removeNode(Node node)

Remove this Node from the Graph. If it is not in the Graph, there will be no effect. The corresponding inlinks and outlinks of the appropriate Node will be updated.

Parameters:

node - is the Node to remove from the Graph.

addDirectedEdge

public void addDirectedEdge(String strNodeFrom,
                            String strNodeTo,
                            float weight)

Add a directed edge with the specified weight from one node to another node.

If one of the Nodes is not in the Graph already, it will be added. It only adds a directed edge from the from-node to the to-node (storing the inlinks and outlinks for each respective Node correctly).

Parameters:

strNodeFrom - is the name of the source Node.

strNodeTo - is the name of the destination Node.

weight - is the weight of the Edge.

addDirectedEdge

public void addDirectedEdge(String strNodeFrom,
                            String strNodeTo)

Add a directed edge with the default weight (GraphConst.DEFAULT_WEIGHT) from one node to another node.

If one of the Nodes is not in the Graph already, it will be added. It only adds a directed edge from the from-node to the to-node (storing the inlinks and outlinks for each respective Node correctly).

Parameters:

strNodeFrom - is the name of the source Node.

strNodeTo - is the name of the destination Node.

See Also:

GraphConst

addDirectedEdge

public void addDirectedEdge(Node nodeFrom,
                            Node nodeTo)

Add a directed edge with the default weight (GraphConst.DEFAULT_WEIGHT) from one node to another node.

If one of the Nodes is not in the Graph already, it will be added (with the inlinks and outlinks correctly set up). It only adds a directed edge from the from-node to the to-node (storing the inlinks and outlinks for each respective Node correctly).

Parameters:

nodeFrom - is the source Node.

nodeTo - is the destination Node.

See Also:

GraphConst

addDirectedEdge

public void addDirectedEdge(Node nodeFrom,
                            Node nodeTo,
                            float weight)

Add a directed edge with the specified weight from one node to another node.

If one of the Nodes is not in the Graph already, it will be added (with the inlinks and outlinks correctly set up). It only adds a directed edge from the from-node to the to-node (storing the inlinks and outlinks for each respective Node correctly).

Parameters:

nodeFrom - is the source Node.

nodeTo - is the destination Node.

weight - is the weight of the Edge.

addUndirectedEdge

public void addUndirectedEdge(String strNodeFrom,
                              String strNodeTo,
                              float weight)

Add an undirected edge with the specified weight from one node to another node.

If one of the Nodes is not in the Graph already, it will be added. It adds an undirected edge from the from-node to the to-node (storing the inlinks and outlinks for each respective Node correctly).

Parameters:

strNodeFrom - is the name of the source Node.

strNodeTo - is the name of the destination Node.

weight - is the weight of the Edge.

addUndirectedEdge

public void addUndirectedEdge(String strNodeFrom,
                              String strNodeTo)

Add an undirected edge with the default weight (GraphConst.DEFAULT_WEIGHT) from one node to another node.

If one of the Nodes is not in the Graph already, it will be added. It adds an undirected edge from the from-node to the to-node (storing the inlinks and outlinks for each respective Node correctly).

Parameters:

strNodeFrom - is the name of the source Node.

strNodeTo - is the name of the destination Node.

See Also:

GraphConst

addUndirectedEdge

public void addUndirectedEdge(Node nodeFrom,
                              Node nodeTo)

Add an undirected edge with the default weight (GraphConst.DEFAULT_WEIGHT) from one node to another node.

If one of the Nodes is not in the Graph already, it will be added (with the inlinks and outlinks correctly set up). It adds an undirected edge from the from-node to the to-node (storing the inlinks and outlinks for each respective Node correctly).

Parameters:

nodeFrom - is the source Node.

nodeTo - is the destination Node.

See Also:

GraphConst

addUndirectedEdge

public void addUndirectedEdge(Node nodeFrom,
                              Node nodeTo,
                              float weight)

Add an undirected edge with the specified weight from one node to another node.

If one of the Nodes is not in the Graph already, it will be added (with the inlinks and outlinks correctly set up). It adds an undirected edge from the from-node to the to-node (storing the inlinks and outlinks for each respective Node correctly).

Parameters:

nodeFrom - is the source Node.

nodeTo - is the destination Node.

weight - is the weight of the Edge.

removeDirectedEdge

public void removeDirectedEdge(String strNodeFrom,
                               String strNodeTo)

Remove a directed edge from one node to another. If the edge does not exist, nothing will happen. If one of the Nodes does not exist, will still try to remove the edge (if for some strange reason it exists).

Parameters:

strNodeFrom - is the name of the source Node.

strNodeTo - is the name of the destination Node.

removeDirectedEdge

public void removeDirectedEdge(Node nodeFrom,
                               Node nodeTo)

Remove a directed edge from one node to another. If the nodes are not already in the Graph, they will be added. If the edge does not exist, nothing will happen. If one of the Nodes does not exist, will still try to remove the edge (if for some strange reason it exists).

Parameters:

nodeFrom - is the source Node.

nodeTo - is the destination Node.

removeUndirectedEdge

public void removeUndirectedEdge(String strNodeFrom,
                                 String strNodeTo)

Remove an undirected edge between two nodes. If the edge does not exist, nothing will happen.

Parameters:

strNodeFrom - is the name of the source Node.

strNodeTo - is the name of the destination Node.

removeUndirectedEdge

public void removeUndirectedEdge(Node nodeFrom,
                                 Node nodeTo)

Remove an undirected edge between two nodes. If the edge does not exist, nothing will happen.

Parameters:

nodeFrom - is the source Node.

nodeTo - is the destination Node.

getNode

public Node getNode(String strNodeName)

Get a Node from this Graph.

Parameters:

strNodeName - is the name of the Node to retrieve.

Returns:

the Node, or null if it does not exist.

nodeExists

public boolean nodeExists(String strNodeName)

See if the given Node is in the Graph or not.

Parameters:

strNodeName - is the name of the Node to check for.

Returns:

true if the given Node is in the Graph, false otherwise.

nodeExists

public boolean nodeExists(Node node)

See if the given Node is in the Graph or not.

Parameters:

node - is the Node to check for.

Returns:

true if the given Node is in the Graph, false otherwise.

isAdjacent

public boolean isAdjacent(String strNodeFrom,
                          String strNodeTo)

See if you can get from the from-node to the to-node.

Parameters:

strNodeFrom - is the name of the source Node.

strNodeTo - is the name of the destination Node.

Returns:

true if the two nodes are adjacent, false otherwise.

isAdjacent

public boolean isAdjacent(Node nodeFrom,
                          Node nodeTo)

See if you can get from the from-node to the to-node.

Parameters:

nodeFrom - is the source Node.

nodeTo - is the destination Node.

Returns:

true if the two nodes are adjacent, false otherwise.

getWeight

public float getWeight(String strNodeFrom,
                       String strNodeTo)

Get the weight of the edge between the from-node to the to-node.

Parameters:

strNodeFrom - is the name of the source Node.

strNodeTo - is the name of the destination Node.

Returns:

true if the two nodes are adjacent, false otherwise.

getWeight

public float getWeight(Node nodeFrom,
                       Node nodeTo)

Get the weight of the edge between the from-node to the to-node.

Parameters:

strNodeFrom - is the name of the source Node.

strNodeTo - is the name of the destination Node.

Returns:

true if the two nodes are adjacent, false otherwise.

numberOfNodes

public int numberOfNodes()

Count the number of Nodes in this Graph.

Returns:

An integer containing the number of Nodes in this Graph.

numberOfEdges

public int numberOfEdges()

Count the number of Edges in this Graph.

Returns:

An integer containing the number of Edges in this Graph.

toString

public String toString()

Overrides:

toString in class Object