Giter Club home page Giter Club logo

lightgraphsmatching.jl's Introduction

LightGraphsMatching

Matching algorithms on top of LightGraphs.

Note: Development of this package has been moved to GraphsMatching.jl. LightGraphsMatching.jl will note receive any updates anymore.

lightgraphsmatching.jl's People

Contributors

dourouc05 avatar matbesancon avatar simonschoelly avatar wikunia avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar

lightgraphsmatching.jl's Issues

Is the function `maximum_weight_maximal_matching`correct?

I was looking at this, because I wanted to convert it to Julia v1.0, but I'm not sure this function actually does what it should do.
From my understanding, it tries to solve the following (simplified here) linear program:

Given bipartite graph G with parts |V1| <= |V2|  and weightmap W = {w_ij}

maximize  Sum( x_ij * w_ij  ) where   w_ij > 0   s.t.
(I)   forall i,j     :  x_ij >= 0
(II)  forall i in V1 : Sum(x_ij) == 1 where j in neighbors(G, i)
(III) forall j in V2 : Sum(x_ij) <= 1 where i in neighbors(G, j)

There are two issues:

  1. Now the objective function clearly aims to maximize the total weight. But I don't see why it only does this among the matchings with the largest number of edges. And shouldn't it be called maximum_weight_maximum_matching then? After all, the documentation suggests it looks for a maximum set of edges and not simply a maximal one.

  2. Condition (II) is not possible in all cases (at least for integer solutions). For example there are bipartite graphs with parts of equal size that do not contain a perfect matching, even if the graph is connected and does not have isolated vertices.

Deprecated generator syntax

Generator comprehension syntax used for the formulation of the objective and constraints for JuMP is deprecated and must be changed

Dependency-less matching algorithm?

I was trying to compute matchings with this package, I had a problem when installing the dependency BlossomV.jl (mlewe/BlossomV.jl#12). Then, I saw that the other way to solve matchings is to use mathematical programming. However, what I expected from this package was rather an implementation of the Hungarian algorithm (provided by BlossomV.jl, but not available on most platforms). Would it be possible to consider adding a pure-Julia implementation, so that it is ensured to work on all platforms? (Either coding one for this package, or using something like https://github.com/Gnimuc/Hungarian.jl or https://github.com/FugroRoames/Munkres.jl.)

Remove JuMP from weighted matching

Just like LGFlows.jl, JuMP can be removed as a dependency from the package by explicitly building the LP problem and solving it using MathProgBase.jl

maximum_matching

A maximum_matching or more precise maximum_cardinality_matching function can be useful. This will add no new dependences.
Will work on this as well so feel free to assign this issue to me ;)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.