path: root/src/com.example.portfolio3/com/example/portfolio3/MatrixGraph.java

package com.example.portfolio3;

// origin: <https://moodle.ruc.dk/course/section.php?id=211877>

import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/// Matrix Graph: weights are stored in a twodimensional array
public class MatrixGraph extends AbstractGraph {

    /// foo
    private Integer[][] matrix = null; // made in constructor

    /// foo
    // We must be able to map vertices to index in matrix and back again
    private Vertex[] index2vertex; // made in constructor

    /// foo
    private Map<Vertex, Integer> vertex2index = new HashMap<>();

    /// maximum number of vertices
    private int numVertex;

    /// foo
    ///
    /// @param numVertex  maximum number of vertices allowed
    public MatrixGraph(final int numVertex) {
        this.numVertex = numVertex;
        matrix = new Integer[numVertex][numVertex];
        index2vertex = new Vertex[numVertex];
    }

    /// foo
    ///
    /// @param v  vertex
    /// @return int
    private int getIndex(final Vertex v) {
        if (vertex2index.containsKey(v)) {
            return vertex2index.get(v);
        }
        int index = vertex2index.size();
        if (index >= index2vertex.length) {
            throw new RuntimeException("Too many vertices in graph");
        }
        vertex2index.put(v, index);
        index2vertex[index] = v;

        return index;
    }

    /// foo
    public final void insertEdge(final Vertex v1, final Vertex v2, final int w) {
        matrix[getIndex(v1)][getIndex(v2)] = w;
    }

    /// foo
    public final Collection<Edge> edges() {
        HashSet<Edge> edges = new HashSet<>();
        for (int i = 0; i < numVertex; i++) {
            for (int j = 0; j < numVertex; j++) {
                Integer weight = matrix[i][j]; // may be null
                if (weight == null) {
                    continue;
                }
                edges.add(new Edge(index2vertex[i], index2vertex[j], weight));
            }
        }

        return edges;
    }

    /// foo
    public final Collection<Edge> outEdge(final Vertex v1) {
        HashSet<Edge> edges = new HashSet<>();
        int i = vertex2index.get(v1);
        for (int j = 0; j < numVertex; j++) {
            Integer weight = matrix[i][j]; // may be null
            if (weight == null) {
                continue;
            }
            edges.add(new Edge(v1, index2vertex[j], weight));
        }

        return edges;
    }

    /// foo
    public final Integer getWeight(final Vertex v1, final Vertex v2) {

        // constant time operation
        return matrix[vertex2index.get(v1)][vertex2index.get(v2)];
    }
}