From a5e648d8e1f17b4a5302182980077efdcff80c57 Mon Sep 17 00:00:00 2001 From: Jonas Smedegaard <dr@jones.dk> Date: Sun, 20 Apr 2025 18:26:01 +0200 Subject: fix newlines --- com/example/portfolio3/GraphAlgorithms.java | 526 ++++++++++++++-------------- com/example/portfolio3/Graphs.java | 362 +++++++++---------- 2 files changed, 444 insertions(+), 444 deletions(-) (limited to 'com/example/portfolio3') diff --git a/com/example/portfolio3/GraphAlgorithms.java b/com/example/portfolio3/GraphAlgorithms.java index fdf6def..c794bc5 100644 --- a/com/example/portfolio3/GraphAlgorithms.java +++ b/com/example/portfolio3/GraphAlgorithms.java @@ -1,263 +1,263 @@ -import java.io.*; -import java.util.*; - -public class GraphAlgorithms { - 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(); - } - - 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; - } - - 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)); - if(w==null)return null; - length+=w; - } - return length; - } - - //------------------------------------------------------------ - // - // Comparators and sorting methods - - 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()); - } - 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()); - } - 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; - } - - 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; - } - 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; - } - 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; - } - - 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; - } - - //------------------------------------------------------------ - // - // Algorithms for traverse and minimum spanning tree - - 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<>(); - thisLevel.add(v); - while(thisLevel.size()>0){ - System.out.println("level "+thisLevel); - for(Vertex w:thisLevel){ - //System.out.println("visited "+w); - visited.add(w); - Collection<Edge> outedge=g.outEdge(w); - if(outedge==null)continue; - for(Edge e: outedge){ - if(visited.contains(e.to()))continue; - if(thisLevel.contains(e.to()))continue; - nextLevel.add(e.to()); - } - } - thisLevel=nextLevel; - nextLevel=new HashSet<Vertex>(); - } - return visited; - } - - 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; - } - - private static void visitDepthFirst(Graph g,Vertex v,Set<Vertex> visited){ - if(visited.contains(v))return; - //System.out.println("visited "+v); - visited.add(v); - for(Edge e: g.outEdge(v)) - visitDepthFirst(g,e.to(),visited); - } - - 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<>(); - for(Edge e:edges){frontier.add(e.from());break;} - while(true) { - Edge nearest = null; - for (Edge e : edges) { - if (!frontier.contains(e.from())) continue; - if (frontier.contains(e.to())) continue; - if (nearest == null || nearest.weight() > e.weight()) - nearest = e; - } - if(nearest==null)break; - mst.add(nearest); - frontier.add(nearest.to()); - } - return mst; - } - - 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<>(); - HashMap<Vertex,Edge> prev=new HashMap<>(); - HashMap<Vertex,Integer> weight=new HashMap<>(); - for(Vertex w:g.vertices())weight.put(w,maxint); - // start node is done, distance 0 from start - weight.put(start,0); - done.add(start); - - while(true){ - // find nearest from a done vertex - Vertex nearest = null; - int neardist = maxint; - Edge done2near=null; - for(Vertex w1:done){ - for (Edge e : g.outEdge(w1)) { - Vertex w2 = e.to(); - if (done.contains(w2)) continue; - if ((weight.get(w1) + e.weight()) < neardist) { - nearest = e.to(); - neardist = weight.get(w1) + e.weight(); - done2near = e; - } - } - } - // System.out.println("find nearest "+done2near); - // if no more, then we are done - if (nearest == null) break; - // update distance from this node to other nodes - for (Edge e1 : g.outEdge(nearest)) { - Vertex w3 = e1.to(); - int wght = e1.weight(); - if (weight.get(w3) > (neardist + wght)) { - weight.put(w3, neardist + wght); - } - } - done.add(nearest); - prev.put(nearest,done2near); - weight.put(nearest,neardist); - } - return new HashSet<Edge>(prev.values()); - } - - //------------------------------------------------------------ - // - // IO operations - - 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()) { - if(line.length()==0) continue; - String[] arr = line.split(","); - if(arr.length!=3) throw new RuntimeException("CSV file format error: "+line); - g.insertEdge(arr[0].trim(), arr[1].trim(), Integer.parseInt(arr[2].trim())); - g.insertEdge(arr[1].trim(), arr[0].trim(), Integer.parseInt(arr[2].trim())); - } - in.close(); - }catch(IOException e){ - throw new RuntimeException(e); - } - } - - static void printGraph(Graph g) { - for(Vertex v: sortVertex(g.vertices())) { - System.out.println(v.toString()); - for(Edge e:sortEdgesTo(g.outEdge(v))) - System.out.println(" "+e.toString()); - } - } - - 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){ - out.println(s); - } - out.close(); - }catch(IOException e){ - throw new RuntimeException(e); - } - } - - 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)); - while(true){ - String s=in.readLine(); - if(s==null)break; - list.add(s); - } - in.close(); - }catch(IOException e){ - throw new RuntimeException(e); - } - return list; - } -} +import java.io.*; +import java.util.*; + +public class GraphAlgorithms { + 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(); + } + + 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; + } + + 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)); + if(w==null)return null; + length+=w; + } + return length; + } + + //------------------------------------------------------------ + // + // Comparators and sorting methods + + 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()); + } + 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()); + } + 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; + } + + 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; + } + 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; + } + 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; + } + + 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; + } + + //------------------------------------------------------------ + // + // Algorithms for traverse and minimum spanning tree + + 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<>(); + thisLevel.add(v); + while(thisLevel.size()>0){ + System.out.println("level "+thisLevel); + for(Vertex w:thisLevel){ + //System.out.println("visited "+w); + visited.add(w); + Collection<Edge> outedge=g.outEdge(w); + if(outedge==null)continue; + for(Edge e: outedge){ + if(visited.contains(e.to()))continue; + if(thisLevel.contains(e.to()))continue; + nextLevel.add(e.to()); + } + } + thisLevel=nextLevel; + nextLevel=new HashSet<Vertex>(); + } + return visited; + } + + 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; + } + + private static void visitDepthFirst(Graph g,Vertex v,Set<Vertex> visited){ + if(visited.contains(v))return; + //System.out.println("visited "+v); + visited.add(v); + for(Edge e: g.outEdge(v)) + visitDepthFirst(g,e.to(),visited); + } + + 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<>(); + for(Edge e:edges){frontier.add(e.from());break;} + while(true) { + Edge nearest = null; + for (Edge e : edges) { + if (!frontier.contains(e.from())) continue; + if (frontier.contains(e.to())) continue; + if (nearest == null || nearest.weight() > e.weight()) + nearest = e; + } + if(nearest==null)break; + mst.add(nearest); + frontier.add(nearest.to()); + } + return mst; + } + + 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<>(); + HashMap<Vertex,Edge> prev=new HashMap<>(); + HashMap<Vertex,Integer> weight=new HashMap<>(); + for(Vertex w:g.vertices())weight.put(w,maxint); + // start node is done, distance 0 from start + weight.put(start,0); + done.add(start); + + while(true){ + // find nearest from a done vertex + Vertex nearest = null; + int neardist = maxint; + Edge done2near=null; + for(Vertex w1:done){ + for (Edge e : g.outEdge(w1)) { + Vertex w2 = e.to(); + if (done.contains(w2)) continue; + if ((weight.get(w1) + e.weight()) < neardist) { + nearest = e.to(); + neardist = weight.get(w1) + e.weight(); + done2near = e; + } + } + } + // System.out.println("find nearest "+done2near); + // if no more, then we are done + if (nearest == null) break; + // update distance from this node to other nodes + for (Edge e1 : g.outEdge(nearest)) { + Vertex w3 = e1.to(); + int wght = e1.weight(); + if (weight.get(w3) > (neardist + wght)) { + weight.put(w3, neardist + wght); + } + } + done.add(nearest); + prev.put(nearest,done2near); + weight.put(nearest,neardist); + } + return new HashSet<Edge>(prev.values()); + } + + //------------------------------------------------------------ + // + // IO operations + + 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()) { + if(line.length()==0) continue; + String[] arr = line.split(","); + if(arr.length!=3) throw new RuntimeException("CSV file format error: "+line); + g.insertEdge(arr[0].trim(), arr[1].trim(), Integer.parseInt(arr[2].trim())); + g.insertEdge(arr[1].trim(), arr[0].trim(), Integer.parseInt(arr[2].trim())); + } + in.close(); + }catch(IOException e){ + throw new RuntimeException(e); + } + } + + static void printGraph(Graph g) { + for(Vertex v: sortVertex(g.vertices())) { + System.out.println(v.toString()); + for(Edge e:sortEdgesTo(g.outEdge(v))) + System.out.println(" "+e.toString()); + } + } + + 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){ + out.println(s); + } + out.close(); + }catch(IOException e){ + throw new RuntimeException(e); + } + } + + 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)); + while(true){ + String s=in.readLine(); + if(s==null)break; + list.add(s); + } + in.close(); + }catch(IOException e){ + throw new RuntimeException(e); + } + return list; + } +} diff --git a/com/example/portfolio3/Graphs.java b/com/example/portfolio3/Graphs.java index 54cad9e..e0fb381 100644 --- a/com/example/portfolio3/Graphs.java +++ b/com/example/portfolio3/Graphs.java @@ -1,181 +1,181 @@ -import java.util.*; -public class Graphs {} - -class Vertex{ - private String name; - public String name(){return name;} - public Vertex(String s){name=s;} - public String toString(){return name;} -} -class Edge{ - private Vertex from,to; - private int weight; - public Vertex from(){return from;} - public Vertex to(){return to;} - public int weight(){return weight;} - Edge(Vertex from,Vertex to,int w){this.from=from; this.to=to; weight=w;} - public String toString(){return from.name()+" - "+weight+" -> "+to.name(); } -} -interface Graph { - void insertEdge(String v, String u, int w); - Collection<Vertex> vertices(); - Collection<Edge> edges(); - Collection<Edge> outEdge(Vertex v); - Integer getWeight(Vertex v1, Vertex v2); -} - -abstract class AbstractGraph implements Graph{ - private HashMap<String,Vertex> vertexMap=new HashMap<>(); - private HashSet<Vertex> vertexSet=new HashSet<>(); - 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; - } - public void insertEdge(String v, String u, int w){ - insertEdge(vertex(v),vertex(u),w); - } - public Collection<Vertex> vertices() { return vertexSet; } - // - abstract public void insertEdge(Vertex v1, Vertex v2, int w); - abstract public Collection<Edge> edges(); - abstract public Collection<Edge> outEdge(Vertex v); - abstract public Integer getWeight(Vertex v1, Vertex v2); -} - -//-------------------------------------------------------- -// EdgeGraph - One big set of all edges in the graph - -class EdgeGraph extends AbstractGraph { - Set<Edge> edges=new HashSet<>(); - public void insertEdge(Vertex v1,Vertex v2,int w){ - edges.add(new Edge(v1,v2,w)); - } - public Collection<Edge> edges(){return edges;} - public Collection<Edge> outEdge(Vertex v){ - ArrayList<Edge> outEdge=new ArrayList<>(); - for(Edge e:edges)if(e.from()==v)outEdge.add(e); - return outEdge; - } - 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 - -class AdjListGraph extends AbstractGraph { - private Map<Vertex,Set<Edge>> outEdge= new HashMap<>(); - 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); - } - public Collection<Edge> edges(){ - Set<Edge> edges=new HashSet<>(); - for(Vertex v:outEdge.keySet())edges.addAll(outEdge.get(v)); - return edges; - } - public Collection<Edge> outEdge(Vertex v){ - if(!outEdge.containsKey(v)) - return new HashSet<Edge>(); - return outEdge.get(v); - } - 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 - -class AdjMapGraph extends AbstractGraph { - private Map<Vertex, Map<Vertex, Edge>> outEdge = new HashMap<>(); - - 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); - } - 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; - } - public Collection<Edge> outEdge(Vertex v) { - return outEdge.get(v).values(); - } - 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 - -class MatrixGraph extends AbstractGraph { - private Integer[][] matrix=null; // made in constructor - // We must be able to map vertices to index in matrix and back again - private Vertex[] index2vertex; // made in constructor - private Map<Vertex,Integer> vertex2index=new HashMap<>(); - private int numVertex; // maximum number of vertices - MatrixGraph(int numVertex){ // maximum number of vertices allowed - this.numVertex=numVertex; - matrix =new Integer[numVertex][numVertex]; - index2vertex=new Vertex[numVertex]; - } - 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; - } - public void insertEdge(Vertex v1,Vertex v2,int w){ - matrix[getIndex(v1)][getIndex(v2)] = w; - } - 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; - } - 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; - } - public Integer getWeight(Vertex v1,Vertex v2){ - // constant time operation - return matrix[vertex2index.get(v1)][vertex2index.get(v2)];} -} +import java.util.*; +public class Graphs {} + +class Vertex{ + private String name; + public String name(){return name;} + public Vertex(String s){name=s;} + public String toString(){return name;} +} +class Edge{ + private Vertex from,to; + private int weight; + public Vertex from(){return from;} + public Vertex to(){return to;} + public int weight(){return weight;} + Edge(Vertex from,Vertex to,int w){this.from=from; this.to=to; weight=w;} + public String toString(){return from.name()+" - "+weight+" -> "+to.name(); } +} +interface Graph { + void insertEdge(String v, String u, int w); + Collection<Vertex> vertices(); + Collection<Edge> edges(); + Collection<Edge> outEdge(Vertex v); + Integer getWeight(Vertex v1, Vertex v2); +} + +abstract class AbstractGraph implements Graph{ + private HashMap<String,Vertex> vertexMap=new HashMap<>(); + private HashSet<Vertex> vertexSet=new HashSet<>(); + 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; + } + public void insertEdge(String v, String u, int w){ + insertEdge(vertex(v),vertex(u),w); + } + public Collection<Vertex> vertices() { return vertexSet; } + // + abstract public void insertEdge(Vertex v1, Vertex v2, int w); + abstract public Collection<Edge> edges(); + abstract public Collection<Edge> outEdge(Vertex v); + abstract public Integer getWeight(Vertex v1, Vertex v2); +} + +//-------------------------------------------------------- +// EdgeGraph - One big set of all edges in the graph + +class EdgeGraph extends AbstractGraph { + Set<Edge> edges=new HashSet<>(); + public void insertEdge(Vertex v1,Vertex v2,int w){ + edges.add(new Edge(v1,v2,w)); + } + public Collection<Edge> edges(){return edges;} + public Collection<Edge> outEdge(Vertex v){ + ArrayList<Edge> outEdge=new ArrayList<>(); + for(Edge e:edges)if(e.from()==v)outEdge.add(e); + return outEdge; + } + 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 + +class AdjListGraph extends AbstractGraph { + private Map<Vertex,Set<Edge>> outEdge= new HashMap<>(); + 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); + } + public Collection<Edge> edges(){ + Set<Edge> edges=new HashSet<>(); + for(Vertex v:outEdge.keySet())edges.addAll(outEdge.get(v)); + return edges; + } + public Collection<Edge> outEdge(Vertex v){ + if(!outEdge.containsKey(v)) + return new HashSet<Edge>(); + return outEdge.get(v); + } + 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 + +class AdjMapGraph extends AbstractGraph { + private Map<Vertex, Map<Vertex, Edge>> outEdge = new HashMap<>(); + + 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); + } + 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; + } + public Collection<Edge> outEdge(Vertex v) { + return outEdge.get(v).values(); + } + 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 + +class MatrixGraph extends AbstractGraph { + private Integer[][] matrix=null; // made in constructor + // We must be able to map vertices to index in matrix and back again + private Vertex[] index2vertex; // made in constructor + private Map<Vertex,Integer> vertex2index=new HashMap<>(); + private int numVertex; // maximum number of vertices + MatrixGraph(int numVertex){ // maximum number of vertices allowed + this.numVertex=numVertex; + matrix =new Integer[numVertex][numVertex]; + index2vertex=new Vertex[numVertex]; + } + 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; + } + public void insertEdge(Vertex v1,Vertex v2,int w){ + matrix[getIndex(v1)][getIndex(v2)] = w; + } + 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; + } + 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; + } + public Integer getWeight(Vertex v1,Vertex v2){ + // constant time operation + return matrix[vertex2index.get(v1)][vertex2index.get(v2)];} +} -- cgit v1.2.3