edu.ucla.structure
Class HashDirectedGraph

Object
  extended by AbstractDirectedGraph
      extended by HashDirectedGraph
All Implemented Interfaces:
DirectedGraph, Cloneable, Iterable, Collection

public class HashDirectedGraph
extends AbstractDirectedGraph
implements DirectedGraph

An implementation of a dirrected graph which stores the nodes and edges in a hash table to allow O(1) testing for inclusion, insertion, removal etc.

Author:
jpark, Keith Cascio

Field Summary
static PrintStream STREAM_DEBUG
           
 
Constructor Summary
HashDirectedGraph()
          Creates new HashDirectedGraph
HashDirectedGraph(DirectedGraph g)
           
HashDirectedGraph(int size)
           
 
Method Summary
 boolean addEdge(Object vertex1, Object vertex2)
          Adds the directed edge to the graph(Optional operation).
 boolean addVertex(Object vertex)
          Adds vertex to the graph(Optional operation).
 void clear()
           
 Object clone()
          interface DirectedGraph
 Map cloneAdjacencyMap(Map map)
           
 boolean contains(Object vertex)
          Returns whether or not a particular Object is a vertex in the graph.
 boolean containsEdge(Object vertex1, Object vertex2)
          Returns whether or not a particular edge is in the graph.
 int degree(Object vertex)
          Returns the degree of the vertex.
 boolean equals(Object p)
           
 int hashCode()
           
 Set inComing(Object vertex)
          Constructs an Iterator over the vertices adjacent to edges entering the specified vertex.
 int inDegree(Object vertex)
          Returns the number of edges entering the vertex.
 int numEdges()
           
 int outDegree(Object vertex)
          Returns the number of edges leaving the vertex.
 Set outGoing(Object vertex)
          Constructs an Iterator over the vertices adjacent to edges leaving the specified vertex.
 boolean removeEdge(Object vertex1, Object vertex2)
          Removes the directed edge from the graph(Optional operation).
 boolean removeVertex(Object vertex)
          Removes vertex from the graph(Optional operation).
 void replaceVertex(Object oldVertex, Object newVertex)
           
 void replaceVertices(Map verticesOldToNew, NodeLinearTask task)
           
 String toString()
           
 
Methods inherited from class AbstractDirectedGraph
add, addAll, containsAll, depthFirstIterator, hasPath, isAcyclic, isEmpty, isSinglyConnected, isWeaklyConnected, isWeaklyConnected, iterator, maintainsAcyclicity, remove, removeAll, retainAll, size, toArray, toArray, topologicalOrder, vertices
 
Methods inherited from class Object
getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface DirectedGraph
hasPath, isAcyclic, isSinglyConnected, isWeaklyConnected, isWeaklyConnected, maintainsAcyclicity, size, topologicalOrder, vertices
 
Methods inherited from interface Collection
add, addAll, containsAll, isEmpty, iterator, remove, removeAll, retainAll, toArray, toArray
 

Field Detail

STREAM_DEBUG

public static final PrintStream STREAM_DEBUG
Constructor Detail

HashDirectedGraph

public HashDirectedGraph()
Creates new HashDirectedGraph


HashDirectedGraph

public HashDirectedGraph(int size)

HashDirectedGraph

public HashDirectedGraph(DirectedGraph g)
Method Detail

clone

public Object clone()
Description copied from class: AbstractDirectedGraph
interface DirectedGraph

Specified by:
clone in interface DirectedGraph
Specified by:
clone in class AbstractDirectedGraph
Since:
081502

cloneAdjacencyMap

public Map cloneAdjacencyMap(Map map)
Since:
081502

replaceVertices

public void replaceVertices(Map verticesOldToNew,
                            NodeLinearTask task)
Specified by:
replaceVertices in interface DirectedGraph
Overrides:
replaceVertices in class AbstractDirectedGraph
Since:
20020603

replaceVertex

public void replaceVertex(Object oldVertex,
                          Object newVertex)
Specified by:
replaceVertex in interface DirectedGraph
Overrides:
replaceVertex in class AbstractDirectedGraph
Since:
20020603, 20060523

toString

public String toString()
Overrides:
toString in class Object

inComing

public Set inComing(Object vertex)
Constructs an Iterator over the vertices adjacent to edges entering the specified vertex.

Precondition:
vertex is in the graph(tested by "equals").

Specified by:
inComing in interface DirectedGraph
Parameters:
vertex- - An Object which is in the graph.
Returns:
Iterator over the vertices adjacent to edges entering vertex.

outGoing

public Set outGoing(Object vertex)
Constructs an Iterator over the vertices adjacent to edges leaving the specified vertex.

Precondition:
vertex is in the graph(tested by "equals").

Specified by:
outGoing in interface DirectedGraph
Parameters:
vertex- - An Object which is in the graph.
Returns:
Iterator over the vertices adjacent to edges leaving vertex.

degree

public int degree(Object vertex)
Returns the degree of the vertex. This includes both in and out edges

Precondition:
vertex is in the graph(tested by "equals").

Specified by:
degree in interface DirectedGraph
Overrides:
degree in class AbstractDirectedGraph
Parameters:
vertex- - An Object which is in the graph.
Returns:
the number of vertices adjacent to vertex.

inDegree

public int inDegree(Object vertex)
Returns the number of edges entering the vertex.

Precondition:
vertex is in the graph(tested by "equals").

Specified by:
inDegree in interface DirectedGraph
Overrides:
inDegree in class AbstractDirectedGraph
Parameters:
vertex- - An Object which is in the graph.
Returns:
the number of edges entering the vertex.

outDegree

public int outDegree(Object vertex)
Returns the number of edges leaving the vertex.

Precondition:
vertex is in the graph(tested by "equals").

Specified by:
outDegree in interface DirectedGraph
Overrides:
outDegree in class AbstractDirectedGraph
Parameters:
vertex- - An Object which is in the graph.
Returns:
the number of edges leaving the vertex.

containsEdge

public boolean containsEdge(Object vertex1,
                            Object vertex2)
Returns whether or not a particular edge is in the graph. The edge leaves vertex1 and enters vertex2.

Precondition:
vertex1 and vertex2 are in the graph(tested by "equals").

Specified by:
containsEdge in interface DirectedGraph
Overrides:
containsEdge in class AbstractDirectedGraph
Parameters:
vertex1- - An Object which is in the graph.
vertex2- - An Object which is in the graph.
Returns:
true if edge (vertex1,vertex2) is in the graph, false otherwise.

contains

public boolean contains(Object vertex)
Returns whether or not a particular Object is a vertex in the graph.

Specified by:
contains in interface DirectedGraph
Specified by:
contains in interface Collection
Parameters:
vertex- - Any Object.
Returns:
true if vertex is in the graph(tested by "equals"), false otherwise.

numEdges

public int numEdges()
Specified by:
numEdges in interface DirectedGraph
Overrides:
numEdges in class AbstractDirectedGraph
Since:
102402

addVertex

public boolean addVertex(Object vertex)
Adds vertex to the graph(Optional operation). If the vertex is already a member of the graph, the graph is unchanged and the method returns false, following the Collection convention.

Postcondition:
vertex is in the graph(as tested by "equals").

Specified by:
addVertex in interface DirectedGraph
Overrides:
addVertex in class AbstractDirectedGraph
Parameters:
vertex- - An Object to be added as a vertex.
Returns:
true if the graph was modified(i.e. vertex was not a vertex already) false otherwise.

removeVertex

public boolean removeVertex(Object vertex)
Removes vertex from the graph(Optional operation). If the vertex is not a member of the graph, the method returns false and leaves the graph unchanged. If the parameter is a vertex of the graph, it is removed and the method returns true.

Postcondition:
vertex is not in the graph(as tested by "equals").

Specified by:
removeVertex in interface DirectedGraph
Overrides:
removeVertex in class AbstractDirectedGraph
Parameters:
vertex- - An Object which is currently in the graph.

addEdge

public boolean addEdge(Object vertex1,
                       Object vertex2)
Adds the directed edge to the graph(Optional operation). If either of the vertices are not in the graph, they are added, and the edge is added. If the edge was already in the graph, it returns false, otherwise it returns true.

Postcondition:
the edge (vertex1,vertex2) is in the graph.

Specified by:
addEdge in interface DirectedGraph
Overrides:
addEdge in class AbstractDirectedGraph

removeEdge

public boolean removeEdge(Object vertex1,
                          Object vertex2)
Removes the directed edge from the graph(Optional operation). If the edge is not in the graph when the call is made, it returns false, otherwise it returns true.

Postcondition:
the edge (vertex1,vertex2) is in the graph.

Specified by:
removeEdge in interface DirectedGraph
Overrides:
removeEdge in class AbstractDirectedGraph

clear

public void clear()
Specified by:
clear in interface Collection

hashCode

public int hashCode()
Specified by:
hashCode in interface Collection
Overrides:
hashCode in class Object

equals

public boolean equals(Object p)
Specified by:
equals in interface Collection
Overrides:
equals in class Object


Copyright 2010 UCLA Automated Reasoning Group