Bug?: strongly_connected_components

[oyamad]

(Copied from QuantEcon/QuantEcon.jl#32, comment)

I was considering the digraph in Figure 8 on page 12 in "Graph-Theoretic Analysis of Finite Markov Chains" by J. P. Jarvis and D. R. Shier, which is clearly strongly connected, but LightGraphs.strongly_connected_components returns three components:

julia> g = DiGraph(6)
{6, 0} directed graph

julia> eds = [(1, 3), (3, 4), (4, 2), (2, 1), (3, 5), (5, 6), (6, 4)]
7-element Array{Tuple{Int64,Int64},1}:
 (1,3)
 (3,4)
 (4,2)
 (2,1)
 (3,5)
 (5,6)
 (6,4)

julia> for (ed_from, ed_to) in eds
           add_edge!(g, ed_from, ed_to)
       end

julia> edges(g)
Set([edge 3 - 5,edge 5 - 6,edge 6 - 4,edge 3 - 4,edge 1 - 3,edge 2 - 1,edge 4 - 2])

julia> strongly_connected_components(g)
3-element Array{Array{Int64,1},1}:
 [6]      
 [5]      
 [1,3,4,2]

I wonder if I am missing anything.

Just in case, NetworkX returns the whole set of nodes as a unique strongly connected component:

>>> import networkx as nx
>>> nodes = list(range(1, 7))
>>> edges = [(1, 3), (3, 4), (4, 2), (2, 1), (3, 5), (5, 6), (6, 4)]
>>> G = nx.DiGraph()
>>> G.add_nodes_from(nodes)
>>> G.add_edges_from(edges)
>>> G.edges()
[(1, 3), (2, 1), (3, 4), (3, 5), (4, 2), (5, 6), (6, 4)]
>>> nx.number_strongly_connected_components(G)
1
>>> list(nx.strongly_connected_components(G))
[[1, 3, 5, 6, 4, 2]]

[sbromberger]

Definitely a bug.

[sbromberger]

OK, I think I fixed it. Can you test with this and other graphs?

[oyamad]

@sbromberger Thanks, it worked correctly with v.0.4.0-dev (for the particular graph above).

But with v.0.3.9, I got the following error:

julia> strongly_connected_components(g)
ERROR: type cannot be constructed
 in strongly_connected_components at /Users/oyama/.julia/v0.3/LightGraphs/src/connectivity.jl:73

[sbromberger]

@oyamad - yes - bfsdfs isn't going to work on 0.3 until https://github.com/JuliaLang/Compat.jl/issues/105 is fixed. It's because I'm using Vector{Int}() to create vectors instead of Int[], which is the "old" way.

[sbromberger]

Looks like we've squashed this bug, so I'll go ahead and close it out. Thanks - feel free to reopen if you continue to see a problem.