include code from course material

2 files changed, 444 insertions, 0 deletions

diff --git a/com/example/portfolio3/GraphAlgorithms.java b/com/example/portfolio3/GraphAlgorithms.java
new file mode 100644
index 0000000..fdf6def
--- /dev/null
+++ b/com/example/portfolio3/GraphAlgorithms.java
@@ -0,0 +1,263 @@
+import java.io.*;

+import java.util.*;

+

+public class GraphAlgorithms {

+  public static int pathLength(Collection<Edge> edges){

+    // Calculates the length of a path or any other collection of edes

+    // does not require the edges to form a path

+    return edges.stream().mapToInt(e-> e.weight()).sum();

+  }

+

+  public static boolean isPath(List<Edge> edges){

+    // checks whether a list of edges form a path so that

+    // the to-vertex in one edge is the from-vertex of the next

+    for(int i=1;i<edges.size();i++){

+      if(edges.get(i-1).to()!=edges.get(i).from())return false;

+    }

+    return true;

+  }

+

+  public static Integer pathLength(Graph g,List<Vertex> path){

+    //Calculates the length of a path vertices in a graph

+    // return null if vertices are not connected as a path

+    int length=0;

+    for(int i=1;i<path.size();i++){

+      Integer w=g.getWeight(path.get(i-1),path.get(i));

+      if(w==null)return null;

+      length+=w;

+    }

+    return length;

+  }

+

+  //------------------------------------------------------------

+  //

+  //  Comparators and sorting methods

+

+  static int cmpEdgeWeight(Edge e1,Edge e2) {

+    // Comparator of edges based on weight

+    // can be used for sorting a list of edges

+    int w1=e1.weight(),w2=e2.weight();

+    if(w1!=w2)return w1-w2;

+    if(e1.from()!=e2.from())return e1.from().name().compareTo(e2.from().name());

+    return e1.to().name().compareTo(e2.to().name());

+  }

+  static int cmpEdgeFrom(Edge e1,Edge e2) {

+    // Comparator of edges based on from-vertex

+    // can be used for sorting a list of edges

+    if(e1.from()!=e2.from())return e1.from().name().compareTo(e2.from().name());

+    int w1=e1.weight(),w2=e2.weight();

+    if(w1!=w2)return w1-w2;

+    return e1.to().name().compareTo(e2.to().name());

+  }

+  static int cmpEdgeTo(Edge e1,Edge e2) {

+    // Comparator of edges based on from-vertex

+    // can be used for sorting a list of edges

+    if(e1.to()!=e2.to())return e1.to().name().compareTo(e2.to().name());

+    if(e1.from()!=e2.from())return e1.from().name().compareTo(e2.from().name());

+    int w1=e1.weight(),w2=e2.weight();

+    return w1-w2;

+  }

+

+  static List<Edge> sortEdges(Collection<Edge> edges){

+    // sort a collection of edges based on their weights

+    ArrayList<Edge> list=new ArrayList<>(edges);

+    Collections.sort(list,GraphAlgorithms::cmpEdgeWeight);

+    return list;

+  }

+  static List<Edge> sortEdgesFrom(Collection<Edge> edges){

+    // sort a collection of edges based on from-vertex

+    ArrayList<Edge> list=new ArrayList<>(edges);

+    Collections.sort(list,GraphAlgorithms::cmpEdgeFrom);

+    return list;

+  }

+  static List<Edge> sortEdgesTo(Collection<Edge> edges){

+    // sort a collection of edges based on to-vertex

+    ArrayList<Edge> list=new ArrayList<>(edges);

+    Collections.sort(list,GraphAlgorithms::cmpEdgeTo);

+    return list;

+  }

+

+  static List<Vertex> sortVertex(Collection<Vertex> vertices){

+    // sort a collection of vertices based on their name

+    ArrayList<Vertex> list=new ArrayList<>(vertices);

+    Collections.sort(list,(Vertex v1,Vertex v2)-> v1.name().compareTo(v2.name()));

+    return list;

+  }

+

+  //------------------------------------------------------------

+  //

+  //  Algorithms for traverse and minimum spanning tree

+

+  public static Set<Vertex> visitBreadthFirst(Graph g,Vertex v){

+    // traverse a graph depth first from a given vertex

+    // return the set of visited vertices

+    HashSet<Vertex> thisLevel=new HashSet<>();

+    HashSet<Vertex> nextLevel=new HashSet<>();

+    HashSet<Vertex> visited=new HashSet<>();

+    thisLevel.add(v);

+    while(thisLevel.size()>0){

+      System.out.println("level "+thisLevel);

+      for(Vertex w:thisLevel){

+        //System.out.println("visited "+w);

+        visited.add(w);

+        Collection<Edge> outedge=g.outEdge(w);

+        if(outedge==null)continue;

+        for(Edge e: outedge){

+          if(visited.contains(e.to()))continue;

+          if(thisLevel.contains(e.to()))continue;

+          nextLevel.add(e.to());

+        }

+      }

+      thisLevel=nextLevel;

+      nextLevel=new HashSet<Vertex>();

+    }

+    return visited;

+  }

+

+  public static Set<Vertex> visitDepthFirst(Graph g,Vertex v){

+    // traverse a graph depth first from a given vertex

+    // return the set of visited vertices

+    HashSet<Vertex> visit=new HashSet<>();

+    visitDepthFirst(g, v,visit);

+    return visit;

+  }

+

+  private static void visitDepthFirst(Graph g,Vertex v,Set<Vertex> visited){

+    if(visited.contains(v))return;

+    //System.out.println("visited "+v);

+    visited.add(v);

+    for(Edge e: g.outEdge(v))

+      visitDepthFirst(g,e.to(),visited);

+  }

+

+  public static Set<Edge> minimumSpanningTree(Graph g){

+    // an implementation of Prim's algorithm

+    // naive implementation without priorityqueue

+    Collection<Edge> edges=g.edges();

+    HashSet<Edge> mst=new HashSet<>();

+    HashSet<Vertex> frontier=new HashSet<>();

+    for(Edge e:edges){frontier.add(e.from());break;}

+    while(true) {

+      Edge nearest = null;

+      for (Edge e : edges) {

+        if (!frontier.contains(e.from())) continue;

+        if (frontier.contains(e.to())) continue;

+        if (nearest == null || nearest.weight() > e.weight())

+          nearest = e;

+      }

+      if(nearest==null)break;

+      mst.add(nearest);

+      frontier.add(nearest.to());

+    }

+    return mst;

+  }

+

+  public static Set<Edge> dijkstra(Graph g, Vertex start){

+    // returns the tree of shortest paths from start to

+    // all vertices  in the graph

+    // naive implementation without a prorityqueue

+    // create table for done, prev and weight from start

+    int maxint =Integer.MAX_VALUE;

+    HashSet<Vertex> done=new HashSet<>();

+    HashMap<Vertex,Edge> prev=new HashMap<>();

+    HashMap<Vertex,Integer> weight=new HashMap<>();

+    for(Vertex w:g.vertices())weight.put(w,maxint);

+    // start node is done, distance 0 from start

+    weight.put(start,0);

+    done.add(start);

+

+    while(true){

+      // find nearest from a done vertex

+      Vertex nearest = null;

+      int neardist = maxint;

+      Edge done2near=null;

+      for(Vertex w1:done){

+        for (Edge e : g.outEdge(w1)) {

+          Vertex w2 = e.to();

+          if (done.contains(w2)) continue;

+          if ((weight.get(w1) + e.weight()) < neardist) {

+            nearest = e.to();

+            neardist = weight.get(w1) + e.weight();

+            done2near = e;

+          }

+        }

+      }

+      // System.out.println("find nearest "+done2near);

+      // if no more, then we are done

+      if (nearest == null) break;

+        // update distance from this node to other nodes

+      for (Edge e1 : g.outEdge(nearest)) {

+        Vertex w3 = e1.to();

+        int wght = e1.weight();

+        if (weight.get(w3) > (neardist + wght)) {

+          weight.put(w3, neardist + wght);

+        }

+      }

+      done.add(nearest);

+      prev.put(nearest,done2near);

+      weight.put(nearest,neardist);

+    }

+    return new HashSet<Edge>(prev.values());

+  }

+

+  //------------------------------------------------------------

+  //

+  //  IO operations

+

+  public static void readGraph(Graph g, String file) {

+    // read a comma-separated file in the format

+    // stores file as bidirectional graph

+    // <vertex> , <vertex> , <weight>

+    try{

+      BufferedReader in = new BufferedReader(new FileReader(file));

+      for(String line=in.readLine(); line!=null; line=in.readLine()) {

+        if(line.length()==0) continue;

+        String[] arr = line.split(",");

+        if(arr.length!=3) throw new RuntimeException("CSV file format error: "+line);

+        g.insertEdge(arr[0].trim(), arr[1].trim(), Integer.parseInt(arr[2].trim()));

+        g.insertEdge(arr[1].trim(), arr[0].trim(), Integer.parseInt(arr[2].trim()));

+      }

+      in.close();

+    }catch(IOException e){

+      throw new RuntimeException(e);

+    }

+  }

+

+  static void printGraph(Graph g) {

+    for(Vertex v: sortVertex(g.vertices())) {

+      System.out.println(v.toString());

+      for(Edge e:sortEdgesTo(g.outEdge(v)))

+        System.out.println("  "+e.toString());

+    }

+  }

+

+  public static void storeStrings(List<String> list,String f){

+    // store a list of lines as a file

+    try{

+      PrintWriter out=new PrintWriter(new FileWriter(f));

+      for(String s:list){

+        out.println(s);

+      }

+      out.close();

+    }catch(IOException e){

+      throw new RuntimeException(e);

+    }

+  }

+

+  public static ArrayList<String> loadStrings(String f){

+    // read a file a returns a list of lines

+    ArrayList<String> list=new ArrayList<>();

+    try{

+      BufferedReader in=new BufferedReader(new FileReader(f));

+      while(true){

+        String s=in.readLine();

+        if(s==null)break;

+        list.add(s);

+      }

+      in.close();

+    }catch(IOException e){

+      throw new RuntimeException(e);

+    }

+    return list;

+  }

+}

diff --git a/com/example/portfolio3/Graphs.java b/com/example/portfolio3/Graphs.java
new file mode 100644
index 0000000..54cad9e
--- /dev/null
+++ b/com/example/portfolio3/Graphs.java
@@ -0,0 +1,181 @@
+import java.util.*;

+public class Graphs {}

+

+class Vertex{

+  private String name;

+  public String name(){return name;}

+  public Vertex(String s){name=s;}

+  public String toString(){return name;}

+}

+class Edge{

+  private Vertex from,to;

+  private int weight;

+  public Vertex from(){return from;}

+  public Vertex to(){return to;}

+  public int weight(){return weight;}

+  Edge(Vertex from,Vertex to,int w){this.from=from; this.to=to; weight=w;}

+  public String toString(){return from.name()+" - "+weight+" -> "+to.name(); }

+}

+interface Graph {

+  void insertEdge(String v, String u, int w);

+  Collection<Vertex> vertices();

+  Collection<Edge> edges();

+  Collection<Edge> outEdge(Vertex v);

+  Integer getWeight(Vertex v1, Vertex v2);

+}

+

+abstract class AbstractGraph implements Graph{

+  private HashMap<String,Vertex> vertexMap=new HashMap<>();

+  private HashSet<Vertex> vertexSet=new HashSet<>();

+  public Vertex vertex(String s){

+    if(vertexMap.containsKey(s))return vertexMap.get(s);

+    Vertex v=new Vertex(s);

+    vertexMap.put(s,v);

+    vertexSet.add(v);

+    return v;

+  }

+  public void insertEdge(String v, String u, int w){

+    insertEdge(vertex(v),vertex(u),w);

+  }

+  public Collection<Vertex> vertices() { return vertexSet;  }

+  //

+  abstract public void insertEdge(Vertex v1, Vertex v2, int w);

+  abstract public Collection<Edge> edges();

+  abstract public Collection<Edge> outEdge(Vertex v);

+  abstract public Integer getWeight(Vertex v1, Vertex v2);

+}

+

+//--------------------------------------------------------

+//  EdgeGraph - One big set of all edges in the graph

+

+class EdgeGraph extends AbstractGraph {

+  Set<Edge> edges=new HashSet<>();

+  public void insertEdge(Vertex v1,Vertex v2,int w){

+    edges.add(new Edge(v1,v2,w));

+  }

+  public Collection<Edge> edges(){return edges;}

+  public Collection<Edge> outEdge(Vertex v){

+    ArrayList<Edge> outEdge=new ArrayList<>();

+    for(Edge e:edges)if(e.from()==v)outEdge.add(e);

+    return outEdge;

+  }

+  public Integer getWeight(Vertex v1,Vertex v2){

+    // linear in number of edges in the graph

+    for(Edge e:edges){

+      if(e.from()==v1 && e.to()==v2)return e.weight();

+    }

+    return null;

+  }

+}

+

+//--------------------------------------------------------

+//  Adjecency List Graph - A map from vertices to set of outedges from the vertex

+

+class AdjListGraph extends AbstractGraph {

+  private Map<Vertex,Set<Edge>> outEdge= new HashMap<>();

+  public void insertEdge(Vertex v1,Vertex v2,int w){

+    Edge e=new Edge(v1,v2,w);

+    if(!outEdge.containsKey(e.from()))

+      outEdge.put(e.from(),new HashSet<Edge>());

+    outEdge.get(e.from()).add(e);

+  }

+  public Collection<Edge> edges(){

+    Set<Edge> edges=new HashSet<>();

+    for(Vertex v:outEdge.keySet())edges.addAll(outEdge.get(v));

+    return edges;

+  }

+  public Collection<Edge> outEdge(Vertex v){

+    if(!outEdge.containsKey(v))

+      return new HashSet<Edge>();

+    return outEdge.get(v);

+  }

+  public Integer getWeight(Vertex v1,Vertex v2){

+    // linear in number of outedges from vertices

+    if(!outEdge.containsKey(v1))return null;

+    for(Edge e:outEdge.get(v1)){

+      if(e.to()==v2)return e.weight();

+    }

+    return null;

+  }

+}

+

+//--------------------------------------------------------

+//  Adjecency Map Graph - A map from vertices to map of target vertex to edge

+

+class AdjMapGraph extends AbstractGraph {

+  private Map<Vertex, Map<Vertex, Edge>> outEdge = new HashMap<>();

+

+  public void insertEdge(Vertex v1, Vertex v2, int w) {

+    Edge e = new Edge(v1,v2, w);

+    if (!outEdge.containsKey(e.from()))

+      outEdge.put(e.from(), new HashMap<Vertex, Edge>());

+    outEdge.get(e.from()).put(e.to(), e);

+  }

+  public Collection<Edge> edges() {

+    Set<Edge> edges = new HashSet<>();

+    for (Vertex v : outEdge.keySet())

+      for (Vertex w : outEdge.get(v).keySet())

+        edges.add(outEdge.get(v).get(w));

+    return edges;

+  }

+  public Collection<Edge> outEdge(Vertex v) {

+    return outEdge.get(v).values();

+  }

+  public Integer getWeight(Vertex v1, Vertex v2) {

+    // constant time operation

+    if(!outEdge.containsKey(v1))return null;

+    if(!outEdge.get(v1).containsKey(v2))return null;

+    return outEdge.get(v1).get(v2).weight();

+  }

+}

+

+//--------------------------------------------------------

+//  Matrix Graph:  weights are stored in a twodimensional array

+

+class MatrixGraph extends AbstractGraph {

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

+  // We must be able to map vertices to index in matrix and back again

+  private Vertex[] index2vertex; // made in constructor

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

+  private int numVertex; // maximum number of vertices

+  MatrixGraph(int numVertex){ // maximum number of vertices allowed

+    this.numVertex=numVertex;

+    matrix =new Integer[numVertex][numVertex];

+    index2vertex=new Vertex[numVertex];

+  }

+  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;

+  }

+  public void insertEdge(Vertex v1,Vertex v2,int w){

+    matrix[getIndex(v1)][getIndex(v2)] = w;

+  }

+  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;

+  }

+  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;

+  }

+  public Integer getWeight(Vertex v1,Vertex v2){

+    // constant time operation

+    return matrix[vertex2index.get(v1)][vertex2index.get(v2)];}

+}