Class StringGraph

java.lang.Object
StringGraph
All Implemented Interfaces:
Graph
public class StringGraph extends Object implements Graph
Class for Graph Assignment Part 1
Author:
Dr. Lillis

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected int
    capacity
    Number of vertices that can be stored in this graph before the size of the labels and adjacency arrays needs to be increased.
    protected boolean[][]
    edgeMatrix
    2D array that stores adjacencies between pairs of vertices.
    protected String[]
    labels
    1D array that stores the vertex labels.
    protected int
    numEdges
    Number of edges in this graph (the "size" of this graph).
    protected int
    numVertices
    Number of vertices in this graph (the "BFS_Order" of this graph).

    Fields inherited from interface Graph

    DEFAULT_CAPACITY

  • Constructor Summary

    Constructors
    Constructor
    Description
    StringGraph()
    Default constructor sets initial capacity to the value indicated by the constant value Graph.Default_Capacity.
    StringGraph(int initCapacity)
    Parameterized constructor sets initial capacity to given capacity
    StringGraph(String[] initVertices)
    Parameterized constructor gives initial set of vertex labels.
    StringGraph(String[] initVertices, String[][] initEdges)
    Parameterized constructor gives initial set of vertex labels and edges.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    addEdge(String vertex1, String vertex2)
    Adds a new edge.
    final void
    addEdges(String[][] newEdges)
    Adds multiple edges.
    void
    addVertex(String newVertex)
    Adds a new vertex to this graph.
    final void
    addVertices(String[] newVertices)
    Adds one or more vertices to this graph.
    double
    averageDegree()
    Returns the average degree of the graph
    String[]
    bfsOrder(String vertex)
    Performs a Breadth First Search traversal starting at a given vertex.
    Graph
    bfsTree(String vertex)
    Performs a Breadth First Search traversal starting at a given vertex.
    int
    capacity()
    Returns the number of vertices that can be added to this graph before the array of vertices needs to be increased.
    private void
    decreaseCapacity(int smallerCapacity)
    Decreases the the size of labels array and adjacency matrix and sets the capacity variable to smallerCapacity.
    private int
    degree(int index)
    Returns the degree of the vertex whose label is stored at the given index in the labels array.
    int
    degree(String vertex)
    Returns the degree of a vertex
    int[]
    degreeSequence()
    Return the degree sequence for this graph.
    private double[]
    degreeStats()
    Return maximum degree, minimum degree, and average degree of this graph.
    void
    deleteEdge(String vertex1, String vertex2)
    Deletes an edge.
    void
    deleteVertex(String vertex)
    Deletes a vertex and all of its incident edges.
    String[]
    dfsOrder(String vertex)
    Performs a Depth First Search traversal starting at a given vertex.
    Graph
    dfsTree(String vertex)
    Performs a Depth First Search traversal starting at a given vertex.
    boolean
    edgeExists(String vertex1, String vertex2)
    Determines if an edge with the given end vertices exists.
    String[][]
    getEdges()
    Creates and returns a new 2D array of strings containing the edges of this graph.
    String
    getGraphString()
    Return a string showing the vertices and edges of this graph.
    private int
    getIndex(String vertex)
    Returns the index at which a vertex label is stored.
    String
    getMatrixString()
    Returns a string containing the adjacency matrix for this graph.
    private int[]
    getNeighborIndices(int index)
    Returns the indices of all neighbors of the vertex with the given index.
    String[]
    getNeighbors(String vertex)
    Returns the labels of all neighbors of a vertex.
    String[]
    getVertices()
    Creates and returns a new array of Strings containing the vertices of this graph.
    private void
    increaseCapacity(int biggerCapacity)
    Increases the the size of labels array and adjacency matrix and sets the capacity variable to biggerCapacity.
    boolean
    isConnected()
    Determines if the graph is connected.
    int
    maxDegree()
    Returns the maximum degree of the graph
    int
    minDegree()
    Returns the minimum degree of the graph.
    int
    numberOfEdges()
    Returns the number of edges in this graph (the "size" of this graph).
    int
    numberOfVertices()
    Returns the number of vertices in this graph (the "order" of this graph).
    void
    resize(int newCapacity)
    Resizes the array of labels and the adjacency matrix to a new capacity.
    String
    toString()
    Returns a string representation of this Graph.
    boolean
    vertexExists(String vertex)
    Determines if a vertex with the given label exists.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Field Details

    • labels

      protected String[] labels
      1D array that stores the vertex labels.

    • edgeMatrix

      protected boolean[][] edgeMatrix
      2D array that stores adjacencies between pairs of vertices.

    • numVertices

      protected int numVertices
      Number of vertices in this graph (the "BFS_Order" of this graph).

    • numEdges

      protected int numEdges
      Number of edges in this graph (the "size" of this graph).

    • capacity

      protected int capacity
      Number of vertices that can be stored in this graph before the size of the labels and adjacency arrays needs to be increased.

  • Constructor Details

    • StringGraph

      public StringGraph()
      Default constructor sets initial capacity to the value indicated by the constant value Graph.Default_Capacity. Note: This constructor calls the parameterized constructor that takes an initial capacity.

    • StringGraph

      public StringGraph(int initCapacity)
      Parameterized constructor sets initial capacity to given capacity
      Parameters:
      initCapacity - initial capacity for number of vertices
      Throws:
      GraphException - if initialCapacity is < 1

    • StringGraph

      public StringGraph(String[] initVertices)
      Parameterized constructor gives initial set of vertex labels. Constructs A graph with capacity equal to the number of labels and adds a vertex for each given label. No edges are added.
      Parameters:
      initVertices - Initial vertex labels.

    • StringGraph

      public StringGraph(String[] initVertices, String[][] initEdges)
      Parameterized constructor gives initial set of vertex labels and edges. Constructs a graph with capacity equal to the number of labels, adds a vertex for each given label, and adds the edges specified.
      Parameters:
      initVertices - An initial set of vertex labels.
      initEdges - An 2 x m array representing the edges of the graph.

  • Method Details

    • numberOfVertices

      public int numberOfVertices()
      Description copied from interface: Graph
      Returns the number of vertices in this graph (the "order" of this graph).
      Specified by:
      numberOfVertices in interface Graph
      Returns:
      the number of vertices in this graph

    • numberOfEdges

      public int numberOfEdges()
      Description copied from interface: Graph
      Returns the number of edges in this graph (the "size" of this graph).
      Specified by:
      numberOfEdges in interface Graph
      Returns:
      the number of edges in this graph

    • capacity

      public int capacity()
      Description copied from interface: Graph
      Returns the number of vertices that can be added to this graph before the array of vertices needs to be increased.
      Specified by:
      capacity in interface Graph
      Returns:
      the number of vertices that can be added to this graph before the array of vertices needs to be increased.

    • resize

      public void resize(int newCapacity)
      Description copied from interface: Graph
      Resizes the array of labels and the adjacency matrix to a new capacity. If the new capacity is larger than the current capacity, the capacity is increased. Note: In future assignment the capacity may also be made smaller. newCapacity.
      Specified by:
      resize in interface Graph
      Parameters:
      newCapacity - The new capacity

    • increaseCapacity

      private void increaseCapacity(int biggerCapacity)
      Increases the the size of labels array and adjacency matrix and sets the capacity variable to biggerCapacity.
      Parameters:
      biggerCapacity - The new, larger, capacity of this graph.

    • decreaseCapacity

      private void decreaseCapacity(int smallerCapacity)
      Decreases the the size of labels array and adjacency matrix and sets the capacity variable to smallerCapacity.
      Parameters:
      smallerCapacity - The new, smaller, capacity of this graph.
      Throws:
      GraphException - if newCapacity less than number of vertices.

    • getIndex

      private int getIndex(String vertex)
      Returns the index at which a vertex label is stored.
      Parameters:
      vertex - the vertex of interest
      Returns:
      the index at which the vertex is stored. Returns -1 if not found

    • vertexExists

      public boolean vertexExists(String vertex)
      Description copied from interface: Graph
      Determines if a vertex with the given label exists.
      Specified by:
      vertexExists in interface Graph
      Parameters:
      vertex - the label of a vertex.
      Returns:
      true of the vertex exist, false if it does not exist.

    • addVertex

      public void addVertex(String newVertex)
      Description copied from interface: Graph
      Adds a new vertex to this graph.
      Specified by:
      addVertex in interface Graph
      Parameters:
      newVertex - the new vertex to be added

    • addVertices

      public final void addVertices(String[] newVertices)
      Description copied from interface: Graph
      Adds one or more vertices to this graph.
      Specified by:
      addVertices in interface Graph
      Parameters:
      newVertices - the vertices to be added

    • edgeExists

      public boolean edgeExists(String vertex1, String vertex2)
      Description copied from interface: Graph
      Determines if an edge with the given end vertices exists.
      Specified by:
      edgeExists in interface Graph
      Parameters:
      vertex1 - the label of one end of the edge
      vertex2 - the label of the other end of the edge
      Returns:
      true edge {vertex1, vertex2} is in this graph, returns false if the edge is not in this graph

    • addEdge

      public void addEdge(String vertex1, String vertex2)
      Description copied from interface: Graph
      Adds a new edge.
      Specified by:
      addEdge in interface Graph
      Parameters:
      vertex1 - the label of one end of the new edge
      vertex2 - the label of the other end of the new edge

    • addEdges

      public final void addEdges(String[][] newEdges)
      Description copied from interface: Graph
      Adds multiple edges. Each row i in the edges parameter represents the pair of vertices edges[i][0] and edges[i][1] for a new edge.
      Specified by:
      addEdges in interface Graph
      Parameters:
      newEdges - a 2 x w array of vertices, w ≥ 0

    • getVertices

      public String[] getVertices()
      Description copied from interface: Graph
      Creates and returns a new array of Strings containing the vertices of this graph. The length of the returned array equals the number of vertices. The order of the vertices is unspecified.
      Specified by:
      getVertices in interface Graph
      Returns:
      a String array containing the vertex labels

    • getEdges

      public String[][] getEdges()
      Description copied from interface: Graph
      Creates and returns a new 2D array of strings containing the edges of this graph. The size of the returned array is m x 2. In other words, there is one row for each edge. The order of the edges is unspecified and the order of the vertices in each edge is also unspecified. For example, a graph with the three edges {"A", "B"}, {"C", "A"}, and {"F", "D"} may return: { {"A", "B"}, {"C", "A"}, {"F", "D"} }
      Specified by:
      getEdges in interface Graph
      Returns:
      an m x 2 array in which each row represents and edge in this graph.

    • getGraphString

      public String getGraphString()
      Return a string showing the vertices and edges of this graph. The vertices are in sorted order. The two vertices of each edge are in sorted order and the list of all edges are shown in sorted order.
      Returns:
      a string showing the vertices and edges of this graph

    • getMatrixString

      public String getMatrixString()
      Returns a string containing the adjacency matrix for this graph. The entire adjacency matrix is not necessarily included. Only rows and columns corresponding to vertices are provided. True values are shown as "T" and false values are shown as "-". The rows and columns are labeled with both the index as well as the vertex label.
      Returns:
      A string showing the adjacency matrix for this graph.

    • toString

      public String toString()
      Description copied from interface: Graph
      Returns a string representation of this Graph.
      Specified by:
      toString in interface Graph
      Overrides:
      toString in class Object
      Returns:
      a string representation of this Graph.

    • deleteVertex

      public void deleteVertex(String vertex)
      Description copied from interface: Graph
      Deletes a vertex and all of its incident edges.
      Specified by:
      deleteVertex in interface Graph
      Parameters:
      vertex - the vertex to be deleted

    • deleteEdge

      public void deleteEdge(String vertex1, String vertex2)
      Description copied from interface: Graph
      Deletes an edge.
      Specified by:
      deleteEdge in interface Graph
      Parameters:
      vertex1 - one end vertex of the edge
      vertex2 - the other end vertex of the edge

    • degree

      public int degree(String vertex)
      Description copied from interface: Graph
      Returns the degree of a vertex
      Specified by:
      degree in interface Graph
      Parameters:
      vertex - the vertex of interest
      Returns:
      the degree of the given vertex

    • degree

      private int degree(int index)
      Returns the degree of the vertex whose label is stored at the given index in the labels array.
      Parameters:
      index - The index of the vertex of interest
      Returns:
      The degree of the vertex with the given index
      Throws:
      GraphException - if the given index is not valid

    • maxDegree

      public int maxDegree()
      Description copied from interface: Graph
      Returns the maximum degree of the graph
      Specified by:
      maxDegree in interface Graph
      Returns:
      the maximum degree

    • minDegree

      public int minDegree()
      Description copied from interface: Graph
      Returns the minimum degree of the graph.
      Specified by:
      minDegree in interface Graph
      Returns:
      the minimum degree

    • averageDegree

      public double averageDegree()
      Description copied from interface: Graph
      Returns the average degree of the graph
      Specified by:
      averageDegree in interface Graph
      Returns:
      the average degree

    • degreeStats

      private double[] degreeStats()
      Return maximum degree, minimum degree, and average degree of this graph.
      Returns:
      A three-element array of doubles containing max, min, avg degree.

    • degreeSequence

      public int[] degreeSequence()
      Description copied from interface: Graph
      Return the degree sequence for this graph. The degree sequence is a sequence consisting of the degree of each vertex, sorted from largest to smallest.
      Specified by:
      degreeSequence in interface Graph
      Returns:
      an int array containing the degrees of all vertices, sorted from largest degree to smallest degree.

    • getNeighbors

      public String[] getNeighbors(String vertex)
      Description copied from interface: Graph
      Returns the labels of all neighbors of a vertex. The order of the neighbors is unspecified.
      Specified by:
      getNeighbors in interface Graph
      Parameters:
      vertex - the vertex of interest
      Returns:
      a String array holding the labels the neighbors.

    • getNeighborIndices

      private int[] getNeighborIndices(int index)
      Returns the indices of all neighbors of the vertex with the given index.
      Parameters:
      index - The index of the vertex of interest
      Returns:
      an array of int values containing the indices of the neighbors of the vertex of interest
      Throws:
      GraphException - if the given index is not valid.

    • bfsOrder

      public String[] bfsOrder(String vertex)
      Description copied from interface: Graph
      Performs a Breadth First Search traversal starting at a given vertex. The label of each vertex visited is added to an array of Strings in the order visited.
      Specified by:
      bfsOrder in interface Graph
      Parameters:
      vertex - the vertex at which the BFS traversal is started
      Returns:
      an array of Strings containing the labels of the vertices visited in the order that they were visited.

    • bfsTree

      public Graph bfsTree(String vertex)
      Description copied from interface: Graph
      Performs a Breadth First Search traversal starting at a given vertex. Constructs and returns a BFS spanning tree of the connected component containing the specified vertex. Adjacent vertices are visited in the lexicographical order of their labels.
      Specified by:
      bfsTree in interface Graph
      Parameters:
      vertex - The vertex at which the BFS traversal is started
      Returns:
      A BFS spanning tree of the connected component containing the given vertex.

    • dfsOrder

      public String[] dfsOrder(String vertex)
      Description copied from interface: Graph
      Performs a Depth First Search traversal starting at a given vertex. The label of each vertex visited is added to an array of Strings in the order visited.
      Specified by:
      dfsOrder in interface Graph
      Parameters:
      vertex - the vertex at which the DFS traversal is started
      Returns:
      an array of Strings containing the labels of the vertices visited in the order that they were visited.

    • dfsTree

      public Graph dfsTree(String vertex)
      Description copied from interface: Graph
      Performs a Depth First Search traversal starting at a given vertex. Constructs and returns a DFS spanning tree of the connected component containing the specified vertex. Adjacent vertices are visited in the lexicographical order of their labels.
      Specified by:
      dfsTree in interface Graph
      Parameters:
      vertex - the vertex at which the DFS traversal is started
      Returns:
      a DFS spanning tree of the connected component containing

    • isConnected

      public boolean isConnected()
      Description copied from interface: Graph
      Determines if the graph is connected.
      Specified by:
      isConnected in interface Graph
      Returns:
      true if the graph is connected, false otherwise.