Package graphql.schema.impl

Class StronglyConnectedComponentsTopologicallySorted

java.lang.Object

graphql.schema.impl.StronglyConnectedComponentsTopologicallySorted

public class StronglyConnectedComponentsTopologicallySorted
extends java.lang.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 java.util.Map<GraphQLSchemaElement,java.lang.Integer>	nodeToIndex
private java.util.Map<GraphQLSchemaElement,java.lang.Integer>	nodeToLowLink
private java.util.Map<GraphQLSchemaElement,java.lang.Boolean>	nodeToOnStack
private java.util.List<java.util.List<GraphQLSchemaElement>>	result
private java.util.Map<GraphQLSchemaElement,java.util.List<GraphQLSchemaElement>>	reverseDependencies
private java.util.Deque<GraphQLSchemaElement>	stack
private java.util.Map<java.lang.String,java.util.List<GraphQLSchemaElement>>	typeRefReverseDependencies

Constructor Summary

Constructors

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

Method Summary

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

Methods inherited from class java.lang.Object

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

Field Detail

index

private int index

nodeToIndex

private final java.util.Map<GraphQLSchemaElement,java.lang.Integer> nodeToIndex

nodeToLowLink

private final java.util.Map<GraphQLSchemaElement,java.lang.Integer> nodeToLowLink

nodeToOnStack

private final java.util.Map<GraphQLSchemaElement,java.lang.Boolean> nodeToOnStack

stack

private final java.util.Deque<GraphQLSchemaElement> stack

result

private final java.util.List<java.util.List<GraphQLSchemaElement>> result

reverseDependencies

private final java.util.Map<GraphQLSchemaElement,java.util.List<GraphQLSchemaElement>> reverseDependencies

typeRefReverseDependencies

private final java.util.Map<java.lang.String,java.util.List<GraphQLSchemaElement>> typeRefReverseDependencies

Constructor Detail

StronglyConnectedComponentsTopologicallySorted

private StronglyConnectedComponentsTopologicallySorted(java.util.Map<GraphQLSchemaElement,java.util.List<GraphQLSchemaElement>> reverseDependencies,
                                                       java.util.Map<java.lang.String,java.util.List<GraphQLSchemaElement>> typeRefReverseDependencies)

Method Detail

getStronglyConnectedComponentsTopologicallySorted

public static java.util.List<java.util.List<GraphQLSchemaElement>> getStronglyConnectedComponentsTopologicallySorted(java.util.Map<GraphQLSchemaElement,java.util.List<GraphQLSchemaElement>> reverseDependencies,
                                                                                                                     java.util.Map<java.lang.String,java.util.List<GraphQLSchemaElement>> typeRefReverseDependencies)

calculate

private void calculate()

stronglyConnect

private void stronglyConnect(GraphQLSchemaElement v)

topologicallySort

private java.util.List<GraphQLSchemaElement> topologicallySort(java.util.Set<GraphQLSchemaElement> allNodes)

visit

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