CODEWITHSUNDEEP
javagraphgraph-theoryjgraphtweighted-graph
Gevorg Harutyunyan
Gevorg Harutyunyan

Reputation: 431

How to get max_weight_matching in java

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

Upvotes: 0

Views: 457

Answers (1)

Joris Kinable
Joris Kinable

Reputation: 2411

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]

Upvotes: 1

Related Questions