Package edu.princeton.cs.algs4

Class SymbolGraph

  • public class SymbolGraph
extends Object
    The SymbolGraph class represents an undirected graph, where the vertex names are arbitrary strings. By providing mappings between string vertex names and integers, it serves as a wrapper around the Graph data type, which assumes the vertex names are integers between 0 and V - 1. It also supports initializing a symbol graph from a file.

    This implementation uses an ST to map from strings to integers, an array to map from integers to strings, and a Graph to store the underlying graph. The indexOf and contains operations take time proportional to log V, where V is the number of vertices. The nameOf operation takes constant time.

    For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    Author:
    Robert Sedgewick, Kevin Wayne

    • Constructor Detail

      • SymbolGraph

        public SymbolGraph​(String filename,
                   String delimiter)
        Initializes a graph from a file using the specified delimiter. Each line in the file contains the name of a vertex, followed by a list of the names of the vertices adjacent to that vertex, separated by the delimiter.
        Parameters:
        filename - the name of the file
        delimiter - the delimiter between fields

    • Method Detail

      • contains

        public boolean contains​(String s)
        Does the graph contain the vertex named s?
        Parameters:
        s - the name of a vertex
        Returns:
        true if s is the name of a vertex, and false otherwise

      • indexOf

        public int indexOf​(String s)
        Returns the integer associated with the vertex named s.
        Parameters:
        s - the name of a vertex
        Returns:
        the integer (between 0 and V - 1) associated with the vertex named s

      • nameOf

        public String nameOf​(int v)
        Returns the name of the vertex associated with the integer v.
        Parameters:
        v - the integer corresponding to a vertex (between 0 and V - 1)
        Returns:
        the name of the vertex associated with the integer v
        Throws:
        IllegalArgumentException - unless 0 <= v < V

      • graph

        public Graph graph()
        Returns the graph associated with the symbol graph. It is the client's responsibility not to mutate the graph.
        Returns:
        the graph associated with the symbol graph

      • main

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