Comments (4)
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.
from rgl.
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.
from rgl.
@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.
from rgl.
@MarcWeber : I would like to close this issue. Could you answer my question before?
from rgl.
Related Issues (20)
- Automate release process HOT 4
- Fix links in README link section
- Fix link to LICENSE in CONTRIBUTING.md
- dependency on pairing_heap would downgrade from v3.0.1 to v0.3.0 HOT 1
- Gem is not loading HOT 2
- set_to_begin incorrect for graph iterator
- Unclear how to use bellman_ford_shortest_paths method HOT 2
- The License of the Project is Unclear HOT 6
- how i can use this in laravel ? HOT 2
- `depth_first_search` Doesn't work HOT 1
- Remove superfluous :GRAY assignment in depth first visit
- Support Ruby 3.2
- doc: Fix bad badge for codeclimate
- Fix wrong module and class comments in generated documentation
- How can I add a subgraph? HOT 2
- each_in_neighbor() does not call a passed block
- each_in_neighbor() raises exception on unconnected vertices
- Refactor edge/vertex settings to no longer require individual options initialization HOT 1
- undefined method `set_vertex_options' HOT 7
- calling require inside a mehtod is causing memory bloat if this method is called multiple times. HOT 4
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from rgl.