From a5e648d8e1f17b4a5302182980077efdcff80c57 Mon Sep 17 00:00:00 2001
From: Jonas Smedegaard <dr@jones.dk>
Date: Sun, 20 Apr 2025 18:26:01 +0200
Subject: fix newlines

---
 com/example/portfolio3/GraphAlgorithms.java | 526 ++++++++++++++--------------
 com/example/portfolio3/Graphs.java          | 362 +++++++++----------
 2 files changed, 444 insertions(+), 444 deletions(-)

(limited to 'com')

diff --git a/com/example/portfolio3/GraphAlgorithms.java b/com/example/portfolio3/GraphAlgorithms.java
index fdf6def..c794bc5 100644
--- a/com/example/portfolio3/GraphAlgorithms.java
+++ b/com/example/portfolio3/GraphAlgorithms.java
@@ -1,263 +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;
-  }
-}
+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
index 54cad9e..e0fb381 100644
--- a/com/example/portfolio3/Graphs.java
+++ b/com/example/portfolio3/Graphs.java
@@ -1,181 +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)];}
-}
+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)];}
+}
-- 
cgit v1.2.3