From 241ccd42439621386d3c2a6322cbb9ae1ddb511d Mon Sep 17 00:00:00 2001 From: Jonas Smedegaard Date: Sun, 20 Apr 2025 18:22:22 +0200 Subject: include code from course material --- com/example/portfolio3/GraphAlgorithms.java | 263 ++++++++++++++++++++++++++++ com/example/portfolio3/Graphs.java | 181 +++++++++++++++++++ 2 files changed, 444 insertions(+) create mode 100644 com/example/portfolio3/GraphAlgorithms.java create mode 100644 com/example/portfolio3/Graphs.java (limited to 'com') diff --git a/com/example/portfolio3/GraphAlgorithms.java b/com/example/portfolio3/GraphAlgorithms.java new file mode 100644 index 0000000..fdf6def --- /dev/null +++ b/com/example/portfolio3/GraphAlgorithms.java @@ -0,0 +1,263 @@ +import java.io.*; +import java.util.*; + +public class GraphAlgorithms { + public static int pathLength(Collection 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(); + } + + public static boolean isPath(List 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 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 sortEdges(Collection edges){ + // sort a collection of edges based on their weights + ArrayList list=new ArrayList<>(edges); + Collections.sort(list,GraphAlgorithms::cmpEdgeWeight); + return list; + } + static List sortEdgesFrom(Collection edges){ + // sort a collection of edges based on from-vertex + ArrayList list=new ArrayList<>(edges); + Collections.sort(list,GraphAlgorithms::cmpEdgeFrom); + return list; + } + static List sortEdgesTo(Collection edges){ + // sort a collection of edges based on to-vertex + ArrayList list=new ArrayList<>(edges); + Collections.sort(list,GraphAlgorithms::cmpEdgeTo); + return list; + } + + static List sortVertex(Collection vertices){ + // sort a collection of vertices based on their name + 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 + + public static Set visitBreadthFirst(Graph g,Vertex v){ + // traverse a graph depth first from a given vertex + // return the set of visited vertices + 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; + } + + public static Set visitDepthFirst(Graph g,Vertex v){ + // traverse a graph depth first from a given vertex + // return the set of visited vertices + HashSet visit=new HashSet<>(); + visitDepthFirst(g, v,visit); + return visit; + } + + 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); + } + + public static Set minimumSpanningTree(Graph g){ + // an implementation of Prim's algorithm + // naive implementation without priorityqueue + 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; + } + + public static Set 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 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 + + public static void readGraph(Graph g, String file) { + // read a comma-separated file in the format + // stores file as bidirectional graph + // , , + 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); + } + } + + 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()); + } + } + + public static void storeStrings(List list,String f){ + // store a list of lines as a file + try{ + PrintWriter out=new PrintWriter(new FileWriter(f)); + for(String s:list){ + out.println(s); + } + out.close(); + }catch(IOException e){ + throw new RuntimeException(e); + } + } + + public static ArrayList loadStrings(String f){ + // read a file a returns a list of lines + 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/com/example/portfolio3/Graphs.java b/com/example/portfolio3/Graphs.java new file mode 100644 index 0000000..54cad9e --- /dev/null +++ b/com/example/portfolio3/Graphs.java @@ -0,0 +1,181 @@ +import java.util.*; +public class Graphs {} + +class Vertex{ + private String name; + public String name(){return name;} + public Vertex(String s){name=s;} + public String toString(){return name;} +} +class Edge{ + private Vertex from,to; + private int weight; + public Vertex from(){return from;} + public Vertex to(){return to;} + public int weight(){return weight;} + Edge(Vertex from,Vertex to,int w){this.from=from; this.to=to; weight=w;} + public String toString(){return from.name()+" - "+weight+" -> "+to.name(); } +} +interface Graph { + void insertEdge(String v, String u, int w); + Collection vertices(); + Collection edges(); + Collection outEdge(Vertex v); + Integer getWeight(Vertex v1, Vertex v2); +} + +abstract class AbstractGraph implements Graph{ + private HashMap vertexMap=new HashMap<>(); + private HashSet vertexSet=new HashSet<>(); + public Vertex vertex(String s){ + if(vertexMap.containsKey(s))return vertexMap.get(s); + Vertex v=new Vertex(s); + vertexMap.put(s,v); + vertexSet.add(v); + return v; + } + public void insertEdge(String v, String u, int w){ + insertEdge(vertex(v),vertex(u),w); + } + public Collection vertices() { return vertexSet; } + // + abstract public void insertEdge(Vertex v1, Vertex v2, int w); + abstract public Collection edges(); + abstract public Collection outEdge(Vertex v); + abstract public Integer getWeight(Vertex v1, Vertex v2); +} + +//-------------------------------------------------------- +// EdgeGraph - One big set of all edges in the graph + +class EdgeGraph extends AbstractGraph { + Set edges=new HashSet<>(); + public void insertEdge(Vertex v1,Vertex v2,int w){ + edges.add(new Edge(v1,v2,w)); + } + public Collection edges(){return edges;} + public Collection outEdge(Vertex v){ + ArrayList outEdge=new ArrayList<>(); + for(Edge e:edges)if(e.from()==v)outEdge.add(e); + return outEdge; + } + public Integer getWeight(Vertex v1,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; + } +} + +//-------------------------------------------------------- +// Adjecency List Graph - A map from vertices to set of outedges from the vertex + +class AdjListGraph extends AbstractGraph { + private Map> outEdge= new HashMap<>(); + public void insertEdge(Vertex v1,Vertex v2,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); + } + public Collection edges(){ + Set edges=new HashSet<>(); + for(Vertex v:outEdge.keySet())edges.addAll(outEdge.get(v)); + return edges; + } + public Collection outEdge(Vertex v){ + if(!outEdge.containsKey(v)) + return new HashSet(); + return outEdge.get(v); + } + public Integer getWeight(Vertex v1,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; + } +} + +//-------------------------------------------------------- +// Adjecency Map Graph - A map from vertices to map of target vertex to edge + +class AdjMapGraph extends AbstractGraph { + private Map> outEdge = new HashMap<>(); + + public void insertEdge(Vertex v1, Vertex v2, 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); + } + 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; + } + public Collection outEdge(Vertex v) { + return outEdge.get(v).values(); + } + public Integer getWeight(Vertex v1, 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(); + } +} + +//-------------------------------------------------------- +// Matrix Graph: weights are stored in a twodimensional array + +class MatrixGraph extends AbstractGraph { + private Integer[][] matrix=null; // made in constructor + // We must be able to map vertices to index in matrix and back again + private Vertex[] index2vertex; // made in constructor + private Map vertex2index=new HashMap<>(); + private int numVertex; // maximum number of vertices + MatrixGraph(int numVertex){ // maximum number of vertices allowed + this.numVertex=numVertex; + matrix =new Integer[numVertex][numVertex]; + index2vertex=new Vertex[numVertex]; + } + private int getIndex(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; + } + public void insertEdge(Vertex v1,Vertex v2,int w){ + matrix[getIndex(v1)][getIndex(v2)] = w; + } + public Collection edges(){ + HashSet edges=new HashSet<>(); + for(int i=0;i outEdge(Vertex v1){ + HashSet edges=new HashSet<>(); + int i=vertex2index.get(v1); + for(int j=0;j