edu.princeton.cs.algorithms

Class SymbolDigraph

java.lang.Object

edu.princeton.cs.algorithms.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 index and contains operations take time proportional to log V, where V is the number of vertices. The name 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 Summary

Constructors

Constructor and Description
SymbolDigraph(String filename, String delimiter) Initializes a digraph from a file using the specified delimiter.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	contains(String s) Does the digraph contain the vertex named s?
Digraph	G() Returns the digraph assoicated with the symbol graph.
int	index(String s) Returns the integer associated with the vertex named s.
static void	main(String[] args) Unit tests the SymbolDigraph data type.
String	name(int v) Returns the name of the vertex associated with the integer v.

Methods inherited from class java.lang.Object

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

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

index

public int index(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

name

public String name(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

G

public Digraph G()

Returns the digraph assoicated 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.