de.aitools.aq.structure.graph
Class UndirectedLongHashGraph

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

All Implemented Interfaces:

UndirectedLongGraph, java.io.Serializable, java.lang.Cloneable

public final class UndirectedLongHashGraph
extends java.lang.Object
implements UndirectedLongGraph

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

Version:

$Id: UndirectedLongHashGraph.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.UndirectedLongGraph

UndirectedLongGraph.Edge

Field Summary

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

DEFAULT_UNCONNECTED_WEIGHT

Constructor Summary

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

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

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

Method Summary

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

UndirectedLongHashGraph

public UndirectedLongHashGraph()

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

See Also:

UndirectedLongGraph, UndirectedLongHashGraph, setUnconnectedWeight(double), UndirectedLongHashGraph(double, int)

UndirectedLongHashGraph

public UndirectedLongHashGraph(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:

UndirectedLongGraph, UndirectedLongHashGraph, setUnconnectedWeight(double), UndirectedLongHashGraph(double, int)

UndirectedLongHashGraph

public UndirectedLongHashGraph(double unconnectedWeight,
                               int initialCapacity)

Create a new graph.

Parameters:

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

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

See Also:

UndirectedLongGraph, UndirectedLongHashGraph, setUnconnectedWeight(double), UndirectedLongHashGraph(double, int), UndirectedLongGraph.DEFAULT_UNCONNECTED_WEIGHT

Method Detail

getUnconnectedWeight

public double getUnconnectedWeight()

Description copied from interface: UndirectedLongGraph

Returns the default weight for unconnected vertices.

The method getEdgeWeight(long, long) 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 UndirectedLongGraph

Returns:

a weight for not existing edges.

See Also:

UndirectedLongGraph.getEdgeWeight(long, long), UndirectedLongGraph.setUnconnectedWeight(double)

setUnconnectedWeight

public void setUnconnectedWeight(double unconnectedWeight)

Description copied from interface: UndirectedLongGraph

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

Specified by:

setUnconnectedWeight in interface UndirectedLongGraph

Parameters:

unconnectedWeight - the new weight for unconnected vertices.

See Also:

UndirectedLongGraph.getEdgeWeight(long, long), UndirectedLongGraph.getUnconnectedWeight()

getNumberOfVertices

public int getNumberOfVertices()

Description copied from interface: UndirectedLongGraph

Returns the number of vertices.

Specified by:

getNumberOfVertices in interface UndirectedLongGraph

Returns:

the number of vertices in the graph.

getNumberOfEdges

public int getNumberOfEdges()

Description copied from interface: UndirectedLongGraph

Returns the number of edges.

Specified by:

getNumberOfEdges in interface UndirectedLongGraph

Returns:

the number of edges in the graph.

getNumberOfEdgesConnectedTo

public int getNumberOfEdgesConnectedTo(long vertex)

Description copied from interface: UndirectedLongGraph

Returns the number of edges connected to given vertex.

Specified by:

getNumberOfEdgesConnectedTo in interface UndirectedLongGraph

Parameters:

vertex - which vertex to count edges of.

Returns:

the number of edges this vertex is connected with.

getVertices

public long[] getVertices()

Description copied from interface: UndirectedLongGraph

Returns an array containing all current vertices of this graph.

Specified by:

getVertices in interface UndirectedLongGraph

Returns:

the array.

See Also:

UndirectedLongGraph.getNumberOfVertices()

getVerticesConnectedTo

public long[] getVerticesConnectedTo(long vertex)

Description copied from interface: UndirectedLongGraph

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

Specified by:

getVerticesConnectedTo in interface UndirectedLongGraph

Parameters:

vertex - the vertex.

Returns:

the array.

See Also:

#getNumberOfEdges(long)

getMass

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

Description copied from interface: UndirectedLongGraph

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

Specified by:

getMass in interface UndirectedLongGraph

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 UndirectedLongGraph.Edge> getEdges()

Description copied from interface: UndirectedLongGraph

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

Specified by:

getEdges in interface UndirectedLongGraph

Returns:

the iterator.

See Also:

UndirectedLongGraph.getNumberOfEdges()

getEdgesConnectedTo

public java.util.Iterator<? extends UndirectedLongGraph.Edge> getEdgesConnectedTo(long vertex)

Description copied from interface: UndirectedLongGraph

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

Specified by:

getEdgesConnectedTo in interface UndirectedLongGraph

Parameters:

vertex - the vertex.

Returns:

the iterator.

See Also:

#getNumberOfEdges(long)

containsVertex

public boolean containsVertex(long vertex)

Description copied from interface: UndirectedLongGraph

Checks if given vertex is contained in the graph.

Specified by:

containsVertex in interface UndirectedLongGraph

Parameters:

vertex - the vertex to look for.

Returns:

true if the vertex is contained.

containsEdge

public boolean containsEdge(long vertexA,
                            long vertexB)

Description copied from interface: UndirectedLongGraph

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

Specified by:

containsEdge in interface UndirectedLongGraph

Parameters:

vertexA - one vertex.

vertexB - the other vertex.

Returns:

true if both vertices are connected.

getEdgeWeight

public double getEdgeWeight(long vertexA,
                            long vertexB)

Description copied from interface: UndirectedLongGraph

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 UndirectedLongGraph

Parameters:

vertexA - one vertex.

vertexB - the other vertex.

Returns:

the weight of the edge or getUnconnectedWeight().

See Also:

UndirectedLongGraph.containsEdge(long, long), UndirectedLongGraph.getEdge(long, long), UndirectedLongGraph.getUnconnectedWeight()

getEdge

public UndirectedLongGraph.Edge getEdge(long vertexA,
                                        long vertexB)

Description copied from interface: UndirectedLongGraph

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 UndirectedLongGraph

Parameters:

vertexA - one vertex.

vertexB - the other vertex.

Returns:

the edge.

See Also:

UndirectedLongGraph.Edge, UndirectedLongGraph.containsEdge(long, long), UndirectedLongGraph.getEdgeWeight(long, long), UndirectedLongGraph.Edge.exists()

addVertex

public boolean addVertex(long vertex)

Description copied from interface: UndirectedLongGraph

Adds a vertex to the graph.

Specified by:

addVertex in interface UndirectedLongGraph

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(long vertex)

Description copied from interface: UndirectedLongGraph

Removes a vertex from the graph.

Specified by:

removeVertex in interface UndirectedLongGraph

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(long vertexA,
                            long vertexB,
                            double weight)

Description copied from interface: UndirectedLongGraph

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

Specified by:

setEdgeWeight in interface UndirectedLongGraph

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

See Also:

UndirectedLongGraph.getUnconnectedWeight(), UndirectedLongGraph.getEdgeWeight(long, long), UndirectedLongGraph.removeEdge(long, long)

removeEdge

public double removeEdge(long vertexA,
                         long vertexB)

Description copied from interface: UndirectedLongGraph

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 UndirectedLongGraph

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

See Also:

UndirectedLongGraph.getUnconnectedWeight(), UndirectedLongGraph.getEdgeWeight(long, long), UndirectedLongGraph.setEdgeWeight(long, long, double)

clone

public UndirectedLongHashGraph clone()

Specified by:

clone in interface UndirectedLongGraph

Overrides:

clone in class java.lang.Object