Package edu.princeton.cs.algs4

Class SymbolDigraph

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

    This implementation uses an ST to map from strings to integers, an array to map from integers to strings, and a Digraph 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.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    Author:
    Robert Sedgewick, Kevin Wayne

    • Constructor Detail

      • SymbolDigraph

        public SymbolDigraph​(String filename,
                     String delimiter)
        Initializes a digraph 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 digraph 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

      • digraph

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

      • main

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