V - the type parameter of the nodes in the graph data sourcepublic class IncSCCAlg<V> extends java.lang.Object implements IGraphObserver<V>, ITcDataSource<V>
| Modifier and Type | Field and Description |
|---|---|
IBiDirectionalGraphDataSource<V> |
gds |
UnionFind<V> |
sccs |
| Constructor and Description |
|---|
IncSCCAlg(IGraphDataSource<V> graphDataSource) |
| Modifier and Type | Method and Description |
|---|---|
void |
attachObserver(ITcObserver<V> to)
Attach a transitive closure relation observer.
|
boolean |
checkTcRelation(DRedTcRelation<V> tc) |
void |
detachObserver(ITcObserver<V> to)
Detach a transitive closure relation observer.
|
void |
dispose()
Call this method to properly dispose the data structures of a transitive closure algorithm.
|
void |
edgeDeleted(V source,
V target)
Used to notify when an edge is deleted from the graph.
|
void |
edgeInserted(V source,
V target)
Used to notify when an edge is inserted into the graph.
|
java.util.Set<V> |
getAllReachableSources(V target)
Returns all nodes from which the target node is reachable.
|
java.util.Set<V> |
getAllReachableTargets(V source)
Returns all nodes which are reachable from the source node.
|
IGraphPathFinder<V> |
getPathFinder()
The returned
IGraphPathFinder can be used to retrieve paths between nodes using transitive reachability. |
java.util.List<V> |
getReachabilityPath(V source,
V target) |
Graph<V> |
getReducedGraph()
The graph of SCCs; each SCC is represented by its representative node (see
getRepresentative(Object)) |
V |
getRepresentative(V node)
Returns the node that is selected as the representative of the SCC containing the argument.
|
java.util.Set<Tuple<V>> |
getTcRelation() |
boolean |
hasIncomingEdges(V root)
Returns true if the SCC represented by the given root node has incoming edges in the reduced graph,
false otherwise (if this SCC is a source in the reduced graph).
|
boolean |
hasOutgoingEdges(V root)
Returns true if the SCC represented by the given root node has outgoing edges in the reduced graph,
false otherwise (if this SCC is a sink in the reduced graph).
|
boolean |
isIsolated(V node) |
boolean |
isReachable(V source,
V target)
Returns true if the target node is reachable from the source node.
|
void |
nodeDeleted(V n)
Used to notify when a node is deleted from the graph.
|
void |
nodeInserted(V n)
Used to notify when a node is inserted into the graph.
|
protected void |
notifyTcObservers(java.util.Set<V> sources,
java.util.Set<V> targets,
Direction direction)
Call this method to notify the observers of the transitive closure relation.
|
public IBiDirectionalGraphDataSource<V> gds
public IncSCCAlg(IGraphDataSource<V> graphDataSource)
public void edgeInserted(V source, V target)
IGraphObserveredgeInserted in interface IGraphObserver<V>source - the source of the edgetarget - the target of the edgepublic void edgeDeleted(V source, V target)
IGraphObserveredgeDeleted in interface IGraphObserver<V>source - the source of the edgetarget - the target of the edgepublic void nodeInserted(V n)
IGraphObservernodeInserted in interface IGraphObserver<V>n - the nodepublic void nodeDeleted(V n)
IGraphObservernodeDeleted in interface IGraphObserver<V>n - the nodepublic void attachObserver(ITcObserver<V> to)
ITcDataSourceattachObserver in interface ITcDataSource<V>to - the observer objectpublic void detachObserver(ITcObserver<V> to)
ITcDataSourcedetachObserver in interface ITcDataSource<V>to - the observer objectpublic java.util.Set<V> getAllReachableTargets(V source)
ITcDataSourcegetAllReachableTargets in interface ITcDataSource<V>source - the source nodepublic java.util.Set<V> getAllReachableSources(V target)
ITcDataSourcegetAllReachableSources in interface ITcDataSource<V>target - the target nodepublic boolean isReachable(V source, V target)
ITcDataSourceisReachable in interface ITcDataSource<V>source - the source nodetarget - the target nodepublic boolean checkTcRelation(DRedTcRelation<V> tc)
public boolean hasIncomingEdges(V root)
root - the root node of an SCCpublic boolean hasOutgoingEdges(V root)
root - the root node of an SCCpublic void dispose()
ITcDataSourcedispose in interface ITcDataSource<V>protected void notifyTcObservers(java.util.Set<V> sources, java.util.Set<V> targets, Direction direction)
sources - the source nodestargets - the target nodesdirection - public V getRepresentative(V node)
public boolean isIsolated(V node)
public IGraphPathFinder<V> getPathFinder()
ITcDataSourceIGraphPathFinder can be used to retrieve paths between nodes using transitive reachability.getPathFinder in interface ITcDataSource<V>public Graph<V> getReducedGraph()
getRepresentative(Object))