path: root/com/example/portfolio3/Graphs.java

package com.example.portfolio3;

// origin: <https://moodle.ruc.dk/course/section.php?id=211877>

import java.util.*;

/// foo
public class Graphs {

  /// foo
  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)];}
}