Class Graph

  • public class Graph
extends Object
    The Graph class represents an undirected graph of vertices with string names. It supports the following operations: add an edge, add a vertex, get all the vertices, iterate over all the neighbors adjacent to a vertex, is there a vertex, is there an edge between two vertices. Self-loops are permitted; parallel edges are discarded.

    For additional documentation, see Section 4.5 of Computer Science: An Interdisciplinary Approach by Robert Sedgewick and Kevin Wayne.

    • Constructor Detail

      • Graph

        public Graph()
        Initializes an empty graph with no vertices or edges.

      • Graph

        public Graph​(String filename,
             String delimiter)
        Initializes a graph from the specified file, using the specified delimiter.
        Parameters:
        filename - the name of the file
        delimiter - the delimiter

    • Method Detail

      • V

        public int V()
        Returns the number of vertices in this graph.
        Returns:
        the number of vertices in this graph

      • E

        public int E()
        Returns the number of edges in this graph.
        Returns:
        the number of edges in this graph

      • degree

        public int degree​(String v)
        Returns the degree of vertex v in this graph.
        Parameters:
        v - the vertex
        Returns:
        the degree of v in this graph
        Throws:
        IllegalArgumentException - if v is not a vertex in this graph

      • addEdge

        public void addEdge​(String v,
                    String w)
        Adds the edge v-w to this graph (if it is not already an edge).
        Parameters:
        v - one vertex in the edge
        w - the other vertex in the edge

      • addVertex

        public void addVertex​(String v)
        Adds vertex v to this graph (if it is not already a vertex).
        Parameters:
        v - the vertex

      • vertices

        public Iterable<String> vertices()
        Returns the vertices in this graph.
        Returns:
        the set of vertices in this graph

      • adjacentTo

        public Iterable<String> adjacentTo​(String v)
        Returns the set of vertices adjacent to v in this graph.
        Parameters:
        v - the vertex
        Returns:
        the set of vertices adjacent to vertex v in this graph
        Throws:
        IllegalArgumentException - if v is not a vertex in this graph

      • hasVertex

        public boolean hasVertex​(String v)
        Returns true if v is a vertex in this graph.
        Parameters:
        v - the vertex
        Returns:
        true if v is a vertex in this graph, false otherwise

      • hasEdge

        public boolean hasEdge​(String v,
                       String w)
        Returns true if v-w is an edge in this graph.
        Parameters:
        v - one vertex in the edge
        w - the other vertex in the edge
        Returns:
        true if v-w is a vertex in this graph, false otherwise
        Throws:
        IllegalArgumentException - if either v or w is not a vertex in this graph

      • toString

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

      • main

        public static void main​(String[] args)
        Unit tests the Graph data type.
        Parameters:
        args - the command-line arguments