I have a digraph created using:
public static DirectedGraph<Point, DefaultEdge> directedGraph = new DefaultDirectedGraph<Point, DefaultEdge>(DefaultEdge.class);
public static Point firstPoint = new Point(2, 7);
Vertices and edges were created with a Flood Fill algorithm implemented in a matrix. In the matrix I use, there are only 0s, 1s and 2s. The Flood fill algorithm detects if there is a loop formed by 1s and 2s, and as it goes through the 1s, it turns them into 3s. Example:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 2 2 0 0 0
0 0 0 0 0 2 2 1 0 0
0 0 0 1 1 1 0 1 0 0
0 0 0 1 0 0 1 1 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Will Become:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 2 2 0 0 0
0 0 0 0 0 2 2 3 0 0
0 0 0 3 3 3 0 3 0 0
0 0 0 3 0 0 3 3 0 0
0 0 0 3 3 3 3 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
As the algorithm goes through the Matrix, it creates vertices (each 1 it encounters) and edges (between two consecutive points). Here is the Algorithm, which starts at the point (2,7) in the matrix:
public static class FloodFill {
public static void resolution(String[] args) {
System.out.println("Found loop: "+checkIfPositionIsInLoop(matrix, 2, 7, 3));
//result
System.out.println("-------------------");
for (int i=0; i<matrix.length; i++) {
for (int j=0; j<matrix[i].length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.print("\n");
}
System.out.print("\n");
}
private static Direction direction;
public static boolean checkIfPositionIsInLoop(int[][] matrix, int x, int y, int fillValue) {
int targetX = x;
int targetY = y;
return fillReachesTargetPosition(matrix, x, y, targetX, targetY, fillValue, Direction.LEFT );
}
private static boolean fillReachesTargetPosition(int[][] matrix, int x, int y, int targetX, int targetY, int fillValue, Direction forbiddenDirection) {
if (x>=matrix.length)
return false;
if (y>=matrix[x].length)
return false;
int originValue=matrix[x][y];
matrix[x][y]=fillValue;
int xToFillNext;
int yToFillNext;
boolean fillingReachedTargetPosition = false;
// 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;
}
}
// Right
xToFillNext = x;
yToFillNext = y+1;
if (xToFillNext==targetX && yToFillNext==targetY && !forbiddenDirection.equals(Direction.RIGHT)) {
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 (yToFillNext<matrix[xToFillNext].length && originValue==matrix[xToFillNext][yToFillNext] && !forbiddenDirection.equals(Direction.RIGHT)) {
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.LEFT );
if (fillingReachedTargetPosition) {
return true;
}
}
// Down
xToFillNext = x+1;
yToFillNext = y;
if (xToFillNext==targetX && yToFillNext==targetY && !forbiddenDirection.equals(Direction.DOWN)) {
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<matrix.length && originValue==matrix[xToFillNext][yToFillNext] && !forbiddenDirection.equals(Direction.DOWN)) {
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.UP );
if (fillingReachedTargetPosition) {
return true;
}
}
// Left
xToFillNext = x;
yToFillNext = y-1;
if (xToFillNext==targetX && yToFillNext==targetY && forbiddenDirection.equals(Direction.RIGHT)) {
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 (yToFillNext>=0 && originValue==matrix[xToFillNext][yToFillNext] && !forbiddenDirection.equals(Direction.LEFT)) {
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.RIGHT );
if (fillingReachedTargetPosition) {
return true;
}
}
return false;
}
}
So each Point object/vertex doesn't have an identifier I can use like:
directedGraph.outDegreeOf(firstPoint);
directedGraph.outDegreeOf(secondPoint);
And I'd like to print the number of outwards edges of each vertex. I found this function in the jgrapht library:
directedGraph.outDegreeOf(Point);
So I tried to go through the vertex set as I would go through a list (in my Draw method which keeps looping in Processing, meaning that while the program is running, the Draw method keeps on being executed). Here is my draw method and the circuitState() method that starts the Flood Fill (I normally use Reactivision to add elements to the matrix: each marker detected appears as a 1 in the matrix, but to test it I created a matrix):
void draw() {
matrix [1][5]= 2;
matrix [1][6]= 2;
matrix [2][5]= 2;
matrix [2][6]= 2;
matrix [3][5]=1;
matrix [2][7]=1;
matrix [4][6]=1;
matrix [3][5]=1;
matrix [4][6]=1;
matrix [4][7]=0;
matrix [3][4]=1;
matrix [3][3]=1;
matrix [3][7]=1;
matrix [3][7]=1;
matrix [3][7]=1;
matrix [4][3]=1;
matrix [5][3]=1;
matrix [5][4]=1;
matrix [5][5]=1;
matrix [5][6]=1;
matrix [4][7]=1;
matrix [6][6]=1;
matrix [7][6]=1;
matrix [3][2]=1;
matrix [3][1]=1;
matrix [3][0]=1;
// Print Matrix
for (int i=0; i<matrix.length; i++) {
for (int j=0; j<matrix[i].length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.print("\n");
}
System.out.print("\n");
// This part detects the fiducial markers
float obj_size = object_size*scale_factor;
float cur_size = cursor_size*scale_factor;
ArrayList<TuioObject> tuioObjectList = tuioClient.getTuioObjectList();
for (int i=0; i<tuioObjectList.size (); i++) {
//System.out.println("#vertex: "+ directedGraph.vertexSet());
TuioObject tobj= tuioObjectList.get(i);
stroke(0);
fill(0, 0, 0);
pushMatrix();
translate(tobj.getScreenX(width), tobj.getScreenY(height));
rotate(tobj.getAngle());
rect(-80, -40, 80, 40);
popMatrix();
fill(255);
x = round(10*tobj.getX ());
y = round(10*tobj.getY ());
iD = tobj.getSymbolID();
// directedGraph.addVertex(new Point(x,y));
int taille = fiducialsList.length;
for (int o = 0; o<taille; o++) {
if (iD == o) {
myType = fiducialsList [o];
}
}
activList.add(new Fiducial (x, y, iD, myType));
matrix [x][y] = 1 ;
circuitState ();
for (int p = 0; p < 10; p++) {
for (int r = 0; r < 10; r++) {
System.out.print(matrix[p][r] + " ");
}
System.out.print("\n");
}
System.out.print("\n");
}
System.out.println("#vertices: "+ directedGraph.vertexSet());
System.out.println("#edges: "+ directedGraph.edgeSet());
//Re-initialize matrix
for (int[] row : matrix)
Arrays.fill(row, 0);
for (int z= 0; z < directedGraph.vertexSet ().size(); z++)
{
directedGraph.outDegreeOf(myPoint);
}
}
void circuitState () {
if ( matrix [2][7]==1 ) {
FloodFill.resolution(args);
if (matrix [3][5]== 3) {
System.out.println("Fermé");
} else {
long estimatedTime = System.nanoTime() - startTime;
timeSpent.add(new Time (time));
System.out.println(" Ouvert " + "took" + estimatedTime);
}
}
}
But it can't find the Point object that I created with this 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+"]");
}
@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;
}
}
Is there a more simple way to do this ? If not, what am I missing to allow the other method to use the Point object ? (what's weird is that I use the Point object is other methods and it works fine so why the Draw method can't access it ?) I use processing which is based on Java
Needed to add:
for(Point myPoint : directedGraph.vertexSet()){
int degree = directedGraph.outDegreeOf(myPoint);
System.out.println("Degree of " myPoint.toString() + ": " + degree);
}
Works fine with this