edu.gwu.algtest
Interface UndirectedGraphSearchAlgorithm
- All Superinterfaces:
- Algorithm
- All Known Subinterfaces:
- DirectedGraphSearchAlgorithm
- public interface UndirectedGraphSearchAlgorithm
- extends Algorithm
Algorithms that traverse an undirected graph implement interface
UndirectedGraphSearchAlgorithm.
Not all methods need to be implemented to make a graph search algorithm useful.
Often the most important method is the one that returns the number of connected
components (using depth-first search). Before calling any of the methods, the
initialize method is called with the number of vertices and type of graph.
Next, one of the insert methods is called repeatedly until all edges are given
to the algorithm, analogous to the insert operation of a data structure.
NOTE: the number of edges is not given to the algorithm at
the time of initialization. After the all edges are inserted, one or more
of the other methods are called.
Next, observe that adjacency lists don't often specify the order in which
vertices appear in any particular vertex list. We will use the term "standard ordering"
for the ordering where newly inserted vertices are always added to the rear of
the appropriate list. This will make the adjacency list representation unique
for a particular set of insertions.
|
Method Summary |
GraphEdge[] |
articulationEdges()
articulationEdges should return a list of
articulation edges. |
int[] |
articulationVertices()
articulationVertices should return a list
of articulation vertices. |
int[] |
breadthFirstVisitOrder()
breadthFirstVisitOrder should return an array of
of vertices of exactly the same length as the number of vertices. |
int[] |
componentLabels()
componentLabels should return the component label
for each vertex for an undirected graph. |
int[] |
depthFirstCompletionOrder()
depthFirstCompletionOrder should return an array
where the i-th entry is the completion time (order) of vertex i
in the depth first search. |
int[] |
depthFirstVisitOrder()
depthFirstVisitOrder should return an array of vertices,
of exactly the same length as the number of vertices. |
boolean |
existsCycle()
existsCycle should return true if the graph has
a cycle, false otherwise. |
boolean |
existsOddCycle()
existsOddCycle should return true if the graph
has an odd cycle (i.e., is not bipartite), false otherwise. |
void |
initialize(int numVertices,
boolean isWeighted)
initialize is given the number of vertices, which are assumed
to be numbered 0, 1, 2, ...,numVertices-1, and is informed
whether the graph edges will carry weights. |
void |
insertUndirectedEdge(int startVertex,
int endVertex,
double weight)
insertUndirectedEdge is called with the endpoints of the edge. |
int |
numConnectedComponents()
numConnectedComponents should return the number of
of connected components for an undirected graph. |
initialize
public void initialize(int numVertices,
boolean isWeighted)
initialize is given the number of vertices, which are assumed
to be numbered 0, 1, 2, ...,numVertices-1, and is informed
whether the graph edges will carry weights. If the graph is not a weighted graph,
edge weights are to be ignored. Note: initialize will be called before any inserts
and is an indication that an entirely new graph will be input to the algorithm;
this is a good time to reset all appropriate variables and clear out any
internal data structures.
- Parameters:
numVertices - an int valueisWeighted - a boolean value
insertUndirectedEdge
public void insertUndirectedEdge(int startVertex,
int endVertex,
double weight)
insertUndirectedEdge is called with the endpoints of the edge.
The algorithm should treat this a single undirected edge. Thus, a single
call with startVertex=0 and endVertex=1 indicates
an undirected edge between node 0 and node 1. After this, there will be no
call with startVertex=1 and endVertex=0. Hence,
both matrix entries need to be filled in an adjacency-matrix representation,
and both lists need the edge added in the adjacency-list representation.
Note: we will allow self-loops to be input, i.e., an edge from a vertex to itself.
If the graph is not specified as a weighted graph, the weight parameter can
ignored.
- Parameters:
startVertex - an int valueendVertex - an int valueweight - a double value
breadthFirstVisitOrder
public int[] breadthFirstVisitOrder()
breadthFirstVisitOrder should return an array of
of vertices of exactly the same length as the number of vertices.
This array should contain the visit-order-number for each vertex,
when breadth-first search is applied.
For example, consider the call int[] visitOrder = alg.breadthFirstVisitOrder().
Then, visitOrder[3] = 7, if vertex 3 was visited eighth in
order (visitOrder[i]=0, if i was visited first).
Note that this
order is unique for a particular insertion order if insertions
are done properly. That is, in an adjacency list, insertions
should be added to the rear of the appropriate list. For
an adjacency matrix, it will not matter.
- Returns:
- an
int[] value
depthFirstVisitOrder
public int[] depthFirstVisitOrder()
depthFirstVisitOrder should return an array of vertices,
of exactly the same length as the number of vertices.
This array should contain the visit-order-number for each vertex,
when depth-first search is applied.
For example, consider the call int[] visitOrder = alg.depthFirstVisitOrder().
Then, visitOrder[3] = 7, if vertex 3 was visited eighth in
order (visitOrder[i]=0, if i was visited first).
Note that this
order is unique for a particular insertion order if insertions
are done properly. That is, in an adjacency list, insertions
should be added to the rear of the appropriate list. For
an adjacency matrix, it will not matter.
- Returns:
- an
int[] value
depthFirstCompletionOrder
public int[] depthFirstCompletionOrder()
depthFirstCompletionOrder should return an array
where the i-th entry is the completion time (order) of vertex i
in the depth first search. The time values should start with 0
and end with numVertices-1. For example, with
the call int[] compOrder = alg.depthFirstCompletionOrder()
(where alg is the algorithm instance).
Thus, compOrder[i]==0 for the first vertex i to bottom out
the recursion (i.e., whose recursion completes).
- Returns:
- an
int[] value
numConnectedComponents
public int numConnectedComponents()
numConnectedComponents should return the number of
of connected components for an undirected graph.
- Returns:
- an
int value
componentLabels
public int[] componentLabels()
componentLabels should return the component label
for each vertex for an undirected graph.
When the call int[] compLabels = alg.componentLabels()
(where alg is the algorithm instance) is made,
compLabels[i] is the component to which vertex i belongs.
The component numbering should start at 0. If insertions are done properly,
the component labelling will be unique.
- Returns:
- an
int[] value
existsCycle
public boolean existsCycle()
existsCycle should return true if the graph has
a cycle, false otherwise.
- Returns:
- a
boolean value
articulationVertices
public int[] articulationVertices()
articulationVertices should return a list
of articulation vertices.
- Returns:
- an
int[] value
articulationEdges
public GraphEdge[] articulationEdges()
articulationEdges should return a list of
articulation edges.
- Returns:
- a
GraphEdge[] value
existsOddCycle
public boolean existsOddCycle()
existsOddCycle should return true if the graph
has an odd cycle (i.e., is not bipartite), false otherwise.
- Returns:
- a
boolean value