[PYTHON] Combinatorial optimization-typical problem-weight matching problem

Typical problem and execution method

Weight matching problem

The weight matching problem is a general term such as "maximum weight matching problem, maximum weight maximum matching problem, maximum weight perfect matching problem, minimum weight maximum matching problem, minimum weight perfect matching problem".

--All weights are 0 or more. --The minimum weight matching problem is usually not considered because ** empty ** is a trivial optimal solution. --When all the weights are 1 in "Maximum weight matching problem and maximum weight maximum matching problem and minimum weight maximum matching problem", simply "Maximum weight matching problem" Called. --When the weights are all 1 in the "maximum weight perfect matching problem and the minimum weight perfect matching problem", it is simply called the "perfect matching problem". --The minimum weight maximum matching problem and the minimum weight perfect matching problem can be reduced to the maximum weight maximum matching problem and the maximum weight perfect matching problem by changing the weight to "maximum weight-the weight". --The maximum weight perfect matching problem is a solution only when the solution of the maximum weight maximum matching problem is perfect matching. ――From these things, it is only necessary to have a solution for the maximum weight matching problem and the maximum weight maximum matching problem. --The maximum weight matching problem can be solved by the following max_weight_matching (Edmonds method). --Maximum weight To solve the maximum matching problem, specify maxcardinality = True in max_weight_matching below. --If the graph is a bipartite graph, there is an algorithm (such as Hungarian law) that has higher performance than general graphs.

Maximum weight matching problem

For the undirected graph $ G = (V, E) $, when the weight $ w (e) $ of each side $ e \ in E $ is given, $ \ sum_ {e \ in M} {w ( e) Find the matching $ M $ with the largest} $.

Execution method (maximum weight matching problem)

usage

Signature: nx.max_weight_matching(G, maxcardinality=False)
Docstring:
Compute a maximum-weighted matching of G.

A matching is a subset of edges in which no node occurs more than once.
The cardinality of a matching is the number of matched edges.
The weight of a matching is the sum of the weights of its edges.

python

#CSV data
import pandas as pd, networkx as nx, matplotlib.pyplot as plt
from ortoolpy import graph_from_table, networkx_draw
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe)[0]
d = nx.max_weight_matching(g)
pos = networkx_draw(g)
nx.draw_networkx_edges(g, pos, width=3, edgelist=[(i, j) for i, j in d])
plt.show()
print(d)

result

{5: 1, 1: 5, 0: 2, 2: 0, 4: 3, 3: 4}

python

# pandas.DataFrame
from ortoolpy.optimization import MaxWeightMatching
MaxWeightMatching('data/edge0.csv')

python

#Random number data
import networkx as nx, matplotlib.pyplot as plt
from ortoolpy import networkx_draw
g = nx.random_graphs.fast_gnp_random_graph(10, 0.3, 1)
for i, j in g.edges():
    g.adj[i][j]['weight'] = 1
d = nx.max_weight_matching(g)
pos = networkx_draw(g, nx.spring_layout(g))
nx.draw_networkx_edges(g, pos, width=3, edgelist=[(i, j) for i, j in d])
plt.show()

data

• data/node0.csv
• data/edge0.csv