0
我正在研究需要將定向標籤圖劃分成多個子圖的問題。在每個子圖中,節點都連接在一起,並且它們具有相同的標籤。有沒有一種有效的算法來解決這個問題?通過頂點標籤對圖進行分區
我正在研究需要將定向標籤圖劃分成多個子圖的問題。在每個子圖中,節點都連接在一起,並且它們具有相同的標籤。有沒有一種有效的算法來解決這個問題?通過頂點標籤對圖進行分區
這是我用Java實現的解決方案,它使用JGraphT作爲圖庫。
private Set<Set<Node>> partition(DirectedGraph<Node, Edge> graph) {
Map<Node, Set<Node>> map = new HashMap<Node, Set<Node>>();
for (Edge edge : graph.edgeSet()) {
Node source = graph.getEdgeSource(edge);
Node target = graph.getEdgeTarget(edge);
if (source.getLabel().equals(target.getLabel())) {
if (map.get(source) != null && map.get(target) == null) {
map.get(source).add(target);
map.put(target, map.get(source));
} else if (map.get(target) != null && map.get(source) == null) {
map.get(target).add(source);
map.put(source, map.get(target));
} else if (map.get(source) == null && map.get(target) == null) {
Set<Node> set = new HashSet<Node>();
set.add(source);
set.add(target);
map.put(source, set);
map.put(target, set);
} else {
Set<Node> sourceSet = map.get(source);
Set<Node> targetSet = map.get(target);
sourceSet.addAll(targetSet);
for(Node n : targetSet){
map.put(n,sourceSet);
}
targetSet = null;
}
} else {
if (map.get(source) == null) {
Set<Node> set = new HashSet<Node>();
set.add(source);
map.put(source, set);
}
if (map.get(target) == null) {
Set<Node> set = new HashSet<Node>();
set.add(target);
map.put(target, set);
}
}
Collection<Set<Node>> values = map.values();
}
return new HashSet<Set<Node>>(map.values());
}
定義「分區」。聽起來像運行一個簡單的DFS可以解決您的問題。 –
一組連接並具有標籤的頂點進入一個分區 –
因此,您基本上想要檢測圖形組件? https://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29?wprov=sfla1 –