de.aitools.aq.structure.graph
Class UndirectedHashGraph<V>

java.lang.Object
  de.aitools.aq.structure.graph.UndirectedHashGraph<V>

Type Parameters:

V - The vertices in this graph.

All Implemented Interfaces:

UndirectedGraph<V>, java.io.Serializable, java.lang.Cloneable, java.lang.Iterable<V>

public final class UndirectedHashGraph<V>
extends java.lang.Object
implements UndirectedGraph<V>

A general implementation for all kind of vertices. To provide fast access, each weight is of an edge is hold twice in the graph.

Version:

$Id: UndirectedHashGraph.java,v 1.3 2012/03/06 15:01:41 poma1006 Exp $

Author:

johannes.kiesel(/\t)uni-weimar.de

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from interface de.aitools.aq.structure.graph.UndirectedGraph

UndirectedGraph.Edge<V>

Field Summary

Fields inherited from interface de.aitools.aq.structure.graph.UndirectedGraph

DEFAULT_UNCONNECTED_WEIGHT

Constructor Summary

UndirectedHashGraph()
Create a new UndirectedHashGraph with default weight for unconnected vertices and default capacity.

UndirectedHashGraph(double unconnectedWeight, int initialCapacity)
Create a new UndirectedHashGraph.

Method Summary

boolean	addVertex(V vertex) Adds a vertex to the graph.
UndirectedHashGraph<V>	clone()
boolean	containsEdge(V vertexA, V vertexB) Check if there exists an edge in the graph connecting the two vertices given as parameters.
boolean	containsVertex(V vertex) Checks if given vertex is contained in the graph.
UndirectedGraph.Edge<V>	getEdge(V vertexA, V vertexB) Returns the Edge connecting the two vertices.
java.util.Iterator<? extends UndirectedGraph.Edge<V>>	getEdges() Returns an iterator over all edges of the graph.
java.util.Iterator<? extends UndirectedGraph.Edge<V>>	getEdgesConnectedTo(V vertex) Returns an iterator over all edges in the graph that are connected to given vertex
double	getEdgeWeight(V vertexA, V vertexB) Returns the weight of the edge connecting the two vertices.
double	getMass(V vertex) Returns the sum of the weights of all edges connected to given vertex.
int	getNumberOfEdges() Returns the number of edges.
int	getNumberOfEdgesConnectedTo(V vertex) Returns the number of edges connected to given vertex.
int	getNumberOfVertices() Returns the number of vertices.
java.util.Set<UndirectedGraph.Edge<V>>	getSetOfEdges()
java.util.Set<UndirectedGraph.Edge<V>>	getSetOfEdgesConnectedTo(V vertex)
java.util.Set<V>	getSetOfVertices()
java.util.Set<V>	getSetOfVerticesConnectedTo(V vertex)
double	getUnconnectedWeight() Returns the default weight for unconnected vertices.
java.util.Iterator<V>	getVertices() Returns an iterator over all current vertices of this graph.
java.util.Iterator<V>	getVerticesConnectedTo(V vertex) Returns an iterator over all vertices that are connected with given vertex at the moment of this call.
java.util.Iterator<V>	iterator()
double	removeEdge(V vertexA, V vertexB) Removes the edge determined by two vertices.
boolean	removeVertex(V vertex) Remove a vertex from the graph.
double	setEdgeWeight(V vertexA, V vertexB, double weight) Sets the weight of a edge determined by two vertices.
void	setUnconnectedWeight(double unconnectedWeight) Change the weight that is returned by getEdgeWeight(Object, Object) if the two vertices are not connected.

Methods inherited from class java.lang.Object

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

Constructor Detail

UndirectedHashGraph

public UndirectedHashGraph()

Create a new UndirectedHashGraph with default weight for unconnected vertices and default capacity.

See Also:

UndirectedHashGraph, UndirectedGraph, setUnconnectedWeight(double), UndirectedHashGraph(double, int)

UndirectedHashGraph

public UndirectedHashGraph(double unconnectedWeight,
                           int initialCapacity)

Create a new UndirectedHashGraph.

Parameters:

unconnectedWeight - the weight for unconnected vertices. Default is using UndirectedGraph#DEFAULT_UNCONNECTED_WEIGHT.

initialCapacity - the initial capacity of vertices (grows automatically), or a negative value to use a default value.

See Also:

UndirectedHashGraph, UndirectedGraph, UndirectedGraph.DEFAULT_UNCONNECTED_WEIGHT

Method Detail

getUnconnectedWeight

public double getUnconnectedWeight()

Description copied from interface: UndirectedGraph

Returns the default weight for unconnected vertices.

The method getEdgeWeight(Object, Object) returns a double value for any possible edge connecting two vertices in the graph. If an edge does not exist, the method will return this value.

Specified by:

getUnconnectedWeight in interface UndirectedGraph<V>

Returns:

a weight for not existing edges.

See Also:

UndirectedGraph.getEdgeWeight(Object, Object), UndirectedGraph.setUnconnectedWeight(double)

setUnconnectedWeight

public void setUnconnectedWeight(double unconnectedWeight)

Description copied from interface: UndirectedGraph

Change the weight that is returned by getEdgeWeight(Object, Object) if the two vertices are not connected. This will remove all edges that currently have unconnectedWeight as their weight.

Specified by:

setUnconnectedWeight in interface UndirectedGraph<V>

Parameters:

unconnectedWeight - the new weight for unconnected vertices.

See Also:

UndirectedGraph.getEdgeWeight(Object, Object), UndirectedGraph.getUnconnectedWeight()

getNumberOfVertices

public int getNumberOfVertices()

Description copied from interface: UndirectedGraph

Returns the number of vertices.

Specified by:

getNumberOfVertices in interface UndirectedGraph<V>

Returns:

the number of vertices in the graph.

getNumberOfEdges

public int getNumberOfEdges()

Description copied from interface: UndirectedGraph

Returns the number of edges.

Specified by:

getNumberOfEdges in interface UndirectedGraph<V>

Returns:

the number of edges in the graph.

getNumberOfEdgesConnectedTo

public int getNumberOfEdgesConnectedTo(V vertex)
                                throws java.lang.NullPointerException,
                                       java.util.NoSuchElementException

Description copied from interface: UndirectedGraph

Returns the number of edges connected to given vertex.

Specified by:

getNumberOfEdgesConnectedTo in interface UndirectedGraph<V>

Parameters:

vertex - which vertex to count edges of.

Returns:

the number of edges this vertex is connected with.

Throws:

java.lang.NullPointerException - if vertex is null.

java.util.NoSuchElementException - if the vertex is not part of the graph.

getVertices

public java.util.Iterator<V> getVertices()

Description copied from interface: UndirectedGraph

Returns an iterator over all current vertices of this graph. This is the same as calling iterator().

Specified by:

getVertices in interface UndirectedGraph<V>

Returns:

the iterator.

See Also:

Iterable.iterator(), UndirectedGraph.getNumberOfEdges()

getSetOfVertices

public java.util.Set<V> getSetOfVertices()

getVerticesConnectedTo

public java.util.Iterator<V> getVerticesConnectedTo(V vertex)
                                             throws java.lang.NullPointerException,
                                                    java.util.NoSuchElementException

Description copied from interface: UndirectedGraph

Returns an iterator over all vertices that are connected with given vertex at the moment of this call.

Specified by:

getVerticesConnectedTo in interface UndirectedGraph<V>

Parameters:

vertex - the vertex.

Returns:

the iterator.

Throws:

java.lang.NullPointerException - if vertex is null.

java.util.NoSuchElementException - if the vertex is not part of the graph.

See Also:

UndirectedGraph.getNumberOfEdges()

getSetOfVerticesConnectedTo

public java.util.Set<V> getSetOfVerticesConnectedTo(V vertex)
                                             throws java.lang.NullPointerException,
                                                    java.util.NoSuchElementException

Throws:

java.lang.NullPointerException

java.util.NoSuchElementException

getEdges

public java.util.Iterator<? extends UndirectedGraph.Edge<V>> getEdges()

Description copied from interface: UndirectedGraph

Returns an iterator over all edges of the graph. Each edge is only visited once.

Specified by:

getEdges in interface UndirectedGraph<V>

Returns:

the iterator.

See Also:

UndirectedGraph.getNumberOfEdges()

getSetOfEdges

public java.util.Set<UndirectedGraph.Edge<V>> getSetOfEdges()

getEdgesConnectedTo

public java.util.Iterator<? extends UndirectedGraph.Edge<V>> getEdgesConnectedTo(V vertex)
                                                                          throws java.lang.NullPointerException,
                                                                                 java.util.NoSuchElementException

Description copied from interface: UndirectedGraph

Returns an iterator over all edges in the graph that are connected to given vertex

Specified by:

getEdgesConnectedTo in interface UndirectedGraph<V>

Parameters:

vertex - the vertex.

Returns:

the iterator.

Throws:

java.lang.NullPointerException - if the vertex is null.

java.util.NoSuchElementException - if the vertex is not part of the graph.

See Also:

UndirectedGraph.getNumberOfEdges()

getSetOfEdgesConnectedTo

public java.util.Set<UndirectedGraph.Edge<V>> getSetOfEdgesConnectedTo(V vertex)
                                                                throws java.lang.NullPointerException,
                                                                       java.util.NoSuchElementException

Throws:

java.lang.NullPointerException

java.util.NoSuchElementException

containsVertex

public boolean containsVertex(V vertex)
                       throws java.lang.NullPointerException

Description copied from interface: UndirectedGraph

Checks if given vertex is contained in the graph.

Specified by:

containsVertex in interface UndirectedGraph<V>

Parameters:

vertex - the vertex to look for.

Returns:

true if the vertex is contained. false otherwise.

Throws:

java.lang.NullPointerException - if vertex is null.

containsEdge

public boolean containsEdge(V vertexA,
                            V vertexB)
                     throws java.lang.NullPointerException,
                            java.util.NoSuchElementException

Description copied from interface: UndirectedGraph

Check if there exists an edge in the graph connecting the two vertices given as parameters.

Specified by:

containsEdge in interface UndirectedGraph<V>

Parameters:

vertexA - one vertex.

vertexB - the other vertex.

Returns:

true if both vertices are connected.

Throws:

java.lang.NullPointerException - if one of the vertices is null.

java.util.NoSuchElementException - if at least one of the vertices is not part of the graph.

getEdgeWeight

public double getEdgeWeight(V vertexA,
                            V vertexB)
                     throws java.lang.NullPointerException,
                            java.util.NoSuchElementException

Description copied from interface: UndirectedGraph

Returns the weight of the edge connecting the two vertices. This will return the same as getUnconnectedWeight() if the two vertices are not connected.

Specified by:

getEdgeWeight in interface UndirectedGraph<V>

Parameters:

vertexA - one vertex.

vertexB - the other vertex.

Returns:

the weight of the edge or the weight for unconnected vertices.

Throws:

java.lang.NullPointerException - if one of the vertices is null.

java.util.NoSuchElementException - if at least one of the vertices is not part of the graph.

See Also:

UndirectedGraph.containsEdge(Object, Object), UndirectedGraph.getEdge(Object, Object), UndirectedGraph.getUnconnectedWeight()

getEdge

public UndirectedGraph.Edge<V> getEdge(V vertexA,
                                       V vertexB)
                                throws java.lang.NullPointerException,
                                       java.util.NoSuchElementException

Description copied from interface: UndirectedGraph

Returns the Edge connecting the two vertices. The object will also be returned if there does not exists such an edge in the graph. Use edge.exists() to check.

Specified by:

getEdge in interface UndirectedGraph<V>

Parameters:

vertexA - one vertex.

vertexB - the other vertex.

Returns:

the edge.

Throws:

java.lang.NullPointerException - if one of the vertices is null.

java.util.NoSuchElementException - if at least one of the vertices is not part of the graph.

See Also:

UndirectedGraph.Edge, UndirectedGraph.containsEdge(Object, Object), UndirectedGraph.getEdgeWeight(Object, Object)

addVertex

public boolean addVertex(V vertex)
                  throws java.lang.NullPointerException

Description copied from interface: UndirectedGraph

Adds a vertex to the graph.

Specified by:

addVertex in interface UndirectedGraph<V>

Parameters:

vertex - the vertex to be added.

Returns:

true if the graph changed during this call. false if the graph already contained that vertex.

Throws:

java.lang.NullPointerException - if vertex is null.

removeVertex

public boolean removeVertex(V vertex)
                     throws java.lang.NullPointerException

Description copied from interface: UndirectedGraph

Remove a vertex from the graph.

Specified by:

removeVertex in interface UndirectedGraph<V>

Parameters:

vertex - the vertex to be removed.

Returns:

true if the graph changed during this call. false if the graph has not contained that vertex.

Throws:

java.lang.NullPointerException - if vertex is null.

getMass

public double getMass(V vertex)
               throws java.lang.NullPointerException,
                      java.util.NoSuchElementException

Description copied from interface: UndirectedGraph

Returns the sum of the weights of all edges connected to given vertex.

Specified by:

getMass in interface UndirectedGraph<V>

Parameters:

vertex - the vertex.

Returns:

the mass.

Throws:

java.lang.NullPointerException - if vertex is null.

java.util.NoSuchElementException - if the vertex is not part of the graph.

setEdgeWeight

public double setEdgeWeight(V vertexA,
                            V vertexB,
                            double weight)
                     throws java.lang.NullPointerException,
                            java.util.NoSuchElementException

Description copied from interface: UndirectedGraph

Sets the weight of a edge determined by two vertices. If the new weight is the value returned by getUnconnectedWeight(), this is be the same as calling removeEdge(Object, Object).

The old weight of the edge is returned, which may be the same as getUnconnectedWeight(), if the edge had not existed.

Specified by:

setEdgeWeight in interface UndirectedGraph<V>

Parameters:

vertexA - one vertex of the edge.

vertexB - the other vertex of the edge.

weight - the new weight of the edge.

Returns:

the value that would have been returned by a call to getEdgeWeight(Object, Object) directly before this call.

Throws:

java.lang.NullPointerException - if at least one vertex is null.

java.util.NoSuchElementException - if at least one of the two vertices is not a part of the graph.

See Also:

UndirectedGraph.containsVertex(Object), UndirectedGraph.getUnconnectedWeight(), UndirectedGraph.getEdgeWeight(Object, Object), UndirectedGraph.removeEdge(Object, Object)

removeEdge

public double removeEdge(V vertexA,
                         V vertexB)
                  throws java.lang.NullPointerException,
                         java.util.NoSuchElementException

Description copied from interface: UndirectedGraph

Removes the edge determined by two vertices. The old weight of the edge is returned, which may be the value returned by getUnconnectedWeight() if the edge had not existed (in which case nothing has happened).

Specified by:

removeEdge in interface UndirectedGraph<V>

Parameters:

vertexA - one vertex of the edge.

vertexB - the other vertex of the edge.

Returns:

the value that would have been returned by a call to getEdgeWeight(Object, Object) directly before this call.

Throws:

java.lang.NullPointerException - if at least one vertex is null.

java.util.NoSuchElementException - if at least one of the two vertices is not a part of the graph.

See Also:

UndirectedGraph.containsEdge(Object, Object), UndirectedGraph.containsVertex(Object), UndirectedGraph.getEdgeWeight(Object, Object), UndirectedGraph.getUnconnectedWeight(), UndirectedGraph.setEdgeWeight(Object, Object, double)

iterator

public java.util.Iterator<V> iterator()

Specified by:

iterator in interface java.lang.Iterable<V>

clone

public UndirectedHashGraph<V> clone()

Specified by:

clone in interface UndirectedGraph<V>

Overrides:

clone in class java.lang.Object