depth_first_search ? about rgl

[KL-7]

Hi @MarcWeber,

First, DFS iterator doesn't know where the "root" of your graph is. All it does is going through the vertices of your graph one by one (in the same order as the order of the edges in the graph definition) and trying to do DFS from them. In your example it'll do three DFS runs covering vertices (5, 6) first, then (4), then (1, 2, 3).

Second, the block you pass into depth_first_search method is called before we leave the node and return to its parent. That seems a little bit odd to me, but it's by design and is documented here (the block is called at the end of the node visit over here).

One thing you can do is create your own DFSVisitor to handle other events that are triggered during a DFS run. E.g., here's how to do something every time we enter a vertex for the first time:

graph = RGL::DirectedAdjacencyGraph[5,6, 4,5, 1,2, 2,3]
visitor = RGL::DFSVisitor.new(graph)
visitor.set_examine_vertex_event_handler { |v| puts v }
graph.depth_first_search(visitor) {}

# prints 5 6 4 1 2 3

Now the vertices are listed in the order they are visited, but, as you can see, it has the same issue – it tries to traverse the graph from each vertex one by one without identifying the "root" of the graph.

My graph theory is a bit rusty at the moment (haven't used it for a while), but I guess topological sort could help you get the output you're looking for:

require 'rgl/topsort'
graph.topsort_iterator.each { |v| puts v }
# prints 1 2 3 4 5 6

It's not exactly the same output as you'd get if you were to run a simple DFS from the "root" node, but depending on your actual problem I think it might fit.

[MarcWeber]

The Haskell graph library has an nice way to "output a tree as text representation". The case I have (categories from a store) doesn't look readable using dotty output (which is broken a well, because strings (html) get output without quoting) - but that's another story. I have read the code trying to undersctand how it works - which is why I think a "find roots" and or ordering could be useful. I came up with such code:

graph = RGL::DirectedAdjacencyGraph[*a]
graph.dotty

class TextIt < RGL::DFSIterator

  def initialize(graph, start = graph.detect { |x| true })
    @depth = 0
    super(graph)
  end

  def handle_start_vertex(x)
  end

  def handle_examine_vertex(x)
    puts " " * @depth + "c"
  end

  def handle_tree_edge(u,v)
    @depth += 1
    @last = @u
  end

  def handle_finish_vertex(u)
    raise 'x'
    @depth -= 1
  end

  #  * examine_vertex
  #  * examine_edge
  #  * tree_edge
  #  * back_edge
  #  * forward_edge
  #  * finish_vertex
end


graph.depth_first_search(TextIt.new(graph)) {}

eg noting that the back_edge handler wasn't called at all.

At that point I felt I should have written my own code (I would have been done within 15min).

Anyway I feel it should be documnted that DFS is not guaranteed to yield DFS order. So I feel its a documentation issue at least.

Thus what do you suggest? Patch this library? Look for a different one? Write my own code (for this purpose rewriting woud have been much faster than digging into the code) or provide patches for a) sorting and b) finding roots? Don't you think this is a common task for a graph library?

top_sort:

  # The topological sort algorithm creates a linear ordering of the vertices
  # such that if edge (u,v) appears in the graph, then u comes before v in
  # the ordering. The graph must be a directed acyclic graph (DAG).

Thus for my graph example 1,4 (roots) then showing all childs would be valid, but not DFS.

[monora]

@MarcWeber I think that you are right concerning the documentation of
depth_first_search. It should note that for directed graphs it does not
garantee that roots are at the top of each spanning subtree (in undirected graphs each node is a root node). If you want to have this behaviour you could to it like in the test_depth_first_search_with_parens in
https://github.com/monora/rgl/blob/master/test/traversal_test.rb:

  def test_depth_first_search_with_parens
    @dg.add_edge 10, 11
    # We must ensure, that the order of the traversal is not dependend on the
    # order of the each iterator in the hash map of the adjacency graph. Therefor we
    # wrap the graph with an implicit graph that simply ensures a sort order on
    # the vertices.
    dg  = @dg.implicit_graph { |g|
      g.vertex_iterator { |b| @dg.vertices.sort.each(&b) }
    }
    a = ""
    vis = DFSVisitor.new(dg)
    vis.set_examine_vertex_event_handler { |v| a << "(#{v} " }
    vis.set_finish_vertex_event_handler  { |v| a << " #{v})" }
    dg.depth_first_search(vis) { |x| }
    assert_equal("(1 (2 (3  3)(4 (5  5) 4) 2)(6  6) 1)(10 (11  11) 10)", a)
  end

Using this idiom with the topsort iterator as @KL-7 proposed, we have:

dg  = graph.implicit_graph { |g|
  g.vertex_iterator { |b| graph.topsort_iterator.each(&b) }
}
visitor = RGL::DFSVisitor.new(dg)
visitor.set_examine_vertex_event_handler { |v| puts v }
dg.depth_first_search(visitor) {}
1
2
3
4
5
6

Would that help you? I will clarify this in the documentation of depth_first_search.

[monora]

@MarcWeber : I would like to close this issue. Could you answer my question before?