org.mathIT.graphs

Class WeightedGraph<V extends Vertible<V>>

java.lang.Object

org.mathIT.graphs.Graph<V>

org.mathIT.graphs.WeightedGraph<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

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.

See Also:

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