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