Fiduccia-Mattheyses-algoritmus
A Fiduccia-Mattheyses-algoritmus egy gyors és hatékony algoritmus gráfok particionálására, amelyet főként az elektronikai tervezésben (VLSI áramkörök optimalizálása) használnak. Az algoritmus célja egy gráf csúcsainak két részre bontása úgy, hogy a két rész közötti élkapcsolatok száma minimális legyen, miközben a particiók egyensúlyban maradnak (azaz hasonló méretűek).
Az alábbi Python-kód egyszerűsíti az FM-algoritmus lényegét.
import random
from collections import defaultdict
def calculate_gain(graph, part1, part2, vertex):
"""Gain kiszámítása a csúcs mozgatásához."""
E_from = sum(weight for neighbor, weight in graph if neighbor in part1)
E_to = sum(weight for neighbor, weight in graph if neighbor in part2)
return E_to - E_from
def fiduccia_mattheyses(graph, initial_part1):
"""
Fiduccia-Mattheyses algoritmus implementáció.
:param graph: Gráf (szomszédsági lista súlyokkal)
:param initial_part1: Az első partició kezdeti csúcsai
:return: Optimalizált particiók
"""
vertices = set(graph.keys())
part1 = set(initial_part1)
part2 = vertices - part1
locked = set()
best_cut_size = float('inf')
best_part1, best_part2 = None, None
while len(locked) < len(vertices):
gains = {}
for vertex in vertices - locked:
if vertex in part1:
gains = calculate_gain(graph, part1, part2, vertex)
else:
gains = calculate_gain(graph, part2, part1, vertex)
# Legnagyobb gain csúcs kiválasztása
max_gain_vertex = max(gains, key=gains.get)
max_gain = gains
# Csúcs mozgatása
if max_gain_vertex in part1:
part1.remove(max_gain_vertex)
part2.add(max_gain_vertex)
else:
part2.remove(max_gain_vertex)
part1.add(max_gain_vertex)
locked.add(max_gain_vertex)
# Cut size újraszámítása
cut_size = sum(weight for v in part1 for neighbor, weight in graph if neighbor in part2)
if cut_size < best_cut_size:
best_cut_size = cut_size
best_part1, best_part2 = set(part1), set(part2)
return best_part1, best_part2
# Példa gráf
graph = {
'a': ,
'b': ,
'c': ,
'd': ,
}
initial_part1 =
part1, part2 = fiduccia_mattheyses(graph, initial_part1)
print("Particiók:")
print("Part1:", part1)
print("Part2:", part2)
Az alábbi C++ kód az FM-algoritmus alapjait illusztrálja:
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;
struct Edge {
int to, weight;
};
using Graph = unordered_map<int, vector<Edge>>;
int calculateGain(const Graph& graph, const unordered_set<int>& part1, const unordered_set<int>& part2, int vertex) {
int E_from = 0, E_to = 0;
for (const auto& edge : graph.at(vertex)) {
if (part1.count(edge.to)) {
E_from += edge.weight;
} else if (part2.count(edge.to)) {
E_to += edge.weight;
}
}
return E_to - E_from;
}
pair<unordered_set<int>, unordered_set<int>> fiducciaMattheyses(const Graph& graph, unordered_set<int> initialPart1) {
unordered_set<int> part1 = initialPart1;
unordered_set<int> part2;
for (const auto& : graph) {
if (!part1.count(vertex)) {
part2.insert(vertex);
}
}
unordered_set<int> locked;
int bestCutSize = INT_MAX;
unordered_set<int> bestPart1 = part1, bestPart2 = part2;
while (locked.size() < graph.size()) {
unordered_map<int, int> gains;
for (int vertex : part1) {
if (!locked.count(vertex)) {
gains = calculateGain(graph, part1, part2, vertex);
}
}
for (int vertex : part2) {
if (!locked.count(vertex)) {
gains = calculateGain(graph, part2, part1, vertex);
}
}
int maxGainVertex = max_element(gains.begin(), gains.end(), (auto& a, auto& b) {
return a.second < b.second;
})->first;
if (part1.count(maxGainVertex)) {
part1.erase(maxGainVertex);
part2.insert(maxGainVertex);
} else {
part2.erase(maxGainVertex);
part1.insert(maxGainVertex);
}
locked.insert(maxGainVertex);
int cutSize = 0;
for (int v : part1) {
for (const auto& edge : graph.at(v)) {
if (part2.count(edge.to)) {
cutSize += edge.weight;
}
}
}
if (cutSize < bestCutSize) {
bestCutSize = cutSize;
bestPart1 = part1;
bestPart2 = part2;
}
}
return {bestPart1, bestPart2};
}
int main() {
Graph graph = {
{1, {{2, 1}, {3, 2}}},
{2, {{1, 1}, {4, 1}}},
{3, {{1, 2}, {4, 2}}},
{4, {{2, 1}, {3, 2}}}
};
unordered_set<int> initialPart1 = {1, 2};
auto = fiducciaMattheyses(graph, initialPart1);
cout << "Part1: ";
for (int v : part1) cout << v << " ";
cout << "\nPart2: ";
for (int v : part2) cout << v << " ";
cout << endl;
return 0;
}