connected_components dispatch too broad?

[ivirshup]

connected_components doesn't seem to have a meaningful return when called on a directed graph.

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

julia> [add_edge!(g, Pair(x...)) for x in Array[[3,2],[3,4],[4,5],[5,1]]]
4-element Array{Pair{Int64,Int64},1}:
 edge 3 - 2
 edge 3 - 4
 edge 4 - 5
 edge 5 - 1

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

julia> g2 = DiGraph(5)
{5, 0} directed graph

julia> [add_edge!(g2, Pair(x...)) for x in Array[[1,2],[1,3],[3,4],[3,5]]]
4-element Array{Pair{Int64,Int64},1}:
 edge 1 - 2
 edge 1 - 3
 edge 3 - 4
 edge 3 - 5

julia> connected_components(g2)
1-element Array{Array{Int64,1},1}:
 [1,2,3,4,5]

julia> symdiff(strongly_connected_components(g), strongly_connected_components(g2))
0-element Array{Array{Int64,1},1}

julia> symdiff(weakly_connected_components(g), weakly_connected_components(g2))
0-element Array{Array{Int64,1},1}

Should it's dispatch be limited to undirected graphs where it has meaning? Or could the documentation change of 9873d0f be reverted to specify that's the type it works on?

edit: This is on julia 0.4.5 using LightGraphs master.

[sbromberger]

weakly_connected_components(dg) is the same as connected_components(Graph(dg)), but yes - I'm not quite sure what value connected_components has with DiGraphs. Paging @jpfairbanks and @CarloLucibello .

[jpfairbanks]

If I recall correctly, the algorithm we have for connected components is repeated BFS until you find everybody with care taken in the implementation so that you touch every edge at most once. Thus the output on directed graphs is currently "vertex sets reachable from some lower numbered vertex by (directed) BFS." That is not labeling independent which makes it not so useful for graph theory purposes.

We should probably dispatch connected_components to either strongly_connected or weakly_connected but that requires making a decision about what a typical user would expect to get.

@ivirshup what did you expect to get when you called connected_components on a digraph?

I am inclined to say we should let it be a no such method error and have the docs point to both options.

[jpfairbanks]

The benefit of that is explicitness. A user should know the difference and should know which is right for their use case. They alone have the knowledge to make the right choice.

[ivirshup]

I think I expected the behavior of weakly_connected_components. On realizing it didn't do what I thought, and seeing that weakly_connected_components existed, I thought it should return a method error.

[sbromberger]

What have we decided to do? I'd like to get this resolved soon. :)

[jpfairbanks]

I think we decided to make it a methoderror with a reference to weakly_connected_components. Since it currently returns nonsense, I am not concerned with breaking legacy code. Such code is already broken. All we need to do is change the connected_components method from SimpleGraph to Graph right?

[sbromberger]

Question: should is_bipartite work for directed graphs?

[sbromberger]

OK, so after talking with @jpfairbanks I've done the following:

1. removed is_connected for digraphs (must use is_strongly_connected or is_weakly_connected).
2. removed connected_components for digraphs (must use strongly_connected_components or weakly_connected_components).
3. test for directedness in is_bipartite - will use weakly_connected_components for digraphs or connected_components for undirected.

Branch is sbromberger/fix-368, based off of #541 (sbromberger/simplegraphs). Cannot merge until #541 is merged.