Package com.zybooks.dsaj.graph

Class AdjacencyMapGraph<V,E>

java.lang.Object
com.zybooks.dsaj.graph.AdjacencyMapGraph<V,E>
Type Parameters:
V - Associated data stored with a vertex
E - Associated data stored with an edge
All Implemented Interfaces:
Graph<V,E>
public class AdjacencyMapGraph<V,E> extends Object implements Graph<V,E>
An implementation for a graph structure using an adjacency map for each vertex. Every vertex stores an element of type V. Every edge stores an element of type E.

  • Constructor Details

    • AdjacencyMapGraph

      public AdjacencyMapGraph(boolean directed)
      Constructs an empty graph. The parameter determines whether this is an undirected or directed graph.
      Parameters:
      directed - true if a directed graph, false if an undirected graph

  • Method Details

    • numVertices

      public int numVertices()
      Returns the number of vertices of the graph
      Specified by:
      numVertices in interface Graph<V,E>
      Returns:
      the number of vertices of the graph

    • vertices

      public Iterable<Vertex<V>> vertices()
      Returns the vertices of the graph as an iterable collection
      Specified by:
      vertices in interface Graph<V,E>
      Returns:
      the vertices of the graph as an iterable collection

    • numEdges

      public int numEdges()
      Returns the number of edges of the graph
      Specified by:
      numEdges in interface Graph<V,E>
      Returns:
      the number of edges of the graph

    • edges

      public Iterable<Edge<E>> edges()
      Returns the edges of the graph as an iterable collection
      Specified by:
      edges in interface Graph<V,E>
      Returns:
      the edges of the graph as an iterable collection

    • outDegree

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

    • outgoingEdges

      public 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(v).
      Specified by:
      outgoingEdges in interface Graph<V,E>
      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

    • inDegree

      public 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(v).
      Specified by:
      inDegree in interface Graph<V,E>
      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

    • incomingEdges

      public 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(v).
      Specified by:
      incomingEdges in interface Graph<V,E>
      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

      public 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.
      Specified by:
      getEdge in interface Graph<V,E>
      Parameters:
      u - origin vertex
      v - destination vertex
      Returns:
      the edge from u to v, or null if they are not adjacent.
      Throws:
      IllegalArgumentException

    • endVertices

      public 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.
      Specified by:
      endVertices in interface Graph<V,E>
      Parameters:
      e - edge
      Returns:
      an array of length two containing the vertices of edge e
      Throws:
      IllegalArgumentException

    • opposite

      public Vertex<V> opposite(Vertex<V> v, Edge<E> e) throws IllegalArgumentException
      Returns the vertex that is opposite vertex v on edge e.
      Specified by:
      opposite in interface Graph<V,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

      public Vertex<V> insertVertex(V element)
      Inserts and returns a new vertex with the given element.
      Specified by:
      insertVertex in interface Graph<V,E>
      Parameters:
      element - data to be stored at newly created vertex
      Returns:
      newly created Vertex instance

    • insertEdge

      public 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.
      Specified by:
      insertEdge in interface Graph<V,E>
      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

      public void removeVertex(Vertex<V> v) throws IllegalArgumentException
      Removes a vertex and all its incident edges from the graph.
      Specified by:
      removeVertex in interface Graph<V,E>
      Parameters:
      v - the vertex to remove
      Throws:
      IllegalArgumentException

    • removeEdge

      public void removeEdge(Edge<E> e) throws IllegalArgumentException
      Description copied from interface: Graph
      Removes an edge from the graph.
      Specified by:
      removeEdge in interface Graph<V,E>
      Parameters:
      e - the edge to remove
      Throws:
      IllegalArgumentException

    • toString

      public String toString()
      Returns a string representation of the graph. This is used only for debugging; do not rely on the string representation.
      Overrides:
      toString in class Object