AdjacencyMatrixGraph.java

package graph_algorithms;

import data_structures.LinkedList;

public class AdjacencyMatrixGraph extends Graph {

 public final double[][] adjacencyMatrix;

 public AdjacencyMatrixGraph(int n, boolean directed) {
 super(n, directed);
 adjacencyMatrix = new double[n][n];
 for (int from = 0; from < adjacencyMatrix.length; ++from) {
 for (int to = 0; to < adjacencyMatrix[from].length; ++to) {
 if (from == to) {
 adjacencyMatrix[from][to] = 0;
 } else {
 adjacencyMatrix[from][to] = Double.POSITIVE_INFINITY;
 }
 }
 }
 }

 public static void main(String[] args) {
 // Examples:

 // Undirected
 Graph graph = new AdjacencyMatrixGraph(4, false);
 constructExampleGraph(graph);
 System.out.println(graph.containsEdge(1, 3)); // true
 System.out.println(graph.outEdges(3).size()); // 3
 System.out.println(graph.getVertexCount()); // 4
 System.out.println(graph.getEdgeCount()); // 5

 // Directed
 Graph digraph = new AdjacencyMatrixGraph(4, true);
 constructExampleGraph(digraph);
 System.out.println(digraph.containsEdge(1, 3)); // false
 System.out.println(digraph.outEdges(3).size()); // 2
 System.out.println(digraph.getVertexCount()); // 4
 System.out.println(digraph.getEdgeCount()); // 5
 }

 @Override
 public boolean containsEdge(int from, int to) {
 return adjacencyMatrix[from][to] != Double.POSITIVE_INFINITY;
 }

 @Override
 public LinkedList<Integer> outEdges(int vertex) {
 LinkedList<Integer> out = new LinkedList<>();
 for (int to = 0; to < adjacencyMatrix[vertex].length; ++to) {
 if (containsEdge(vertex, to)) {
 out.addLast(to);
 }
 }
 return out;
 }

 @Override
 protected void _addEdge(int from, int to, double cost) {
 adjacencyMatrix[from][to] = cost;
 }

 @Override
 public double cost(int from, int to) {
 return adjacencyMatrix[from][to];
 }

}