aboutsummaryrefslogtreecommitdiff
path: root/com/example/portfolio3/Graphs.java
diff options
context:
space:
mode:
Diffstat (limited to 'com/example/portfolio3/Graphs.java')
-rw-r--r--com/example/portfolio3/Graphs.java145
1 files changed, 140 insertions, 5 deletions
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:37:18 +0000