2

特定のマップを逆にして、その逆のキーと値を別のマップに保存するのに少し問題があります。次のようなメソッドプロトタイプがあります。

public static Map<String, Set<String>> reverse (Map <String, Set<String>> graph);

したがって、次のような有向グラフのサンプル キーがあるとします。

{c -> arraySet{f, e}}
{b -> d}
{a -> arraySet{c, b}} 
{d -> g}
{e -> d}
{f -> arraySet{g, d}}

このグラフを効果的に逆にして、b -> d の代わりに d -> b になるようにする必要があります。

これに必要なのは、元のグラフの値とキーを交換して、reverseMap に追加することだけだと思います。グラフ内の特定のキーの値の各セットを反復処理し、それらをリストに格納できると思います。

残念ながら、私はこれを実装して考え抜くのに苦労しています。正しい方向へのナッジを本当に感謝します。

4

4 に答える 4

5

Guava Multimapsを使用した、実際に動作する最新のコードを次に示します。

SetMultimap<Integer, Integer> graph = HashMultimap.create();
graph.put(1, 2); // add an edge from 1 to 2
SetMultimap<Integer, Integer> inverse = Multimaps.invertFrom(
  graph, HashMultimap.<Integer, Integer> create());

（開示：私はGuavaに貢献しています。）

ただし、サードパーティのライブラリを使用できない場合は、次のようにしてください...

Map<Integer, Set<Integer>> g;
Map<Integer, Set<Integer>> gInverse = new HashMap<Integer, Set<Integer>>();
for (Map.Entry<Integer, Set<Integer>> gAdj : g.entrySet()) {
  Integer v = gAdj.getKey();
  for (Integer w : gAdj.getValue()) {
    Set<Integer> wInverseAdj = gInverse.get(w);
    if (wInverseAdj == null) {
      gInverse.put(w, wInverseAdj = new HashSet<Integer>());
    }
    wInverseAdj.add(v);
  }
}

または、Java 8を使用できる場合は、これを使用してください...

map.entrySet().stream()
   .flatMap(entryKToVs -> entryKToVs.getValue().stream()
       .map(v -> new AbstractMap.SimpleEntry<>(entryKToVs.getKey(), str)))
   .collect(groupingBy(Map.Entry::getValue, mapping(Map.Entry::getKey, toList())))
于 2012-10-04T22:48:34.073 に答える
2

疑似コードですが、本物に近いです。Multimapを使用するだけです。

Multimap<String, String> ret = Multimaps.newSetMultimap();
for (Entry<String, Set<String>> entry : graph) {
  for(String neighbor : entry.getValue()) {
    ret.addTo(neighbor, entry.getKey());
  }
}
于 2012-10-04T22:32:06.757 に答える
1

マップ内のエントリをループする必要があります。次に、値がセットに格納されているため、そのセットをループする必要があります。各キーの結果マップを確認し、キーがまだ存在しない場合は常に新しいセットを作成する必要があります。

public static Map<String, Set<String>> reverse (Map <String, Set<String>> graph) {
    Map<String, Set<String>> result = new HashMap<String, Set<String>>();
    for (Map.Entry<String, Set<String>> graphEntry: graph.entrySet()) {
        for (String graphValue: graphEntry.getValue()) {
            Set<String> set = result.get(graphValue);
            if (set == null) {
                set = new HashSet<String>();
                result.put(graphValue, set);
            }
            set.add(graphEntry.getKey());
        }
    }
    return result;
}
于 2012-10-04T22:31:13.497 に答える
0

最初に、基礎となるデータ構造Graphを抽象化するクラスを作成することをお勧めします。Mapもちろん、これはGraphインターフェイスを直接処理するのではなく、実装をインターフェイスにプッシュするだけMapです。

だから今のところ、あなたの地図に固執してください：

Map<String, Set<String>> graph;
Map<String, Set<String>> reverse;

Map.entrySet()を使用して、からエントリのセットを取得することをお勧めしますgraph。次に、Map.Entryごとに、それぞれのキーと値を取得します。次に、 value の各「頂点」について、頂点に関連付けられているSetにキーを挿入します。Set

これは、英語の文章ではなく Java コードに似た形式にすると、より明確になる可能性があります。基本的な考え方を理解していただければ幸いです。もちろん、プロジェクトの制約に適合する場合は、事前に作成および事前にテストされたソリューションを使用することをお勧めします。

于 2012-10-04T22:25:56.433 に答える