java - Algorithm for minimal cost + maximum matching in a general graph -

i've got dataset consisting of nodes , edges. nodes respresent people , edges represent relations, each has cost that's been calculated using euclidean distance.

now wish match these nodes through respective edges, there 1 constraint:

• any node can matched single other node.

now know i'm working in general graph, every node theoretically matched node in dataset, long there edge between them.

what wish do, find solution maximum matches , overall minimum cost.

node node b node c node d  - edge 1: start:       end      cost node       node b   0.5  - edge 2: start:       end      cost node b       node c   1  - edge 3: start:       end      cost node c       node d   0.5  - edge 2: start:       end      cost node d       node   1 

the solution problem, following:

• assign edge 1 , edge 3, maximum amount of matches ( in case, there's 2 solutions, there tons of branching edges other nodes)

• edge 1 , edge 3 assigned, because it's solution maximum amount of matches , minimum overall cost (1)

i've looked quite few algorithms including hungarian, blossom, minimal-cost flow, i'm uncertain best case. there seems awful lot of material solving these kinds of problems in bipartial graph's, isn't case in matter.

so ask you:

1. which algorithm best in scenario return (a) maximum amount of matches , (b) lowest overall cost.

2. do know of material (maybe easy-to-understand pseudocode), recomended algorithm? i'm not strongest in mathematical notation.

for (a), suitable algorithm (there theoretically faster ones, they're more difficult understand) edmonds' blossom algorithm. unfortunately quite complicated, i'll try explain basis best can.

the basic idea take matching, , continually improve (increase number of matched nodes) making local changes. key concept alternating path: path unmatched node unmatched node, property edges alternate between being in matching, , being outside it.

if have alternating path, can increase size of matching 1 flipping state (whether or not in matching) of edges in alternating path.

if there exists alternating path, matching not maximum (since path gives way increase size of matching) , conversely, can show if there no alternating path, matching maximum. so, find maximum matching, need able find alternating path.

in bipartite graphs, easy (it can done dfs). in general graphs more complicated, , edmonds' blossom algorithm comes in. speaking:

• build new graph, there edge between 2 vertices if can u v first traversing edge in matching, , traversing , edge isn't.

• in graph, try find path unmatched vertex matched vertex has unmatched neighbor (that is, neighbor in original graph).

each edge in path find corresponds 2 edges of original graph (namely edge in matching , 1 not in matching), path translates alternating walk in new graph, not alternating path (the distinction between path , walk path uses each vertex once, walk can use each vertex multiple times).

• if walk path, have alternating path , done.

• if not, walk uses vertex more once. can remove part of walk between 2 visits vertex, , obtain new graph (with part of vertices removed). in new graph have whole search again, , if find alternating path in new graph can "lift" alternating path original graph.

going details of (crucial) last step bit stackoverflow answer, can find more details on wikipedia , perhaps having high-level overview helps understand more mathematical articles.

implementing scratch quite challenging.

for weighted version (with euclidean distance), there more complicated variant of edmonds' algorithm can handle weights. kolmogorov offers c++ implementation , accompanying paper. can used unweighted case, using implementation might idea (even if not in java, there should way interface it).

since weights based on euclidean distances there might specialized algorithm case, more general version mentioned above work , and implementation available it.