Избегайте создания повторяющихся вершин в орграфе (используя jgrapht)

Я ищу способ избежать создания дубликатов в моем орграфе (я использую библиотеку 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+"]");
  }
}

java duplicates digraphs processing jgrapht
person Graham Slick    schedule 26.07.2015    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Чтобы обнаружить повторяющиеся вершины, вам также необходимо указать метод для equals и hashCode. В противном случае JVM не знает, как сравнивать объекты, и использует идентификатор объекта (==), который не идентифицирует два разных объекта класса 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;
}
person adamliesko    schedule 26.07.2015
comment
Должен ли я добавить это в свой класс Point? - person Graham Slick; 27.07.2015
comment
да, просто добавьте эти методы в существующий класс Point - person adamliesko; 27.07.2015
comment
Отлично работал с созданием вершин, но теперь, если я создаю ArrayList из одних и тех же объектов Point, могут быть дубликаты, даже когда я добавил предоставленный вами фрагмент кода. Разве это не должно применяться к любому списку? - person Graham Slick; 29.07.2015
comment
Нет, ArrayList не специфичен в этом. Вы можете использовать какой-то набор Java. - person adamliesko; 29.07.2015

arrow_upward
1
arrow_downward

Я попытался создать несколько повторяющихся вершин и ребер с помощью следующей программы:

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, но вы неправильно переопределяете equals и hashCode. Без переопределения этих методов DirectedGraph не сможет сказать, существует ли уже вершина или нет.

person heenenee    schedule 26.07.2015
comment
Спасибо за вашу помощь ! Что вы подразумеваете под переопределением equals и hashCode...? я не знаю как это сделать - person Graham Slick; 27.07.2015
comment
Вы используете свой собственный класс Point? Если да, можете ли вы опубликовать его исходный код? - person heenenee; 27.07.2015