Package com.intellij.util.graph

Class DFSTBuilder<Node>

java.lang.Object

com.intellij.util.graph.DFSTBuilder<Node>

public final class DFSTBuilder<Node>
extends java.lang.Object

Constructor Summary

Constructors

Constructor and Description
DFSTBuilder(Graph<Node> graph)
DFSTBuilder(Graph<Node> graph, Node entryNode)
DFSTBuilder(OutboundSemiGraph<Node> graph)
DFSTBuilder(OutboundSemiGraph<Node> graph, Node entryNode)

Method Summary

Modifier and Type	Method and Description
java.util.Comparator<Node>	comparator()
java.util.Comparator<Node>	comparator(boolean useNNumber)
Couple<Node>	getCircularDependency()
java.util.Collection<java.util.Collection<Node>>	getComponents()
Node	getNodeByNNumber(int n)
Node	getNodeByTNumber(int n)
TIntArrayList	getSCCs()
java.util.List<Node>	getSortedNodes()
boolean	isAcyclic()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DFSTBuilder

public DFSTBuilder(Graph<Node> graph)

See Also:

DFSTBuilder(OutboundSemiGraph, Object)

DFSTBuilder

public DFSTBuilder(Graph<Node> graph,
                   Node entryNode)

See Also:

DFSTBuilder(OutboundSemiGraph, Object)

DFSTBuilder

public DFSTBuilder(OutboundSemiGraph<Node> graph)

See Also:

DFSTBuilder(OutboundSemiGraph, Object)

DFSTBuilder

public DFSTBuilder(OutboundSemiGraph<Node> graph,
                   Node entryNode)

Parameters:

entryNode - is a first node for Tarjan's algorithm. Different entry nodes produce different node numbers in topological ordering. if all nodes of the graph is reachable from the entry node and the entry node doesn't have incoming edges then passing the entry node could be used for finding "natural" back edges (like a loop back edge)

Method Detail

comparator

public java.util.Comparator<Node> comparator()

comparator

public java.util.Comparator<Node> comparator(boolean useNNumber)

Parameters:

useNNumber - if true then a node number in topological ordering will be used for comparison otherwise a node number in scc topological order will be used

getCircularDependency

public Couple<Node> getCircularDependency()

isAcyclic

public boolean isAcyclic()

getNodeByNNumber

public Node getNodeByNNumber(int n)

getNodeByTNumber

public Node getNodeByTNumber(int n)

getSCCs

public TIntArrayList getSCCs()

Returns:

the list containing the number of nodes in strongly connected components. Respective nodes could be obtained via getNodeByTNumber(int).

getComponents

public java.util.Collection<java.util.Collection<Node>> getComponents()

getSortedNodes

public java.util.List<Node> getSortedNodes()