SHARE
TWEET

Untitled

a guest Dec 8th, 2019 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Creates an adjacency list graph/
  3.  *
  4.  * @author Kathryn Swint
  5.  * @version 12/04/2019
  6.  */
  7. package javafoundations;
  8.  
  9. import java.util.*;
  10. import java.io.*;
  11. import java.lang.StackOverflowError;
  12. import java.text.Format;
  13. import javafoundations.exceptions.*;
  14. import java.lang.reflect.Array;
  15.  
  16. public class AdjListsGraph<T> implements Graph<T>{
  17.     // instance variables
  18.     protected Vector<T> vertices;
  19.     protected Vector<LinkedList<T>> arcs;
  20.  
  21.     /**
  22.      * Constructor for objects of class AdjListsGraph
  23.      */
  24.     public AdjListsGraph()
  25.     {
  26.         vertices = new Vector<T>();
  27.         arcs = new Vector<LinkedList<T>>();
  28.     }
  29.  
  30.     /**
  31.      * Determines whether a graph is empty
  32.      *
  33.      * @return a boolean indicating whether the graph is empty
  34.      */
  35.     public boolean isEmpty()
  36.     {
  37.         return vertices.size() == 0;
  38.     }
  39.  
  40.     /**
  41.      * Checks the number of vertices in the graph.
  42.      *
  43.      * @return an integer representation of the number of vertices
  44.      */
  45.     public int getNumVertices() {
  46.         return vertices.size();
  47.     }
  48.  
  49.     /**
  50.      * Checks the total number of arcs in the graph.
  51.      *
  52.      * @return an integer representation of the number of arcs
  53.      */
  54.     public int getNumArcs(){
  55.         int total = 0;
  56.         for (int i = 0; i < arcs.size(); i++) {
  57.             total += arcs.get(i).size();
  58.         }
  59.         return total;
  60.     }
  61.  
  62.     /**
  63.      * Determines whether two vertices are connected by an arc.
  64.      *
  65.      * @returns boolean indicating whether the two vertices are connected
  66.      */
  67.     public boolean isArc(T v1, T v2){
  68.         boolean connected;
  69.         if (vertices.contains(v1) && vertices.contains(v2)) {
  70.             int origin = vertices.indexOf(v1); //beginning vertex
  71.             int destination = vertices.indexOf(v2); //vertex to connect to
  72.             connected = arcs.get(origin).contains(v2); //checks if they're connected
  73.         } else {
  74.             connected = false;
  75.             System.out.println("Tried to add edge to one or more vertex that doesn't exist.");
  76.         }
  77.         return connected;
  78.     }
  79.  
  80.     /**
  81.      * Determines whether two vertices are connected by an edge.
  82.      *
  83.      * @returns boolean indicating whether the two vertices are connected by an edge
  84.      */
  85.     public boolean isEdge(T v1, T v2){
  86.         return (isArc(v1, v2) && isArc(v2, v1));
  87.     }
  88.  
  89.     /**
  90.      * Determines whether the graph is undirected.
  91.      *
  92.      * @returns boolean indicating whether the graph is undirected
  93.      */
  94.     public boolean isUndirected(){
  95.         for (int i = 0; i < arcs.size(); i++) {
  96.             LinkedList<T> current = arcs.get(i);
  97.             for (int j = 0; j < current.size(); j++) {
  98.                 // as soon as two vertices are found that are not connected by
  99.                 // an edge, returns false
  100.                 if (!isEdge(vertices.get(i), current.get(j))) {
  101.                     return false;
  102.                 }
  103.             }
  104.         }
  105.         return true;
  106.     }
  107.  
  108.     /**
  109.      * Adds a vertex to the graph
  110.      *
  111.      * @param v the vertex to be added
  112.      */
  113.     public void addVertex(T v){
  114.         if (!vertices.contains(v)) {
  115.             vertices.add(v);
  116.             LinkedList<T> vertexEdges = new LinkedList<T>();
  117.             arcs.add(vertexEdges);
  118.         }
  119.     }
  120.  
  121.     /**
  122.      * Removes a vertex from the graph
  123.      *
  124.      * @param v the vertex to be removed
  125.      */
  126.     public void removeVertex(T v){
  127.         if (vertices.contains(v)) { //checks that the vertex is in the graph
  128.             for (int i = 0; i < vertices.size(); i++) {
  129.                 // remove connections to the vertex from all other vertices
  130.                 removeArc(v, vertices.get(i));
  131.                 removeArc(vertices.get(i), v);
  132.             }
  133.             int index = vertices.indexOf(v);
  134.             vertices.remove(index);
  135.             arcs.remove(index);
  136.         } else {
  137.             System.out.println("Tried to remove vertex that doesn't exist.");
  138.         }
  139.     }
  140.  
  141.     /**
  142.      * Adds an arc between two vertices
  143.      *
  144.      * @param v1 the origin vertex
  145.      * @param v2 the destination vertex
  146.      */
  147.     public void addArc(T v1, T v2){
  148.         // checks that both vertices exist
  149.         if (vertices.contains(v1) && vertices.contains(v2)) {
  150.             int origin = vertices.indexOf(v1);
  151.             int destination = vertices.indexOf(v2);
  152.             // checks if the vertices are already connected in the specified direction
  153.             if (!arcs.get(origin).contains(v2)){
  154.                 arcs.get(origin).add(v2);
  155.             }
  156.         } else {
  157.             System.out.println("Tried to add edge to one or more vertex that doesn't exist.");
  158.         }
  159.     }
  160.  
  161.     /**
  162.      * Removes an arc between two vertices
  163.      *
  164.      * @param v1 the origin vertex
  165.      * @param v2 the destination vertex
  166.      */
  167.     public void removeArc(T v1, T v2){
  168.         // checks that both vertices exist
  169.         if (vertices.contains(v1) && vertices.contains(v2)) {
  170.             int origin = vertices.indexOf(v1);
  171.             int destination = vertices.indexOf(v2);
  172.             arcs.get(origin).remove(v2);
  173.         } else {
  174.             System.out.println("Tried to remove edge from one or more vertex that doesn't exist.");
  175.         }
  176.     }
  177.  
  178.     /**
  179.      * Adds an edge between two vertices
  180.      *
  181.      * @param v1 the first vertex
  182.      * @param v2 the second vertex
  183.      */
  184.     public void addEdge(T v1, T v2){
  185.         addArc(v1, v2);
  186.         addArc(v2, v1);
  187.     }
  188.  
  189.     /**
  190.      * Removes an edge between two vertices
  191.      *
  192.      * @param v1 the first vertex
  193.      * @param v2 the second vertex
  194.      */
  195.     public void removeEdge(T v1, T v2){
  196.         removeArc(v1, v2);
  197.         removeArc(v2, v1);
  198.     }
  199.  
  200.     /**
  201.      * Gets two levels of successors for a given vertex
  202.      *
  203.      * @return a linked list with two levels of arcs
  204.      *
  205.      * @param v the vertex to check
  206.      */
  207.     public LinkedList<T> getArcs(T v) {
  208.         LinkedList<T> allArcs = arcs.get(vertices.indexOf(v));
  209.         LinkedList<T> temp = new LinkedList<T>();
  210.         for (T vertex : allArcs) {
  211.             temp.addAll(arcs.get(vertices.indexOf(vertex)));
  212.         }
  213.         return allArcs;
  214.     }
  215.  
  216.     /**
  217.      * Returns a linked list of the successors of vertex v.
  218.      * Only checks the next level down from v.
  219.      *
  220.      * @return a linked list with the successors of v
  221.      * @param v the vertex you want the successors of
  222.      */
  223.     public LinkedList<T> getSuccessors(T v){
  224.         LinkedList<T> successors = arcs.get(vertices.indexOf(v));
  225.         return successors;
  226.     }
  227.  
  228.     /**
  229.      * Returns a linked list of the predecessors of vertex v.
  230.      * Only checks the next level up from v.
  231.      *
  232.      * @return a linked list with the predecessors of v
  233.      * @param v the vertex you want the predecessors of
  234.      */
  235.     public LinkedList<T> getPredecessors(T v){
  236.         LinkedList<T> predecessors = new LinkedList<T>();
  237.         LinkedList<T> currentSuccessors;
  238.         T currentVertex;
  239.  
  240.         for (int i = 0; i < vertices.size(); i++) {
  241.             currentVertex = vertices.get(i);
  242.             currentSuccessors = getSuccessors(currentVertex);
  243.             if (currentSuccessors.contains(v)){
  244.                 predecessors.add(currentVertex);
  245.             }
  246.         }
  247.  
  248.         return predecessors;
  249.     }
  250.  
  251.     /**
  252.      * Creates a TGF file with the vertices and arcs of this graph.
  253.      *
  254.      * @param fileName the name you want the file to be saved with
  255.      */
  256.     public void saveToTGF(String fileName){
  257.         try {
  258.             PrintWriter w = new PrintWriter(new File(fileName));
  259.             String s = "";
  260.             // prints all the vertices in the right format
  261.             for (int i = 0; i < vertices.size(); i++) {
  262.                 s += (i + 1) + " " + vertices.get(i) + "\n";
  263.             }
  264.  
  265.             s += "#";
  266.  
  267.             for (int i = 0; i < arcs.size(); i++) {
  268.                 LinkedList<T> current = arcs.get(i);
  269.                 for (T vertex : current) {
  270.                     if (isEdge(vertices.get(i), vertex)) {
  271.                         s += "\n" + i + " " + vertices.indexOf(vertex);
  272.                     }
  273.                 }
  274.             }
  275.  
  276.             w.println(s);
  277.             w.close(); //for tidiness!
  278.         }
  279.         catch (IOException e) {
  280.             System.out.println (e);
  281.         }  
  282.     }
  283.  
  284.     /**
  285.      * Performs a breadth-first traversal of the graph, beginning at the
  286.      * user-specificed vertex.
  287.      *
  288.      * @return a linked list with all vertexes visited in the traversal
  289.      * @param v the vertex you want to begin your traversal from
  290.      */
  291.     public LinkedList<T> BFtraversal(T v){
  292.         LinkedList<T> path = new LinkedList<T>();
  293.         LinkedList<T> checked = new LinkedList<T>();
  294.         LinkedList<T> current = arcs.get(vertices.indexOf(v));
  295.         LinkedQueue<T> queue = new LinkedQueue<T>();
  296.  
  297.         queue.enqueue(v);
  298.  
  299.         while (queue.size() != 0) {
  300.             if (!checked.contains(v)) {
  301.                 for (T vertex : arcs.get(vertices.indexOf(v))) {
  302.                     queue.enqueue(vertex);
  303.                 }
  304.                 checked.add(v);
  305.             }
  306.  
  307.             T currentVertex = queue.dequeue();
  308.  
  309.             if (!checked.contains(currentVertex)) {
  310.                 for (T vertex : arcs.get(vertices.indexOf(currentVertex))) {
  311.                     queue.enqueue(vertex);
  312.                 }
  313.                 checked.add(currentVertex);
  314.             }
  315.  
  316.             if (!path.contains(currentVertex)) {
  317.                 path.add(currentVertex);
  318.             }
  319.         }
  320.  
  321.         return path;
  322.     }
  323.  
  324.     /**
  325.      * Performs a depth-first traversal of the graph, beginning at the
  326.      * user-specificed vertex.
  327.      *
  328.      * @return a linked list with all vertexes visited in the traversal
  329.      * @param v the vertex you want to begin your traversal from
  330.      */
  331.     public LinkedList<T> DFtraversal(T v)
  332.     {
  333.         int startIndex = vertices.indexOf(v);
  334.         T currentVertex;
  335.         LinkedStack<T> traversalStack = new LinkedStack<T>();
  336.         ArrayIterator<T> iter = new ArrayIterator<T>();
  337.         boolean[] visited = new boolean[vertices.size()];
  338.         boolean found;
  339.         LinkedList<T> results = new LinkedList<T>();
  340.  
  341.         if (!vertices.contains(v))
  342.             return results;
  343.  
  344.         for (int vertexIdx = 0; vertexIdx < vertices.size(); vertexIdx++)
  345.             visited[vertexIdx] = false;
  346.  
  347.         traversalStack.push(vertices.get(startIndex));
  348.         iter.add(vertices.get(startIndex));
  349.         visited[startIndex] = true;
  350.  
  351.         while (!traversalStack.isEmpty()) {
  352.             currentVertex = traversalStack.peek();
  353.             found = false;
  354.             for (int vertexIdx = 0; vertexIdx < vertices.size() && !found; vertexIdx++)
  355.                 if (isArc((currentVertex),(vertices.get(vertexIdx))) && !visited [vertexIdx]) {
  356.                     traversalStack.push(vertices.get(vertexIdx));
  357.                     iter.add(vertices.get(vertexIdx));
  358.                     visited[vertexIdx] = true;
  359.                     found = true;
  360.                 }
  361.             if (!found && !traversalStack.isEmpty())
  362.                 traversalStack.pop();
  363.         }
  364.  
  365.         for (T element : iter.toArray()) {
  366.             if (element != null) {
  367.                 results.add(element);
  368.             }
  369.         }
  370.  
  371.         return results;
  372.     }
  373.  
  374.     /**
  375.      * Standard toString method
  376.      *
  377.      * @return a string representation of the graph
  378.      */
  379.     public String toString() {
  380.         String result = "Vertices:\n" + vertices + "\nEdges:\n";
  381.         for (int i = 0; i < vertices.size(); i++) {
  382.             result += "from " + vertices.get(i) + ":\t" + arcs.get(i) + "\n";
  383.         }
  384.         return result;
  385.     }
  386.  
  387.     public static void main(String args[]) {
  388.         AdjListsGraph<String> g = new AdjListsGraph<String>();
  389.  
  390.         g.addVertex("A");
  391.         g.addVertex("B");
  392.         g.addVertex("C");
  393.         g.addVertex("D");
  394.         g.addVertex("E");
  395.         g.addVertex("F");
  396.         g.addVertex("G");
  397.         g.addVertex("H");
  398.         g.addVertex("I");
  399.         g.addVertex("J");
  400.         g.addVertex("K");
  401.         g.addVertex("L");
  402.         g.addVertex("M");
  403.         g.addVertex("N");
  404.         g.addVertex("O");
  405.         g.addVertex("P");
  406.         g.addVertex("Q");
  407.         g.addVertex("R");
  408.         g.addVertex("S");
  409.         g.addVertex("T");
  410.         g.addVertex("U");
  411.         g.addVertex("V");
  412.         g.addVertex("W");
  413.         g.addVertex("X");
  414.         g.addVertex("Y");
  415.         g.addVertex("Z");
  416.         g.addVertex("1");
  417.         g.addVertex("2");
  418.         g.addVertex("3");
  419.         g.addVertex("4");
  420.         g.addVertex("5");
  421.  
  422.         // g.removeVertex("P");
  423.         // g.removeVertex("J");
  424.         // g.removeVertex("G");
  425.         // g.removeVertex("L");
  426.         // g.removeVertex("Q");
  427.         // g.removeVertex("Z");
  428.  
  429.         g.addArc("A", "B");
  430.         g.addArc("A", "C");
  431.         g.addArc("B", "D");
  432.         g.addArc("B", "E");
  433.         g.addArc("C", "F");
  434.         g.addArc("C", "G");
  435.         g.addArc("D","H");
  436.         g.addArc("D","I");
  437.         g.addArc("E","J");
  438.         g.addArc("E","K");
  439.         g.addArc("F","L");
  440.         g.addArc("F","M");
  441.         g.addArc("G","N");
  442.         g.addArc("G","O");
  443.         g.addArc("H","P");
  444.         g.addArc("H","Q");
  445.         g.addArc("I","R");
  446.         g.addArc("I","S");
  447.         g.addArc("J","T");
  448.         g.addArc("J","U");
  449.         g.addArc("K","V");
  450.         g.addArc("K","W");
  451.         g.addArc("L","X");
  452.         g.addArc("L","Y");
  453.         g.addArc("M","Z");
  454.         g.addArc("M","1");
  455.         g.addArc("N","2");
  456.         g.addArc("N","3");
  457.         g.addArc("O","4");
  458.         g.addArc("O","5");
  459.  
  460.         // g.addEdge("C", "D");
  461.         // g.addEdge("C", "E");
  462.         // g.addArc("D", "E");
  463.         // g.addArc("D", "E");
  464.         // g.addArc("D", "F");
  465.         // g.addArc("D", "G");
  466.         // g.addArc("F", "I");
  467.         // g.addArc("I", "K");
  468.         // g.addArc("K", "M");
  469.         // g.addArc("M", "N");
  470.         // g.addArc("M", "D");
  471.         // g.addArc("O", "M");
  472.         // g.addArc("O", "T");
  473.         // g.addArc("H", "R");
  474.         // g.addArc("R", "T");
  475.         // g.addArc("T", "A");
  476.         // g.addArc("S", "A");
  477.         // g.addArc("A", "S");
  478.         // g.addArc("N", "K");
  479.         // g.addArc("T", "K");
  480.         // g.addArc("S", "M");
  481.         // g.addArc("F", "N");
  482.         // g.addArc("F", "D");
  483.         // g.addArc("H", "M");
  484.         // g.addArc("H", "T");
  485.         // g.addArc("I", "R");
  486.         // g.addArc("I", "T");
  487.         // g.addArc("K", "A");
  488.         // g.addArc("O", "A");
  489.         // g.addArc("K", "S");
  490.         // g.addArc("O", "F");
  491.  
  492.         // System.out.println("\nTesting isArc() with A to B: \t" + g.isArc("A", "B"));
  493.         // System.out.println("Testing isArc() with A to C: \t" + g.isArc("A", "C"));
  494.         // System.out.println("Testing isArc() with A to F: \t" + g.isArc("A", "F"));
  495.         // System.out.println("Testing isArc() with I to F: \t" + g.isArc("I", "F"));
  496.  
  497.         // System.out.println("\nTesting isEdge() with A and B:\t" + g.isEdge("A", "B"));
  498.         // System.out.println("Testing isEdge() with B and E:\t" + g.isEdge("B", "E"));
  499.         // System.out.println("Testing isEdge() with H and R:\t" + g.isEdge("H", "R"));
  500.  
  501.         //System.out.println("\nTesting isUndirected():\t" + g.isUndirected());
  502.  
  503.         System.out.println("\n" + g);
  504.  
  505.         System.out.println("Testing getPredecessors() with G:\t" + g.getPredecessors("G"));
  506.         System.out.println("\nTesting getSuccessors() with A: \t" + g.getSuccessors("A"));
  507.  
  508.         //System.out.println("\n" + g);
  509.  
  510.         //System.out.println(g.arcs.get(4));
  511.  
  512.         System.out.println("\nTesting BFtraversal() with A:\t" + g.BFtraversal("A"));
  513.  
  514.         System.out.println("\nTesting DFtraversal() with A:\t" + g.DFtraversal("A"));
  515.  
  516.         //g.saveToTGF("GraphOutput.tgf");
  517.     }
  518. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top