Package jetbrains.buildServer.util.graph

Class DAG<T>

java.lang.Object

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

Direct Known Subclasses:

BaseModificationDAG, GenericDAG

public abstract class DAG<T>
extends Object

Directed acyclic graph

Author:

dmitry.neverov

Constructor Summary

Constructors

Constructor	Description
DAG()

Method Summary

Modifier and Type	Method	Description
abstract void	breadthFirstSearch(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(Collection<T> nodesToExclude)	Returns DAG which doesn't contain nodes in the specified collection
protected abstract void	fillSelfChildren(T node, List<T> accumulator)
DAG<T>	filter(Filter<T> filter)	Returns filtered DAG which contains only nodes accepted by specified filter, same as calling {@link #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 Set<T>	getAllNodes()
List<T>	getChildren(T node)	Get children of the specified node
abstract List<T>	getCommonAncestors(List<T> nodes)	Get list of common ancestors for collection of graph nodes
List<T>	getCommonAncestors(T... nodes)
abstract DepthFirstSearch<T>	getDepthFirstSearch(T start, DFSVisitor<T> visitor)	Returns depth-first search from the specified start node
Set<T>	getNodesWithMissingParents()	Returns nodes where some parent nodes are missing.
abstract List<T>	getNodesWithoutChildren()	Returns nodes without children
abstract List<T>	getNodesWithoutParents()	Returns nodes without parents
abstract List<T>	getParents(T node)	Get parents of the specified node
abstract DepthFirstSearch<T>	getReverseDepthFirstSearch(T start, DFSVisitor<T> visitor)
protected abstract List<T>	getSelfParents(T node)
boolean	hasParents(T node)	Returns true if the given node has parents
DAG<T>	include(Collection<T> nodesToInclude)	Returns DAG which contains only nodes in the specified collection
DAG<T>	include(Collection<T> nodesToInclude, boolean extrapolateEdges)
boolean	isEmpty()
DAGIterator<T>	iterator()	Get iterator through the nodes of the graph.
DAGIterator<T>	iterator(Collection<T> startNodes)	Get iterator through the nodes of the graph
DAGIterator<T>	iterator(T startNode)	Get iterator through the nodes of the graph
protected abstract void	processNodesWithoutChildren(ItemProcessor<T> nodesProcessor)	Passes nodes without children to the specified processor.
abstract void	reverseBreadthFirstSearch(Set<T> starts, BFSVisitor<T> visitor)
abstract void	reverseBreadthFirstSearch(T start, BFSVisitor<T> visitor)
abstract int	size()	Returns number of nodes in the graph
List<DAG<T>>	splitIsolatedDAGs()
abstract 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 List<T> toposort()

Get topologically sorted list of graph nodes (parents go before children)

Returns:

see above

getCommonAncestors

@NotNull
public List<T> getCommonAncestors(@NotNull
                                  T... nodes)

See Also:

getCommonAncestors(java.util.List)

getCommonAncestors

@NotNull
public abstract List<T> getCommonAncestors(@NotNull
                                           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 List<T> getParents(@NotNull
                                   T node)

Get parents of the specified node

Parameters:

node - node of interest

Returns:

see above

hasParents

public boolean hasParents(@NotNull
                          T node)

Returns true if the given node has parents

Parameters:

node - node of interest

Returns:

see above

getChildren

@NotNull
public List<T> getChildren(@NotNull
                           T node)

Get children of the specified node

Parameters:

node - node of interest

Returns:

see above

fillSelfChildren

protected abstract void fillSelfChildren(@NotNull
                                         T node,
                                         @NotNull
                                         List<T> accumulator)

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
                               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
                      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
                      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
                      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 {@link #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 List<T> getNodesWithoutParents()

Returns nodes without parents

Returns:

see above

getNodesWithMissingParents

public Set<T> getNodesWithMissingParents()

Returns nodes where some parent nodes are missing. Unlike getNodesWithoutParents() also returns nodes where some parents are present and other parents are missing.

Since:

2017.2.2

getNodesWithoutChildren

@NotNull
public abstract List<T> getNodesWithoutChildren()

Returns nodes without children

Returns:

see above

depthFirstSearch

public 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
                                        Set<T> starts,
                                        @NotNull
                                        BFSVisitor<T> visitor)

reverseBreadthFirstSearch

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

reverseBreadthFirstSearch

public abstract void reverseBreadthFirstSearch(@NotNull
                                               Set<T> starts,
                                               @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 Set<T> getAllNodes()

ensureContainsNode

protected void ensureContainsNode(@NotNull
                                  T node)

getSelfParents

@Nullable
protected abstract List<T> getSelfParents(@NotNull
                                          T node)

processNodesWithoutChildren

protected abstract void processNodesWithoutChildren(@NotNull
                                                    ItemProcessor<T> nodesProcessor)

Passes nodes without children to the specified processor.

Since:

2019.1.3

splitIsolatedDAGs

public List<DAG<T>> splitIsolatedDAGs()