Package graphql.schema.impl
Class StronglyConnectedComponentsTopologicallySorted
java.lang.Object
graphql.schema.impl.StronglyConnectedComponentsTopologicallySorted
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
FieldsModifier and TypeFieldDescriptionprivate int
private final Map
<GraphQLSchemaElement, Integer> private final Map
<GraphQLSchemaElement, Integer> private final Map
<GraphQLSchemaElement, Boolean> private final List
<List<GraphQLSchemaElement>> private final Map
<GraphQLSchemaElement, List<GraphQLSchemaElement>> private final Deque
<GraphQLSchemaElement> private final Map
<String, List<GraphQLSchemaElement>> -
Constructor Summary
ConstructorsModifierConstructorDescriptionprivate
StronglyConnectedComponentsTopologicallySorted
(Map<GraphQLSchemaElement, List<GraphQLSchemaElement>> reverseDependencies, Map<String, List<GraphQLSchemaElement>> typeRefReverseDependencies) -
Method Summary
Modifier and TypeMethodDescriptionprivate void
static List
<List<GraphQLSchemaElement>> getStronglyConnectedComponentsTopologicallySorted
(Map<GraphQLSchemaElement, List<GraphQLSchemaElement>> reverseDependencies, Map<String, List<GraphQLSchemaElement>> typeRefReverseDependencies) private void
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)
-
Field Details
-
index
private int index -
nodeToIndex
-
nodeToLowLink
-
nodeToOnStack
-
stack
-
result
-
reverseDependencies
-
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
-
topologicallySort
-
visit
private void visit(GraphQLSchemaElement n, Set<GraphQLSchemaElement> tempMarked, Set<GraphQLSchemaElement> permMarked, Set<GraphQLSchemaElement> notPermMarked, List<GraphQLSchemaElement> result, Set<GraphQLSchemaElement> allNodes)
-