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}}

我需要有效地反转这个图，以便我有 d -> b 而不是 b -> d。

我认为这对我来说就是交换原始图中的值和键并将它们添加到 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，将 key 插入Set与顶点关联的 key 中。

如果我将其格式化为类似于 Java 代码而不是英文句子，这可能会更清楚。我希望你能得到基本的想法。当然，如果它适合您的项目限制，则最好使用预制和预先测试的解决方案。

于 2012-10-04T22:25:56.433 回答