Interface Graph

All Known Implementing Classes:
StringGraph
public interface Graph
A graph whose vertices are strings.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int
    DEFAULT_CAPACITY
    The default capacity used when the no-argument constructor is called.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    addEdge(String vertex1, String vertex2)
    Adds a new edge.
    void
    addEdges(String[][] edges)
    Adds multiple edges.
    void
    addVertex(String vertex)
    Adds a new vertex to this graph.
    void
    addVertices(String[] vertices)
    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.
    String[]
    bfsSSSP(String vertex)
    Perform BFS Single Source Shortest Path from specified 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.
    int
    degree(String vertex)
    Returns the degree of a vertex
    int[]
    degreeSequence()
    Return the degree sequence for 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[]
    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.
    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[]
    shortestPath(String s, String t)
    Returns the shortest path in this graph from vertex s to vertex t.
    String
    toString()
    Returns a string representation of this Graph.
    boolean
    vertexExists(String vertex)
    Determines if a vertex with the given label exists.

  • Field Details

    • DEFAULT_CAPACITY

      static final int DEFAULT_CAPACITY
      The default capacity used when the no-argument constructor is called.
      See Also:

  • Method Details

    • numberOfVertices

      int numberOfVertices()
      Returns the number of vertices in this graph (the "order" of this graph).
      Returns:
      the number of vertices in this graph

    • numberOfEdges

      int numberOfEdges()
      Returns the number of edges in this graph (the "size" of this graph).
      Returns:
      the number of edges in this graph

    • getVertices

      String[] getVertices()
      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.
      Returns:
      a String array containing the vertex labels

    • getEdges

      String[][] getEdges()
      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"} }
      Returns:
      an m x 2 array in which each row represents and edge in this graph.

    • capacity

      int capacity()
      Returns the number of vertices that can be added to this graph before the array of vertices needs to be increased.
      Returns:
      the number of vertices that can be added to this graph before the array of vertices needs to be increased.

    • resize

      void resize(int newCapacity)
      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.
      Parameters:
      newCapacity - The new capacity

    • vertexExists

      boolean vertexExists(String vertex)
      Determines if a vertex with the given label exists.
      Parameters:
      vertex - the label of a vertex.
      Returns:
      true of the vertex exist, false if it does not exist.

    • addVertex

      void addVertex(String vertex) throws GraphException
      Adds a new vertex to this graph.
      Parameters:
      vertex - the new vertex to be added
      Throws:
      GraphException - if the specified vertex already exists.

    • addVertices

      void addVertices(String[] vertices)
      Adds one or more vertices to this graph.
      Parameters:
      vertices - the vertices to be added

    • edgeExists

      boolean edgeExists(String vertex1, String vertex2) throws GraphException
      Determines if an edge with the given end vertices exists.
      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
      Throws:
      GraphException - if either vertex1 or vertex2 is not in this graph.

    • addEdge

      void addEdge(String vertex1, String vertex2) throws GraphException
      Adds a new edge.
      Parameters:
      vertex1 - the label of one end of the new edge
      vertex2 - the label of the other end of the new edge
      Throws:
      GraphException - if the edge already exists or if either end vertex does not exist.

    • addEdges

      void addEdges(String[][] edges)
      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.
      Parameters:
      edges - a 2 x w array of vertices, w ≥ 0

    • toString

      String toString()
      Returns a string representation of this Graph.
      Overrides:
      toString in class Object
      Returns:
      a string representation of this Graph.

    • deleteVertex

      void deleteVertex(String vertex) throws GraphException
      Deletes a vertex and all of its incident edges.
      Parameters:
      vertex - the vertex to be deleted
      Throws:
      GraphException - if vertex does not exist.

    • deleteEdge

      void deleteEdge(String vertex1, String vertex2) throws GraphException
      Deletes an edge.
      Parameters:
      vertex1 - one end vertex of the edge
      vertex2 - the other end vertex of the edge
      Throws:
      GraphException - if the edge does not exist or if either end vertex does not exist.

    • degree

      int degree(String vertex) throws GraphException
      Returns the degree of a vertex
      Parameters:
      vertex - the vertex of interest
      Returns:
      the degree of the given vertex
      Throws:
      GraphException - if the vertex does not exist.

    • maxDegree

      int maxDegree()
      Returns the maximum degree of the graph
      Returns:
      the maximum degree

    • minDegree

      int minDegree()
      Returns the minimum degree of the graph.
      Returns:
      the minimum degree

    • averageDegree

      double averageDegree()
      Returns the average degree of the graph
      Returns:
      the average degree

    • degreeSequence

      int[] degreeSequence()
      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.
      Returns:
      an int array containing the degrees of all vertices, sorted from largest degree to smallest degree.

    • getNeighbors

      String[] getNeighbors(String vertex) throws GraphException
      Returns the labels of all neighbors of a vertex. The order of the neighbors is unspecified.
      Parameters:
      vertex - the vertex of interest
      Returns:
      a String array holding the labels the neighbors.
      Throws:
      GraphException - if the vertex does not exist.

    • bfsOrder

      String[] bfsOrder(String vertex) throws GraphException
      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.
      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.
      Throws:
      GraphException - if the given vertex is not in this graph.

    • bfsTree

      Graph bfsTree(String vertex) throws GraphException
      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.
      Parameters:
      vertex - The vertex at which the BFS traversal is started
      Returns:
      A BFS spanning tree of the connected component containing the given vertex.
      Throws:
      GraphException - if the given vertex is not in this graph.

    • dfsOrder

      String[] dfsOrder(String vertex) throws GraphException
      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.
      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.
      Throws:
      GraphException - if the given vertex is not in this graph.

    • dfsTree

      Graph dfsTree(String vertex) throws GraphException
      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.
      Parameters:
      vertex - the vertex at which the DFS traversal is started
      Returns:
      a DFS spanning tree of the connected component containing
      Throws:
      GraphException - if the given vertex is not in this graph.

    • isConnected

      boolean isConnected()
      Determines if the graph is connected.
      Returns:
      true if the graph is connected, false otherwise.

    • bfsSSSP

      String[] bfsSSSP(String vertex) throws GraphException
      Perform BFS Single Source Shortest Path from specified vertex.
      Parameters:
      vertex - Source for shortest paths
      Returns:
      String array containing the "Previous" vertices for the shortest path.
      Throws:
      GraphException - if the specified vertex does not exist.
      See Also:

    • shortestPath

      String[] shortestPath(String s, String t) throws GraphException
      Returns the shortest path in this graph from vertex s to vertex t.
      Parameters:
      s - the source vertex
      t - the destination vertex
      Returns:
      a list of strings containing the labels of the vertices along the shortest path from s to t, starting with s and ending with t.
      Throws:
      GraphException - of either specified vertex does not exist.