From 705b7a5a32793f7ed8a24b8b35afe3f9d49348be Mon Sep 17 00:00:00 2001 From: Jonas Smedegaard Date: Tue, 29 Apr 2025 07:19:10 +0200 Subject: tidy whitespace --- .../com/example/portfolio3/AbstractGraph.java | 92 +-- .../com/example/portfolio3/AdjListGraph.java | 82 +-- .../com/example/portfolio3/AdjMapGraph.java | 76 +-- .../com/example/portfolio3/Edge.java | 70 +- .../com/example/portfolio3/EdgeGraph.java | 66 +- .../com/example/portfolio3/Graph.java | 48 +- .../com/example/portfolio3/GraphAlgorithms.java | 701 +++++++++++---------- .../com/example/portfolio3/Graphs.java | 5 +- .../com/example/portfolio3/MatrixGraph.java | 145 +++-- .../com/example/portfolio3/Vertex.java | 33 +- 10 files changed, 715 insertions(+), 603 deletions(-) (limited to 'src/com.example.portfolio3') diff --git a/src/com.example.portfolio3/com/example/portfolio3/AbstractGraph.java b/src/com.example.portfolio3/com/example/portfolio3/AbstractGraph.java index 95c1030..793260a 100644 --- a/src/com.example.portfolio3/com/example/portfolio3/AbstractGraph.java +++ b/src/com.example.portfolio3/com/example/portfolio3/AbstractGraph.java @@ -7,48 +7,52 @@ import java.util.HashMap; import java.util.HashSet; /// foo -public abstract class AbstractGraph implements Graph{ - - /// foo - AbstractGraph() {} - - /// foo - private HashMap vertexMap=new HashMap<>(); - - /// foo - private HashSet vertexSet=new HashSet<>(); - - /// foo - /// @param s foo - /// @return Vertex - public Vertex vertex(final String s){ - if(vertexMap.containsKey(s))return vertexMap.get(s); - Vertex v=new Vertex(s); - vertexMap.put(s,v); - vertexSet.add(v); - return v; - } - - /// foo - public void insertEdge(final String v, final String u, final int w){ - insertEdge(vertex(v),vertex(u),w); - } - - /// foo - public Collection vertices() { return vertexSet; } - - /// foo - /// @param v1 foo - /// @param v2 foo - /// @param w foo - abstract public void insertEdge(Vertex v1, Vertex v2, int w); - - /// foo - abstract public Collection edges(); - - /// foo - abstract public Collection outEdge(Vertex v); - - /// foo - abstract public Integer getWeight(Vertex v1, Vertex v2); +public abstract class AbstractGraph implements Graph { + + /// foo + AbstractGraph() { } + + /// foo + private HashMap vertexMap = new HashMap<>(); + + /// foo + private HashSet vertexSet = new HashSet<>(); + + /// foo + /// @param s foo + /// @return Vertex + public Vertex vertex(final String s) { + if (vertexMap.containsKey(s)) + return vertexMap.get(s); + Vertex v = new Vertex(s); + vertexMap.put(s, v); + vertexSet.add(v); + + return v; + } + + /// foo + public void insertEdge(final String v, final String u, final int w) { + insertEdge(vertex(v), vertex(u), w); + } + + /// foo + public Collection vertices() { + return vertexSet; + } + + /// foo + /// @param v1 foo + /// @param v2 foo + /// @param w foo + abstract public void insertEdge(Vertex v1, Vertex v2, int w); + + /// foo + abstract public Collection edges(); + + /// foo + abstract public Collection outEdge(Vertex v); + + /// foo + abstract public Integer getWeight(Vertex v1, Vertex v2); } diff --git a/src/com.example.portfolio3/com/example/portfolio3/AdjListGraph.java b/src/com.example.portfolio3/com/example/portfolio3/AdjListGraph.java index 765eeca..88e54d6 100644 --- a/src/com.example.portfolio3/com/example/portfolio3/AdjListGraph.java +++ b/src/com.example.portfolio3/com/example/portfolio3/AdjListGraph.java @@ -8,44 +8,50 @@ import java.util.HashSet; import java.util.Map; import java.util.Set; -/// Adjecency List Graph - A map from vertices to set of outedges from the vertex +/// Adjecency List Graph - A map from vertices to set of outedges from the vertex public class AdjListGraph extends AbstractGraph { - /// foo - public AdjListGraph() {} - - /// foo - private Map> outEdge= new HashMap<>(); - - /// foo - public void insertEdge(final Vertex v1, final Vertex v2, final int w){ - Edge e=new Edge(v1,v2,w); - if(!outEdge.containsKey(e.from())) - outEdge.put(e.from(),new HashSet()); - outEdge.get(e.from()).add(e); - } - - /// foo - public Collection edges(){ - Set edges=new HashSet<>(); - for(Vertex v:outEdge.keySet())edges.addAll(outEdge.get(v)); - return edges; - } - - /// foo - public Collection outEdge(final Vertex v){ - if(!outEdge.containsKey(v)) - return new HashSet(); - return outEdge.get(v); - } - - /// foo - public Integer getWeight(final Vertex v1, final 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; - } + /// foo + public AdjListGraph() { } + + /// foo + private Map> outEdge = new HashMap<>(); + + /// foo + public void insertEdge(final Vertex v1, final Vertex v2, final int w) { + Edge e = new Edge(v1, v2, w); + if (!outEdge.containsKey(e.from())) + outEdge.put(e.from(), new HashSet()); + outEdge.get(e.from()).add(e); + } + + /// foo + public Collection edges() { + Set edges = new HashSet<>(); + for (Vertex v: outEdge.keySet())edges.addAll(outEdge.get(v)); + + return edges; + } + + /// foo + public Collection outEdge(final Vertex v) { + if (!outEdge.containsKey(v)) + return new HashSet(); + + return outEdge.get(v); + } + + /// foo + public Integer getWeight(final Vertex v1, final 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; + } } diff --git a/src/com.example.portfolio3/com/example/portfolio3/AdjMapGraph.java b/src/com.example.portfolio3/com/example/portfolio3/AdjMapGraph.java index 353f934..e85db6c 100644 --- a/src/com.example.portfolio3/com/example/portfolio3/AdjMapGraph.java +++ b/src/com.example.portfolio3/com/example/portfolio3/AdjMapGraph.java @@ -8,42 +8,46 @@ import java.util.HashSet; import java.util.Map; import java.util.Set; -/// Adjecency Map Graph - A map from vertices to map of target vertex to edge +/// Adjecency Map Graph - A map from vertices to map of target vertex to edge class AdjMapGraph extends AbstractGraph { - /// foo - AdjMapGraph() {} - - /// foo - private Map> outEdge = new HashMap<>(); - - /// foo - public void insertEdge(final Vertex v1, final Vertex v2, final int w) { - Edge e = new Edge(v1,v2, w); - if (!outEdge.containsKey(e.from())) - outEdge.put(e.from(), new HashMap()); - outEdge.get(e.from()).put(e.to(), e); - } - - /// foo - public Collection edges() { - Set edges = new HashSet<>(); - for (Vertex v : outEdge.keySet()) - for (Vertex w : outEdge.get(v).keySet()) - edges.add(outEdge.get(v).get(w)); - return edges; - } - - /// foo - public Collection outEdge(final Vertex v) { - return outEdge.get(v).values(); - } - - /// foo - public Integer getWeight(final Vertex v1, final 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(); - } + /// foo + AdjMapGraph() { } + + /// foo + private Map> outEdge = new HashMap<>(); + + /// foo + public void insertEdge(final Vertex v1, final Vertex v2, final int w) { + Edge e = new Edge(v1,v2, w); + if (!outEdge.containsKey(e.from())) + outEdge.put(e.from(), new HashMap()); + outEdge.get(e.from()).put(e.to(), e); + } + + /// foo + public Collection edges() { + Set edges = new HashSet<>(); + for (Vertex v : outEdge.keySet()) + for (Vertex w : outEdge.get(v).keySet()) + edges.add(outEdge.get(v).get(w)); + + return edges; + } + + /// foo + public Collection outEdge(final Vertex v) { + return outEdge.get(v).values(); + } + + /// foo + public Integer getWeight(final Vertex v1, final 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(); + } } diff --git a/src/com.example.portfolio3/com/example/portfolio3/Edge.java b/src/com.example.portfolio3/com/example/portfolio3/Edge.java index 7cb8d5a..065b6ae 100644 --- a/src/com.example.portfolio3/com/example/portfolio3/Edge.java +++ b/src/com.example.portfolio3/com/example/portfolio3/Edge.java @@ -3,33 +3,45 @@ package com.example.portfolio3; // origin: /// foo -public class Edge{ - - /// foo - private Vertex from,to; - - /// foo - private int weight; - - /// foo - /// @return Vertex - public Vertex from(){return from;} - - /// foo - /// @return Vertex - public Vertex to(){return to;} - - /// foo - /// @return int - public int weight(){return weight;} - - /// foo - /// @param from foo - /// @param to foo - /// @param w foo - Edge(final Vertex from, final Vertex to, final int w){this.from=from; this.to=to; weight=w;} - - /// foo - /// @return String - public String toString(){return from.name()+" - "+weight+" -> "+to.name(); } +public class Edge { + + /// foo + private Vertex from, to; + + /// foo + private int weight; + + /// foo + /// @return Vertex + public Vertex from() { + return from; + } + + /// foo + /// @return Vertex + public Vertex to() { + return to; + } + + /// foo + /// @return int + public int weight() { + return weight; + } + + /// foo + /// @param from foo + /// @param to foo + /// @param w foo + Edge(final Vertex from, final Vertex to, final int w) { + this.from = from; + this.to = to; + weight = w; + } + + /// foo + /// @return String + public String toString() { + return from.name() + " - " + weight + " -> " + to.name(); + } } diff --git a/src/com.example.portfolio3/com/example/portfolio3/EdgeGraph.java b/src/com.example.portfolio3/com/example/portfolio3/EdgeGraph.java index 979b118..8bd9259 100644 --- a/src/com.example.portfolio3/com/example/portfolio3/EdgeGraph.java +++ b/src/com.example.portfolio3/com/example/portfolio3/EdgeGraph.java @@ -10,33 +10,41 @@ import java.util.Set; /// EdgeGraph - One big set of all edges in the graph class EdgeGraph extends AbstractGraph { - /// foo - EdgeGraph() {} - - /// foo - Set edges=new HashSet<>(); - - /// foo - public void insertEdge(final Vertex v1, final Vertex v2, final int w){ - edges.add(new Edge(v1,v2,w)); - } - - /// foo - public Collection edges(){return edges;} - - /// foo - public Collection outEdge(final Vertex v){ - ArrayList outEdge=new ArrayList<>(); - for(Edge e:edges)if(e.from()==v)outEdge.add(e); - return outEdge; - } - - /// foo - public Integer getWeight(final Vertex v1, final 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; - } + /// foo + EdgeGraph() { } + + /// foo + Set edges = new HashSet<>(); + + /// foo + public void insertEdge(final Vertex v1, final Vertex v2, final int w) { + edges.add(new Edge(v1, v2, w)); + } + + /// foo + public Collection edges() { + return edges; + } + + /// foo + public Collection outEdge(final Vertex v) { + ArrayList outEdge = new ArrayList<>(); + for (Edge e: edges) + if (e.from() == v) + outEdge.add(e); + + return outEdge; + } + + /// foo + public Integer getWeight(final Vertex v1, final 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; + } } diff --git a/src/com.example.portfolio3/com/example/portfolio3/Graph.java b/src/com.example.portfolio3/com/example/portfolio3/Graph.java index a8fbde0..b6e294c 100644 --- a/src/com.example.portfolio3/com/example/portfolio3/Graph.java +++ b/src/com.example.portfolio3/com/example/portfolio3/Graph.java @@ -7,28 +7,28 @@ import java.util.Collection; /// foo public interface Graph { - /// foo - /// @param v foo - /// @param u foo - /// @param w foo - void insertEdge(String v, String u, int w); - - /// foo - /// @return Collection - Collection vertices(); - - /// foo - /// @return Collection - Collection edges(); - - /// foo - /// @param v foo - /// @return Collection - Collection outEdge(Vertex v); - - /// foo - /// @param v1 foo - /// @param v2 foo - /// @return Integer - Integer getWeight(Vertex v1, Vertex v2); + /// foo + /// @param v foo + /// @param u foo + /// @param w foo + void insertEdge(String v, String u, int w); + + /// foo + /// @return Collection + Collection vertices(); + + /// foo + /// @return Collection + Collection edges(); + + /// foo + /// @param v foo + /// @return Collection + Collection outEdge(Vertex v); + + /// foo + /// @param v1 foo + /// @param v2 foo + /// @return Integer + Integer getWeight(Vertex v1, Vertex v2); } diff --git a/src/com.example.portfolio3/com/example/portfolio3/GraphAlgorithms.java b/src/com.example.portfolio3/com/example/portfolio3/GraphAlgorithms.java index d2a20f2..6b47bd2 100644 --- a/src/com.example.portfolio3/com/example/portfolio3/GraphAlgorithms.java +++ b/src/com.example.portfolio3/com/example/portfolio3/GraphAlgorithms.java @@ -19,324 +19,385 @@ 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(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 path){ - int length=0; - for(int i=1;i - 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; - } + /// 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(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(), 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(), 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(), 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; + } } diff --git a/src/com.example.portfolio3/com/example/portfolio3/Graphs.java b/src/com.example.portfolio3/com/example/portfolio3/Graphs.java index 74e1dbe..a246761 100644 --- a/src/com.example.portfolio3/com/example/portfolio3/Graphs.java +++ b/src/com.example.portfolio3/com/example/portfolio3/Graphs.java @@ -5,7 +5,6 @@ package com.example.portfolio3; /// foo public class Graphs { - /// foo - Graphs() {} - + /// foo + Graphs() { } } diff --git a/src/com.example.portfolio3/com/example/portfolio3/MatrixGraph.java b/src/com.example.portfolio3/com/example/portfolio3/MatrixGraph.java index 985fcbb..5a1f327 100644 --- a/src/com.example.portfolio3/com/example/portfolio3/MatrixGraph.java +++ b/src/com.example.portfolio3/com/example/portfolio3/MatrixGraph.java @@ -7,74 +7,83 @@ import java.util.HashMap; import java.util.HashSet; import java.util.Map; -/// Matrix Graph: weights are stored in a twodimensional array +/// Matrix Graph: weights are stored in a twodimensional array public class MatrixGraph extends AbstractGraph { - /// foo - private Integer[][] matrix=null; // made in constructor - - /// foo - // We must be able to map vertices to index in matrix and back again - private Vertex[] index2vertex; // made in constructor - - /// foo - private Map vertex2index=new HashMap<>(); - - /// foo - private int numVertex; // maximum number of vertices - - /// foo - /// @param numVertex maximum number of vertices allowed - public MatrixGraph(final int numVertex){ - this.numVertex=numVertex; - matrix =new Integer[numVertex][numVertex]; - index2vertex=new Vertex[numVertex]; - } - - /// foo - /// @param v vertex - /// @return int - private int getIndex(final 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; - } - - /// foo - public void insertEdge(final Vertex v1, final Vertex v2, final int w){ - matrix[getIndex(v1)][getIndex(v2)] = w; - } - - /// foo - public Collection edges(){ - HashSet edges=new HashSet<>(); - for(int i=0;i outEdge(final Vertex v1){ - HashSet edges=new HashSet<>(); - int i=vertex2index.get(v1); - for(int j=0;j vertex2index = new HashMap<>(); + + /// maximum number of vertices + private int numVertex; + + /// foo + /// + /// @param numVertex maximum number of vertices allowed + public MatrixGraph(final int numVertex) { + this.numVertex = numVertex; + matrix = new Integer[numVertex][numVertex]; + index2vertex = new Vertex[numVertex]; + } + + /// foo + /// + /// @param v vertex + /// @return int + private int getIndex(final 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; + } + + /// foo + public void insertEdge(final Vertex v1, final Vertex v2, final int w) { + matrix[getIndex(v1)][getIndex(v2)] = w; + } + + /// foo + public Collection edges() { + HashSet 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; + } + + /// foo + public Collection outEdge(final Vertex v1) { + HashSet 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; + } + + /// foo + public Integer getWeight(final Vertex v1, final Vertex v2) { + + // constant time operation + return matrix[vertex2index.get(v1)][vertex2index.get(v2)]; + } } diff --git a/src/com.example.portfolio3/com/example/portfolio3/Vertex.java b/src/com.example.portfolio3/com/example/portfolio3/Vertex.java index caf3930..420263a 100644 --- a/src/com.example.portfolio3/com/example/portfolio3/Vertex.java +++ b/src/com.example.portfolio3/com/example/portfolio3/Vertex.java @@ -3,20 +3,29 @@ package com.example.portfolio3; // origin: /// foo -public class Vertex{ +public class Vertex { - /// foo - private String name; + /// foo + private String name; - /// foo - /// @return String - public String name(){return name;} + /// foo + /// + /// @return String + public String name() { + return name; + } - /// foo - /// @param s foo - public Vertex(final String s){name=s;} + /// foo + /// + /// @param s foo + public Vertex(final String s) { + name = s; + } - /// foo - /// @return String - public String toString(){return name;} + /// foo + /// + /// @return String + public String toString() { + return name; + } } -- cgit v1.2.3