search

sbromberger / LightGraphs.jl

An optimized graphs package for the Julia programming language
Other
673 stars 185 forks source link

optimize is_bipartite #190

Closed sbromberger closed 9 years ago

sbromberger commented 9 years ago

Right now, is_bipartite (in bfs.jl) probably isn't as optimized as it could be. It does nv(g) traversals to check for bipartiteness.

ref: https://github.com/JuliaGraphs/LightGraphs.jl/blob/master/src/traversals/bfs.jl#L263-L278

cc: @jpfairbanks

"we should grab the connected components, and then run is_bipartite on the first vertex of each."

sbromberger commented 9 years ago

OK, I think I fixed this in v4:

function is_bipartite(g::SimpleGraph)
    cc = filter(x->length(x)>2, connected_components(g))
    return all(x->is_bipartite(g,x[1]), cc)
end
sbromberger commented 9 years ago

@jpfairbanks if there's a better way of doing this, I'm all ears.

CarloLucibello commented 9 years ago

I'm working on the bipartite matching algorithm, and I would need a function bipartitemap. I took a look at the is_bipartite code and it looks like the information should be easy to export, since it is contained in the visitor. Can you please create such function?

sbromberger commented 9 years ago

It's a couple of lines of code if you need the visitor info:

    nvg = nv(g)
    visitor = BipartiteVisitor(nvg)
    traverse_graph(g, BreadthFirst(), s, visitor)

and then you get what you need from visitor.