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 "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

  • 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.
    int
    capacity()
    Returns the number of vertices that can be added to this graph before the array of vertices needs to be increased.
    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.
    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.
    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 "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

  • 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.
      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.

    • 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.