package com.example.portfolio3; // origin: import java.io.BufferedReader; import java.io.BufferedReader; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Collection; import java.util.Collections; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Set; /// foo public class GraphAlgorithms { /// foo GraphAlgorithms() {} /// Calculates the length of a path or any other collection of edes /// /// does not require the edges to form a path /// @param edges foo /// @return int public static int pathLength(Collection edges){ return edges.stream().mapToInt(e-> e.weight()).sum(); } /// checks whether a list of edges form a path so that /// /// the to-vertex in one edge is the from-vertex of the next /// @param edges foo /// @return boolean public static boolean isPath(List edges){ for(int i=1;i path){ int length=0; for(int i=1;i static List sortEdges(Collection edges){ ArrayList list=new ArrayList<>(edges); Collections.sort(list,GraphAlgorithms::cmpEdgeWeight); return list; } /// sort a collection of edges based on from-vertex /// @param edges foo /// @return List static List sortEdgesFrom(Collection edges){ ArrayList list=new ArrayList<>(edges); Collections.sort(list,GraphAlgorithms::cmpEdgeFrom); return list; } /// sort a collection of edges based on to-vertex /// @param edges foo /// @return List static List sortEdgesTo(Collection edges){ ArrayList list=new ArrayList<>(edges); Collections.sort(list,GraphAlgorithms::cmpEdgeTo); return list; } /// sort a collection of vertices based on their name /// @param vertices foo /// @return List public static List sortVertex(Collection vertices){ ArrayList 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 /// traverse a graph depth first from a given vertex /// return the set of visited vertices /// @param g foo /// @param v foo /// @return Set public static Set visitBreadthFirst(Graph g,Vertex v){ HashSet thisLevel=new HashSet<>(); HashSet nextLevel=new HashSet<>(); HashSet 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 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(); } return visited; } /// traverse a graph depth first from a given vertex /// return the set of visited vertices /// @param g foo /// @param v foo /// @return Set public static Set visitDepthFirst(Graph g,Vertex v){ HashSet visit=new HashSet<>(); visitDepthFirst(g, v,visit); return visit; } /// foo /// @param g foo /// @param v foo /// @param visited foo private static void visitDepthFirst(Graph g,Vertex v,Set 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); } /// an implementation of Prim's algorithm /// naive implementation without priorityqueue /// @param g foo /// @return Set public static Set minimumSpanningTree(Graph g){ Collection edges=g.edges(); HashSet mst=new HashSet<>(); HashSet 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; } /// returns the tree of shortest paths from start to /// all vertices in the graph /// /// naive implementation without a prorityqueue /// @param g foo /// @param start foo /// @return Set public static Set dijkstra(Graph g, Vertex start){ // create table for done, prev and weight from start int maxint =Integer.MAX_VALUE; HashSet done=new HashSet<>(); HashMap prev=new HashMap<>(); HashMap 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(prev.values()); } //------------------------------------------------------------ // // IO operations /// read a comma-separated file in the format /// , , /// /// stores file as bidirectional graph /// @param g foo /// @param file foo public static void readGraph(Graph g, String file) { 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); } } /// foo /// @param g foo public 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()); } } /// store a list of lines as a file /// @param list foo /// @param f foo public static void storeStrings(List list,String f){ try{ PrintWriter out=new PrintWriter(new FileWriter(f)); for(String s:list){ out.println(s); } out.close(); }catch(IOException e){ throw new RuntimeException(e); } } /// read a file a returns a list of lines /// @param f foo /// @return ArrayList public static ArrayList loadStrings(String f){ ArrayList 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; } }