Confused about depth-first order (right first)

[Julian Claus]

I have the following directed graph:

strict digraph {
    // Node definitions.
    I;
    prefer;
    the;
    morning;
    flight;
    through;
    Denver;

    // Edge definitions.
    prefer -> I;
    prefer -> flight;
    flight -> the;
    flight -> morning;
    flight -> through;
    through -> Denver;
}

Using the depth-first traversal yields a different order I see from the edge definitions above.

Expected:

prefer 

I 

flight 

the 

morning 

through 

Denver

Received:

prefer 

flight 

through 

Denver 

morning 

the 

I

It seems to me that it iterates the right side of the graph first instead of the left one. Is that expected and how can I influence it?

[Dan Kortschak]

Showing the code that you used would be helpful here. I would expect
the ordering to be random (depending on the graph implementation that
you are using). There is no ordering of co-equal paths in a graph
traversal, so the DFS walk is free to choose which ever way it wants.
If you want a particular order, you will need to implement an graph
that has an ordering of out edges.

[Julian Claus]

Thank you for your fast answer.

I assumed that the iteration follows the order of the edges. Here is an example:

package main

import (
"fmt"

"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/encoding/dot"
"gonum.org/v1/gonum/graph/simple"
"gonum.org/v1/gonum/graph/traverse"
)

type node string

func (n node) ID() int64 {
switch n {
case "I":
return 1
case "prefer":
return 2
case "the":
return 3
case "morning":
return 4
case "flight":
return 5
case "through":
return 6
case "Denver":
return 7
}

return -1
}

func (n node) DOTID() string {
return string(n)
}

func main() {
g := simple.NewDirectedGraph()
g.AddNode(node("prefer"))
g.AddNode(node("I"))
g.AddNode(node("flight"))
g.AddNode(node("the"))
g.AddNode(node("morning"))
g.AddNode(node("through"))
g.AddNode(node("Denver"))

g.SetEdge(g.NewEdge(
node("prefer"),
node("I"),
))
g.SetEdge(g.NewEdge(
node("prefer"),
node("flight"),
))
g.SetEdge(g.NewEdge(
node("flight"),
node("the"),
))
g.SetEdge(g.NewEdge(
node("flight"),
node("morning"),
))
g.SetEdge(g.NewEdge(
node("flight"),
node("through"),
))
g.SetEdge(g.NewEdge(
node("through"),
node("Denver"),
))

b, _ := dot.Marshal(g, "", "", " ")
fmt.Println(string(b))

fmt.Println()

traverser := traverse.DepthFirst{}
traverser.Visit = func(n graph.Node) {
fmt.Println(string(n.(node)))
}
traverser.Walk(g, node("prefer"), nil)
}

This returns the array I posted first. 

[Dan Kortschak]

On Wed, 2025-04-09 at 08:28 -0700, Julian Claus wrote:
> I assumed that the iteration follows the order of the edges. Here is
> an example:
>

Thanks.

The important thing to understand here is that "order of the edges" is
not a concept in a graph (unless you make it one — by default, we
don't). A graph is an unordered pair of sets, E and V. Because of this
definition there is no intrinsic ordering of edges.

If the graph is represented as an edge list (each element of V has a
set out edges in E), then it is possible to get the behaviour that you
want, but the set of out edges held by each v must be an ordered set.
We specifically do not do this for two reasons; the first is that in
large graphs this would impact on performance since we would need to do
linear search for edges, and possible more importantly, in nearly all
graph algorithms order of edge iteration should not matter, but if it
is not randomised can cause subtle incorrect success. Randomisation
prevents a lucky success. If ordering is important, you will need to
encode that in the graph.

Please read https://www.gonum.org/post/word_ladder/ for an explanation
of the design principles around the graph packages use.

> This returns the array I posted first. 

Sometimes it does, sometimes it does not. If you run it a number of
times, you'll see that it does not print a consistently ordered output,
but all the orders are correct for the traversal.

[Julian Claus]

Very comprehensive and helpful, thank you!

Well, I'm dealing with textual nodes (actually tokens in a dependency tree) and a deterministic order (in my case maintaining the position in sentences) would be preferable, but I guess not inevitable. Implementing a custom iterator, as you said, would impact performance for millions of tokens significantly because of the extra check.

Thanks again.

[Julian Claus]

I decided to implement my own iterator but I'm not quite sure if I should implement the traverse or nodes interface. Could you help me making a decision? 

[Dan Kortschak]

On Sun, 2025-04-20 at 03:42 -0700, Julian Claus wrote:
> I decided to implement my own iterator but I'm not quite sure if I
> should implement the traverse or nodes interface. Could you help me
> making a decision? 

You only need to implement the traverse.Graph interface for those
routines, but the From method should return an ordered iterator. I
would suggest using a slice of graph.Node and using
interator.OrderedNodes[1] via interator.NewOrderedNodes.

[1]https://pkg.go.dev/gonum.org/v1/go...@v0.16.0/graph/iterator#OrderedNodes

[Julian Claus]

It works, thanks a lot! 

Why do I need to return the nodes in a descending order in the From interface method? I see that always the latest node is pushed to the stack, but I don't understand why.

[Dan Kortschak]

On Mon, 2025-04-21 at 00:21 -0700, Julian Claus wrote:
> Why do I need to return the nodes in a descending order in the From
> interface method? I see that always the latest node is pushed to the
> stack, but I don't understand why.

I don't know what your code is, so I can't answer this, but if it's
just based off the DOT unmarshaller code with no other effort by you, I
would guess that it has something to do with how we add nodes in that
package.

(Note that while we're unlikely to change the behaviour of the DOT
package, certainly not intentionally, what you are doing depends on
unspecified behaviour; it's not in the DOT language definition that
nodes are an ordered set)

[Julian Claus]

This is the interface implementation traverse.From:

https://github.com/ndabAP/assocentity/blob/43bab7af24603da33c3757397d27dcda93638b97/dependency/traverse.go#L15-L34

As you can see here I need to sort the slice in a descending order in order to get the expected outcome. This is my custom Walk method that accepts my type that implements the interface:

https://github.com/ndabAP/assocentity/blob/43bab7af24603da33c3757397d27dcda93638b97/dependency/traverse.go#L43-L53

I'm just wondering why not ascending.

[Dan Kortschak]

On Mon, 2025-04-21 at 04:28 -0700, Julian Claus wrote:
> This is the interface implementation traverse.From:
>
> https://github.com/ndabAP/assocentity/blob/43bab7af24603da33c3757397d27dcda93638b97/dependency/traverse.go#L15-L34
>
> As you can see here I need to sort the slice in a descending order in
> order to get the expected outcome. This is my custom Walk method that
> accepts my type that implements the interface:
>
> https://github.com/ndabAP/assocentity/blob/43bab7af24603da33c3757397d27dcda93638b97/dependency/traverse.go#L43-L53
>
> I'm just wondering why not ascending.

Take a look at the traverse code and it should be clear why this is;
work order is based on a stack.

BTW, I would suggest that you implement your own graph type that
doesn't require that you do a sort for each node's out edge traversal.