Class Graph

java.lang.Object
  Graph

Direct Known Subclasses:

AdjListsGraph, ListOfEdgesGraph

public abstract class Graph

extends java.lang.Object

This abstract class defines a set of variables and implements some methods that are common in every implementation of a graph object. It also specifies the minimum interface that a graph implementation should support. Each graph is described by the number of its nodes, the fact whether it is directed or undirected, and the set of its weighted edges. The number of nodes and the directed/undirected property are determined when the graph is instantiated, and do not change during the lifetime of the graph. The nodes of the graph are labeled by integers 0,1,..,(n-1), where n is the number of nodes. The set of edges of a graph is not fixed. Initially, a graph contains no edges at all. A graph implementation should support methods for inserting and removing edges. No self edges or multi-edges (i.e., from the same source to the same target node) are allowed.

Field Summary

protected boolean	directed True if the edges are directed.
protected int	nNodes The number of nodes of the graph.

Constructor Summary

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

Method Summary

void	addEdge(Edge e) This is an alternative method prototype for unsafe edge addition, when the edge is given as an object.
abstract 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(Edge e) This is an alternative method prototype for safe edge addition, when the edge is given as an object.
abstract 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.
int	getNNodes()
boolean	isDirected()
abstract void	removeAllEdges() This method removes all edges in the graph.
abstract 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.
abstract 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.
abstract 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 java.lang.Object

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

Field Detail

nNodes

protected int nNodes

The number of nodes of the graph.

directed

protected boolean directed

True if the edges are directed.

Constructor Detail

Graph

public Graph(int nodes,
             boolean directed)

The class constructor.

Method Detail

getNNodes

public int getNNodes()

Returns:

the number of nodes of the graph.

isDirected

public boolean isDirected()

Returns:

true if the graph is directed, and false otherwise.

addEdge

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

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.

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 abstract 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. It throws an IndexOutOfBoundsException if the source or target do not correspond to valid node numbers.

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.

addEdge

public void addEdge(Edge e)

This is an alternative method prototype for unsafe edge addition, when the edge is given as an object.

Parameters:

e - the edge to be added to the graph.

addEdgeSafe

public boolean addEdgeSafe(Edge e)

This is an alternative method prototype for safe edge addition, when the edge is given as an object.

Parameters:

e - the edge to be added.

Returns:

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

removeEdge

public abstract 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. Otherwise, the graph is not modified and +Infinity is returned.

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 abstract void removeAllEdges()

This method removes all edges in the graph.

weightOfEdge

public abstract 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.

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.

toAltGraphRepr

public abstract 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. 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.

Parameters:

g - the graph to copy this graph to.

Returns:

graph g