Package jetbrains.buildServer.util.graph

Class DAGUtil

java.lang.Object

jetbrains.buildServer.util.graph.DAGUtil

public class DAGUtil
extends Object

Since:

9.0

Constructor Summary

Constructors

Constructor	Description
DAGUtil()

Method Summary

Modifier and Type	Method	Description
static <T> Collection<Pair<T,T>>	omitRedundantEdges(Collection<Pair<T,T>> edges)	This operation simplifies the DAG by removing direct edges between nodes if there is indirect path between these nodes.
static <T> Pair<DAG<T>,List<T>>	removeCycles(Collection<Pair<T,T>> edges)	If there cycle in graph, this function will eliminate all nodes in that cycle from graph and all nodes which depends on cycle.

Methods inherited from class java.lang.Object

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

Constructor Detail

DAGUtil

public DAGUtil()

Method Detail

removeCycles

@NotNull
public static <T> Pair<DAG<T>,List<T>> removeCycles(@NotNull
                                                          Collection<Pair<T,T>> edges)

If there cycle in graph, this function will eliminate all nodes in that cycle from graph and all nodes which depends on cycle. In worst case O(n^2) performance (chain). O(n) additional memory.

Returns:

first element of pair - constructed DAG, second - list of nodes excluded because of cycles

Since:

9.0

omitRedundantEdges

public static <T> Collection<Pair<T,T>> omitRedundantEdges(@NotNull
                                                                 Collection<Pair<T,T>> edges)

This operation simplifies the DAG by removing direct edges between nodes if there is indirect path between these nodes. In other words, if for some of the child and parent pair there is more than one path from parent to child, this method removes [child, parent] edge.

Type Parameters:

T -

Parameters:

edges - edges to process

Returns:

new edges

Since:

2017.1