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

package com.example.portfolio3;

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

import java.util.*;

///  Matrix Graph:  weights are stored in a twodimensional array
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<>();

  /// foo
  private int numVertex; // maximum number of vertices

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

  /// foo
  /// @param v  vertex
  /// @return int
  private int getIndex(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 void insertEdge(Vertex v1,Vertex v2,int w){
    matrix[getIndex(v1)][getIndex(v2)] = w;
  }

  /// foo
  public 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 Collection<Edge> outEdge(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 Integer getWeight(Vertex v1,Vertex v2){
    // constant time operation
    return matrix[vertex2index.get(v1)][vertex2index.get(v2)];}
}