Suggestion - branch depth viewer

D

DosEsh

Virgin
I would appreciate an option that could be turned on to show how many chapters a branch has when you're choosing a next chapter - a story might say "200 chapters deep", but how do I figure out which branch that is? On popular stories there can be a dozen branches from the first chapter, each one 3 or 4 chapters deep. You find one that goes for 80 chapters, and you're even more confused. The current story maps are rather confusing once a story hits a certain complexity and not that good for checking length anyway (at least on mobile).

Reaching the end of a chapter and having each option have a small number which displays the highest chapter number you can access following this branch, or how many chapters follow it, would be a godsend.
 
So I think this is what you'd want to compute https://hackernoon.com/shortest-and-longest-path-algorithms-job-interview-cheatsheet-2adc8e18869 (what is relevant from here is the shortest simple path, meaning path with no loops in a graph that can have loops) from each node to each reachable termination node and take the max. It would be expensive to do and would have to be recalculated every time the graph changed, but it's certainly do-able. That would give you the remaining chapters to the furthest end chapter reachable from your current chapter though.
 
Last edited:
loki said:
So I think this is what you'd want to compute https://hackernoon.com/shortest-and-longest-path-algorithms-job-interview-cheatsheet-2adc8e18869 (what is relevant from here is the shortest simple path, meaning path with no loops in a graph that can have loops) from each node to each reachable termination node and take the max. It would be expensive to do and would have to be recalculated every time the graph changed, but it's certainly do-able. That would give you the remaining chapters to the furthest end chapter reachable from your current chapter though.
Click to expand...
Actually, CHYOA stories are by default trees, not graphs, and you would be looking for the longest path, not the shortest. Each chapter can store a value representing the height of the subtree rooted at that chapter, and when a new chapter is added or deleted, increment or decrement that value on all of its ancestors. The Introduction chapter effectively already does this.

I'm assuming OP doesn't care about linked chapters, but it's interesting to consider how they could be handled, since they would indeed turn the tree into a graph. Without cycles, you could just have backward references to linked chapters so that some chapters have multiple parents, and keep track of which chapters have been incremented or decremented while updating subtree heights. Perhaps the story could scan for infinite cycles whenever a new linked chapter is added, and if so, do something special to prevent them from ruining the operation, like excluding them from calculations, or replacing the relevant values with some indication to the reader, like an infinity sign.
 
So, my solution is for the case of graphs with loops. That's why I included the doing the shortest path to every leaf node, then taking the max, you're getting the "longest shortest path". Longest path is indeed not defined in graphs with cycles, whereas a shortest path always is.
 
So this reminded of my college days writing cute little graph algorithms that never did anything. So here's a POC in python for this. Give it your username/password (you can't view the story map without logging in) the story map url and your current chapter url and it'll give the deepest end path from there.
Screenshot_220.png
 

Attachments

insertnamehere said:
Perhaps the story could scan for infinite cycles whenever a new linked chapter is added, and if so, do something special to prevent them from ruining the operation,.
Click to expand...
You just need depth first search and keep a list of visited nodes and if you hit a cycle return infinity for the shortest path in that direction. I think the entire confusion here was the idea that you need to compute longest path at all, which you are correct isn't tractable in this case. However this is actually a very easy problem using shortest paths, and the time complexity is something exponential I'm sure, it's an NP-hard problem, but that doesn't matter with the graph sizes we're dealing with here. My program takes longer to download and parse the graph from the html than to calculate the distance
 
Calculating the depth to the deepest chapter of the branch might not be that hard. As a chapter has a start and end value that encloses all chapters below.
E.g. a story with 3 chapters might look like
Code: 
Branching:
S1 E6 D1 R1 (introduction)
   - S2 E3 D2 R0
   - S4 E5 D2 R0
or
Code: 
Linear:
S1 E6 D1 R2 (introduction)
   - S2 E5 D2 R1
      - S3 E4 D3 R0
(S = start; E = end; D = depth; R = remaining chapters)
So you could query the "highest value of D from all chapters where S(any) > S(current) AND S(any) < E(current)"
(current = chapter to calculate the remaining depth; any = any chapter below current)

So calculating that number from scratch wouldn't be too difficult.

When a chapter is added you could do "R+1 for direct ancestors with D(added) - D(ancestor) = 0"
(ancestor = ancestor chapter)

So adding should be doable as well.

If you delete a chapter, you need to update all chapters until you reach a branching point. At the branching chapter, you have to check if there is a descendant chapter that has a deeper depth than the deleted chapter. If so, you're done. If not, update R of the branching point and proceed with its ancestors.


Though that doesn't include link chapters, so I could guess there would be a few additional calculations and queries necessary with every added and deleted chapter.
 
You must log in or register to reply here.
Back
Top