Traversing multiple cycles or detecting a cycle after traversal stopped

[Bruno Batarelo]

Hi, 

  I am using .withSubgraph to traverse a graph and am using EdgeFilter to filter out some paths - nothing fancy there. However, it is possible to encounter a path which is circular and from my observations, traversal just stops right before hitting the node that was already traversed. My use case requires repeating the traversal even if it is theoretically infinite.

Is it possible to enforce infinite cyclical traversals?

Alternatively, when traversing stops because already traversed node is next ahead, is it possible to detect that scenario so that I can manually initiate next cycle?

Thanks,

Bruno

[Peter Empen]

Hi Bruno,

I think it is possible since you can pass your individual node visitor that will be in charge of making the desired look-ahead.

For further discussion, could you please post your exact call?

Thanks

Peter

[Bruno Batarelo]

Thanks for quick response. Here's the call:

val traversedStates = startNode.withSubgraph(edges = _.label.asInstanceOf[StoryTransition].canProceed(userContext) == true).toList

Basically edges store an object in label that contains canProceed method which allows or disallows traversal via that edge. That system is working fine, until I encounter a scenario where traversal returns to previously traversed node and stops before traversing it so my last node in this traversedStates variable is always the last one before the already traversed one.
My question is is this some sort of default behaviour of traverser where it just stops traversing a branch at cycle completion or should I be looking for a problem somewhere on my end? If it really is a standard behaviour then can it be overriden somehow?

Thank you,

Bruno

[Peter Empen]

Bruno,

simple traversals, meaning those based on DFS/BFS, are not about cycle detection. They retrieve the set of nodes reachable from the start node.

I understand you try to use the order of such a simple traversal to detect cycles, right? I think that cannot work as expected:

1. The order of nodes is specific to the underlying algorithm.
2. Take a look at Graph(1 ~> 2, 2 ~> 3, 1 ~> 4, 4 ~> 3). Starting the traversal from 1, assume 1, 2 and 3 have been visited. When visiting 4 and seeing 3 as a visited adjacent, do you detect any cycle?
3. Even if you were able to assume the existence of a cycle at any node, you could not get the cycle itself because the previously visited nodes are not necessarily ordered to be a path.

As to "enforce infinite cyclical traversals", do you mean a traversal that revisits already visited nodes? How this would help to solve any problem?

As a side note, you may want to also consider the down-up traverser or extended visitors.

Hope this helps, though I'm still not sure about what you want to achieve.

[Bruno Batarelo]

Hey Peter,

  yes, that's exactly what I mean - revisiting already visited nodes. Reasoning behind it is as follows: I am working on a complex story telling engine which uses graph of Labeled Directed Edges as an in memory storage for a story itself. Your example from point #2 is valid in my case - if traversal ends in a node in which multiple paths end, but nothing goes out, I consider story to be complete.

However, my overlay logic contains more complexities (conditions that decide on branchings, user context and so on) so it is possible that sometimes traversal is possible in some directions, and sometimes it's not (as per that EdgeFilter thing I have mentioned earlier).

All this is working and ScalaGraph proved to be a good traversal tool for scenario above. However, now I am exploring possibility that story may end up in a branch where it circles several times before it proceeds out of the circle given certain condition and that is the reason why I'm asking about revisiting nodes in a first place. Take a look at this graph:

1~+>2, 2~+>3, 3~+>4, 4~+>2, 4~+>5

Story ends in node 5, but it is also possible to go back from 4 to 2 (according to some condition employed by story logic and the edge filtering). My need is to allow for such cyclical traversals any number of times until higher level context changes in such a way that 4~+5 becomes "possible" and 4~+2 "impossible". I put "possible" and "impossible" in quotes because those edges are always in memory, but EdgeFilter might not decide they are traversable.

I hope this makes my case clear.

Bruno

[Peter Empen]

Hi Bruno,

when does your userContext change? Are you mutating it during the traversal or will it change on an external event or both?

If it only changes on an external event you need to think about suspending the traversal until a relevant event occurs.

If you are mutating it while visiting nodes and it is not sufficient to examine just the neighbor nodes including visited ones, I'd recommend to start a new traversal whenever necessary. Such a new traversal would then have an additional node filter based on the results of the initiating traversal. This approach seems to be clearer to me than dealing with revisiting, all the more so, you have no library support for revisiting. Do you think it could work out for you?

Peter

[Bruno Batarelo]

Hi Peter,

  thanks, this is all I needed to know. I'm mutating context along traversal - nothing externally. I was considering implementing mechanism of continuous traversals in case I run out of options (no revisiting nodes) which is clearly what I now have to do.

Thank you once again for this insight, this is really useful library.

Bruno

[Peter Empen]

No problem, Bruno, thank you for your patient. I'm sorry there is no direct support for this yet.

I'll think about how to add true support and possibly get back to you with some design ideas...