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> @sbromberger do you want to see what I have been at, and why I have been poking so many graph things lately? Perhaps if we are both online I can show you it at some point
    [slack] <oxinabox> I now have like a small collection of functions I think should be somewhere in the JuliaGraphs ecosystem
    [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.