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
All Methods Static Methods Instance Methods Concrete Methods 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)
-
-
-
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)
-
-