From e4a0762c7a2ac3afb8e33bf24fd7495553b5819f Mon Sep 17 00:00:00 2001 From: Jonas Smedegaard Date: Sat, 26 Apr 2025 19:32:53 +0200 Subject: use Maven idiomatic root path src/main/java --- .../com/example/portfolio3/AbstractGraph.java | 52 ++++ .../com/example/portfolio3/AdjListGraph.java | 47 +++ .../com/example/portfolio3/AdjMapGraph.java | 45 +++ .../com/example/portfolio3/Edge.java | 37 +++ .../com/example/portfolio3/EdgeGraph.java | 37 +++ .../com/example/portfolio3/Graph.java | 34 +++ .../com/example/portfolio3/GraphAlgorithms.java | 331 +++++++++++++++++++++ .../com/example/portfolio3/Graphs.java | 13 + .../com/example/portfolio3/MatrixGraph.java | 77 +++++ .../com/example/portfolio3/Vertex.java | 24 ++ 10 files changed, 697 insertions(+) create mode 100644 src/main/java/com.example.portfolio3/com/example/portfolio3/AbstractGraph.java create mode 100644 src/main/java/com.example.portfolio3/com/example/portfolio3/AdjListGraph.java create mode 100644 src/main/java/com.example.portfolio3/com/example/portfolio3/AdjMapGraph.java create mode 100644 src/main/java/com.example.portfolio3/com/example/portfolio3/Edge.java create mode 100644 src/main/java/com.example.portfolio3/com/example/portfolio3/EdgeGraph.java create mode 100644 src/main/java/com.example.portfolio3/com/example/portfolio3/Graph.java create mode 100644 src/main/java/com.example.portfolio3/com/example/portfolio3/GraphAlgorithms.java create mode 100644 src/main/java/com.example.portfolio3/com/example/portfolio3/Graphs.java create mode 100644 src/main/java/com.example.portfolio3/com/example/portfolio3/MatrixGraph.java create mode 100644 src/main/java/com.example.portfolio3/com/example/portfolio3/Vertex.java (limited to 'src/main/java/com.example.portfolio3') diff --git a/src/main/java/com.example.portfolio3/com/example/portfolio3/AbstractGraph.java b/src/main/java/com.example.portfolio3/com/example/portfolio3/AbstractGraph.java new file mode 100644 index 0000000..c2cf433 --- /dev/null +++ b/src/main/java/com.example.portfolio3/com/example/portfolio3/AbstractGraph.java @@ -0,0 +1,52 @@ +package com.example.portfolio3; + +// origin: + +import java.util.*; + +/// foo +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(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(String v, String u, 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/main/java/com.example.portfolio3/com/example/portfolio3/AdjListGraph.java b/src/main/java/com.example.portfolio3/com/example/portfolio3/AdjListGraph.java new file mode 100644 index 0000000..a677d3e --- /dev/null +++ b/src/main/java/com.example.portfolio3/com/example/portfolio3/AdjListGraph.java @@ -0,0 +1,47 @@ +package com.example.portfolio3; + +// origin: + +import java.util.*; + +/// 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(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); + } + + /// foo + public Collection edges(){ + Set edges=new HashSet<>(); + for(Vertex v:outEdge.keySet())edges.addAll(outEdge.get(v)); + return edges; + } + + /// foo + public Collection outEdge(Vertex v){ + if(!outEdge.containsKey(v)) + return new HashSet(); + return outEdge.get(v); + } + + /// foo + 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; + } +} diff --git a/src/main/java/com.example.portfolio3/com/example/portfolio3/AdjMapGraph.java b/src/main/java/com.example.portfolio3/com/example/portfolio3/AdjMapGraph.java new file mode 100644 index 0000000..85e5d04 --- /dev/null +++ b/src/main/java/com.example.portfolio3/com/example/portfolio3/AdjMapGraph.java @@ -0,0 +1,45 @@ +package com.example.portfolio3; + +// origin: + +import java.util.*; + +/// 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(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); + } + + /// 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(Vertex v) { + return outEdge.get(v).values(); + } + + /// foo + 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(); + } +} diff --git a/src/main/java/com.example.portfolio3/com/example/portfolio3/Edge.java b/src/main/java/com.example.portfolio3/com/example/portfolio3/Edge.java new file mode 100644 index 0000000..abc3c72 --- /dev/null +++ b/src/main/java/com.example.portfolio3/com/example/portfolio3/Edge.java @@ -0,0 +1,37 @@ +package com.example.portfolio3; + +// origin: + +import java.util.*; + +/// foo +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(Vertex from,Vertex to,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/main/java/com.example.portfolio3/com/example/portfolio3/EdgeGraph.java b/src/main/java/com.example.portfolio3/com/example/portfolio3/EdgeGraph.java new file mode 100644 index 0000000..ae9cbe9 --- /dev/null +++ b/src/main/java/com.example.portfolio3/com/example/portfolio3/EdgeGraph.java @@ -0,0 +1,37 @@ +package com.example.portfolio3; + +// origin: + +/// 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(Vertex v1,Vertex v2,int w){ + edges.add(new Edge(v1,v2,w)); + } + + /// foo + public Collection edges(){return edges;} + + /// foo + public Collection outEdge(Vertex v){ + ArrayList outEdge=new ArrayList<>(); + for(Edge e:edges)if(e.from()==v)outEdge.add(e); + return outEdge; + } + + /// foo + 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; + } +} diff --git a/src/main/java/com.example.portfolio3/com/example/portfolio3/Graph.java b/src/main/java/com.example.portfolio3/com/example/portfolio3/Graph.java new file mode 100644 index 0000000..6e58029 --- /dev/null +++ b/src/main/java/com.example.portfolio3/com/example/portfolio3/Graph.java @@ -0,0 +1,34 @@ +package com.example.portfolio3; + +// origin: + +import java.util.*; + +/// 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); +} diff --git a/src/main/java/com.example.portfolio3/com/example/portfolio3/GraphAlgorithms.java b/src/main/java/com.example.portfolio3/com/example/portfolio3/GraphAlgorithms.java new file mode 100644 index 0000000..3be7c70 --- /dev/null +++ b/src/main/java/com.example.portfolio3/com/example/portfolio3/GraphAlgorithms.java @@ -0,0 +1,331 @@ +package com.example.portfolio3; + +// origin: + +import java.io.*; +import java.util.*; + +/// 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(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(List edges){ + for(int i=1;i path){ + int length=0; + for(int i=1;i + static List sortEdges(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(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(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 + static List sortVertex(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(Graph g,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(Graph g,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(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); + } + + /// an implementation of Prim's algorithm + /// naive implementation without priorityqueue + /// @param g foo + /// @return Set + public static Set minimumSpanningTree(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(Graph g, 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(Graph g, 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(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(List list,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(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/main/java/com.example.portfolio3/com/example/portfolio3/Graphs.java b/src/main/java/com.example.portfolio3/com/example/portfolio3/Graphs.java new file mode 100644 index 0000000..2975e44 --- /dev/null +++ b/src/main/java/com.example.portfolio3/com/example/portfolio3/Graphs.java @@ -0,0 +1,13 @@ +package com.example.portfolio3; + +// origin: + +import java.util.*; + +/// foo +public class Graphs { + + /// foo + Graphs() {} + +} diff --git a/src/main/java/com.example.portfolio3/com/example/portfolio3/MatrixGraph.java b/src/main/java/com.example.portfolio3/com/example/portfolio3/MatrixGraph.java new file mode 100644 index 0000000..29005b7 --- /dev/null +++ b/src/main/java/com.example.portfolio3/com/example/portfolio3/MatrixGraph.java @@ -0,0 +1,77 @@ +package com.example.portfolio3; + +// origin: + +import java.util.*; + +/// 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(int numVertex){ + this.numVertex=numVertex; + matrix =new Integer[numVertex][numVertex]; + index2vertex=new Vertex[numVertex]; + } + + /// foo + /// @param v vertex + /// @return int + 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; + } + + /// foo + public void insertEdge(Vertex v1,Vertex v2,int w){ + matrix[getIndex(v1)][getIndex(v2)] = w; + } + + /// foo + 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 + +import java.util.*; + +/// foo +public class Vertex{ + + /// foo + private String name; + + /// foo + /// @return String + public String name(){return name;} + + /// foo + /// @param s foo + public Vertex(String s){name=s;} + + /// foo + /// @return String + public String toString(){return name;} +} -- cgit v1.2.3