edu.princeton.cs.algorithms

Class SymbolGraph

java.lang.Object

edu.princeton.cs.algorithms.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 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.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
boolean	contains(String s) Does the graph contain the vertex named s?
Graph	G() Returns the graph 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 SymbolGraph 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

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

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 Graph G()

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