V
 the type of the vertices of this graphpublic class WeightedGraph<V extends Vertible<V>> extends Graph<V>
Vertible
.
To create a weighted graph, a set of vertices implementing Vertible.java
along with the distance matrix is necessary.
It is important to note that the indices of the vertices depend uniquely on the
distance matrix weight
in the sense that the distance from
vertex i to vertex j is given by the matrix entry
weight[i][j]
.
Most easily, a vertex class is programmed by extending the vertex
class Vertex
.
For example, if a network of cities is to be established, a class
City
can be written such as
public class City extends Vertex<City> { ... }
and the network of cities as
public class CityNetwork extends WeightedGraph<City> { ... }
A more tedious, but also more flexible way is to implement instead the
interface Vertible
, e.g.,
public class City implements Vertible<City> { ... }
If one is interested only in a simple weighted graph consisting of vertices
with the minimal set of attributes, the static method
createWeightedGraph(double[][])
can be invoked,
public class MyGraph { double[][] matrix; ... WeightedGraph<SimpleVertex> graph = WeightedGraph.create(matrix); ... }
Modifier and Type  Field and Description 

static DecimalFormat 
DF
Decimal Format "#,##0.#####".

double[][] 
dist
Distance matrix filled by FloydWarshall algorithm.

double[] 
distance
Distance matrix filled by BellmanFord algorithm.

static double 
INFINITY
Constant representing the infinite weight.

int[][] 
next
Successor matrix filled by FloydWarshall algorithm.

int[] 
pred
Successor matrix filled by BellmanFord algorithm.

protected double[][] 
weight
Weight matrix. weight[i][j] is the distance from vertex i to vertex j.

adjacency, modifiableHashimoto, numberOfEdges, relevance, SEPARATOR, undirected, vertices, weighted
Constructor and Description 

WeightedGraph(ArrayList<V> vertices,
double[][] weight,
V[] arrayTemplate)
Creates a directed graph from the specified array list of vertices and the weight matrix;
the adjacency list of each vertex is derived from the weight matrix.

WeightedGraph(boolean undirected,
V[] vertices,
double[][] weight)
Creates a graph from the specified array of vertices and the weight matrix.

WeightedGraph(boolean undirected,
V[] vertices,
int[][] adjacency)
Creates a weighted graph from the specified array of vertices and the adjacency matrix,
deriving a weight matrix where each edge has weight 1.

WeightedGraph(V[] vertices,
double[][] weight)
Creates a graph from the specified array of vertices and the weight matrix.

WeightedGraph(V[] vertices,
int[][] adjacency)
Creates a directed weighted graph from the specified array of vertices and the adjacency matrix,
deriving a weight matrix where each edge has weight 1.

Modifier and Type  Method and Description 

void 
bellmanFord(int source)
Finds shortest paths from source vertex v[s] to all other vertices of this graph.

static WeightedGraph<SimpleVertex> 
create(JTable jTable)
Creates a graph from the weight matrix specified by the input table.

static WeightedGraph<SimpleVertex> 
createWeightedGraph(double[][] weight)
Creates a graph from the specified weight matrix.

static WeightedGraph<SimpleVertex> 
createWeightedGraphFromCSVFile()
Creates a weighted graph from a CSV file selected by a file chooser dialog.

void 
dijkstra(int s)
Finds shortest paths from source vertex v[s] to all other vertices of this graph.

void 
floydWarshall()
Finds allpairs shortest paths in this graph.

double[][] 
getWeight()
The weight matrix of this graph.

static void 
show(JTable tabelle) 
StringBuilder 
toCSV()
Returns a representation of this graph as a text in CSV format.

String 
toString()
Returns a string representation of the object.

breadthFirstSearch, collectEdges, computeHashimoto, computeNumberOfEdges, createGraph, createGraphFromCSVFile, depthFirstSearch, depthFirstSearch, detectClusters, detectClustersExactly, getAdjacency, getComponents, getCycles, getDegree, getDegree, getDegrees, getIndegree, getIndegree, getIndegrees, getModifiedHashimoto, getNumberOfEdges, getOutdegree, getOutdegree, getOutdegrees, getRelevance, getRelevanceClusters, getVertex, getVertices, hasCycles, isUndirected, laplacian, main, saveAsCSV, setUndirected, setVertices, subgraph, subgraph, toHTMLString, toJTable, topologicalSort
public static final double INFINITY
public static final DecimalFormat DF
protected double[][] weight
public double[][] dist
public int[][] next
public double[] distance
public int[] pred
public WeightedGraph(V[] vertices, double[][] weight)
vertices[i]
and vertices[j]
do not have an edge connecting them, the respective weight matrix entry
weight[i][j]
is expected to have the value zero or Double.POSITIVE_INFINITY
.
In each vertex, previously stored values for its index or its adjacency
list are always overwritten with the ones derived by the weight matrix!vertices
 array of the vertices forming this graphweight
 the weight matrix determing the weights of each edge of this graphpublic WeightedGraph(boolean undirected, V[] vertices, double[][] weight)
vertices[i]
and vertices[j]
do not have an edge connecting them, the respective weight matrix entry
weight[i][j]
is expected to have the value zero or Double.POSITIVE_INFINITY
.
In each vertex, previously stored values for its index or its adjacency
list are always overwritten with the ones derived by the weight matrix!undirected
 indicator whether this graph is undirectedvertices
 array of the vertices forming this graphweight
 the weight matrix determing the weights of each edge of this graphIllegalArgumentException
 if the weight matrix is not symmetric or if
the number of vertices is inconsistent with the matrix sizepublic WeightedGraph(ArrayList<V> vertices, double[][] weight, V[] arrayTemplate)
v_{i}
and vertices_{j}
do not have an edge connecting them, the respective weight matrix entry
weight[i][j]
is expected to have the value zero or Double.POSITIVE_INFINITY
.
In each vertex, previously stored values for its index or its adjacency
list are always overwritten with the ones derived by the weight matrix!vertices
 array of the vertices forming this graphweight
 the weight matrix determing the weights of each edge of this grapharrayTemplate
 an array of the type of vertices. This array may be empty.
It is necessary technically because generic array creation is prohibited in Java.public WeightedGraph(V[] vertices, int[][] adjacency)
vertices[i]
and vertices[j]
do not have an edge connecting them, the respective adjacency matrix entry
adjacency[i][j]
is expected to have the value 0.
In each vertex, previously stored values for its index or its adjacency
list are always overwritten with the ones derived by the adjacency matrix!vertices
 array of the vertices forming this graphadjacency
 the adjacency matrix determining the adjacencies of each vertex of this graphIllegalArgumentException
 if adjacency is not a square matrix or if
the number of vertices does not equal the length of the adjacency matrixpublic WeightedGraph(boolean undirected, V[] vertices, int[][] adjacency)
vertices[i]
and vertices[j]
do not have an edge connecting them, the respective adjacency matrix entry
adjacency[i][j]
is expected to have the value 0.
In each vertex, previously stored values for its index or its adjacency
list are always overwritten with the ones derived by the adjacency matrix!undirected
 flag indicating whether this graph is undirectedvertices
 array of the vertices forming this graphadjacency
 the adjacency matrix determining the adjacencies of each vertex of this graphIllegalArgumentException
 if adjacency is not a square matrix, or if
the number of vertices does not equal the length of the adjacency matrix,
or if the graph is undirected and the adjacency matrix is not symmetricpublic double[][] getWeight()
public void floydWarshall()
public void dijkstra(int s)
s
 index of the source vertexIllegalArgumentException
 if there are negative weightspublic void bellmanFord(int source)
Running time T(n, e) = Θ(n e) where n denotes the number of vertices and e the number of edges.
source
 index of the source vertexIllegalArgumentException
 if the grapph contains negative cyclespublic StringBuilder toCSV()
public String toString()
public static WeightedGraph<SimpleVertex> createWeightedGraph(double[][] weight)
vertices[i]
and vertices[j]
do not have an edge connecting them, the respective weight matrix entry
weight[i][j]
is expected to have the value
Double.POSITIVE_INFINITY
or 0.0
.
The vertices of the returned weighted graph are of the raw type
Vertex
.weight
 the weight matrix determing the weights of each edge of this graphpublic static WeightedGraph<SimpleVertex> createWeightedGraphFromCSVFile()
vertices[i]
and vertices[j]
do not have an edge connecting them, the respective adjacency matrix entry
adjacency[i][j]
is expected to have the value Double.POSITIVE_INFINITY
.
The vertices of the returned graph are of the raw type SimpleVertex
.public static WeightedGraph<SimpleVertex> create(JTable jTable) throws NumberFormatException
vertices[i]
and vertices[j]
do not have an edge connecting them, the respective weight matrix entry
weight[i][j]
is expected to have the value Double.POSITIVE_INFINITY
.
The vertices of the returned weighted graph are of the raw type
Vertex
.jTable
 the weight matrix determing the weights of each edge of this graphNumberFormatException
public static void show(JTable tabelle)