org.rollerjm.graph
Class AdjacencyMatrixGraph

java.lang.Object
  |
  +--org.rollerjm.graph.AdjacencyMatrixGraph

All Implemented Interfaces:

IGraph

public class AdjacencyMatrixGraph

extends java.lang.Object

implements IGraph

Title: graphs

Description: Interface which specifies a weighted oriented graph. All search algorithms and client classes use that Interface to deal with graphs. If the implementation changes, no change will be needed in the clients classes (that's the advantages of using Interfaces !).

Copyright: Copyright (c) 2002

Company:

Version:

1.0

Author:

Jean-Michel Garnier

Field Summary

private int[][]	adjacencyMatrix Adjacency Matrix AM, with AM[start][destination] = weight.
private int[][]	adjacencyMatrixInversed Adjacency Matrix inversed (mathematical meaning)
private int	indexCurrentVertex Current number of vertices contained in the graph
private java.lang.Object[]	objectsArray Array used to map the index used in the Adjacency Matrix and the object contained in a vertex I.e.
private java.util.HashMap	verticesMap Map used to map an object contained in a vertex and the index used in the Adjacency Matrix.
private int	verticesNumber number of vertices in the graph

Constructor Summary

AdjacencyMatrixGraph(int verticesNumber)

Method Summary

void	addEdge(java.lang.Object startVertex, java.lang.Object destinationVertex, int weight) add an new edge in the graph.
void	addVertex(java.lang.Object vertex) add a new vertex in the graph
boolean	edgeExist(java.lang.Object startVertex, java.lang.Object destinationVertex) Remove an edge to the graph
private java.util.ArrayList	getAdjacentsFromMatrix(java.lang.Object vertex, int[][] matrix) This method is used by getAdjacentVertices and getPredecessors
java.util.Iterator	getAdjacentVertices(java.lang.Object vertex)
int	getEdgeWeight(java.lang.Object startVertex, java.lang.Object destinationVertex)
int	getEdgeWeight(Path path)
java.util.Iterator	getPredecessors(java.lang.Object vertex)
private int	getVertexIndex(java.lang.Object vertex)
private java.lang.Object	getVertexObject(int index)
int	getVerticesNumber()
void	removeEdge(java.lang.Object startVertex, java.lang.Object destinationVertex) Remove an edge
boolean	vertexExist(java.lang.Object vertex)

Methods inherited from class java.lang.Object

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

Field Detail

verticesNumber

private int verticesNumber

number of vertices in the graph

verticesMap

private java.util.HashMap verticesMap

Map used to map an object contained in a vertex and the index used in the Adjacency Matrix. I.e. for the Graph A---B : int indexA = ((Integer) verticesMap(A)).intValue;

objectsArray

private java.lang.Object[] objectsArray

Array used to map the index used in the Adjacency Matrix and the object contained in a vertex I.e. for the Graph A--B : Object objectA = objectsArray[indexA];

indexCurrentVertex

private int indexCurrentVertex

Current number of vertices contained in the graph

adjacencyMatrix

private int[][] adjacencyMatrix

Adjacency Matrix AM, with AM[start][destination] = weight. If AM[start][destination] = 0, the path does not exist

adjacencyMatrixInversed

private int[][] adjacencyMatrixInversed

Adjacency Matrix inversed (mathematical meaning)

Constructor Detail

AdjacencyMatrixGraph

public AdjacencyMatrixGraph(int verticesNumber)

Method Detail

getVerticesNumber

public int getVerticesNumber()

Specified by:

getVerticesNumber in interface IGraph

Returns:

int the number of vertices in the graph

addVertex

public void addVertex(java.lang.Object vertex)

add a new vertex in the graph

Specified by:

addVertex in interface IGraph

Parameters:

vertex -

addEdge

public void addEdge(java.lang.Object startVertex,
                    java.lang.Object destinationVertex,
                    int weight)

add an new edge in the graph.

Specified by:

addEdge in interface IGraph

Parameters:

startVertex - should be a vertex in the Graph

destinationVertex - should be a vertex in the Graph

weight -

removeEdge

public void removeEdge(java.lang.Object startVertex,
                       java.lang.Object destinationVertex)

Remove an edge

Specified by:

removeEdge in interface IGraph

Parameters:

startVertex -

destinationVertex -

edgeExist

public boolean edgeExist(java.lang.Object startVertex,
                         java.lang.Object destinationVertex)

Remove an edge to the graph

Specified by:

edgeExist in interface IGraph

Parameters:

startVertex - should belong to the Graph

destinationVertex - should belong to the Graph

Returns:

boolean

vertexExist

public boolean vertexExist(java.lang.Object vertex)

Specified by:

vertexExist in interface IGraph

Parameters:

vertex -

Returns:

boolean true if the vertex belongs to the Graph

getEdgeWeight

public int getEdgeWeight(java.lang.Object startVertex,
                         java.lang.Object destinationVertex)

Specified by:

getEdgeWeight in interface IGraph

Parameters:

startVertex - should belong to the Graph

destinationVertex - should belong to the Graph

Returns:

int the weight (distance) of the edge. 0 if the edge does not exist

getEdgeWeight

public int getEdgeWeight(Path path)

Specified by:

getEdgeWeight in interface IGraph

Parameters:

path - list of vertices

Returns:

int the total weight (distance) of the path or 0 if the path does not exist

getAdjacentVertices

public java.util.Iterator getAdjacentVertices(java.lang.Object vertex)

Specified by:

getAdjacentVertices in interface IGraph

Parameters:

vertex - should belong to the Graph

Returns:

Iterator on the list of adjacent vertices of the param

getPredecessors

public java.util.Iterator getPredecessors(java.lang.Object vertex)

Specified by:

getPredecessors in interface IGraph

Parameters:

vertex - should belong to the Graph

Returns:

Iterator on the list of predecessor vertices of the param

getAdjacentsFromMatrix

private java.util.ArrayList getAdjacentsFromMatrix(java.lang.Object vertex,
                                                   int[][] matrix)

This method is used by getAdjacentVertices and getPredecessors

Parameters:

vertex -

matrix - Adjacency Matrix inversed or Adjacency Matrix

Returns:

ArrayList list of predecessor adjacent / vertices of the param

getVertexIndex

private int getVertexIndex(java.lang.Object vertex)

Parameters:

vertex -

Returns:

int the index used in the Adjacency Matrix

getVertexObject

private java.lang.Object getVertexObject(int index)

Parameters:

index - index used in the Adjacency Matrix

Returns:

Object return the object contained in the vertex mapped by the param