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] <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).
    The things that are not documented to be part of the interface are in the main /src/EmbeddedGraphs.jl file.
    BridgingBot
    @GitterIRCbot
    [slack] <oxinabox> What special algorithms exist for Minimum Perfect Matching, for Bipartite Graphs
    [slack] <oxinabox> Perhaps @Tushar Sinha might know, since it relates to the JSOC you just posted
    BridgingBot
    @GitterIRCbot
    [slack] <simonschoelly> isn't that the hungarian algorithm?
    [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
    BridgingBot
    @GitterIRCbot
    This message was deleted
    [slack] <oxinabox> Excellent thanks
    This message was deleted
    This message was deleted
    BridgingBot
    @GitterIRCbot
    [slack] <matbesancon> Min-cost matching is equivalent to a min-cost flow on the bi-partite graph + one source + one sink, so formulating as a linear opt problem works, not the most efficient but is nice to highlight polynomial time
    Guillaume Larocque
    @glaroc
    Hi, I've been struggling to find a way to import an existing graph with vertex and edge attributes into LightGraphs or MetaGraphs. Can anyone point me to some documentation?
    BridgingBot
    @GitterIRCbot
    [slack] <sbromberger> you'll lose attributes if you import into SimpleGraph.
    [slack] <sbromberger> MetaGraphs supports DOT format AFAIR.
    Guillaume Larocque
    @glaroc
    @GitterIRCbot Thanks, although GraphIO doesn't seem to keep the attributes when importing graphs. So, how you one import graphs with attributes into Metagraphs? I guess the only way is to import the edges and vertices as CSVs and build the graph from scratch?
    BridgingBot
    @GitterIRCbot
    [slack] <sbromberger> that's probably the best we can do for now, but you might check MetaGraphs.jl to see whether @jpfairbanks' DOT code was merged.
    BridgingBot
    @GitterIRCbot
    [slack] <jpfairbanks> So the Dot format is write only. You could implement a dot reader although it would be quite time consuming because of the flexibility inherent in the dot format
    [slack] <sbromberger> ah, I didn't know that.
    [slack] <jpfairbanks> I would recommend storing graphs with metadata in a tabular format like CSV, juliadb, SQLite etc. and then using queries to build the graph when you need it.