Class MysteryUnweightedGraphImplementation

  • All Implemented Interfaces:
    Graph, UnweightedGraph
    public class MysteryUnweightedGraphImplementation
extends java.lang.Object
implements UnweightedGraph
    An implementation of the Unweighted Graph ADT. This class can represent both directed and undirected graphs, but the choice must be made at construction time, and is final. Technically, this implementation supports self-loops; it makes no effort to prevent these. Any method that takes one or more vertex IDs as arguments may throw an IndexOutOfBoundsException if any input ID is out of bounds.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean addEdge​(int begin, int end)
      Adds an edge between two vertices.
      int addVertex()
      Adds a new vertex.
      void clear()
      Removes all vertices and edges from the graph.
      int getDegree​(int v)
      Returns the out-degree of the specified vertex.
      int getInDegree​(int v)
      Returns the in-degree of the specified vertex.
      java.lang.Iterable<java.lang.Integer> getNeighbors​(int v)
      Returns an iterator over the neighbors of the specified vertex.
      boolean hasEdge​(int begin, int end)
      Checks whether an edge exists between two vertices.
      boolean isDirected()
      Returns true if the graph is directed.
      boolean isEmpty()
      Returns true if there are no vertices in the graph.
      int numEdges()
      Returns the number of edges in the graph.
      int numVerts()
      Returns the number of vertices in the graph.

      • Methods inherited from class java.lang.Object

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

    • Constructor Detail

      • MysteryUnweightedGraphImplementation

        public MysteryUnweightedGraphImplementation()
        Default constructor: an empty directed graph.

      • MysteryUnweightedGraphImplementation

        public MysteryUnweightedGraphImplementation​(boolean directed)
        Constructs an empty graph with the specified directedness.

      • MysteryUnweightedGraphImplementation

        public MysteryUnweightedGraphImplementation​(boolean directed,
                                            int N)
        Constructs a graph with N vertices and the specified directedness.

    • Method Detail

      • addVertex

        public int addVertex()
        Adds a new vertex.
        Specified by:
        addVertex in interface Graph
        Returns:
        the ID of the added vertex.

      • addEdge

        public boolean addEdge​(int begin,
                       int end)
        Adds an edge between two vertices. In an undirected graph, this has the same effect as addEdge(end, begin).
        Specified by:
        addEdge in interface UnweightedGraph
        Returns:
        false if the edge was already in the graph.

      • hasEdge

        public boolean hasEdge​(int begin,
                       int end)
        Checks whether an edge exists between two vertices. In an undirected graph, this returns the same as hasEdge(end, begin).
        Specified by:
        hasEdge in interface Graph
        Returns:
        true if there is an edge from begin to end.

      • getDegree

        public int getDegree​(int v)
        Returns the out-degree of the specified vertex.
        Specified by:
        getDegree in interface Graph

      • getInDegree

        public int getInDegree​(int v)
        Returns the in-degree of the specified vertex.
        Specified by:
        getInDegree in interface Graph

      • getNeighbors

        public java.lang.Iterable<java.lang.Integer> getNeighbors​(int v)
        Returns an iterator over the neighbors of the specified vertex. In particular, the vertex u is included in the returned iterator's sequence if and only if there is an edge from v to u in the graph.
        Specified by:
        getNeighbors in interface Graph

      • numVerts

        public int numVerts()
        Returns the number of vertices in the graph.
        Specified by:
        numVerts in interface Graph

      • numEdges

        public int numEdges()
        Returns the number of edges in the graph. The result does *not* double-count edges in undirected graphs.
        Specified by:
        numEdges in interface Graph

      • isDirected

        public boolean isDirected()
        Returns true if the graph is directed.
        Specified by:
        isDirected in interface Graph

      • isEmpty

        public boolean isEmpty()
        Returns true if there are no vertices in the graph.
        Specified by:
        isEmpty in interface Graph

      • clear

        public void clear()
        Removes all vertices and edges from the graph.
        Specified by:
        clear in interface Graph