Class AdjListsGraph

java.lang.Object
  Graph
      AdjListsGraph

public class AdjListsGraph

extends Graph

This is a graph implementation that uses adjacency lists to store edges. It contains one linked-list for every node i of the graph. The list for i contains one instance of AdjListElmnt for every node that is adjacent to i. In case the graph is directed, if there is an edge from node i to node j then there is a corresponding element in the adjacency lists of node i (only). In case the graph is undirected, if there is an edge between nodes i and j, then there is a corresponding element in the adjacency lists of *both* nodes i and j. The lists are not sorted; they contain the adjacent nodes in *reverse* order of edge insertion. In other words, for a directed graph, the node at the head of the list of some node i corresponds to the edge with source i that was added to the graph most recently (and has not been removed, yet). Similarly, for an undirected graph, the node at the head of the list of some node i corresponds to the edge with source or target i that was added to the graph most recently (and has not been removed, yet).

Field Summary

Fields inherited from class Graph

directed, nNodes

Constructor Summary

AdjListsGraph(int nodes, boolean directed)
The class constructor.

Method Summary

void	addEdge(int source, int target, double weight) This method adds an edge to the graph without checking whether the edge already exists.
boolean	addEdgeSafe(int source, int target, double weight) This method adds an edge to the graph as follows: first check whether the edge already exists in the graph; if it does not exist, then add the edge and return true; if it does exist, then do nothing and return false.
java.util.LinkedList	getAdjListOfNode(int i) This method returns the adjacency linked-list of node i.
void	removeAllEdges() This method removes all edges in the graph.
double	removeEdge(int source, int target) This method removes an edge as follows: if the graph contains an edge from source to target node, then this edge is removed and the weight of the edge is returned.
Graph	toAltGraphRepr(Graph g) This method copies this graph to graph g, if g has the same number of nodes, and both g and this graph are directed, or both are undirected.
java.lang.String	toString()
double	weightOfEdge(int source, int target) This method returns the weight of the edge from the source node to the target node, or +Infinity if no such edge exists.

Methods inherited from class Graph

addEdge, addEdgeSafe, getNNodes, isDirected

Methods inherited from class java.lang.Object

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

Constructor Detail

AdjListsGraph

public AdjListsGraph(int nodes,
                     boolean directed)

The class constructor. It initializes the number of nodes and the directed variable instances, and instantiates the array of adjacency lists so that each list is empty.

Parameters:

nodes - the number of nodes.

directed - true if the graph is be directed.

Method Detail

addEdge

public void addEdge(int source,
                    int target,
                    double weight)

Description copied from class: Graph

This method adds an edge to the graph without checking whether the edge already exists. This method can be used for efficiently adding edges to the graph, when we are certain that the edges we are to add do not already exist. It throws an IndexOutOfBoundsException if the source or target do not correspond to valid node numbers.

Specified by:

addEdge in class Graph

Parameters:

source - the source of the edge to be added to the graph.

target - the target of the edge to be added to the graph.

weight - the weight of the edge to be added to the graph.

addEdgeSafe

public boolean addEdgeSafe(int source,
                           int target,
                           double weight)

Description copied from class: Graph

This method adds an edge to the graph as follows: first check whether the edge already exists in the graph; if it does not exist, then add the edge and return true; if it does exist, then do nothing and return false. It throws an IndexOutOfBoundsException if the source or target do not correspond to valid node numbers.

Specified by:

addEdgeSafe in class Graph

Parameters:

source - the source of the edge to be added to the graph.

target - the target of the edge to be added to the graph.

weight - the weight of the edge to be added to the graph.

Returns:

true if the edge is successfully added to the graph, and false otherwise.

removeEdge

public double removeEdge(int source,
                         int target)

Description copied from class: Graph

This method removes an edge as follows: if the graph contains an edge from source to target node, then this edge is removed and the weight of the edge is returned. Otherwise, the graph is not modified and +Infinity is returned.

Specified by:

removeEdge in class Graph

Parameters:

source - the source node of the edge to remove.

target - the target node of the edge to remove.

Returns:

the weight of the edge from source to target, or +Infinity if no such edge exists.

removeAllEdges

public void removeAllEdges()

Description copied from class: Graph

This method removes all edges in the graph.

Specified by:

removeAllEdges in class Graph

weightOfEdge

public double weightOfEdge(int source,
                           int target)

Description copied from class: Graph

This method returns the weight of the edge from the source node to the target node, or +Infinity if no such edge exists.

Specified by:

weightOfEdge in class Graph

Parameters:

source - the source node of the edge.

target - the target node of the edge.

Returns:

the weight of the edge from source to target, or +Infinity if no such edge exists.

toString

public java.lang.String toString()

toAltGraphRepr

public Graph toAltGraphRepr(Graph g)

Description copied from class: Graph

This method copies this graph to graph g, if g has the same number of nodes, and both g and this graph are directed, or both are undirected. Otherwise, it does nothing. g may be using a different internal representation than this graph. For efficiency sake, this method should use only the unsafe version of the edge addition method (of g). So, in the implementation of the method when we construct an (undirected) graph g by adding edges, we should make sure we do not add the same edge twice.

Specified by:

toAltGraphRepr in class Graph

Parameters:

g - the graph to copy this graph to.

Returns:

graph g

getAdjListOfNode

public java.util.LinkedList getAdjListOfNode(int i)

This method returns the adjacency linked-list of node i.

Parameters:

i - node

Returns:

the adjacency linked-list of i