Post-order traversal on a medium-size and large graph
- Dominant language
- Java
- Stars
- 60
- Forks
- 21
- PR merge metrics
- No merged PRs in 30d
Description
Traverser context builder defines a context strategy (see TraverseContextBuilder.[ContextStrategy](https://github.com/intuit/Traverser/blob/4ad80b64ca4cfb5492bb822b9363ec5cafc209c2/src/main/java/com/intuit/commons/traverser/TraverseContextBuilder.java#L173)), which helps to control result during traversal.
In case of post order traversal, the action to set result is invoked once traversal of a current node is complete (hence the name).
On a medium and large graphs this final termination could happen very far from start/root node, the path from start to this node could easily include thousands of intermediate nodes.
Current implementation of [NORMAL_STRATEGY](https://github.com/intuit/Traverser/blob/4ad80b64ca4cfb5492bb822b9363ec5cafc209c2/src/main/java/com/intuit/commons/traverser/TraverseContextBuilder.java#L210) propagates result from current context to parent, and then from parent to grandparent, which utilize application call stack.
On a JVM with standard configuration (512K), this could generate _StackOverflowError_ once call stack is exceeded.
In my case, it took 14-15K nodes in a path to cause the error.
There are several ways to mitigate it.
### Increase JVM stack size
Use configuration to increase stack size with `java -Xss1M` (10M, etc). This is usually enough to enable traversal on a graph with millions nodes.
### Create custom context strategy
Another way to avoid stack overflow is to handle result differently by utilizing custom context strategy.
This example is for illustration purposes, it assumes default configuration and expects custom strategy. It gives up ability to call strategy per every result, therefore it is not general enough.
```java
private static final ContextStrategy CUSTOM_NORMAL_STRATEGY = new ContextStrategy() {
@Override
public void setResult(TraverseContextBuilder outer, U result) {
outer.result = result;
rootContext(outer).setResult(result);
}
@Override
public U getResult(TraverseContextBuilder outer) {
return rootContext(outer).getResult();
}
private TraverseContextBuilder rootContext(TraverseContextBuilder outer) {
TraverseContextBuilder parent = outer.parentContext;
while(parent.contextStrategy == CUSTOM_NORMAL_STRATEGY) { // walk till ROOT
parent = parent.parentContext;
}
return parent;
}
@Override
public U getVar(TraverseContextBuilder outer, Class key) {
U value;
return ((value = (U)outer.vars.get(key)) != null || outer.vars.containsKey(key))
? value
: outer.parentContext.getVar(key);
}
@Override
public U setVar(TraverseContextBuilder outer, Class key, U newValue) {
return outer.vars.containsKey(key)
? (U)outer.vars.put(key, newValue)
: outer.parentContext.setVar(key, newValue);
}
@Override
public String toString() {
return "CUSTOM_NORMAL_STRATEGY";
}
};
```
Find very unit test to illustrate above in [my private gist](https://gist.github.com/amatiushkin/7909ee3c249fd5b213ea60dbd5c0d6d8).
## Question to the community
**Traverser** is designed as a general-purpose library and some limitations and tradeoffs needs to be made.
What is more important for default configuration: ability to traverse large graphs or functionality set? Shall it strive to have both?
PS
This is practical question for anyone, who operates with linked and connected data on a scale of [wikidata](https://www.wikidata.org/wiki/Wikidata:Main_Page) (~100M "entities").
Contributor guide
Assessment
This issue has not been assessed yet.