public class Graph<T>
extends java.lang.Object
Modifier and Type | Class and Description |
---|---|
static class |
Graph.Node<T> |
Modifier and Type | Field and Description |
---|---|
private java.util.Comparator<Graph.Node<T>> |
comparator |
private java.util.Map<T,Graph.Node<T>> |
m_independentNodes |
private java.util.Map<T,Graph.Node<T>> |
m_nodes |
private java.util.List<T> |
m_strictlySortedNodes |
private static boolean |
m_verbose |
Constructor and Description |
---|
Graph(java.util.Comparator<Graph.Node<T>> comparator) |
Modifier and Type | Method and Description |
---|---|
private void |
addNeighbor(T tm,
T predecessor) |
void |
addNode(T tm) |
void |
addPredecessor(T tm,
T predecessor) |
private void |
dumpSortedNodes() |
private Graph.Node<T> |
findNode(T object) |
private Graph.Node<T> |
findNodeWithNoPredecessors(java.util.List<Graph.Node<T>> nodes) |
java.util.List<T> |
findPredecessors(T o) |
java.util.Set<T> |
getIndependentNodes() |
private java.util.Collection<Graph.Node<T>> |
getNodes() |
java.util.Set<T> |
getPredecessors(T node) |
java.util.List<T> |
getStrictlySortedNodes() |
private void |
initializeIndependentNodes() |
boolean |
isIndependent(T object) |
private static void |
ppp(java.lang.String s) |
private void |
removeFromNodes(java.util.List<Graph.Node<T>> nodes,
Graph.Node<T> node)
Remove a node from a list of nodes and update the list of predecessors for all the remaining
nodes.
|
void |
topologicalSort() |
java.lang.String |
toString() |
private static boolean m_verbose
private java.util.Map<T,Graph.Node<T>> m_nodes
private java.util.List<T> m_strictlySortedNodes
private final java.util.Comparator<Graph.Node<T>> comparator
private java.util.Map<T,Graph.Node<T>> m_independentNodes
public Graph(java.util.Comparator<Graph.Node<T>> comparator)
public void addNode(T tm)
public boolean isIndependent(T object)
private Graph.Node<T> findNode(T object)
private java.util.Collection<Graph.Node<T>> getNodes()
public java.util.Set<T> getIndependentNodes()
public java.util.List<T> getStrictlySortedNodes()
public void topologicalSort()
private void initializeIndependentNodes()
private void dumpSortedNodes()
private void removeFromNodes(java.util.List<Graph.Node<T>> nodes, Graph.Node<T> node)
private static void ppp(java.lang.String s)
private Graph.Node<T> findNodeWithNoPredecessors(java.util.List<Graph.Node<T>> nodes)
public java.util.List<T> findPredecessors(T o)
o
- - The predecessorpublic java.lang.String toString()
toString
in class java.lang.Object