CODEWITHSUNDEEP
javaduplicatesprocessingjgraphtdigraphs
Graham Slick
Graham Slick

Reputation: 6870

Avoid creation of duplicate vertices in digraph (using jgrapht)

I am looking for a way to avoid creating duplicates in my digraph (I use the jgrapht library).

I read some topics which said to use: directedGraph.setCloneable(false); But it doesn't seem to be right, can't find it in the library's documentation and I get an error on this line saying it doesn't exists.

I created my graph using:

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

And then it adds vertices to it based on the flood fill algorithm (adds vertices and edges as the algorithm go through every point, below is a part of it):

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

But when I print the list of vertices, there are duplicates which I either need to get rid of, or avoid them to be created. Is there a way to do it ?

EDIT: I created a Point class:

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

Upvotes: 4

Views: 1332

Answers (2)

adamliesko
adamliesko

Reputation: 1915

In order to detect duplicate vertices you need to supply also method for equals and hashCode. Ohterwise JVM does not know, how to compare the objects, and uses object id (==) which would not identify two different object of class Point as duplicate or equal.

e.g. ( The hashCode has countless number of possible implementations)

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

Upvotes: 2

heenenee
heenenee

Reputation: 20125

I tried creating some duplicate vertices and edges with the following program:

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

But it showed no duplicates in the output:

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])

So I'm guessing that you are using your own Point class, but you're not properly overriding equals and hashCode. Without those methods being overridden, DirectedGraph won't be able to tell if a vertex exists already or not.

Upvotes: 1

Related Questions