Package com.zybooks.dsaj.graph

Interface Graph<V,E>

Type Parameters:
V - type for associated element stored at each vertex
E - type for associated element stored at each edge
All Known Implementing Classes:
AdjacencyMapGraph
public interface Graph<V,E>
An interface for a graph structure. A graph can be declared as either directed or undirected. In the case of an undirected graph, methods outgoingEdges and incomingEdges return the same collection, and outDegree and inDegree return the same value.

  • Method Details

    • numVertices

      int numVertices()
      Returns the number of vertices of the graph.
      Returns:
      the number of vertices of the graph

    • numEdges

      int numEdges()
      Returns the number of edges of the graph.
      Returns:
      the number of edges of the graph

    • vertices

      Iterable<Vertex<V>> vertices()
      Returns the vertices of the graph as an iterable collection.
      Returns:
      the vertices of the graph as an iterable collection

    • edges

      Iterable<Edge<E>> edges()
      Returns the edges of the graph as an iterable collection.
      Returns:
      the edges of the graph as an iterable collection

    • outDegree

      int outDegree(Vertex<V> v) throws IllegalArgumentException
      Returns the number of edges leaving vertex v. Note that for an undirected graph, this is the same result returned by inDegree
      Parameters:
      v - the vertex
      Returns:
      the number of edges leaving vertex v
      Throws:
      IllegalArgumentException - if v is not a valid vertex

    • inDegree

      int inDegree(Vertex<V> v) throws IllegalArgumentException
      Returns the number of edges for which vertex v is the destination. Note that for an undirected graph, this is the same result returned by outDegree
      Parameters:
      v - the vertex
      Returns:
      the number of edges for which vertex v is the destination
      Throws:
      IllegalArgumentException - if v is not a valid vertex

    • outgoingEdges

      Iterable<Edge<E>> outgoingEdges(Vertex<V> v) throws IllegalArgumentException
      Returns an iterable collection of edges for which vertex v is the origin. Note that for an undirected graph, this is the same result returned by incomingEdges.
      Parameters:
      v - the vertex
      Returns:
      an iterable collection of edges for which vertex v is the origin
      Throws:
      IllegalArgumentException - if v is not a valid vertex

    • incomingEdges

      Iterable<Edge<E>> incomingEdges(Vertex<V> v) throws IllegalArgumentException
      Returns an iterable collection of edges for which vertex v is the destination. Note that for an undirected graph, this is the same result returned by outgoingEdges.
      Parameters:
      v - the vertex
      Returns:
      an iterable collection of edges for which vertex v is the destination
      Throws:
      IllegalArgumentException - if v is not a valid vertex

    • getEdge

      Edge<E> getEdge(Vertex<V> u, Vertex<V> v) throws IllegalArgumentException
      Returns the edge from u to v, or null if they are not adjacent.
      Parameters:
      u - origin vertex
      v - destination vertex
      Returns:
      the edge from u to v, or null if they are not adjacent.
      Throws:
      IllegalArgumentException

    • endVertices

      Vertex<V>[] endVertices(Edge<E> e) throws IllegalArgumentException
      Returns the vertices of edge e as an array of length two. If the graph is directed, the first vertex is the origin, and the second is the destination. If the graph is undirected, the order is arbitrary.
      Parameters:
      e - edge
      Returns:
      an array of length two containing the vertices of edge e
      Throws:
      IllegalArgumentException

    • opposite

      Vertex<V> opposite(Vertex<V> v, Edge<E> e) throws IllegalArgumentException
      Returns the vertex that is opposite to vertex v on edge e.
      Parameters:
      v - an incident vertex to edge e
      e - an edge incident to vertex v
      Returns:
      the vertex that is opposite to vertex v on edge e
      Throws:
      IllegalArgumentException

    • insertVertex

      Vertex<V> insertVertex(V element)
      Inserts and returns a new vertex with the given element.
      Parameters:
      element - data to be stored at newly created vertex
      Returns:
      newly created Vertex instance

    • insertEdge

      Edge<E> insertEdge(Vertex<V> u, Vertex<V> v, E element) throws IllegalArgumentException
      Inserts and returns a new edge between vertices u and v, storing given element.
      Parameters:
      u - origin of new edge
      v - destination of new edge
      element - data to be stored at newly created edge
      Returns:
      newly created Edge instance
      Throws:
      IllegalArgumentException - if u or v are invalid vertices, or if an edge already exists between u and v.

    • removeVertex

      void removeVertex(Vertex<V> v) throws IllegalArgumentException
      Removes a vertex and all its incident edges from the graph.
      Parameters:
      v - the vertex to remove
      Throws:
      IllegalArgumentException

    • removeEdge

      void removeEdge(Edge<E> e) throws IllegalArgumentException
      Removes an edge from the graph.
      Parameters:
      e - the edge to remove
      Throws:
      IllegalArgumentException