The mathIT Library
A Java™ API for mathematics
org.mathIT.graphs

## Class WeightedGraph<V extends Vertible<V>>

• Type Parameters:
`V` - the type of the vertices of this graph
Direct Known Subclasses:
SocialNetwork

```public class WeightedGraph<V extends Vertible<V>>
extends Graph<V>```
This class represents a weighted directed graph as an array list of vertices. Each vertex of a graph of this class must be an instance of a class implementing the interface `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);
...
}
```
Version:
1.1
Author:
Andreas de Vries
• ### Field Summary

Fields
Modifier and Type Field and Description
`static DecimalFormat` `DF`
Decimal Format "#,##0.#####".
`double[][]` `dist`
Distance matrix filled by Floyd-Warshall algorithm.
`double[]` `distance`
Distance matrix filled by Bellman-Ford algorithm.
`static double` `INFINITY`
Constant representing the infinite weight.
`int[][]` `next`
Successor matrix filled by Floyd-Warshall algorithm.
`int[]` `pred`
Successor matrix filled by Bellman-Ford algorithm.
`protected double[][]` `weight`
Weight matrix. weight[i][j] is the distance from vertex i to vertex j.
• ### Fields inherited from class org.mathIT.graphs.Graph

`adjacency, modifiableHashimoto, numberOfEdges, relevance, SEPARATOR, undirected, vertices, weighted`
• ### Constructor Summary

Constructors
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.
• ### Method Summary

All Methods
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 all-pairs 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.
• ### Methods inherited from class org.mathIT.graphs.Graph

`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`
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait`
• ### Field Detail

• #### INFINITY

`public static final double INFINITY`
Constant representing the infinite weight.
Constant Field Values
• #### DF

`public static final DecimalFormat DF`
Decimal Format "#,##0.#####".
• #### weight

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

`public double[][] dist`
Distance matrix filled by Floyd-Warshall algorithm.
• #### next

`public int[][] next`
Successor matrix filled by Floyd-Warshall algorithm.
• #### distance

`public double[] distance`
Distance matrix filled by Bellman-Ford algorithm.
• #### pred

`public int[] pred`
Successor matrix filled by Bellman-Ford algorithm.
• ### Constructor Detail

• #### WeightedGraph

```public WeightedGraph(V[] vertices,
double[][] weight)```
Creates a graph from the specified array of vertices and the weight matrix. In particular, the adjacency list of each vertex is derived from the matrix. If two vertices `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!
Parameters:
`vertices` - array of the vertices forming this graph
`weight` - the weight matrix determing the weights of each edge of this graph
• #### WeightedGraph

```public WeightedGraph(boolean undirected,
V[] vertices,
double[][] weight)```
Creates a graph from the specified array of vertices and the weight matrix. In particular, the adjacency list of each vertex is derived from the matrix. If two vertices `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!
Parameters:
`undirected` - indicator whether this graph is undirected
`vertices` - array of the vertices forming this graph
`weight` - the weight matrix determing the weights of each edge of this graph
Throws:
`IllegalArgumentException` - if the weight matrix is not symmetric or if the number of vertices is inconsistent with the matrix size
• #### WeightedGraph

```public 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. If two vertices `vi` and `verticesj` 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!
Parameters:
`vertices` - array of the vertices forming this graph
`weight` - the weight matrix determing the weights of each edge of this graph
`arrayTemplate` - an array of the type of vertices. This array may be empty. It is necessary technically because generic array creation is prohibited in Java.
• #### WeightedGraph

```public WeightedGraph(V[] vertices,
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. In particular, the adjacency list of each vertex is constructed from the adjacency matrix. If two vertices `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!
Parameters:
`vertices` - array of the vertices forming this graph
`adjacency` - the adjacency matrix determining the adjacencies of each vertex of this graph
Throws:
`IllegalArgumentException` - if adjacency is not a square matrix or if the number of vertices does not equal the length of the adjacency matrix
• #### WeightedGraph

```public WeightedGraph(boolean undirected,
V[] vertices,
Creates a weighted graph from the specified array of vertices and the adjacency matrix, deriving a weight matrix where each edge has weight 1. In particular, the adjacency list of each vertex is constructed from the adjacency matrix. If two vertices `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!
Parameters:
`undirected` - flag indicating whether this graph is undirected
`vertices` - array of the vertices forming this graph
`adjacency` - the adjacency matrix determining the adjacencies of each vertex of this graph
Throws:
`IllegalArgumentException` - 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 symmetric
• ### Method Detail

• #### getWeight

`public double[][] getWeight()`
The weight matrix of this graph.
Returns:
the weight matrix of this graph
• #### floydWarshall

`public void floydWarshall()`
Finds all-pairs shortest paths in this graph. The method stores for each vertex in the matrices dist and pred.
• #### dijkstra

`public void dijkstra(int s)`
Finds shortest paths from source vertex v[s] to all other vertices of this graph. The method stores for each vertex individually its minimal distance to s and its predecessor on a shortest path.
Parameters:
`s` - index of the source vertex
Throws:
`IllegalArgumentException` - if there are negative weights
• #### bellmanFord

`public void bellmanFord(int source)`
Finds shortest paths from source vertex v[s] to all other vertices of this graph. The method stores for each vertex individually its minimal distance to s and its predecessor on a shortest path.

Running time T(n, e) = Θ(n e) where n denotes the number of vertices and e the number of edges.

Parameters:
`source` - index of the source vertex
Throws:
`IllegalArgumentException` - if the grapph contains negative cycles
• #### toCSV

`public StringBuilder toCSV()`
Returns a representation of this graph as a text in CSV format.
Overrides:
`toCSV` in class `Graph<V extends Vertible<V>>`
Returns:
a StringBuilder representation of this graph in CSV fomat
• #### toString

`public String toString()`
Returns a string representation of the object.
Overrides:
`toString` in class `Graph<V extends Vertible<V>>`
Returns:
a string representation of the object
• #### createWeightedGraph

`public static WeightedGraph<SimpleVertex> createWeightedGraph(double[][] weight)`
Creates a graph from the specified weight matrix. In particular, the adjacency list of each vertex is derived from the matrix. If two vertices `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`.
Parameters:
`weight` - the weight matrix determing the weights of each edge of this graph
Returns:
the graph specified by the weight matrix
• #### createWeightedGraphFromCSVFile

`public static WeightedGraph<SimpleVertex> createWeightedGraphFromCSVFile()`
Creates a weighted graph from a CSV file selected by a file chooser dialog. In particular, the adjacency list of each vertex is derived from the matrix. If two vertices `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`.
Returns:
the graph specified by the CSV file
• #### create

```public static WeightedGraph<SimpleVertex> create(JTable jTable)
throws NumberFormatException```
Creates a graph from the weight matrix specified by the input table. In particular, the adjacency list of each vertex is derived from the matrix. If two vertices `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`.
Parameters:
`jTable` - the weight matrix determing the weights of each edge of this graph
Returns:
the graph specified by the weight matrix
Throws:
`NumberFormatException`
• #### show

`public static void show(JTable tabelle)`