de.aitools.aq.structure.graph
Interface UndirectedGraph<V>

Type Parameters:

V - The vertices in this graph.

All Superinterfaces:

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

All Known Implementing Classes:

UndirectedHashGraph

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

An undirected weighted graph.

Version:

$Id: UndirectedGraph.java,v 1.1 2011/09/29 12:43:04 dogu3912 Exp $

Author:

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

Nested Class Summary

static interface

UndirectedGraph.Edge<V> A possible edge connecting two vertices of an underlying UndirectedGraph.

Field Summary

static double

DEFAULT_UNCONNECTED_WEIGHT The default weight for two not connected vertices.

Method Summary

boolean	addVertex(V vertex) Adds a vertex to the graph.
UndirectedGraph<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.
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.
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 interface java.lang.Iterable

iterator

Field Detail

DEFAULT_UNCONNECTED_WEIGHT

static final double DEFAULT_UNCONNECTED_WEIGHT

The default weight for two not connected vertices. If an edge was removed or simply not set yet, this should by default be it's weight.

See Also:

Constant Field Values

Method Detail

setUnconnectedWeight

void setUnconnectedWeight(double unconnectedWeight)

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.

Parameters:

unconnectedWeight - the new weight for unconnected vertices.

See Also:

getEdgeWeight(Object, Object), getUnconnectedWeight()

getUnconnectedWeight

double getUnconnectedWeight()

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.

Returns:

a weight for not existing edges.

See Also:

getEdgeWeight(Object, Object), setUnconnectedWeight(double)

getNumberOfVertices

int getNumberOfVertices()

Returns the number of vertices.

Returns:

the number of vertices in the graph.

getNumberOfEdges

int getNumberOfEdges()

Returns the number of edges.

Returns:

the number of edges in the graph.

getNumberOfEdgesConnectedTo

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

Returns the number of edges connected to given vertex.

Parameters:

vertex - which vertex to count edges of.

Returns:

the number of edges this vertex is connected with.

Throws:

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

java.lang.NullPointerException - if vertex is null.

addVertex

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

Adds a vertex to the graph.

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

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

Remove a vertex from the graph.

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.

getVertices

java.util.Iterator<V> getVertices()

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

Returns:

the iterator.

See Also:

Iterable.iterator(), getNumberOfEdges()

getVerticesConnectedTo

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

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

Parameters:

vertex - the vertex.

Returns:

the iterator.

Throws:

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

java.lang.NullPointerException - if vertex is null.

See Also:

getNumberOfEdges()

getMass

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

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

Parameters:

vertex - the vertex.

Returns:

the mass.

Throws:

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

java.lang.NullPointerException - if vertex is null.

setEdgeWeight

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

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.

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.util.NoSuchElementException - if at least one of the two vertices is not a part of the graph.

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

See Also:

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

removeEdge

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

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).

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.util.NoSuchElementException - if at least one of the two vertices is not a part of the graph.

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

See Also:

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

getEdges

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

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

Returns:

the iterator.

See Also:

getNumberOfEdges()

getEdgesConnectedTo

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

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

Parameters:

vertex - the vertex.

Returns:

the iterator.

Throws:

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

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

See Also:

getNumberOfEdges()

containsVertex

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

Checks if given vertex is contained in the graph.

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

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

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

Parameters:

vertexA - one vertex.

vertexB - the other vertex.

Returns:

true if both vertices are connected.

Throws:

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

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

getEdgeWeight

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

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

Parameters:

vertexA - one vertex.

vertexB - the other vertex.

Returns:

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

Throws:

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

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

See Also:

containsEdge(Object, Object), getEdge(Object, Object), getUnconnectedWeight()

getEdge

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

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.

Parameters:

vertexA - one vertex.

vertexB - the other vertex.

Returns:

the edge.

Throws:

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

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

See Also:

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

clone

UndirectedGraph<V> clone()