edu.ucla.structure
Class HashGraph

Object
  extended by HashGraph
All Implemented Interfaces:
Graph, Iterable, Collection

public class HashGraph
extends Object
implements Graph

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

Author:
jpark

Constructor Summary
HashGraph()
          Creates new HashGraph
HashGraph(Graph g)
           
HashGraph(int size)
           
 
Method Summary
 boolean add(Object vertex)
          Adds vertex to the graph(Optional operation).
 boolean addAll(Collection p)
           
 boolean addEdge(Object vertex1, Object vertex2)
          Adds edge to the graph(Optional operation).
 void clear()
           
 Object clone()
           
 boolean contains(Object vertex)
          Returns whether or not a particular Object is a vertex in the graph.
 boolean containsAll(Collection p)
           
 boolean containsEdge(Edge e)
           
 boolean containsEdge(Object vertex1, Object vertex2)
          Returns whether or not a particular edge is in the graph.
 Graph createIsomorphic(Map mapping)
           
 int degree(Object vertex)
          Returns the degree of vertex.
 boolean equals(Object p)
           
 int hashCode()
           
 boolean isAcyclic()
          Determines whether or not the graph is acyclic.
 boolean isConnected()
          Determines whether or not the graph is connected.
 boolean isConnected(Object vertex1, Object vertex2)
          Determines if there is a path from vertex1 to vertex2.
 boolean isEmpty()
           
 boolean isTree()
          Determines whether or not the graph is a tree.
 Iterator iterator()
           
static void main(String[] args)
           
 Set neighboringEdges(Object vertex)
           
 Set neighbors(Object vertex)
          Construct an Iterator over the vertices adjacent to vertex.
 boolean remove(Object vertex)
          Removes vertex from the graph(Optional operation).
 boolean removeAll(Collection p)
           
 boolean removeEdge(Object vertex1, Object vertex2)
          Removes edge from the graph(Optional operation).
 boolean retainAll(Collection p)
           
 int size()
          Returns the number of vertices in the graph.
 Object[] toArray()
           
 Object[] toArray(Object[] p)
           
 Set vertices()
          Construct an Iterator over all vertices.
 
Methods inherited from class Object
getClass, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

HashGraph

public HashGraph()
Creates new HashGraph


HashGraph

public HashGraph(Graph g)

HashGraph

public HashGraph(int size)
Method Detail

createIsomorphic

public Graph createIsomorphic(Map mapping)
Specified by:
createIsomorphic in interface Graph

clone

public Object clone()
Overrides:
clone in class Object

vertices

public Set vertices()
Construct an Iterator over all vertices.

Specified by:
vertices in interface Graph

neighbors

public Set neighbors(Object vertex)
Construct an Iterator over the vertices adjacent to vertex.

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

Specified by:
neighbors in interface Graph
Parameters:
vertex- - An Object which is in the graph.

neighboringEdges

public Set neighboringEdges(Object vertex)
Specified by:
neighboringEdges in interface Graph

degree

public int degree(Object vertex)
Returns the degree of vertex. If vertex is not in the graph, the behavior is undefined.

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

Specified by:
degree in interface Graph
Parameters:
vertex- - An Object which is in the graph.

containsEdge

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

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

Specified by:
containsEdge in interface Graph
Parameters:
vertex1- - An Object which is in the graph.
vertex2- - An Object which is in the graph.

containsEdge

public boolean containsEdge(Edge e)
Specified by:
containsEdge in interface Graph

contains

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

Specified by:
contains in interface Graph
Specified by:
contains in interface Collection
Parameters:
vertex- - Any Object.

size

public int size()
Returns the number of vertices in the graph.

Specified by:
size in interface Graph
Specified by:
size in interface Collection

isAcyclic

public boolean isAcyclic()
Determines whether or not the graph is acyclic.

Specified by:
isAcyclic in interface Graph

isConnected

public boolean isConnected()
Determines whether or not the graph is connected.

Specified by:
isConnected in interface Graph

isConnected

public boolean isConnected(Object vertex1,
                           Object vertex2)
Determines if there is a path from vertex1 to vertex2.

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

Specified by:
isConnected in interface Graph
Parameters:
vertex1- - An Object which is in the graph.
vertex2- - An Object which is in the graph.

isTree

public boolean isTree()
Determines whether or not the graph is a tree.

Specified by:
isTree in interface Graph

add

public boolean add(Object vertex)
Adds vertex to the graph(Optional operation).

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

Specified by:
add in interface Graph
Specified by:
add in interface Collection
Parameters:
vertex- - An Object which is not in the graph.

remove

public boolean remove(Object vertex)
Removes vertex from the graph(Optional operation).

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

Specified by:
remove in interface Graph
Specified by:
remove in interface Collection
Parameters:
vertex- - An Object which is currently in the graph.

addEdge

public boolean addEdge(Object vertex1,
                       Object vertex2)
Adds edge to the graph(Optional operation).

Precondition:
vertex1 and vertex2 are in the graph and the edge (vertex1,vertex2) is not.
Postcondition:
the edge (vertex1,vertex2) is in the graph.

Specified by:
addEdge in interface Graph
Parameters:
vertex1-An - Object which is currently in the graph.
vertex2-An - Object which is currently in the graph.

removeEdge

public boolean removeEdge(Object vertex1,
                          Object vertex2)
Removes edge from the graph(Optional operation).

Precondition:
vertex1 and vertex2 are both vertices of the graph and are adjacent.
Postcondition:
the edge (vertex1,vertex2) is in the graph.

Specified by:
removeEdge in interface Graph
Parameters:
vertex1-An - Object which is currently in the graph.
vertex2-An - Object which is currently in the graph.

retainAll

public boolean retainAll(Collection p)
Specified by:
retainAll in interface Collection

toArray

public Object[] toArray(Object[] p)
Specified by:
toArray in interface Collection

toArray

public Object[] toArray()
Specified by:
toArray in interface Collection

removeAll

public boolean removeAll(Collection p)
Specified by:
removeAll in interface Collection

iterator

public Iterator iterator()
Specified by:
iterator in interface Iterable
Specified by:
iterator in interface Collection

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

addAll

public boolean addAll(Collection p)
Specified by:
addAll in interface Collection

containsAll

public boolean containsAll(Collection p)
Specified by:
containsAll in interface Collection

isEmpty

public boolean isEmpty()
Specified by:
isEmpty in interface Collection

equals

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

main

public static void main(String[] args)


Copyright 2010 UCLA Automated Reasoning Group