aboutsummaryrefslogtreecommitdiff
path: root/com
diff options
context:
space:
mode:
Diffstat (limited to 'com')
-rw-r--r--com/example/portfolio3/GraphAlgorithms.java121
-rw-r--r--com/example/portfolio3/Graphs.java145
2 files changed, 231 insertions, 35 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));
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: <https://moodle.ruc.dk/course/section.php?id=211877>
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<Vertex> vertices();
+
+ /// foo
+ /// @return Collection
Collection<Edge> edges();
+
+ /// foo
+ /// @param v foo
+ /// @return Collection
Collection<Edge> 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<String,Vertex> vertexMap=new HashMap<>();
+
+ /// foo
private HashSet<Vertex> 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<Vertex> 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<Edge> edges();
+
+ /// foo
abstract public Collection<Edge> 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<Edge> edges=new HashSet<>();
+
+ /// foo
public void insertEdge(Vertex v1,Vertex v2,int w){
edges.add(new Edge(v1,v2,w));
}
+
+ /// foo
public Collection<Edge> edges(){return edges;}
+
+ /// foo
public Collection<Edge> outEdge(Vertex v){
ArrayList<Edge> 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<Vertex,Set<Edge>> 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<Edge>());
outEdge.get(e.from()).add(e);
}
+
+ /// foo
public Collection<Edge> edges(){
Set<Edge> edges=new HashSet<>();
for(Vertex v:outEdge.keySet())edges.addAll(outEdge.get(v));
return edges;
}
+
+ /// foo
public Collection<Edge> outEdge(Vertex v){
if(!outEdge.containsKey(v))
return new HashSet<Edge>();
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<Vertex, Map<Vertex, Edge>> 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<Vertex, Edge>());
outEdge.get(e.from()).put(e.to(), e);
}
+
+ /// foo
public Collection<Edge> edges() {
Set<Edge> 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<Edge> 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<Vertex,Integer> 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<Edge> edges(){
HashSet<Edge> edges=new HashSet<>();
for(int i=0;i<numVertex;i++){
@@ -169,6 +300,8 @@ class MatrixGraph extends AbstractGraph {
}
return edges;
}
+
+ /// foo
public Collection<Edge> outEdge(Vertex v1){
HashSet<Edge> 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)];}
generated by cgit v1.2.3 (git 2.46.0) at 2025-05-08 20:55:02 +0000