nick.graph
Class AdjacencyMatrixGraph<E>

java.lang.Object
  nick.graph.AdjacencyMatrixGraph<E>

Type Parameters:

E - The type for this class would typically be numerical (Integer or Double). In some applications it might be some other class, but it is important that those classes override both the hashCode() and equals() methods.

All Implemented Interfaces:

GraphInterface<E>

public class AdjacencyMatrixGraph<E>
extends java.lang.Object
implements GraphInterface<E>

Let G = (V, E) be a simple weighted graph. An adjacency matrix is implemented by this class using a symmetric |V| x |V| matrix. A non-zero or non-null value represents an edge with given weight from an from vertex at a given row_i and column_j . Because we are modeling a simple graph, self edges and parallel edges are not allowed. User specified matrices must be symmetric with regards to their dimensions and information. A minimal amount of information is kept about the graph. Edge names and Vertex values are ignored by this graph representation. The graph may be connected or disconnected.

See below graph for a basic example:

Adjacency matrix:

	A	B	C
A	0	2	6
B	2	0	4
C	6	4	0

Here is the source code to create the above graph:

Integer[][] matrix = new Integer[3][3];
AdjacencyMatrixGraph<Integer> amg = new AdjacencyMatrixGraph<Integer>(matrix);
amg.addVertex("A");
amg.addVertex("B");
amg.addVertex("C");
amg.addEdge("A", "B", 2);
amg.addEdge("A", "C", 6);
amg.addEdge("B", "C", 4);


This implementation requires a user to specify how many vertices are in the graph upon instantiation. Note that vertices must be added before edges can be added.

The advantage to using a matrix as the backing store are that you get constant O(1) look up time to see if an edge exists between two vertices. This implementation is more space efficient when the graph is dense (D > 0.5). For sparse graphs (D < 0.5) it is more space efficient to use a adjacency list implementation.

For undirected, simple graphs the graph density can be defined:

D = 2 * |E| / (|V| * |V| - 1)

This evaluates to 0.0 for graphs with no edges and 1.0 for complete graphs (K_n).

Version:

March 15, 2009

Author:

Nick Aschenbach

Constructor Summary

AdjacencyMatrixGraph(E[][] the_matrix)
Construct this object with a given class and size.

Method Summary

void	addEdge(java.lang.String vertex1, java.lang.String vertex2, E edge_value) Add an edge on the graph.
void	addEdge(java.lang.String vertex1, java.lang.String vertex2, E edge_value, java.lang.String edge_name) Add an edge on the graph.
void	addVertex(java.lang.String vertex_name) Add a vertex with a specified name.
void	addVertex(java.lang.String vertex_name, java.lang.Object vertex_value) Add a vertex with a specified name.
java.util.HashSet	edges()
java.lang.String	getAVertex()
java.util.HashSet	getEdges(java.lang.String vertex) Get all edges adjacent to a specified vertex.
java.util.HashSet	getNeighbors(java.lang.String vertex)
E[][]	graph()
java.lang.String	toString()
java.util.Set	vertices()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

AdjacencyMatrixGraph

public AdjacencyMatrixGraph(E[][] the_matrix)

Construct this object with a given class and size.

Parameters:

the_matrix - Create an n x n matrix with given size.

Method Detail

addEdge

public void addEdge(java.lang.String vertex1,
                    java.lang.String vertex2,
                    E edge_value)

Add an edge on the graph. A lookup is performed to determine positions in the matrix and then an edge_value is assigned. Adding an edge where an edge already exists simply replaces it. Multiple edges between two vertices is not allowed in a simple graph.

Specified by:

addEdge in interface GraphInterface<E>

Parameters:

vertex1 - The first edge to connect.

vertex2 - The second edge to connect.

edge_value - The value to assign to this edge.

addEdge

public void addEdge(java.lang.String vertex1,
                    java.lang.String vertex2,
                    E edge_value,
                    java.lang.String edge_name)

Add an edge on the graph. A lookup is performed to determine positions in the matrix and then an edge_value is assigned. Adding an edge where an edge already exists simply replaces it. Multiple edges between two vertices is not allowed in a simple graph.

Specified by:

addEdge in interface GraphInterface<E>

Parameters:

vertex1 - The first edge to connect.

vertex2 - The second edge to connect.

edge_value - The value to assign to this edge.

edge_name - The name to assign to this edge (ignored).

addVertex

public void addVertex(java.lang.String vertex_name)

Add a vertex with a specified name.

Specified by:

addVertex in interface GraphInterface<E>

Parameters:

vertex_name - The name to use for this vertex.

addVertex

public void addVertex(java.lang.String vertex_name,
                      java.lang.Object vertex_value)

Add a vertex with a specified name. The vertex value is ignored by this implementation.

Specified by:

addVertex in interface GraphInterface<E>

Parameters:

vertex_name - The name to use for this vertex.

vertex_value - The value that is ignored by this class.

edges

public java.util.HashSet edges()

Specified by:

edges in interface GraphInterface<E>

Returns:

Get the set of edges.

getEdges

public java.util.HashSet getEdges(java.lang.String vertex)

Get all edges adjacent to a specified vertex.

Specified by:

getEdges in interface GraphInterface<E>

Parameters:

vertex - The vertex to check.

Returns:

A HashSet of edges adjacent to the vertex.

getNeighbors

public java.util.HashSet getNeighbors(java.lang.String vertex)

Specified by:

getNeighbors in interface GraphInterface<E>

vertices

public java.util.Set vertices()

Specified by:

vertices in interface GraphInterface<E>

Returns:

Get the set of vertices.

graph

public E[][] graph()

Returns:

Get the matrix that represents this graph. Use mainly for testing purposes. Runs in constant time.

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

Returns:

A string representation of this object.

getAVertex

public java.lang.String getAVertex()

Specified by:

getAVertex in interface GraphInterface<E>

Returns:

Get a vertex from the graph. Used by utility methods.