Traversal ordering

[Bruno Batarelo]

Hello,

  I am using LDiEdge graph which I am populating by supplying edges. I was under probably wrong impression that traversal will be defined by the order edges were supplied to the graph during creation.

Let's consider tree that starts like this and was created in that order (or is contained within a bigger graph): 

1~+>2

1~+>3

1~+>4

1~+>5

This tree can branch further from nodes 2, 3, 4 and 5, but should be irrelevant.

I am traversing using withSubgraph and am using filtering to ensure that there is always one path possible, and others are not. It is of outmost importance that traversals are tried in predefined order, but when testing, order is unpredictable.

Since it's not weighted graph, I can not use weights, but I can add an attribute in object I am using for Label that might have order/weight information should that be of any help. Below is my attempt.

I tried adding following ordering:
def eo = graph.EdgeOrdering.apply{(x, y) =>

  Logger.info("Comparing: " + x + " and " + y)
  x.label.asInstanceOf[StoryTransition].weight.compareTo(y.label.asInstanceOf[StoryTransition].weight)
}

and using it during traversal:

startNode.withOrdering(eo).withSubgraph(edges =...

but to no avail - traversal is still not ordered.

Does anyone have a clue to what I'm doing wrong?

Thanks,

Bruno

[Peter Empen]

Did you add withOrdering to your Traverser?

For examples, see

https://github.com/scala-graph/scala-graph/blob/master/core/src/test/scala/scalax/collection/TTraversal.scala and

https://github.com/scala-graph/scala-graph/blob/master/core/src/test/scala/scalax/collection/TCycle.scala

[Bruno Batarelo]

Yes,

  maybe I didn't describe it well enough, but here's digest:

graph.get(state).withOrdering(eo).withSubgraph(edges = ...

where eo is defined as:

def eo = graph.EdgeOrdering.apply{(x, y) => x.label.asInstanceOf[StoryTransition].weight.compareTo(y.label.asInstanceOf[StoryTransition].weight)}

By default here we are working with InnerNodeTraverser.

Is my EdgeOrdering defined properly?

Bruno

[Bruno Batarelo]

OK, I made a self executing sample. Only thing needed to run it is “sbt run”.

 

Here’s quick background:

 

• We have branching from S1 to possible S2, S3, S4 and S5 and then back from S2, S3, S4 and S5 to S6.
• In first branching only allowed path is S1 to S4, and on second, everything is allowed.

This works as expected and gives traversal result S1, S4, S6.

 

However, order of traversal during first branching is: S1-S2, S1-S5, S1-S4, S1-S3 which is I guess expected because edges have been supplied in that order, but in my production application varies randomly (I have big network of edges).

 

If I uncomment line 22 in MyGraph.scala to enable ordering, nothing changes and that is the source of problem. Ordering should be done by weight attribute included in label object on edges.

Bruno

[Peter Empen]

Hi Bruno,

I'm not sure I really got what you want to achieve.

You are using an edge filter meaning that edges not satisfying your filter wont be included in the traversal.

In addition you are supplying an edge ordering. Your edge ordering is applied to the set of direct successors except those filtered out by the above edge filter. Your set of direct successors is a single node S4. So edge ordering takes place but won't change anything.

What am I missing? To help me understand your requirement, it would be nice to have your expectation along with an example that fails.

[Bruno Batarelo]

Hey Peter,

  I have come up with a minimal sample here. I took out all the ordering and unnecessary code.

My question in the end boiled down to this: why does scala-graph try to traverse graph differently depending on presence of seemingly insignificant states?

Sample from the attachment will have one log output if you run it as is, and will have different output if Hello.scala line 31 is uncommented and line 32 is commented.

I included two images that show different order of paths chosen by the library for those two scenarios. sample1.jpg corresponds to the zipped project and sample2.jpg to the modified version (lines 31 & 32).

[Peter Empen]

Hi Bruno,

thanks for more clarity and the nice graphics.

First, would you agree that we have the right result in both cases: "Travered states: S1, S4, S6"?

Second, provided by "attempted traverser order" you refer to the output of MyTransition, you are using canProceed in your edge filter so Graph for Scala needs to check for this predicate edge by edge. Indeed, the order of these checks is undefined. Why so?

This is because the "order", a wrong term here, of set/graph elements is in general undefined unless you are using an ordered set. It just depends on the set/graph implementation: https://stackoverflow.com/questions/5245713/scala-can-i-rely-on-the-order-of-items-in-a-set.

To see immediate evidence, try the following in Scala REPL:

a) element "order" different from insertion order

(1 to 16).toSet

b) element "order" depends on set size

import scala.collection.mutable.Set
Set.empty[Int] ++ (1 to 6)
Set.empty[Int] ++ (1 to 20)

Note that the "order" is not even stable with respect to the same graph instance since in course of a traversal intermadiate collections may be used.

Hope this helps. Tell me if you need any help to find an appropriate design for your requirement.

Peter