edu.ucla.structure
Class AbstractDirectedGraph

Object
  extended by AbstractDirectedGraph
All Implemented Interfaces:
DirectedGraph, Cloneable, Iterable, Collection
Direct Known Subclasses:
DecisionTreeImpl, HashDirectedGraph

public abstract class AbstractDirectedGraph
extends Object
implements DirectedGraph, Collection, Cloneable

Convenience class for implementing DirectedGraph. You must implement only 5 methods, but you probably want to override others for performance reasons.

Since:
121504
Author:
Keith Cascio

Field Summary
static PrintStream STREAM_DEBUG
           
 
Constructor Summary
AbstractDirectedGraph()
           
 
Method Summary
 boolean add(Object obj)
           
 boolean addAll(Collection p)
           
 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).
abstract  Object clone()
          interface DirectedGraph
 boolean containsAll(Collection p)
           
 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.
 Iterator depthFirstIterator()
           
 boolean hasPath(Object vertex1, Object vertex2)
          Determines if there is a directed path from vertex1 to vertex2.
 int inDegree(Object vertex)
          Returns the number of edges entering the vertex.
 boolean isAcyclic()
          Determines whether or not the graph is acyclic.
 boolean isEmpty()
           
 boolean isSinglyConnected()
          Determines whether or not the graph is a singly connected.
 boolean isWeaklyConnected()
          Determines whether or not the graph is weakly connected.
 boolean isWeaklyConnected(Object vertex1, Object vertex2)
          Determines if there is an undirected path from vertex1 to vertex2.
 Iterator iterator()
           
 boolean maintainsAcyclicity(Object vertex1, Object vertex2)
           Check whether adding the proposed edge would keep the graph acyclic.
 int numEdges()
           
 int outDegree(Object vertex)
          Returns the number of edges leaving the vertex.
 boolean remove(Object obj)
           
 boolean removeAll(Collection p)
           
 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)
           
 boolean retainAll(Collection p1)
           
 int size()
          Returns the number of vertices in the graph.
 Object[] toArray()
           
 Object[] toArray(Object[] p)
           
 List topologicalOrder()
           
 Set vertices()
          Constructs an Iterator over all vertices.
 
Methods inherited from class Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface DirectedGraph
contains, inComing, outGoing
 
Methods inherited from interface Collection
clear, equals, hashCode
 

Field Detail

STREAM_DEBUG

public static final PrintStream STREAM_DEBUG
Constructor Detail

AbstractDirectedGraph

public AbstractDirectedGraph()
Method Detail

clone

public abstract Object clone()
interface DirectedGraph

Specified by:
clone in interface DirectedGraph
Overrides:
clone in class Object

degree

public int degree(Object vertex)
Description copied from interface: DirectedGraph
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
Returns:
the number of vertices adjacent to vertex.

inDegree

public int inDegree(Object vertex)
Description copied from interface: DirectedGraph
Returns the number of edges entering the vertex.

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

Specified by:
inDegree in interface DirectedGraph
Returns:
the number of edges entering the vertex.

outDegree

public int outDegree(Object vertex)
Description copied from interface: DirectedGraph
Returns the number of edges leaving the vertex.

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

Specified by:
outDegree in interface DirectedGraph
Returns:
the number of edges leaving the vertex.

containsEdge

public boolean containsEdge(Object vertex1,
                            Object vertex2)
Description copied from interface: DirectedGraph
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
Returns:
true if edge (vertex1,vertex2) is in the graph, false otherwise.

numEdges

public int numEdges()
Specified by:
numEdges in interface DirectedGraph

depthFirstIterator

public Iterator depthFirstIterator()
Returns:
An iterator over the vertices in the graph, guaranteed to return the vertices in depth first order.
Since:
031502

maintainsAcyclicity

public boolean maintainsAcyclicity(Object vertex1,
                                   Object vertex2)

Check whether adding the proposed edge would keep the graph acyclic.

Precondition: the graph is acyclic.

Specified by:
maintainsAcyclicity in interface DirectedGraph
Since:
080602

vertices

public Set vertices()
Description copied from interface: DirectedGraph
Constructs an Iterator over all vertices.

Specified by:
vertices in interface DirectedGraph
Returns:
Iterator over all vertices.

size

public int size()
Description copied from interface: DirectedGraph
Returns the number of vertices in the graph.

Specified by:
size in interface DirectedGraph
Specified by:
size in interface Collection
Returns:
the number of vertices in the graph.

isAcyclic

public boolean isAcyclic()
Determines whether or not the graph is acyclic. Cycles are considered in the dirrected sense. Ex A->B,A->C,B->C is acyclic while A->B,B->C,C->A is not. It is equivalent to asking if it is a DAG. By convention the empty graph is connected.

Specified by:
isAcyclic in interface DirectedGraph
Returns:
false if the graph contains a cycle, true otherwise.

replaceVertex

public void replaceVertex(Object oldVertex,
                          Object newVertex)
Specified by:
replaceVertex in interface DirectedGraph

replaceVertices

public void replaceVertices(Map verticesOldToNew,
                            NodeLinearTask task)
Specified by:
replaceVertices in interface DirectedGraph

isWeaklyConnected

public boolean isWeaklyConnected()
Determines whether or not the graph is weakly connected. This is the same as asking if the undirected graph produced by eliminating the directionality of the edges is connected. By convention the empty graph is connected.

Specified by:
isWeaklyConnected in interface DirectedGraph
Returns:
true if the graph is connected, false otherwise.

isWeaklyConnected

public boolean isWeaklyConnected(Object vertex1,
                                 Object vertex2)
Determines if there is an undirected path from vertex1 to vertex2.

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

Specified by:
isWeaklyConnected in interface DirectedGraph
Parameters:
vertex1- - An Object which is in the graph.
vertex2- - An Object which is in the graph.
Returns:
true if there is an undirected path from vertex1 to vertex2.

hasPath

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

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

Specified by:
hasPath in interface DirectedGraph
Parameters:
vertex1- - An Object which is in the graph.
vertex2- - An Object which is in the graph.
Returns:
true if there is a directed path from vertex1 to vertex2.

isSinglyConnected

public boolean isSinglyConnected()
Determines whether or not the graph is a singly connected. A singly connected digraph is a directed graph in which there is exactly one undirected path between any two vertices. By convention the empty graph is singly connected.

Specified by:
isSinglyConnected in interface DirectedGraph
Returns:
true if the graph is a singly connected, false otherwise.

addVertex

public boolean addVertex(Object vertex)
Description copied from interface: DirectedGraph
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
Returns:
true if the graph was modified(i.e. vertex was not a vertex already) false otherwise.

removeVertex

public boolean removeVertex(Object vertex)
Description copied from interface: DirectedGraph
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

addEdge

public boolean addEdge(Object vertex1,
                       Object vertex2)
Description copied from interface: DirectedGraph
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

removeEdge

public boolean removeEdge(Object vertex1,
                          Object vertex2)
Description copied from interface: DirectedGraph
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

topologicalOrder

public List topologicalOrder()
Specified by:
topologicalOrder in interface DirectedGraph
Returns:
A List over the vertices of the graph, in topological order.
Since:
031502

add

public final boolean add(Object obj)
Specified by:
add in interface Collection
Since:
100102

remove

public final boolean remove(Object obj)
Specified by:
remove in interface Collection
Since:
100102

retainAll

public boolean retainAll(Collection p1)
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

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


Copyright 2010 UCLA Automated Reasoning Group