2

我想使用 aPriorityQueue对图进行拓扑排序。为简洁起见，我想为比较器使用匿名内部类。但是，我需要访问图表g以确定我正在查看的节点的度数。这可能吗？

    /**
 * topological sort 
 * @param g must be a dag
 */
public static Queue<String> topoSort(DirectedGraph<String, DefaultEdge> g) {
    Queue<String> result = new PriorityQueue<String>(g.vertexSet().size(), 
            new Comparator<String>() {

                DirectedGraph<String, DefaultEdge> g;

                @Override
                public int compare(String arg0, String arg1) {
                    if (g.inDegreeOf(arg0) < g.inDegreeOf(arg1)) {
                        return -1;
                    }
                    if (g.inDegreeOf(arg0) > g.inDegreeOf(arg1)) {
                        return 1;
                    }
                    return 0;
                }
    });

    result.addAll(g.vertexSet());

    return result;
}

更正的代码

/**
 * topological sort 
 * @param g must be a dag
 */
public static Queue<String> topoSort(final DirectedGraph<String, DefaultEdge> g) {
    Queue<String> result = new PriorityQueue<String>(g.vertexSet().size(), 
            new Comparator<String>() {          
                @Override
                public int compare(String arg0, String arg1) {
                    if (g.inDegreeOf(arg0) < g.inDegreeOf(arg1)) {
                        return -1;
                    }
                    if (g.inDegreeOf(arg0) > g.inDegreeOf(arg1)) {
                        return 1;
                    }
                    return 0;
                }
    });

    result.addAll(g.vertexSet());

    return result;
}
4

3 回答 3

11

是的，让它成为最终的：

public static Queue<String> topoSort(final DirectedGraph<String, DefaultEdge> g) {

请参阅final 关键字上的最后一句话：

匿名本地类

涉及最终变量的第二种情况实际上是由语言语义要求的。在这种情况下，Java 编译器不会让您使用变量，除非它被声明为 final。这种情况出现在闭包中，也称为匿名本地类。局部类只能引用声明为 final 的局部变量和参数。

public void doSomething(int i, int j)
{
  final int n = i + j; // must be declared final

  Comparator comp = new Comparator()
  {
    public int compare(Object left, Object right)
    {
      return n; // return copy of a local variable
    }
  };
}

如果我们对本地类的实现方式有所了解，这种限制的原因就很明显了。匿名本地类可以使用局部变量，因为编译器会自动为该类提供一个私有实例字段来保存该类使用的每个局部变量的副本。编译器还会为每个构造函数添加隐藏参数来初始化这些自动创建的私有字段。因此，本地类实际上并不访问局部变量，而只是访问它们自己的私有副本。唯一可以正常工作的方法是，如果局部变量被声明为 final，这样就可以保证它们不会改变。有了这个保证，本地类就可以确保其变量的内部副本准确地反映了实际的局部变量。

于 2009-11-17T02:29:25.097 回答
2

如果在内部类中使用了局部变量，编译器会为内部类生成一个实例字段并将局部变量值复制到其中。现在，如果局部变量发生变化，那么实例变量值仍将具有旧值。因此，为了使局部变量的值与实例字段相同且不可变，将其设为 final。

于 2012-08-27T15:03:45.807 回答
0

仅供参考，使用谷歌收藏，您还可以选择

  Ordering.natural().onResultOf(
      new Function<String, Integer>() {
        public Integer apply(String arg) {
          return g.inDegreeOf(arg);
        }
      });

正如您所看到的，这不一定会为您节省大量输入，除非您可以找到该函数的其他用途，但它确实可以保护您免受经常潜入您的手动比较器实现的错误的影响。

于 2009-11-18T09:01:08.183 回答