英文:
How to get max_weight_matching in java
问题
import org.jgrapht.Graph;
import org.jgrapht.Graphs;
import org.jgrapht.alg.matching.EdmondsMaximumCardinalityMatching;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleGraph;
public class MaximumWeightMatchingExample {
public static void main(String[] args) {
Graph<Integer, DefaultWeightedEdge> graph = new SimpleGraph<>(DefaultWeightedEdge.class);
graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);
graph.addVertex(4);
DefaultWeightedEdge e12 = graph.addEdge(1, 2);
graph.setEdgeWeight(e12, 30);
DefaultWeightedEdge e13 = graph.addEdge(1, 3);
graph.setEdgeWeight(e13, 100);
DefaultWeightedEdge e14 = graph.addEdge(1, 4);
graph.setEdgeWeight(e14, 30);
DefaultWeightedEdge e23 = graph.addEdge(2, 3);
graph.setEdgeWeight(e23, 0);
DefaultWeightedEdge e24 = graph.addEdge(2, 4);
graph.setEdgeWeight(e24, 30);
DefaultWeightedEdge e34 = graph.addEdge(3, 4);
graph.setEdgeWeight(e34, 30);
EdmondsMaximumCardinalityMatching<Integer, DefaultWeightedEdge> matcher =
new EdmondsMaximumCardinalityMatching<>(graph);
Graph<Integer, DefaultWeightedEdge> matching = matcher.getMatching();
System.out.println(matching.edgeSet());
}
}
英文:
I have a Weighted and Non-Bipartite graph and would like to get the maximum weight matching. I have done the task with the python networkx library and looking for an alternative library for java. I looked into the JGraphT library but couldn't find the solution.
import networkx as nx
import networkx.algorithms.matching as matching
G=nx.Graph()
G.add_edge(1,2,weight = 30)
G.add_edge(1,3,weight = 100)
G.add_edge(1,4,weight = 30)
G.add_edge(2,3,weight = 0)
G.add_edge(2,4,weight = 30)
G.add_edge(3,4,weight = 30)
M = matching.max_weight_matching(G,maxcardinality=True)
print(list(M))
//OUTPUT: [(1, 3), (2, 4)]
答案1
得分: 1
这是使用 JGraphT 的解决方案：
Graph<Integer, DefaultWeightedEdge> g = new SimpleWeightedGraph<>(SupplierUtil.createIntegerSupplier(1), SupplierUtil.createDefaultWeightedEdgeSupplier());
Integer v1 = g.addVertex();
Integer v2 = g.addVertex();
Integer v3 = g.addVertex();
Integer v4 = g.addVertex();
Graphs.addEdge(g, v1, v2, 30);
Graphs.addEdge(g, v1, v3, 100);
Graphs.addEdge(g, v1, v4, 30);
Graphs.addEdge(g, v2, v3, 0);
Graphs.addEdge(g, v2, v4, 30);
Graphs.addEdge(g, v3, v4, 30);
MatchingAlgorithm<Integer, DefaultWeightedEdge> alg = new KolmogorovWeightedMatching<>(g, ObjectiveSense.MAXIMIZE);
System.out.println(alg.getMatching());
输出：
Matching [edges=[(1 : 3), (2 : 4)], weight=130.0]
英文:
Here's the solution using JGraphT:
Graph<Integer, DefaultWeightedEdge> g = new SimpleWeightedGraph<>(SupplierUtil.createIntegerSupplier(1), SupplierUtil.createDefaultWeightedEdgeSupplier());
Integer v1=g.addVertex();
Integer v2=g.addVertex();
Integer v3=g.addVertex();
Integer v4=g.addVertex();
Graphs.addEdge(g, v1, v2, 30);
Graphs.addEdge(g, v1, v3, 100);
Graphs.addEdge(g, v1, v4, 30);
Graphs.addEdge(g, v2, v3, 0);
Graphs.addEdge(g, v2, v4, 30);
Graphs.addEdge(g, v3, v4, 30);
MatchingAlgorithm<Integer, DefaultWeightedEdge> alg = new KolmogorovWeightedMatching<>(g, ObjectiveSense.MAXIMIZE);
System.out.println(alg.getMatching());
Output:
Matching [edges=[(1 : 3), (2 : 4)], weight=130.0]
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论