simplify path structure

1 files changed, 77 insertions, 0 deletions

diff --git a/src/com.example.portfolio3/com/example/portfolio3/MatrixGraph.java b/src/com.example.portfolio3/com/example/portfolio3/MatrixGraph.java
new file mode 100644
index 0000000..29005b7
--- /dev/null
+++ b/src/com.example.portfolio3/com/example/portfolio3/MatrixGraph.java
@@ -0,0 +1,77 @@
+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
+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<>();
+
+  /// foo
+  private int numVertex; // maximum number of vertices
+
+  /// foo
+  /// @param numVertex  maximum number of vertices allowed
+  public 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)];}
+}