edu.ucla.structure
Interface Graph

All Superinterfaces:
Collection, Iterable
All Known Implementing Classes:
HashGraph

public interface Graph
extends Collection

The interface describing undirected graphs. Any object may be a vertex. Following the convention of the Collection interface, some operations are optional. In this case the modification methods are all optionali allowing for mutable or immutable graphs. Typically the definition of a graph requires a non-empty set of vertices. We will slightly abuse the term by allowing empty graphs(graphs with no vertices). This is done in order to simplify incremental creation and destruction of the graph, as well as to conform to the conventions of the Collection interface. The inspiration for this interface comes from the book Structures in Java.i In many respects the implementation is similar.


Method Summary
 boolean add(Object vertex)
          Adds vertex to the graph(Optional operation).
 boolean addEdge(Object vertex1, Object vertex2)
          Adds edge to the graph(Optional operation).
 boolean contains(Object vertex)
          Returns whether or not a particular Object is a vertex in the graph.
 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 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 isTree()
          Determines whether or not the graph is a tree.
 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 removeEdge(Object vertex1, Object vertex2)
          Removes edge from the graph(Optional operation).
 int size()
          Returns the number of vertices in the graph.
 Set vertices()
          Return the set of verticies.
 
Methods inherited from interface Collection
addAll, clear, containsAll, equals, hashCode, isEmpty, iterator, removeAll, retainAll, toArray, toArray
 

Method Detail

vertices

Set vertices()
Return the set of verticies.


neighbors

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

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

Parameters:
vertex- - An Object which is in the graph.

neighboringEdges

Set neighboringEdges(Object vertex)

degree

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

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

Parameters:
vertex- - An Object which is in the graph.

containsEdge

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").

Parameters:
vertex1- - An Object which is in the graph.
vertex2- - An Object which is in the graph.

containsEdge

boolean containsEdge(Edge e)

contains

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

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

size

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

Specified by:
size in interface Collection

isAcyclic

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


isConnected

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


isConnected

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").

Parameters:
vertex1- - An Object which is in the graph.
vertex2- - An Object which is in the graph.

isTree

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


add

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 Collection
Parameters:
vertex- - An Object which is not in the graph.

remove

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 Collection
Parameters:
vertex- - An Object which is currently in the graph.

addEdge

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.

Parameters:
vertex1-An - Object which is currently in the graph.
vertex2-An - Object which is currently in the graph.

removeEdge

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.

Parameters:
vertex1-An - Object which is currently in the graph.
vertex2-An - Object which is currently in the graph.

createIsomorphic

Graph createIsomorphic(Map mapping)


Copyright 2010 UCLA Automated Reasoning Group