4

我正在寻找一种方法来避免在我的 digraph 中创建重复项（我使用 jgrapht 库）。

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

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

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

然后它根据洪水填充算法向其添加顶点（在算法通过每个点时添加顶点和边，下面是它的一部分）：

// 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+"]");
  }
}
4

2 回答 2

2

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

例如（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;
}
于 2015-07-26T22:15:57.460 回答
1

我尝试使用以下程序创建一些重复的顶点和边：

import org.jgrapht.DirectedGraph;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;

import java.awt.Point;

public class JgraphtTest {
    public static void main(String[] args) {
        DirectedGraph<Point, DefaultEdge> directedGraph = new DefaultDirectedGraph<Point, DefaultEdge>(DefaultEdge.class);
        Point zero = new Point(0, 0), zero2 = new Point(0, 0), one = new Point(1, 1), two = new Point(2, 2);
        directedGraph.addVertex(zero);
        directedGraph.addVertex(one);
        directedGraph.addVertex(two);
        directedGraph.addVertex(zero2);   // should be a dup
        directedGraph.addEdge(zero, one);
        directedGraph.addEdge(one, two);
        directedGraph.addEdge(zero2, one); // should be a dup

        for (Point vertex : directedGraph.vertexSet()) {
            System.out.format("vertex: %s\n", vertex);
        }
        for (DefaultEdge edge : directedGraph.edgeSet()) {
            System.out.format("edge: %s\n", edge);
        }
    }
}

但它在输出中没有显示重复：

vertex: java.awt.Point[x=0,y=0]
vertex: java.awt.Point[x=1,y=1]
vertex: java.awt.Point[x=2,y=2]
edge: (java.awt.Point[x=0,y=0] : java.awt.Point[x=1,y=1])
edge: (java.awt.Point[x=1,y=1] : java.awt.Point[x=2,y=2])

所以我猜你正在使用你自己的Point类，但你没有正确覆盖equalsand hashCode。如果没有覆盖这些方法，DirectedGraph将无法判断顶点是否已经存在。

于 2015-07-26T22:00:56.830 回答