java - 避免在有向图中创建重复顶点(使用 jgrapht)

Question

我正在寻找一种方法来避免在我的有向图中创建重复项(我使用 jgrapht 库)。

我读了一些说要使用的主题:directedGraph.setCloneable(false);但它似乎不对，在库的文档中找不到它，我在这一行收到一个错误，说它不存在。

我使用以下方法创建了图表:

public static DirectedGraph<Point, DefaultEdge> directedGraph = new DefaultDirectedGraph<Point, DefaultEdge>(DefaultEdge.class);

然后它根据flood fill算法添加顶点(随着算法遍历每个点添加顶点和边，下面是它的一部分):

// Up
    xToFillNext = x-1;
    yToFillNext = y;
    if (xToFillNext==targetX && yToFillNext==targetY && !forbiddenDirection.equals(Direction.UP)) {
      Point myPoint = new Point(x, y);
      Point myNextPoint = new Point(xToFillNext, yToFillNext);

      directedGraph.addVertex(myPoint);
      directedGraph.addVertex(myNextPoint);
      directedGraph.addEdge(myPoint, myNextPoint);
      return true;
    } else if (xToFillNext>=0 && originValue==matrix[xToFillNext][yToFillNext] && !forbiddenDirection.equals(Direction.UP)) {  
      Point myPoint = new Point(x, y);
      Point myNextPoint = new Point(xToFillNext, yToFillNext);

      directedGraph.addVertex(myPoint);
      directedGraph.addVertex(myNextPoint);
      directedGraph.addEdge(myPoint, myNextPoint);   
      fillingReachedTargetPosition = 
        fillReachesTargetPosition(matrix, xToFillNext, yToFillNext, targetX, targetY, fillValue, Direction.DOWN );
      if (fillingReachedTargetPosition) {
        return true;
      }
    }

但是当我打印顶点列表时，有一些重复项需要删除或避免创建。有办法吗？

编辑:我创建了一个 Point 类:

public static class Point {

  public int x;
  public int y;

  public  Point(int x, int y) 
  {

    this.x = x;
    this.y = y;
  }
  @Override
    public String toString() {
    return ("[x="+x+" y="+y+"]");
  }
}

Answer 1

为了检测重复顶点，您还需要为 equals 和 hashCode 提供方法。否则 JVM 不知道如何比较对象，并使用对象 ID (==)，这不会将类 Point 的两个不同对象标识为重复或相等。

例如(hashCode有无数种可能的实现方式)

@Override
public int hashCode() {
    int hash = 7;
    hash = 71 * hash + this.x;
    hash = 71 * hash + this.y;
    return hash;
}



@Override
public boolean equals(Object other) 
{
    if (this == other)
       return true;

    if (!(other instanceof Point))
       return false;

    Point otherPoint = (Point) other;
    return otherPoint.x == x && otherPoint.y == y;
}