diff options
Diffstat (limited to 'src/com.example.portfolio3/com/example/portfolio3/GraphAlgorithms.java')
| -rw-r--r-- | src/com.example.portfolio3/com/example/portfolio3/GraphAlgorithms.java | 91 |
1 files changed, 65 insertions, 26 deletions
diff --git a/src/com.example.portfolio3/com/example/portfolio3/GraphAlgorithms.java b/src/com.example.portfolio3/com/example/portfolio3/GraphAlgorithms.java index 4d8a8c2..61ef6c2 100644 --- a/src/com.example.portfolio3/com/example/portfolio3/GraphAlgorithms.java +++ b/src/com.example.portfolio3/com/example/portfolio3/GraphAlgorithms.java @@ -21,7 +21,7 @@ public class GraphAlgorithms { /// foo GraphAlgorithms() { } - /// Calculates the length of a path or any other collection of edes + /// calculate the length of a path or another collection of edges /// /// does not require the edges to form a path /// @@ -39,7 +39,8 @@ public class GraphAlgorithms { /// @return boolean public static boolean isPath(final List<Edge> edges) { for (int i = 1; i < edges.size(); i++) { - if (edges.get(i - 1).to() != edges.get(i).from()) { + if (edges.get(i - 1).to() != edges.get(i).from() + ) { return false; } } @@ -54,10 +55,13 @@ public class GraphAlgorithms { /// @param g foo /// @param path foo /// @return Integer - public static Integer pathLength(final Graph g, final List<Vertex> path) { + public static Integer pathLength( + final Graph g, final List<Vertex> path + ) { int length = 0; for (int i = 1; i < path.size(); i++) { - Integer w = g.getWeight(path.get(i - 1), path.get(i)); + Integer w = g.getWeight( + path.get(i - 1), path.get(i)); if (w == null) { return null; } @@ -84,7 +88,8 @@ public class GraphAlgorithms { return w1 - w2; } if (e1.from() != e2.from()) { - return e1.from().name().compareTo(e2.from().name()); + return e1.from().name().compareTo( + e2.from().name()); } return e1.to().name().compareTo(e2.to().name()); @@ -99,7 +104,8 @@ public class GraphAlgorithms { /// @return int static int cmpEdgeFrom(final Edge e1, final Edge e2) { if (e1.from() != e2.from()) { - return e1.from().name().compareTo(e2.from().name()); + return e1.from().name().compareTo( + e2.from().name()); } int w1 = e1.weight(), w2 = e2.weight(); if (w1 != w2) { @@ -118,10 +124,12 @@ public class GraphAlgorithms { /// @return int static int cmpEdgeTo(final Edge e1, final Edge e2) { if (e1.to() != e2.to()) { - return e1.to().name().compareTo(e2.to().name()); + return e1.to().name().compareTo( + e2.to().name()); } if (e1.from() != e2.from()) { - return e1.from().name().compareTo(e2.from().name()); + return e1.from().name().compareTo( + e2.from().name()); } int w1 = e1.weight(), w2 = e2.weight(); @@ -165,9 +173,12 @@ public class GraphAlgorithms { /// /// @param vertices foo /// @return List<Vertex> - public static List<Vertex> sortVertex(final Collection<Vertex> vertices) { + public static List<Vertex> sortVertex( + final Collection<Vertex> vertices + ) { ArrayList<Vertex> list = new ArrayList<>(vertices); - Collections.sort(list, (Vertex v1, Vertex v2) -> v1.name().compareTo(v2.name())); + Collections.sort(list, (Vertex v1, Vertex v2) -> + v1.name().compareTo(v2.name())); return list; } @@ -182,7 +193,9 @@ public class GraphAlgorithms { /// @param g foo /// @param v foo /// @return Set<Vertex> - public static Set<Vertex> visitBreadthFirst(final Graph g, final Vertex v) { + public static Set<Vertex> visitBreadthFirst( + final Graph g, final Vertex v + ) { HashSet<Vertex> thisLevel = new HashSet<>(); HashSet<Vertex> nextLevel = new HashSet<>(); HashSet<Vertex> visited = new HashSet<>(); @@ -219,7 +232,9 @@ public class GraphAlgorithms { /// @param g foo /// @param v foo /// @return Set<Vertex> - public static Set<Vertex> visitDepthFirst(final Graph g, final Vertex v) { + public static Set<Vertex> visitDepthFirst( + final Graph g, final Vertex v + ) { HashSet<Vertex> visit = new HashSet<>(); visitDepthFirst(g, v, visit); @@ -231,7 +246,9 @@ public class GraphAlgorithms { /// @param g foo /// @param v foo /// @param visited foo - private static void visitDepthFirst(final Graph g, final Vertex v, final Set<Vertex> visited) { + private static void visitDepthFirst( + final Graph g, final Vertex v, final Set<Vertex> visited + ) { if (visited.contains(v)) { return; } @@ -265,7 +282,9 @@ public class GraphAlgorithms { if (frontier.contains(e.to())) { continue; } - if (nearest == null || nearest.weight() > e.weight()) { + if (nearest == null + || nearest.weight() > e.weight() + ) { nearest = e; } } @@ -287,7 +306,9 @@ public class GraphAlgorithms { /// @param g foo /// @param start foo /// @return Set<Edge> - public static Set<Edge> dijkstra(final Graph g, final Vertex start) { + public static Set<Edge> dijkstra( + final Graph g, final Vertex start + ) { // create table for done, prev and weight from start int maxint = Integer.MAX_VALUE; @@ -314,15 +335,19 @@ public class GraphAlgorithms { if (done.contains(w2)) { continue; } - if ((weight.get(w1) + e.weight()) < neardist) { + if ((weight.get(w1) + + e.weight()) + < neardist + ) { nearest = e.to(); - neardist = weight.get(w1) + e.weight(); + neardist = weight.get(w1) + + e.weight(); done2near = e; } } } - // System.out.println("find nearest "+done2near); + //System.out.println("find nearest "+done2near); // if no more, then we are done if (nearest == null) { break; @@ -357,17 +382,27 @@ public class GraphAlgorithms { /// @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()) { + 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); + 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())); + 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) { @@ -391,9 +426,12 @@ public class GraphAlgorithms { /// /// @param list foo /// @param f foo - public static void storeStrings(final List<String> list, final String f) { + public static void storeStrings( + final List<String> list, final String f + ) { try { - PrintWriter out = new PrintWriter(new FileWriter(f)); + PrintWriter out = new PrintWriter( + new FileWriter(f)); for (String s: list) { out.println(s); } @@ -410,7 +448,8 @@ public class GraphAlgorithms { public static ArrayList<String> loadStrings(final String f) { ArrayList<String> list = new ArrayList<>(); try { - BufferedReader in = new BufferedReader(new FileReader(f)); + BufferedReader in = new BufferedReader( + new FileReader(f)); while (true) { String s = in.readLine(); if (s == null) { |