|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectgoldman.graph.AbstractGraph<V,E>
public abstract class AbstractGraph<V,E extends Edge<V>>
The AbstractGraph class embodies algorithms that perform
computations on a graph in terms of the Graph
interface. This allows subclasses that use any graph
representation to benefit from these algorithms.
Field Summary | |
---|---|
static double |
INF
Representation for infinity. |
Constructor Summary | |
---|---|
AbstractGraph(GraphRepresentation<V,E> graph,
boolean multigraph)
It creates an abstract graph with the given specification. |
Method Summary | |
---|---|
void |
addEdge(E e)
Adds the given edge to this graph. |
boolean |
addVertex(V v)
Adds the given vertex to this graph. |
boolean |
allowsMultiEdges()
Returns true if and only if this graph allows multi-edges. |
boolean |
containsEdge(V source,
V dest)
Returns true if and only if there is an edge from source
to dest in this graph. |
boolean |
containsVertex(V v)
Returns true if and only if the given vertex is in this graph. |
Iterator<E> |
edgesFrom(V v)
Returns an iterator over the outgoing edges from the given vertex. |
Iterator<E> |
edgesTo(V v)
Returns an iterator over the incoming edges for the given vertex. |
Set<Set<V>> |
getConnectedComponents()
Returns a set holding the set of vertices in each connected component of this graph. |
PositionalCollection<E> |
getCycle()
The hasCycle method can be used to determine if the graph has
a directed cycle. |
E |
getEdge(V source,
V dest)
Returns an edge in the graph from source
to dest , or null if there is no such edge. |
Set<Set<V>> |
getStronglyConnectedComponents()
Returns a set holding the set of vertices in each strongly connected component of this graph. |
boolean |
hasCycle()
Returns true if and only this graph has a cycle. |
boolean |
isDirected()
Returns true if and only if this graph is a directed graph. |
NonMutatingIterator<V> |
iterator()
Returns a non-mutating iterator over the vertices in this graph. |
int |
numConnectedComponents()
Returns the number of connected components in this graph. |
int |
numStronglyConnectedComponents()
Returns the number of strongly connected components in this graph. |
int |
numVertices()
Returns the number of vertices in this graph. |
boolean |
removeEdge(E e)
Removes the given edge from this graph. |
boolean |
removeVertex(V v)
Removes the given vertex from this graph. |
PositionalCollection<V> |
topologicalOrder()
The hasCycle method can be called first to find out if
the graph has a cycle. |
String |
toString()
|
InTree<V,E> |
unweightedShortestPaths(V s)
Uses breadth-first search to compute and return a shortest path tree for the given source vertex. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Field Detail |
---|
public static final double INF
Constructor Detail |
---|
public AbstractGraph(GraphRepresentation<V,E> graph, boolean multigraph)
graph
- the graph representationmultigraph
- true if the graph allows multi-edgesMethod Detail |
---|
public boolean isDirected()
Graph
isDirected
in interface Graph<V,E extends Edge<V>>
public boolean allowsMultiEdges()
Graph
allowsMultiEdges
in interface Graph<V,E extends Edge<V>>
public int numVertices()
Graph
numVertices
in interface Graph<V,E extends Edge<V>>
public boolean containsVertex(V v)
Graph
containsVertex
in interface Graph<V,E extends Edge<V>>
v
- the target vertex
public boolean containsEdge(V source, V dest)
Graph
source
to dest
in this graph.
containsEdge
in interface Graph<V,E extends Edge<V>>
source
- the source vertexdest
- the destination vertex
public E getEdge(V source, V dest)
Graph
source
to dest
, or null if there is no such edge.
getEdge
in interface Graph<V,E extends Edge<V>>
source
- the source vertexdest
- the destination vertex
public boolean addVertex(V v)
Graph
addVertex
in interface Graph<V,E extends Edge<V>>
v
- the vertex to add to this graph
public boolean removeVertex(V v)
Graph
removeVertex
in interface Graph<V,E extends Edge<V>>
v
- the vertex to remove
public void addEdge(E e)
Graph
addEdge
in interface Graph<V,E extends Edge<V>>
e
- the edge to add to this graph
public boolean removeEdge(E e)
Graph
removeEdge
in interface Graph<V,E extends Edge<V>>
e
- the edge to remove
public NonMutatingIterator<V> iterator()
Graph
iterator
in interface Graph<V,E extends Edge<V>>
iterator
in interface Iterable<V>
public Iterator<E> edgesFrom(V v)
Graph
edgesFrom
in interface Graph<V,E extends Edge<V>>
v
- the desired vertex
public Iterator<E> edgesTo(V v)
Graph
edgesTo
in interface Graph<V,E extends Edge<V>>
v
- the desired vertex
UnsupportedOperationException
- the graph representation does not
support this capabilitypublic InTree<V,E> unweightedShortestPaths(V s)
Graph
unweightedShortestPaths
in interface Graph<V,E extends Edge<V>>
s
- the source vertex
public boolean hasCycle()
Graph
hasCycle
in interface Graph<V,E extends Edge<V>>
public PositionalCollection<E> getCycle()
hasCycle
method can be used to determine if the graph has
a directed cycle.
getCycle
in interface Graph<V,E extends Edge<V>>
GraphException
- the graph is acyclicpublic int numConnectedComponents()
Graph
GraphException
when
the graph is directed since the connected components are defined only for
an undirected graph.
numConnectedComponents
in interface Graph<V,E extends Edge<V>>
GraphException
- the graph is directed,
since the connected components are defined only for undirected graphspublic Set<Set<V>> getConnectedComponents()
Graph
GraphException
when
the graph is directed since the connected components are defined only for
an undirected graph.
getConnectedComponents
in interface Graph<V,E extends Edge<V>>
GraphException
- the graph is directed,
since the connected components are only defined for undirected graphspublic PositionalCollection<V> topologicalOrder()
hasCycle
method can be called first to find out if
the graph has a cycle.
topologicalOrder
in interface Graph<V,E extends Edge<V>>
GraphException
- the graph is cyclicpublic Set<Set<V>> getStronglyConnectedComponents()
Graph
GraphException
when
the graph is undirected since the strongly connected components are defined only for
a directed graph.
getStronglyConnectedComponents
in interface Graph<V,E extends Edge<V>>
GraphException
- the graph is undirected,
since the strongly connected components are defined only for directed graphspublic int numStronglyConnectedComponents()
Graph
GraphException
when
the graph is undirected since the strongly connected components are defined only for
a directed graph.
numStronglyConnectedComponents
in interface Graph<V,E extends Edge<V>>
GraphException
- the graph is undirected,
since the strongly connected components are defined only for directed graphspublic String toString()
toString
in class Object
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |