From 79e04705c6eeed95992e5753a8328aad90e02f68 Mon Sep 17 00:00:00 2001
From: Jonas Smedegaard <dr@jones.dk>
Date: Sun, 20 Apr 2025 19:39:42 +0200
Subject: move each auxiliary class to own file, to please javadoc
---
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/Graphs.java | 324 ------------------------------
com/example/portfolio3/MatrixGraph.java | 77 +++++++
com/example/portfolio3/Vertex.java | 24 +++
9 files changed, 353 insertions(+), 324 deletions(-)
create mode 100644 com/example/portfolio3/AbstractGraph.java
create mode 100644 com/example/portfolio3/AdjListGraph.java
create mode 100644 com/example/portfolio3/AdjMapGraph.java
create mode 100644 com/example/portfolio3/Edge.java
create mode 100644 com/example/portfolio3/EdgeGraph.java
create mode 100644 com/example/portfolio3/Graph.java
create mode 100644 com/example/portfolio3/MatrixGraph.java
create mode 100644 com/example/portfolio3/Vertex.java
(limited to 'com/example/portfolio3')
diff --git a/com/example/portfolio3/AbstractGraph.java b/com/example/portfolio3/AbstractGraph.java
new file mode 100644
index 0000000..c2cf433
--- /dev/null
+++ b/com/example/portfolio3/AbstractGraph.java
@@ -0,0 +1,52 @@
+package com.example.portfolio3;
+
+// origin: <https://moodle.ruc.dk/course/section.php?id=211877>
+
+import java.util.*;
+
+/// foo
+abstract class AbstractGraph implements Graph{
+
+ /// foo
+ AbstractGraph() {}
+
+ /// 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);
+ 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<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);
+}
diff --git a/com/example/portfolio3/AdjListGraph.java b/com/example/portfolio3/AdjListGraph.java
new file mode 100644
index 0000000..416f646
--- /dev/null
+++ b/com/example/portfolio3/AdjListGraph.java
@@ -0,0 +1,47 @@
+package com.example.portfolio3;
+
+// origin: <https://moodle.ruc.dk/course/section.php?id=211877>
+
+import java.util.*;
+
+/// Adjecency List Graph - A map from vertices to set of outedges from the vertex
+class AdjListGraph extends AbstractGraph {
+
+ /// foo
+ AdjListGraph() {}
+
+ /// 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;
+ for(Edge e:outEdge.get(v1)){
+ if(e.to()==v2)return e.weight();
+ }
+ return null;
+ }
+}
diff --git a/com/example/portfolio3/AdjMapGraph.java b/com/example/portfolio3/AdjMapGraph.java
new file mode 100644
index 0000000..85e5d04
--- /dev/null
+++ b/com/example/portfolio3/AdjMapGraph.java
@@ -0,0 +1,45 @@
+package com.example.portfolio3;
+
+// origin: <https://moodle.ruc.dk/course/section.php?id=211877>
+
+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<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())
+ for (Vertex w : outEdge.get(v).keySet())
+ 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;
+ if(!outEdge.get(v1).containsKey(v2))return null;
+ return outEdge.get(v1).get(v2).weight();
+ }
+}
diff --git a/com/example/portfolio3/Edge.java b/com/example/portfolio3/Edge.java
new file mode 100644
index 0000000..abc3c72
--- /dev/null
+++ b/com/example/portfolio3/Edge.java
@@ -0,0 +1,37 @@
+package com.example.portfolio3;
+
+// origin: <https://moodle.ruc.dk/course/section.php?id=211877>
+
+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/com/example/portfolio3/EdgeGraph.java b/com/example/portfolio3/EdgeGraph.java
new file mode 100644
index 0000000..ae9cbe9
--- /dev/null
+++ b/com/example/portfolio3/EdgeGraph.java
@@ -0,0 +1,37 @@
+package com.example.portfolio3;
+
+// origin: <https://moodle.ruc.dk/course/section.php?id=211877>
+
+/// EdgeGraph - One big set of all edges in the graph
+class EdgeGraph extends AbstractGraph {
+
+ /// foo
+ EdgeGraph() {}
+
+ /// 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){
+ if(e.from()==v1 && e.to()==v2)return e.weight();
+ }
+ return null;
+ }
+}
diff --git a/com/example/portfolio3/Graph.java b/com/example/portfolio3/Graph.java
new file mode 100644
index 0000000..750f996
--- /dev/null
+++ b/com/example/portfolio3/Graph.java
@@ -0,0 +1,34 @@
+package com.example.portfolio3;
+
+// origin: <https://moodle.ruc.dk/course/section.php?id=211877>
+
+import java.util.*;
+
+/// 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);
+}
diff --git a/com/example/portfolio3/Graphs.java b/com/example/portfolio3/Graphs.java
index d1ffc9d..2975e44 100644
--- a/com/example/portfolio3/Graphs.java
+++ b/com/example/portfolio3/Graphs.java
@@ -11,327 +11,3 @@ public class Graphs {
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
- AbstractGraph() {}
-
- /// 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);
- 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<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
-class EdgeGraph extends AbstractGraph {
-
- /// foo
- EdgeGraph() {}
-
- /// 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){
- 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
-
-/// foo
-class AdjListGraph extends AbstractGraph {
-
- /// foo
- AdjListGraph() {}
-
- /// 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;
- 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
-
-/// foo
-class AdjMapGraph extends AbstractGraph {
-
- /// foo
- AdjMapGraph() {}
-
- /// 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())
- for (Vertex w : outEdge.get(v).keySet())
- 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;
- if(!outEdge.get(v1).containsKey(v2))return null;
- return outEdge.get(v1).get(v2).weight();
- }
-}
-
-//--------------------------------------------------------
-// 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
-
- /// 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();
- 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<Edge> edges(){
- HashSet<Edge> 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<Edge> outEdge(Vertex v1){
- HashSet<Edge> 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(Vertex v1,Vertex v2){
- // constant time operation
- return matrix[vertex2index.get(v1)][vertex2index.get(v2)];}
-}
diff --git a/com/example/portfolio3/MatrixGraph.java b/com/example/portfolio3/MatrixGraph.java
new file mode 100644
index 0000000..f3a5bde
--- /dev/null
+++ b/com/example/portfolio3/MatrixGraph.java
@@ -0,0 +1,77 @@
+package com.example.portfolio3;
+
+// origin: <https://moodle.ruc.dk/course/section.php?id=211877>
+
+import java.util.*;
+
+/// Matrix Graph: weights are stored in a twodimensional array
+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
+
+ /// 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();
+ 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<Edge> edges(){
+ HashSet<Edge> 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<Edge> outEdge(Vertex v1){
+ HashSet<Edge> 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(Vertex v1,Vertex v2){
+ // constant time operation
+ return matrix[vertex2index.get(v1)][vertex2index.get(v2)];}
+}
diff --git a/com/example/portfolio3/Vertex.java b/com/example/portfolio3/Vertex.java
new file mode 100644
index 0000000..efc739c
--- /dev/null
+++ b/com/example/portfolio3/Vertex.java
@@ -0,0 +1,24 @@
+package com.example.portfolio3;
+
+// origin: <https://moodle.ruc.dk/course/section.php?id=211877>
+
+import java.util.*;
+
+/// 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;}
+}
--
cgit v1.2.3