Class StronglyConnectedComponentsTopologicallySorted

java.lang.Object

graphql.schema.impl.StronglyConnectedComponentsTopologicallySorted

public class StronglyConnectedComponentsTopologicallySorted
extends Object

This class returns a list of strongly connected components (SCC) which are topologically sorted. The algorithm is from https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm The elements inside a SCC are additionally sorted top. itself: normally this is not possible, but we are using for this "inner sort" only the "reverseDependencies" Map which is made out of dependencies based one the Java references between Schema elements, which can't form a cycle. The inner sort algorithm is from https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search

Field Summary

Fields

Modifier and Type	Field	Description
private int	index
private final Map<GraphQLSchemaElement, Integer>	nodeToIndex
private final Map<GraphQLSchemaElement, Integer>	nodeToLowLink
private final Map<GraphQLSchemaElement, Boolean>	nodeToOnStack
private final List<List<GraphQLSchemaElement>>	result
private final Map<GraphQLSchemaElement, List<GraphQLSchemaElement>>	reverseDependencies
private final Deque<GraphQLSchemaElement>	stack
private final Map<String, List<GraphQLSchemaElement>>	typeRefReverseDependencies

Constructor Summary

Constructors

Modifier	Constructor	Description
private	StronglyConnectedComponentsTopologicallySorted(Map<GraphQLSchemaElement, List<GraphQLSchemaElement>> reverseDependencies, Map<String, List<GraphQLSchemaElement>> typeRefReverseDependencies)

Method Summary

Modifier and Type	Method	Description
private void	calculate()
static List<List<GraphQLSchemaElement>>	getStronglyConnectedComponentsTopologicallySorted(Map<GraphQLSchemaElement, List<GraphQLSchemaElement>> reverseDependencies, Map<String, List<GraphQLSchemaElement>> typeRefReverseDependencies)
private void	stronglyConnect(GraphQLSchemaElement v)
private List<GraphQLSchemaElement>	topologicallySort(Set<GraphQLSchemaElement> allNodes)
private void	visit(GraphQLSchemaElement n, Set<GraphQLSchemaElement> tempMarked, Set<GraphQLSchemaElement> permMarked, Set<GraphQLSchemaElement> notPermMarked, List<GraphQLSchemaElement> result, Set<GraphQLSchemaElement> allNodes)

Methods inherited from class Object

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

Field Details

index

private int index

nodeToIndex

private final Map<GraphQLSchemaElement, Integer> nodeToIndex

nodeToLowLink

private final Map<GraphQLSchemaElement, Integer> nodeToLowLink

nodeToOnStack

private final Map<GraphQLSchemaElement, Boolean> nodeToOnStack

stack

private final Deque<GraphQLSchemaElement> stack

result

private final List<List<GraphQLSchemaElement>> result

reverseDependencies

private final Map<GraphQLSchemaElement, List<GraphQLSchemaElement>> reverseDependencies

typeRefReverseDependencies

private final Map<String, List<GraphQLSchemaElement>> typeRefReverseDependencies

Constructor Details

StronglyConnectedComponentsTopologicallySorted

private StronglyConnectedComponentsTopologicallySorted(Map<GraphQLSchemaElement, List<GraphQLSchemaElement>> reverseDependencies,
 Map<String, List<GraphQLSchemaElement>> typeRefReverseDependencies)

Method Details

getStronglyConnectedComponentsTopologicallySorted

public static List<List<GraphQLSchemaElement>> getStronglyConnectedComponentsTopologicallySorted(Map<GraphQLSchemaElement, List<GraphQLSchemaElement>> reverseDependencies,
 Map<String, List<GraphQLSchemaElement>> typeRefReverseDependencies)

calculate

private void calculate()

stronglyConnect

private void stronglyConnect(GraphQLSchemaElement v)

topologicallySort

private List<GraphQLSchemaElement> topologicallySort(Set<GraphQLSchemaElement> allNodes)

visit

private void visit(GraphQLSchemaElement n,
 Set<GraphQLSchemaElement> tempMarked,
 Set<GraphQLSchemaElement> permMarked,
 Set<GraphQLSchemaElement> notPermMarked,
 List<GraphQLSchemaElement> result,
 Set<GraphQLSchemaElement> allNodes)