de.aitools.aq.structure.graph
Class UndirectedIntHashGraph

java.lang.Object
  de.aitools.aq.structure.graph.UndirectedIntHashGraph

All Implemented Interfaces:

UndirectedIntGraph, java.io.Serializable, java.lang.Cloneable

public final class UndirectedIntHashGraph
extends java.lang.Object
implements UndirectedIntGraph

A general implementation for int vertices. Each weight is stored only once in the graph.

Version:

$Id: UndirectedIntHashGraph.java,v 1.2 2011/10/24 16:51:39 dogu3912 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.UndirectedIntGraph

UndirectedIntGraph.Edge

Field Summary

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

DEFAULT_UNCONNECTED_WEIGHT

Constructor Summary

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

UndirectedIntHashGraph(double unconnectedWeight, int initialCapacity)
Create a new graph.

UndirectedIntHashGraph(int initialCapacity)
Create a new graph with default weight for unconnected vertices.

Method Summary

boolean	addVertex(int vertex) Adds a vertex to the graph.
UndirectedIntHashGraph	clone()
boolean	containsEdge(int vertexA, int vertexB) Checks if there exists an edge in the graph connecting the two vertices given as parameters.
boolean	containsVertex(int vertex) Checks if given vertex is contained in the graph.
UndirectedIntGraph.Edge	getEdge(int vertexA, int vertexB) Returns the Edge connecting the two vertices.
java.util.Iterator<? extends UndirectedIntGraph.Edge>	getEdges() Returns an iterator over all edges of the graph.
java.util.Iterator<? extends UndirectedIntGraph.Edge>	getEdgesConnectedTo(int vertex) Returns an iterator over all edges in the graph to which given vertex is connected to.
double	getEdgeWeight(int vertexA, int vertexB) Returns the weight of the edge connecting the two vertices.
double	getMass(int vertex) Returns the sum of the weights of all edges connected to given vertex.
int	getNumberOfEdges() Returns the number of edges.
int	getNumberOfEdgesConnectedTo(int 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.
int[]	getVertices() Returns an array containing all current vertices of this graph.
int[]	getVerticesConnectedTo(int vertex) Returns an array containing all vertices that are connected with given vertex at the moment of this call.
double	removeEdge(int vertexA, int vertexB) Removes an edge determined by two vertices.
boolean	removeVertex(int vertex) Removes a vertex from the graph.
double	setEdgeWeight(int vertexA, int 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(int, int) 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

UndirectedIntHashGraph

public UndirectedIntHashGraph()

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

See Also:

UndirectedIntGraph, UndirectedIntHashGraph, setUnconnectedWeight(double), UndirectedIntHashGraph(double, int)

UndirectedIntHashGraph

public UndirectedIntHashGraph(int initialCapacity)

Create a new graph with default weight for unconnected vertices.

Parameters:

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

See Also:

UndirectedIntGraph, UndirectedIntHashGraph, setUnconnectedWeight(double), UndirectedIntHashGraph(double, int)

UndirectedIntHashGraph

public UndirectedIntHashGraph(double unconnectedWeight,
                              int initialCapacity)

Create a new graph.

Parameters:

unconnectedWeight - The weight for unconnected vertices. Default is UndirectedIntGraph.DEFAULT_UNCONNECTED_WEIGHT.

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

See Also:

UndirectedIntGraph, UndirectedIntHashGraph, setUnconnectedWeight(double), UndirectedIntHashGraph(double, int), UndirectedIntGraph.DEFAULT_UNCONNECTED_WEIGHT

Method Detail

getUnconnectedWeight

public double getUnconnectedWeight()

Description copied from interface: UndirectedIntGraph

Returns the default weight for unconnected vertices.

The method getEdgeWeight(int, int) 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 UndirectedIntGraph

Returns:

a weight for not existing edges.

See Also:

UndirectedIntGraph.getEdgeWeight(int, int), UndirectedIntGraph.setUnconnectedWeight(double)

setUnconnectedWeight

public void setUnconnectedWeight(double unconnectedWeight)

Description copied from interface: UndirectedIntGraph

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

Specified by:

setUnconnectedWeight in interface UndirectedIntGraph

Parameters:

unconnectedWeight - the new weight for unconnected vertices.

See Also:

UndirectedIntGraph.getEdgeWeight(int, int), UndirectedIntGraph.getUnconnectedWeight()

getNumberOfVertices

public int getNumberOfVertices()

Description copied from interface: UndirectedIntGraph

Returns the number of vertices.

Specified by:

getNumberOfVertices in interface UndirectedIntGraph

Returns:

the number of vertices in the graph.

getNumberOfEdges

public int getNumberOfEdges()

Description copied from interface: UndirectedIntGraph

Returns the number of edges.

Specified by:

getNumberOfEdges in interface UndirectedIntGraph

Returns:

the number of edges in the graph.

getNumberOfEdgesConnectedTo

public int getNumberOfEdgesConnectedTo(int vertex)

Description copied from interface: UndirectedIntGraph

Returns the number of edges connected to given vertex.

Specified by:

getNumberOfEdgesConnectedTo in interface UndirectedIntGraph

Parameters:

vertex - which vertex to count edges of.

Returns:

the number of edges this vertex is connected with.

getVertices

public int[] getVertices()

Description copied from interface: UndirectedIntGraph

Returns an array containing all current vertices of this graph.

Specified by:

getVertices in interface UndirectedIntGraph

Returns:

the array.

See Also:

UndirectedIntGraph.getNumberOfVertices()

getVerticesConnectedTo

public int[] getVerticesConnectedTo(int vertex)

Description copied from interface: UndirectedIntGraph

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

Specified by:

getVerticesConnectedTo in interface UndirectedIntGraph

Parameters:

vertex - the vertex.

Returns:

the array.

See Also:

#getNumberOfEdges(int)

getMass

public double getMass(int vertex)
               throws java.util.NoSuchElementException

Description copied from interface: UndirectedIntGraph

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

Specified by:

getMass in interface UndirectedIntGraph

Parameters:

vertex - the vertex.

Returns:

the mass.

Throws:

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

getEdges

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

Description copied from interface: UndirectedIntGraph

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

Specified by:

getEdges in interface UndirectedIntGraph

Returns:

the iterator.

See Also:

UndirectedIntGraph.getNumberOfEdges()

getEdgesConnectedTo

public java.util.Iterator<? extends UndirectedIntGraph.Edge> getEdgesConnectedTo(int vertex)

Description copied from interface: UndirectedIntGraph

Returns an iterator over all edges in the graph to which given vertex is connected to.

Specified by:

getEdgesConnectedTo in interface UndirectedIntGraph

Parameters:

vertex - the vertex.

Returns:

the iterator.

See Also:

#getNumberOfEdges(int)

containsVertex

public boolean containsVertex(int vertex)

Description copied from interface: UndirectedIntGraph

Checks if given vertex is contained in the graph.

Specified by:

containsVertex in interface UndirectedIntGraph

Parameters:

vertex - the vertex to look for.

Returns:

true if the vertex is contained.

containsEdge

public boolean containsEdge(int vertexA,
                            int vertexB)

Description copied from interface: UndirectedIntGraph

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

Specified by:

containsEdge in interface UndirectedIntGraph

Parameters:

vertexA - one vertex.

vertexB - the other vertex.

Returns:

true if both vertices are connected.

getEdgeWeight

public double getEdgeWeight(int vertexA,
                            int vertexB)

Description copied from interface: UndirectedIntGraph

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 UndirectedIntGraph

Parameters:

vertexA - one vertex.

vertexB - the other vertex.

Returns:

the weight of the edge or getUnconnectedWeight().

See Also:

UndirectedIntGraph.containsEdge(int, int), UndirectedIntGraph.getEdge(int, int), UndirectedIntGraph.getUnconnectedWeight()

getEdge

public UndirectedIntGraph.Edge getEdge(int vertexA,
                                       int vertexB)

Description copied from interface: UndirectedIntGraph

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 UndirectedIntGraph

Parameters:

vertexA - one vertex.

vertexB - the other vertex.

Returns:

the edge.

See Also:

UndirectedIntGraph.Edge, UndirectedIntGraph.containsEdge(int, int), UndirectedIntGraph.getEdgeWeight(int, int), UndirectedIntGraph.Edge.exists()

addVertex

public boolean addVertex(int vertex)

Description copied from interface: UndirectedIntGraph

Adds a vertex to the graph.

Specified by:

addVertex in interface UndirectedIntGraph

Parameters:

vertex - the vertex to be added.

Returns:

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

removeVertex

public boolean removeVertex(int vertex)

Description copied from interface: UndirectedIntGraph

Removes a vertex from the graph.

Specified by:

removeVertex in interface UndirectedIntGraph

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.

setEdgeWeight

public double setEdgeWeight(int vertexA,
                            int vertexB,
                            double weight)

Description copied from interface: UndirectedIntGraph

Sets the weight of a edge determined by two vertices. If the new weight is getUnconnectedWeight(), this should be the same as calling removeEdge(int, int). The old weight of the edge is returned, which may be getUnconnectedWeight() if the edge had not existed.

Specified by:

setEdgeWeight in interface UndirectedIntGraph

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(int, int) directly before this call.

See Also:

UndirectedIntGraph.getUnconnectedWeight(), UndirectedIntGraph.getEdgeWeight(int, int), UndirectedIntGraph.removeEdge(int, int)

removeEdge

public double removeEdge(int vertexA,
                         int vertexB)

Description copied from interface: UndirectedIntGraph

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

Specified by:

removeEdge in interface UndirectedIntGraph

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(int, int) directly before this call.

See Also:

UndirectedIntGraph.getUnconnectedWeight(), UndirectedIntGraph.getEdgeWeight(int, int), UndirectedIntGraph.setEdgeWeight(int, int, double)

clone

public UndirectedIntHashGraph clone()

Specified by:

clone in interface UndirectedIntGraph

Overrides:

clone in class java.lang.Object