Combinatorial optimization-typical problem-maximum matching problem

Typical problem and execution method

Maximum matching problem

Find the matching with the maximum number of edges for the undirected graph $ G = (V, E) $.

Execution method

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]
for i, j in g.edges():
    del g.adj[i][j]['weight']
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: 0, 0: 5, 4: 3, 3: 4, 2: 1, 1: 2}

image.png

python


# pandas.DataFrame
from ortoolpy.optimization import MaxMatching
MaxMatching('data/edge0.csv')
node1 node2 capacity weight
0 0 5 2 4
1 1 2 2 5
2 3 4 2 4

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)
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()

mwm.png

data

Recommended Posts

Combinatorial optimization-typical problem-maximum matching problem
Combinatorial optimization-Typical problem-Stable matching problem
Combinatorial optimization-typical problem-maximum flow problem
Combinatorial optimization-typical problem-weight matching problem
Combinatorial optimization-typical problem-maximum cut problem
Combinatorial optimization-Typical problem-Maximum stable set problem
Combinatorial optimization-typical problem-knapsack problem
Combinatorial optimization-typical problem-n-dimensional packing problem
Combinatorial optimization-Typical problem-Vertex cover problem
Combinatorial optimization-typical problem-generalized allocation problem
Combinatorial optimization-typical problem-bin packing problem
Combinatorial optimization-Typical problem-Secondary allocation problem
Combinatorial optimization-typical problem-shortest path problem
Combinatorial optimization-typical problem-combinatorial auction problem
Combinatorial optimization-typical problem-set cover problem
Combinatorial optimization-Typical problem-Facility placement problem
Combinatorial optimization-typical problem-job shop problem
Combinatorial optimization-typical problem-traveling salesman problem
Combinatorial optimization-typical problem-work scheduling problem
Combinatorial optimization-Typical problem-Minimum spanning tree problem
Combinatorial optimization-typical problem-minimum cost flow problem
Combinatorial optimization-typical problem-Chinese postal delivery problem
Combinatorial optimization-Typical problem-Transportation route (delivery optimization) problem
Combinatorial optimization-minimum cut problem
Combinatorial optimization-typical problems and execution methods