package com.example.portfolio3; // origin: 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() { } /// calculate the length of a path or another collection of edges /// /// does not require the edges to form a path /// /// @param edges foo /// @return int public static int pathLength(final 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(final List edges) { for (int i = 1; i < edges.size(); i++) { if (edges.get(i - 1).to() != edges.get(i).from() ) { return false; } } return true; } /// Calculates the length of a path vertices in a graph /// /// return null if vertices are not connected as a path /// /// @param g foo /// @param path foo /// @return Integer public static Integer pathLength( final Graph g, final List 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 /// Comparator of edges based on weight /// /// can be used for sorting a list of edges /// /// @param e1 foo /// @param e2 foo /// @return int static int cmpEdgeWeight(final Edge e1, final Edge e2) { int w1 = e1.weight(); int 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()); } /// Comparator of edges based on from-vertex /// /// can be used for sorting a list of edges /// /// @param e1 foo /// @param e2 foo /// @return int static int cmpEdgeFrom(final Edge e1, final Edge e2) { if (e1.from() != e2.from()) { return e1.from().name().compareTo( e2.from().name()); } int w1 = e1.weight(); int w2 = e2.weight(); if (w1 != w2) { return w1 - w2; } return e1.to().name().compareTo(e2.to().name()); } /// Comparator of edges based on from-vertex /// /// can be used for sorting a list of edges /// /// @param e1 foo /// @param e2 foo /// @return int static int cmpEdgeTo(final Edge e1, final Edge e2) { 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(); int w2 = e2.weight(); return w1 - w2; } /// sort a collection of edges based on their weights /// /// @param edges foo /// @return List static List sortEdges(final 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(final 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(final 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( final 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( final Graph g, final 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( final Graph g, final 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( final Graph g, final Vertex v, final 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(final 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( final Graph g, final 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(final Graph g, final 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(final 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( final List list, final 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(final 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; } }