[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
[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
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
[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.
[slack] <Ole> yeah not so important thanks for the
reverse hint
[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
[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
[slack] <sbromberger> testing
[slack] <oxinabox> for visualisation
Or some functions are overly specific.
... in what they accept.
Esepcially when it comes to weights.
Repo is here: https://github.com/FHell/EmbeddedGraphs.jl
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).
The things that are not documented to be part of the interface are in the main /src/EmbeddedGraphs.jl file.
[slack] <oxinabox> Perhaps @Tushar Sinha might know, since it relates to the JSOC you just posted
[slack] <simonschoelly> ah no, that seems to be for maximum perfect matching
[slack] <simonschoelly> https://en.wikipedia.org/wiki/Assignment_problem might have some info
[slack] <oxinabox> Excellent thanks
This message was deleted
This message was deleted
[slack] <sbromberger> MetaGraphs supports DOT format AFAIR.