From 3481a2467a1f93ccf6de85d7df9d8abe54065dd1 Mon Sep 17 00:00:00 2001 From: Jonas Smedegaard Date: Sun, 20 Apr 2025 19:17:21 +0200 Subject: add minimal comments to please javadoc --- com/example/portfolio3/GraphAlgorithms.java | 121 +++++++++++++++++------ com/example/portfolio3/Graphs.java | 145 +++++++++++++++++++++++++++- 2 files changed, 231 insertions(+), 35 deletions(-) (limited to 'com/example/portfolio3') 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 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 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 static List sortEdges(Collection edges){ - // sort a collection of edges based on their weights 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){ - // sort a collection of edges based on from-vertex 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){ - // sort a collection of edges based on to-vertex 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){ - // 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; @@ -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 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<>(); @@ -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 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; } + /// 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); @@ -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 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<>(); @@ -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 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<>(); @@ -208,10 +260,13 @@ public class GraphAlgorithms { // // 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) { - // 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()) { @@ -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 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 loadStrings(String f){ - // read a file a returns a list of lines ArrayList list=new ArrayList<>(); try{ BufferedReader in=new BufferedReader(new FileReader(f)); diff --git a/com/example/portfolio3/Graphs.java b/com/example/portfolio3/Graphs.java index 2d82120..639c4fd 100644 --- a/com/example/portfolio3/Graphs.java +++ b/com/example/portfolio3/Graphs.java @@ -3,34 +3,102 @@ package com.example.portfolio3; // origin: import java.util.*; + +/// foo public class Graphs {} +/// foo 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;} } + +/// 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(); } } + +/// foo 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 abstract class AbstractGraph implements Graph{ + + /// 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); @@ -38,31 +106,53 @@ abstract class AbstractGraph implements Graph{ 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); } -//-------------------------------------------------------- -// EdgeGraph - One big set of all edges in the graph - +/// EdgeGraph - One big set of all edges in the graph class EdgeGraph extends AbstractGraph { + + /// 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){ @@ -75,24 +165,35 @@ class EdgeGraph extends AbstractGraph { //-------------------------------------------------------- // Adjecency List Graph - A map from vertices to set of outedges from the vertex +/// foo class AdjListGraph extends AbstractGraph { + + /// 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; @@ -106,15 +207,21 @@ class AdjListGraph extends AbstractGraph { //-------------------------------------------------------- // Adjecency Map Graph - A map from vertices to map of target vertex to edge +/// foo class AdjMapGraph extends AbstractGraph { + + /// 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()) @@ -122,9 +229,13 @@ class AdjMapGraph extends AbstractGraph { 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; @@ -136,17 +247,33 @@ class AdjMapGraph extends AbstractGraph { //-------------------------------------------------------- // Matrix Graph: weights are stored in a twodimensional array +/// foo 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 - MatrixGraph(int numVertex){ // maximum number of vertices allowed + + /// foo + /// @param numVertex maximum number of vertices allowed + 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(); @@ -155,9 +282,13 @@ class MatrixGraph extends AbstractGraph { 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); @@ -179,6 +312,8 @@ class MatrixGraph extends AbstractGraph { } return edges; } + + /// foo public Integer getWeight(Vertex v1,Vertex v2){ // constant time operation return matrix[vertex2index.get(v1)][vertex2index.get(v2)];} -- cgit v1.2.3