diff options
Diffstat (limited to 'com/example/portfolio3/GraphAlgorithms.java')
| -rw-r--r-- | com/example/portfolio3/GraphAlgorithms.java | 121 |
1 files changed, 91 insertions, 30 deletions
diff --git a/com/example/portfolio3/GraphAlgorithms.java b/com/example/portfolio3/GraphAlgorithms.java index 823e2b1..c542689 100644 --- a/com/example/portfolio3/GraphAlgorithms.java +++ b/com/example/portfolio3/GraphAlgorithms.java @@ -5,25 +5,37 @@ package com.example.portfolio3; import java.io.*; import java.util.*; +/// foo public class 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<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(); } + /// 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<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; } + ///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(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)); @@ -37,52 +49,76 @@ public class GraphAlgorithms { // // 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(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()); } + + /// 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(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()); } + + /// 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(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; } + /// sort a collection of edges based on their weights + /// @param edges foo + /// @return List<Edge> 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; } + + /// sort a collection of edges based on from-vertex + /// @param edges foo + /// @return List<Edge> 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; } + + /// sort a collection of edges based on to-vertex + /// @param edges foo + /// @return List<Edge> 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; } + /// sort a collection of vertices based on their name + /// @param vertices foo + /// @return List<Vertex> 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; @@ -92,9 +128,12 @@ public class GraphAlgorithms { // // 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<Vertex> 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<>(); @@ -118,14 +157,21 @@ public class GraphAlgorithms { 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<Vertex> 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; } + /// foo + /// @param g foo + /// @param v foo + /// @param visited foo private static void visitDepthFirst(Graph g,Vertex v,Set<Vertex> visited){ if(visited.contains(v))return; //System.out.println("visited "+v); @@ -134,9 +180,11 @@ public class GraphAlgorithms { visitDepthFirst(g,e.to(),visited); } + /// an implementation of Prim's algorithm + /// naive implementation without priorityqueue + /// @param g foo + /// @return Set<Edge> 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<>(); @@ -156,10 +204,14 @@ public class GraphAlgorithms { 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<Edge> 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<>(); @@ -208,10 +260,13 @@ public class GraphAlgorithms { // // IO operations + /// read a comma-separated file in the format + /// <vertex> , <vertex> , <weight> + /// + /// stores file as bidirectional graph + /// @param g foo + /// @param file foo 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()) { @@ -227,6 +282,8 @@ public class GraphAlgorithms { } } + /// foo + /// @param g foo static void printGraph(Graph g) { for(Vertex v: sortVertex(g.vertices())) { System.out.println(v.toString()); @@ -235,8 +292,10 @@ public class GraphAlgorithms { } } + /// store a list of lines as a file + /// @param list foo + /// @param f foo 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){ @@ -248,8 +307,10 @@ public class GraphAlgorithms { } } + /// read a file a returns a list of lines + /// @param f foo + /// @return ArrayList 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)); |