Class ListOfEdgesGraph

java.lang.Object
  Graph
      ListOfEdgesGraph

public class ListOfEdgesGraph

extends Graph

This is a graph implementation that uses a linked-list of edges representation. The list of edges contains exactly one Edge object for every directed or undirected edge of the graph, if the graph is directed or undirected, respectively. Moreover, if the graph is undirected, the edges are stored such that in every Edge object, the source node is smaller than the target node. The list is not sorted; it contains the edges in reverse order of edge insertion, i.e., the node at the head of the list is the one that was added the most recently (and has not been removed, yet), and so on.

Field Summary

Fields inherited from class Graph

directed, nNodes

Constructor Summary

ListOfEdgesGraph(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	getEdges()
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

ListOfEdgesGraph

public ListOfEdgesGraph(int nodes,
                        boolean directed)

The class constructor. It initializes the number of nodes and the directed variable instances, and instantiates an empty linked-list of edges.

Parameters:

nodes - the number of nodes.

directed - true of the graph is 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

getEdges

public java.util.LinkedList getEdges()

Returns:

the linked-list of edges.