unnecessary BFSVisitorVector as parameter in bfs_tree?

[sbromberger]

@jpfairbanks https://github.com/JuliaGraphs/LightGraphs.jl/blob/master/src/traversals/bfs.jl#L168-L173

Why do we pass in a BFSVisitorVector when we're creating one inside the function?

[jpfairbanks]

What I intended was for there to be the modifying form function bfs_tree!(visitor::TreeBFSVisitorVector, g::SimpleGraph, s::Int) which allows you to use memory efficiently when making repeated BFS. And then the easier to use form if you just need one BFS bfs_tree(g::SimpleGraph, s::Int) so if you just take line 168 and delete the visitor::TreeBFSVisitorVector part it should work. You should then also delete lines 161-166

[sbromberger]

Performance-wise, is the new code at least equivalent? If so we can switch it over right away.

[sbromberger]

Also, thinking aloud here, perhaps we should have a DiGraph(v::Vector{Int}) method that can take this output and create a DAG.

[jpfairbanks]

g = DiGraph(length(v))

v[i] = j implies j is parent of i

for i in length(v) add_edge!(g, v[i], i) end return g

James Fairbanks PhD Candidate Georgia Tech

On Mon, Oct 5, 2015 at 9:56 AM, Seth Bromberger notifications@github.com wrote:

Also, thinking aloud here, perhaps we should have a DiGraph(v::Vector{Int}) method that can take this output and create a DAG.

— Reply to this email directly or view it on GitHub https://github.com/JuliaGraphs/LightGraphs.jl/issues/162#issuecomment-145535100 .

[sbromberger]

Heh, I know how to do it (with sparse matrices we might need to optimize it a bit) - I was just soliciting comments as to whether it would be good to do. Can't hurt, right?

[jpfairbanks]

sorry I thought your question was "How do I interpret the output?" that is what I get for firing off replies without taking time to read first.

The downside I see is encouraging people to use the graph API because they are more comfortable with it, rather than the more efficient API of the predecessor array. In my experience, it is better to have people use the most efficient API that is sufficiently easy rather than the easiest API that is sufficiently efficient.

James Fairbanks PhD Candidate Georgia Tech

On Mon, Oct 5, 2015 at 10:08 AM, Seth Bromberger notifications@github.com wrote:

Heh, I know how to do it (with sparse matrices we might need to optimize it a bit) - I was just soliciting comments as to whether it would be good to do. Can't hurt, right?

— Reply to this email directly or view it on GitHub https://github.com/JuliaGraphs/LightGraphs.jl/issues/162#issuecomment-145539197 .

[jpfairbanks]

So to answer your question "Performance-wise, is the new code at least equivalent?" There are two dimensions to analyze, Digraph API/Parents Array API and single/multiple BFS.

For the Multiple BFS case you really need to reuse the memory to get the speedup. This provides huge savings, but everyone needs to update their code to use the Parents array API. They can't use the old API because constructing the DiGraph object is the slow part. If we do the BFS reusing the memory and then convert to the DiGraph representation so that the client code can use the DiGraph API, we aren't really saving any time.

For the Single BFS Case if you want to use the DiGraph representation, then my way is probably slightly slower because you need to allocate the same memory that you had to make the DiGraph and then the extra memory for the parents array. Its only 1 extra allocation so probably no big deal.

There is another option which is to give the necessary functions to TreeBFSVisitorVector so that it can support the operations that people want to do on the DiGraph representation. We should look at some client code to see what operations they do.

It might actually be faster for everyone to just switch to the Parents array data structure and use it directly.

We could deprecate the old DiGraph API and when people complain about the deprecation they will tell us why they want the DiGraph.

[sbromberger]

At first glance it seems to me that functionality that doesn't involve critical structures of the package itself (i.e., DiGraphs) perhaps isn't appropriate for inclusion in the package. That is, I understand that using a vector of ints to manipulate DAGs in certain contexts is more performant, but this could easily be done outside of LightGraphs, just as representing a graph as a structure of Foos can/should be done outside of LightGraphs.

I'm open to being otherwise persuaded, though.

[jpfairbanks]

@sbromberger I updated the PR #176.

[sbromberger]

We can close this now, right?