edu.cmu.cs.pattis.cs151xx
Interface Graph


public interface Graph

This interface specifies the methods for a Graph object, including a large number of methods to query/update the nodes and edges in the Graph. This interface uses the Set interface to specify a return type for many accessors.


Inner Class Summary
static interface Graph.Edge
          Edge is an immutable inner class for storing edges in a graph; each consists of the origin and desination node in that graph.
 
Method Summary
 Graph addEdge(Graph.Edge edge, Object edgeValue)
          Add an edge to this graph, returning the new graph.
 Graph addEdge(String origin, String destination, Object edgeValue)
          Add an edge to this graph, returning the new graph.
 Graph addNode(String nodeName)
          Add a node to this graph, returning the new graph.
 void clear()
          Remove all the nodes and edges from this graph.
 int degree(String nodeName)
          Returns the degree of the specified node.
 Set getAllEdges()
          Returns an UNMODIFIABLE set containing all the edges in the graph.
 Set getAllNodes()
          Returns an UNMODIFIABLE set containing the names of all the nodes in the graph.
 int getEdgeCount()
          Returns the number of edges in the Graph.
 Object getEdgeValue(Graph.Edge edge)
          Returns the value associated with this edge (null if the edge is not in this graph).
 Object getEdgeValue(String origin, String destination)
          Returns the value associated with the edge with the specified origin and destination.
 EdgeValueIO getEdgeValueIO()
          Return the EdgeValueIO object for this graph.
 Set getInEdges(String nodeName)
          Returns an UNMODIFIABLE set containing all the edges in the graph whose destination node is destinationNodeName.
 Set getInNodes(String nodeName)
          Returns an UNMODIFIABLE set containing the origin nodes that reach to destinationNodeName in the graph.
 int getNodeCount()
          Returns the number of nodes in the Graph.
 Set getOutEdges(String nodeName)
          Returns an UNMODIFIABLE set containing all the edges in the graph whose origin node is originNodeName.
 Set getOutNodes(String nodeName)
          Returns an UNMODIFIABLE set containing the destination nodes reachable from originNodeName in the graph.
 boolean hasEdge(Graph.Edge edge)
          Returns whether or not this graph stores an edge with the specified edge.
 boolean hasEdge(String origin, String destination)
          Returns whether or not this graph stores an edge with the specified origin and destination.
 boolean hasNode(String nodeName)
          Return whether or not this graph stores a node.
 int inDegree(String nodeName)
          Returns the in-degree of the specified node.
 Graph load(edu.cmu.cs.pattis.cs151xx.TypedBufferReader input, char tokenSeparator)
          Read this graph from a file, one line at at time, in the form: origin destination value (where each is separated from the other by tokenSeparator).
 int outDegree(String nodeName)
          Returns the out-degree of the specified node.
 Graph removeEdge(Graph.Edge edge)
          Remove an edge from this graph, returning the new graph.
 Graph removeEdge(String origin, String destination)
          Remove an edge from this graph, returning the new graph.
 Graph removeNode(String nodeName)
          Remove a node from this graph, returning the new graph.
 void write(edu.cmu.cs.pattis.cs151xx.TypedBufferWriter output, char tokenSeparator)
          Write this graph into a file, one line at a time so that it can be read by the load method (in the form origin, destination, value; where each is separated from the other by tokenSeparator).
 

Method Detail

clear

public void clear()
Remove all the nodes and edges from this graph.

addNode

public Graph addNode(String nodeName)
Add a node to this graph, returning the new graph. If the node is already in the graph, make no changes to the graph; otherwise, add the node (associated with empty LocalInformation).
Parameters:
nodeName - - the name of the node to add to this graph.

addEdge

public Graph addEdge(String origin,
                     String destination,
                     Object edgeValue)
Add an edge to this graph, returning the new graph. If the edge is already in the graph, change its value to this value; otherwise, add a new edge. Note that if the origin or destination nodes are not in the graph, add them as well. All appropriate LocalInformation for the origin and destination nodes is updated.
Parameters:
originNodeName - - the origin node for the edge.
destinationNodeName - - the destination node for the edge.
edgeValue - - the value of the edge.

addEdge

public Graph addEdge(Graph.Edge edge,
                     Object edgeValue)
Add an edge to this graph, returning the new graph. If the edge is already in the graph, change its value to this value; otherwise, add a new edge. Note that if the origin or destination nodes are not in the graph, add them as well. All appropriate LocalInformation for the origin and destination nodes is updated.
Parameters:
edge - - the edge to add to this graph.
edgeValue - - the value of the edge.

removeNode

public Graph removeNode(String nodeName)
Remove a node from this graph, returning the new graph. If the node is in the graph, remove all edges connected to it; if not, make no changes.
Parameters:
nodeName - - the name of the node to remove from this graph.

removeEdge

public Graph removeEdge(String origin,
                        String destination)
Remove an edge from this graph, returning the new graph. Update the LocalInformation for the origin/destination nodes of this edge.
Parameters:
originNodeName - - the origin node for the edge to remove from the graph.
destinationNodeName - - the destination node for the edge to remove from the graph.

removeEdge

public Graph removeEdge(Graph.Edge edge)
Remove an edge from this graph, returning the new graph. Update the LocalInformation for the origin/destination nodes of this edge.
Parameters:
edge - - the edge to remove from this graph.

load

public Graph load(edu.cmu.cs.pattis.cs151xx.TypedBufferReader input,
                  char tokenSeparator)
Read this graph from a file, one line at at time, in the form: origin destination value (where each is separated from the other by tokenSeparator). If this graph already contains nodes/edges, these are added; if you want to discard the old graph, call clear first. Note that the EdgeValueIO object supplied to the constructor of this object is used on the value.
Parameters:
input - - file open for reading.
tokeSeparator - - character to use to separate origin, destination, and value.

write

public void write(edu.cmu.cs.pattis.cs151xx.TypedBufferWriter output,
                  char tokenSeparator)
Write this graph into a file, one line at a time so that it can be read by the load method (in the form origin, destination, value; where each is separated from the other by tokenSeparator).
Parameters:
output - - file open for writing.
tokeSeparator - - character to use to separate origin, destination, and value.

getEdgeValueIO

public EdgeValueIO getEdgeValueIO()
Return the EdgeValueIO object for this graph.

getNodeCount

public int getNodeCount()
Returns the number of nodes in the Graph.

getEdgeCount

public int getEdgeCount()
Returns the number of edges in the Graph.

hasNode

public boolean hasNode(String nodeName)
Return whether or not this graph stores a node.
Parameters:
nodeName - - the name of the node to check.

hasEdge

public boolean hasEdge(String origin,
                       String destination)
Returns whether or not this graph stores an edge with the specified origin and destination.
Parameters:
originNodeName - - the origin node for the edge to check.
destinationNodeName - - the destination node for the edge to check.

hasEdge

public boolean hasEdge(Graph.Edge edge)
Returns whether or not this graph stores an edge with the specified edge.
Parameters:
edge - - the edge to check.

getEdgeValue

public Object getEdgeValue(String origin,
                           String destination)
Returns the value associated with the edge with the specified origin and destination.
Parameters:
origin - - the origin node of the edge whose associated value is to be retrieved.
destination - - the destination of the edge whose associated value is to be retrieved.

getEdgeValue

public Object getEdgeValue(Graph.Edge edge)
Returns the value associated with this edge (null if the edge is not in this graph).
Parameters:
edge- - the edge whose associated value is to be retrieved.

inDegree

public int inDegree(String nodeName)
Returns the in-degree of the specified node. If the node is not present in the graph, it returns 0.
Parameters:
nodeName - - the name of the node to check.

outDegree

public int outDegree(String nodeName)
Returns the out-degree of the specified node. If the node is not present in the graph, it returns 0.
Parameters:
nodeName - - the name of the node to check.

degree

public int degree(String nodeName)
Returns the degree of the specified node. If the node is not present in the graph, it returns 0. Otherwise, it returns the sum of the in-degree and out-degree
Parameters:
nodeName - - the name of the node to check.

getAllNodes

public Set getAllNodes()
Returns an UNMODIFIABLE set containing the names of all the nodes in the graph.

getAllEdges

public Set getAllEdges()
Returns an UNMODIFIABLE set containing all the edges in the graph.

getOutNodes

public Set getOutNodes(String nodeName)
Returns an UNMODIFIABLE set containing the destination nodes reachable from originNodeName in the graph.
Parameters:
originNodeName - - the name of the origin node

getInNodes

public Set getInNodes(String nodeName)
Returns an UNMODIFIABLE set containing the origin nodes that reach to destinationNodeName in the graph.
Parameters:
destinationNodeName - - the name of the origin node

getOutEdges

public Set getOutEdges(String nodeName)
Returns an UNMODIFIABLE set containing all the edges in the graph whose origin node is originNodeName.
Parameters:
originNodeName - - the name of the origin node for the edges

getInEdges

public Set getInEdges(String nodeName)
Returns an UNMODIFIABLE set containing all the edges in the graph whose destination node is destinationNodeName.
Parameters:
destinationNodeName - - the name of the destination node for the edges