edu.ucla.structure
Interface DirectedGraph

All Superinterfaces:
Cloneable, Collection, Iterable
All Known Subinterfaces:
BeliefNetwork, GenieNet, HuginNet
All Known Implementing Classes:
AbstractDirectedGraph, BeliefNetworkImpl, DecisionTreeImpl, GenieNetImpl, HashDirectedGraph, HuginNetImpl

public interface DirectedGraph
extends Collection, Cloneable

The interface describing directed 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 optional allowing for mutable or immutable graphs. Typically the definition of a directed graph requires a non-empty set of vertices. We will slightly abuse the term by allowing empty directed 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. In many respects the implementation is similar. Passing an Object that is not a vertex when a vertex is called for is considered bad form, so behavior may vary from implementation to implementation.


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).
 Object clone()
           
 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 hasPath(Object vertex1, Object vertex2)
          Determines if there is a directed path from vertex1 to vertex2.
 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.
 boolean isAcyclic()
          Determines whether or not the graph is acyclic.
 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.
 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.
 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)
           
 int size()
          Returns the number of vertices in the graph.
 List topologicalOrder()
           
 Set vertices()
          Constructs an Iterator over all vertices.
 
Methods inherited from interface Collection
add, addAll, clear, containsAll, equals, hashCode, isEmpty, iterator, remove, removeAll, retainAll, toArray, toArray
 

Method Detail

clone

Object clone()
Since:
20020524

topologicalOrder

List topologicalOrder()
Returns:
A List over the vertices of the graph, in topological order.
Since:
031502

replaceVertex

void replaceVertex(Object oldVertex,
                   Object newVertex)
Since:
20020603

replaceVertices

void replaceVertices(Map verticesOldToNew,
                     NodeLinearTask task)
Since:
20060520

maintainsAcyclicity

boolean maintainsAcyclicity(Object vertex1,
                            Object vertex2)

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

Precondition: the graph is acyclic.

Since:
080602

vertices

Set vertices()
Constructs an Iterator over all vertices.

Returns:
Iterator over all vertices.

inComing

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

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

outGoing

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

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

degree

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

Parameters:
vertex- - An Object which is in the graph.
Returns:
the number of vertices adjacent to vertex.

inDegree

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

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

Parameters:
vertex- - An Object which is in the graph.
Returns:
the number of edges entering the vertex.

outDegree

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

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

Parameters:
vertex- - An Object which is in the graph.
Returns:
the number of edges leaving the vertex.

containsEdge

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

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

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.
Returns:
true if vertex is in the graph(tested by "equals"), false otherwise.

size

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

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

numEdges

int numEdges()

isAcyclic

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.

Returns:
false if the graph contains a cycle, true otherwise.

isWeaklyConnected

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.

Returns:
true if the graph is connected, false otherwise.

isWeaklyConnected

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

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

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

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

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.

Returns:
true if the graph is a singly connected, false otherwise.

addVertex

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

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

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

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

addEdge

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.


removeEdge

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.



Copyright 2010 UCLA Automated Reasoning Group