jetbrains.buildServer.util.graph
Class DAG<T>

java.lang.Object
  extended by jetbrains.buildServer.util.graph.DAG<T>
Direct Known Subclasses:
BaseModificationDAG, GenericDAG

public abstract class DAG<T>
extends java.lang.Object

Directed acyclic graph

Author:
dmitry.neverov

Constructor Summary
DAG()
           
 
Method Summary
abstract  void breadthFirstSearch(java.util.Set<T> starts, BFSVisitor<T> visitor)
           
abstract  void breadthFirstSearch(T start, BFSVisitor<T> visitor)
          Run breadth-first search from the specified start node
abstract  boolean containsNode(T node)
          Check if graph contains specified node
 void depthFirstSearch(T start, DFSVisitor<T> visitor)
          Run depth-first search from the specified start node
protected  void ensureContainsNode(T node)
           
 DAG<T> exclude(java.util.Collection<T> nodesToExclude)
          Returns DAG which doesn't contain nodes in the specified collection
 DAG<T> filter(Filter<T> filter)
          Returns filtered DAG which contains only nodes accepted by specified filter, same as calling #filter(jetbrains.buildServer.util.filters.Filter, false)
 DAG<T> filter(Filter<T> filter, boolean includeAcceptedNodeParents)
          Returns filtered DAG which contains only nodes accepted by specified filter and, if includeAcceptedNodeParents is set to true, their parents
abstract  DAG<T> filter(Filter<T> filter, boolean includeAcceptedNodeParents, boolean extrapolateEdges)
           
abstract  java.util.Set<T> getAllNodes()
           
abstract  java.util.List<T> getChildren(T node)
          Get children of the specified node
abstract  java.util.List<T> getCommonAncestors(java.util.List<T> nodes)
          Get list of common ancestors for collection of graph nodes
 java.util.List<T> getCommonAncestors(T... nodes)
           
abstract  DepthFirstSearch<T> getDepthFirstSearch(T start, DFSVisitor<T> visitor)
          Returns depth-first search from the specified start node
abstract  java.util.List<T> getNodesWithoutChildren()
          Returns nodes without children
abstract  java.util.List<T> getNodesWithoutParents()
          Returns nodes without parents
abstract  java.util.List<T> getParents(T node)
          Get parents of the specified node
abstract  DepthFirstSearch<T> getReverseDepthFirstSearch(T start, DFSVisitor<T> visitor)
           
 DAG<T> include(java.util.Collection<T> nodesToInclude)
          Returns DAG which contains only nodes in the specified collection
 DAG<T> include(java.util.Collection<T> nodesToInclude, boolean extrapolateEdges)
           
 boolean isEmpty()
           
 DAGIterator<T> iterator()
          Get iterator through the nodes of the graph.
 DAGIterator<T> iterator(java.util.Collection<T> startNodes)
          Get iterator through the nodes of the graph
 DAGIterator<T> iterator(T startNode)
          Get iterator through the nodes of the graph
abstract  void reverseBreadthFirstSearch(T start, BFSVisitor<T> visitor)
           
abstract  int size()
          Returns number of nodes in the graph
abstract  java.util.List<T> toposort()
          Get topologically sorted list of graph nodes (parents go before children)
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

DAG

public DAG()
Method Detail

toposort

@NotNull
public abstract java.util.List<T> toposort()
Get topologically sorted list of graph nodes (parents go before children)

Returns:
see above

getCommonAncestors

@NotNull
public final java.util.List<T> getCommonAncestors(@NotNull
                                                          T... nodes)
See Also:
getCommonAncestors(java.util.List)

getCommonAncestors

@NotNull
public abstract java.util.List<T> getCommonAncestors(@NotNull
                                                             java.util.List<T> nodes)
Get list of common ancestors for collection of graph nodes

Parameters:
nodes - nodes of interest, they should be presented in the graph
Returns:
least common ancestors or empty list if collection of nodes is empty or if there is no common ancestor between nodes.

getParents

@NotNull
public abstract java.util.List<T> getParents(@NotNull
                                                     T node)
Get parents of the specified node

Parameters:
node - node of interest
Returns:
see above

getChildren

@NotNull
public abstract java.util.List<T> getChildren(@NotNull
                                                      T node)
Get children of the specified node

Parameters:
node - node of interest
Returns:
see above

iterator

@NotNull
public DAGIterator<T> iterator()
Get iterator through the nodes of the graph. Same as iterator(getNodesWithoutChildren())

Returns:
see above
See Also:
iterator(java.util.Collection)

iterator

@NotNull
public DAGIterator<T> iterator(@NotNull
                                       T startNode)
Get iterator through the nodes of the graph

Parameters:
startNode - start node for iteration
Returns:
see above

iterator

@NotNull
public DAGIterator<T> iterator(@NotNull
                                       java.util.Collection<T> startNodes)
Get iterator through the nodes of the graph

Parameters:
startNodes - start nodes for iteration
Returns:
see above

exclude

@NotNull
public DAG<T> exclude(@NotNull
                              java.util.Collection<T> nodesToExclude)
Returns DAG which doesn't contain nodes in the specified collection

Parameters:
nodesToExclude - collection of nodes resulting DAG should not have
Returns:
see above

include

@NotNull
public DAG<T> include(@NotNull
                              java.util.Collection<T> nodesToInclude)
Returns DAG which contains only nodes in the specified collection

Parameters:
nodesToInclude - collection of nodes resulting DAG should have
Returns:
see above

include

@NotNull
public DAG<T> include(@NotNull
                              java.util.Collection<T> nodesToInclude,
                              boolean extrapolateEdges)

filter

@NotNull
public DAG<T> filter(@NotNull
                             Filter<T> filter)
Returns filtered DAG which contains only nodes accepted by specified filter, same as calling #filter(jetbrains.buildServer.util.filters.Filter, false)

Parameters:
filter - filter of interest
Returns:
see above

filter

public DAG<T> filter(@NotNull
                     Filter<T> filter,
                     boolean includeAcceptedNodeParents)
Returns filtered DAG which contains only nodes accepted by specified filter and, if includeAcceptedNodeParents is set to true, their parents

Parameters:
filter - filter of interest
includeAcceptedNodeParents - if set to true - all parents of accepted nodes are included into result, if set to false - parents will be filtered and result will include only accepted parents
Returns:
see above

filter

public abstract DAG<T> filter(@NotNull
                              Filter<T> filter,
                              boolean includeAcceptedNodeParents,
                              boolean extrapolateEdges)

containsNode

public abstract boolean containsNode(@NotNull
                                     T node)
Check if graph contains specified node

Parameters:
node - node to check
Returns:
true if graph contains node, false otherwise

getNodesWithoutParents

@NotNull
public abstract java.util.List<T> getNodesWithoutParents()
Returns nodes without parents

Returns:
see above

getNodesWithoutChildren

@NotNull
public abstract java.util.List<T> getNodesWithoutChildren()
Returns nodes without children

Returns:
see above

depthFirstSearch

public final void depthFirstSearch(@NotNull
                                   T start,
                                   @NotNull
                                   DFSVisitor<T> visitor)
Run depth-first search from the specified start node

Parameters:
start - start node for the search
visitor - visitor

breadthFirstSearch

public abstract void breadthFirstSearch(@NotNull
                                        T start,
                                        @NotNull
                                        BFSVisitor<T> visitor)
Run breadth-first search from the specified start node

Parameters:
start - start node for the search
visitor - visitor

breadthFirstSearch

public abstract void breadthFirstSearch(@NotNull
                                        java.util.Set<T> starts,
                                        @NotNull
                                        BFSVisitor<T> visitor)

reverseBreadthFirstSearch

public abstract void reverseBreadthFirstSearch(@NotNull
                                               T start,
                                               @NotNull
                                               BFSVisitor<T> visitor)

getDepthFirstSearch

public abstract DepthFirstSearch<T> getDepthFirstSearch(@NotNull
                                                        T start,
                                                        @NotNull
                                                        DFSVisitor<T> visitor)
Returns depth-first search from the specified start node

Parameters:
start - start node for the search
visitor - visitor
Returns:
see above

getReverseDepthFirstSearch

public abstract DepthFirstSearch<T> getReverseDepthFirstSearch(@NotNull
                                                               T start,
                                                               @NotNull
                                                               DFSVisitor<T> visitor)

size

public abstract int size()
Returns number of nodes in the graph

Returns:
see above

isEmpty

public boolean isEmpty()

getAllNodes

@NotNull
public abstract java.util.Set<T> getAllNodes()

ensureContainsNode

protected void ensureContainsNode(@NotNull
                                  T node)