Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Repo info
Activity
    BridgingBot
    @GitterIRCbot
    [slack] <oxinabox> though it could just be that I am doing it wrong
    BridgingBot
    @GitterIRCbot
    [slack] <oxinabox> Wanna work with graphs for matching and strongly connected components. Matching seems to be part of LightGraphsExtras.jl but that is unusable for me without a documentation and doesn't seem to be maintained any longer
    [slack] <oxinabox> @Ole ^

    [slack] <oxinabox> Strongly connected components is implemented in LightGraphs
    http://juliagraphs.github.io/LightGraphs.jl/latest/pathing.html#LightGraphs.strongly_connected_components

    BlossomV is implemented in BlossomV.jl

    [slack] <oxinabox> idk if BlossomV is what you mean by matching
    [slack] <Ole> I am looking for maximum matchings
    BridgingBot
    @GitterIRCbot
    [slack] <matbesancon> BlossomV is used in LGMatching, it would be really nice to remove the dependency on C though
    BridgingBot
    @GitterIRCbot
    [slack] <Ole> LGMatching is not working in julia v1, correct?
    [slack] <matbesancon> I haven't checked it in a while so I assume not yes
    BridgingBot
    @GitterIRCbot
    [slack] <matbesancon> again, the dependency on BlossomV is tough to cope with, and BlossomV.jl is not 1.0 yet
    [slack] <matbesancon> something cool would be to remove the dep and have a pure Julia implementation
    BridgingBot
    @GitterIRCbot
    [slack] <Ole> True. For my purpose I think I'm able to use LGM as I only need the maximum matching which is not connected to BlossomV as far as I can see it
    [slack] <matbesancon> ok, the problem is we LGM depends on it and as such, cannot upgrade without BlossomV upgrading
    BridgingBot
    @GitterIRCbot
    [slack] <Ole> yeah sure. For my purposes I probably copy the code and will update it if possible. Additionaly will have a good read the next days 😂 http://mpc.zib.de/index.php/MPC/article/viewFile/11/4
    BridgingBot
    @GitterIRCbot
    [slack] <matbesancon> if a new pure julia implementation can get us an article in Math Prog Comp, I'm in 😛
    BridgingBot
    @GitterIRCbot
    [slack] <simonschoelly> The other algorithms in LGM that do not depend on BlossomV, have not been updated yet to v1.0, so they won't run without some work
    [slack] <simonschoelly> tim holy has made a PR for BlossomV that should get it running again, but has not been merged yet
    [slack] <simonschoelly> so you could just get BlossomV from tim holy's github page
    [slack] <simonschoelly> I was also thinking about creating a pure julia implementation of Edmond's algorithm, but I'm still sure what datastructures to use for efficient blossom shrinking
    BridgingBot
    @GitterIRCbot
    [slack] <matbesancon> I've run this algorithm mostly on paper, but the paper above probably gives enough details
    BridgingBot
    @GitterIRCbot
    [slack] <simonschoelly> I probably start with an older implementation that does only the unweighted matching and then improve latter
    BGL has also some references to some papers that could be useful: https://www.boost.org/doc/libs/1_66_0/libs/graph/doc/maximum_matching.html
    BridgingBot
    @GitterIRCbot
    [slack] <Ole> Don't really know the difference between #graph and here sry. In SimpleGraphs the edges are not directed but add_edge!(g, 2, 1) results in 1 => 2 is it always from small to big?
    BridgingBot
    @GitterIRCbot
    [slack] <gunnar> Does it matter how the undirected edge is printed?
    [slack] <Ole> Well actually I would prefer <=> 😀 but anyways. I am using the edges twice, in undirected and in directed would like to iterate over the undirected and add them to directed.
    BridgingBot
    @GitterIRCbot
    [slack] <Ole> But I probably should in general not rely on that
    BridgingBot
    @GitterIRCbot
    [slack] <gunnar> I'm not sure how it would help you in the first place to rely on that. Anyway, if you have a SimpleGraph g, you can iterate over both directions with edges(SimpleDiGraph(g)) or you iterate with edges(g) and do something with e and reverse(e).
    [slack] <Ole> yeah not so important thanks for the reverse hint
    BridgingBot
    @GitterIRCbot
    [slack] <sbromberger> hi
    [slack] <sbromberger> so, #graphs is preferred right now, but I monitor this channel as well
    [slack] <sbromberger> to your other question: edges in undirected graphs are… undirected. 1 => 2 is the same as 2 => 1, but we guarantee lexicographical ordering when edges are iterated, and we only show one version of the undirected edge (that is, src less than or equal to dst).
    [slack] <sbromberger> The reason we can’t use <=> is because edges themselves do not have directedness - only the graphs - so there’s no way to tell that a given edge is part of an undirected graph or a directed one.
    [slack] <sbromberger> if you’re adding all edges of an undirected graph to a directed graph, the easiest way to do this is just to convert the graph from undirected to directed:
    julia> g = PathDiGraph(4)
    {4, 3} directed simple Int64 graph
    
    julia> add_edge!(g, 4, 3) # add a reverse edge to this directed graph
    true
    
    julia> collect(edges(g))
    4-element Array{LightGraphs.SimpleGraphs.SimpleEdge{Int64},1}:
     Edge 1 => 2
     Edge 2 => 3
     Edge 3 => 4
     Edge 4 => 3
    
    julia> h = Graph(g)
    {4, 3} undirected simple Int64 graph
    
    julia> collect(edges(h))
    3-element Array{LightGraphs.SimpleGraphs.SimpleEdge{Int64},1}:
     Edge 1 => 2
     Edge 2 => 3
     Edge 3 => 4
    BridgingBot
    @GitterIRCbot
    [slack] <Ole> Looks like it is merged now into Blossom mlewe/BlossomV.jl#13
    BridgingBot
    @GitterIRCbot
    [slack] <simonschoelly> ah thats good, because I haven't even started with edmonds algorithm 🙂
    [slack] <Ole> Ah and a new release is coming https://github.com/mlewe/BlossomV.jl/releases/tag/v0.4.0
    [slack] <simonschoelly> I forgot to original reason for this thread, where you only interested in blossomV or did you need some functionally form LightGraphsMatching?
    [slack] <Ole> I was actually interested in the maximum matching part so not in Blossom for my small project but it's good to hear that it's going forward 😁
    [slack] <Ole> Think I changed the maximum part a little in my project but I might look into the general one on the weekend and maybe try to update it to v0.7/v1 if you're interested
    BridgingBot
    @GitterIRCbot
    [slack] <simonschoelly> sure, might be a good addition for lightgraphsmatching
    BridgingBot
    @GitterIRCbot
    [slack] <sbromberger> hi
    [slack] <sbromberger> testing
    BridgingBot
    @GitterIRCbot
    [slack] <oxinabox> Cytoscape is really cool
    [slack] <oxinabox> for visualisation
    BridgingBot
    @GitterIRCbot
    [slack] <sbromberger> yes, but it can’t handle large graphs.
    Frank Hellmann
    @FHell
    Hello, we are working on a small package to work with embedded graphs, and ran into some trouble along the way. It appears that the developer documentation is a bit out of date.
    Or some functions are overly specific.
    ... in what they accept.
    Esepcially when it comes to weights.
    The stuff we first tried to get weights to work is documented in what_works.jl (we've now settled on just using a sparse matrix instead).