检索有向图的每个顶点的 "out degree" (jgrapht)

Question

我有一个使用以下方法创建的二合字母：

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

顶点和边是使用在矩阵中实现的 Flood Fill 算法创建的。在我使用的矩阵中，只有 0、1 和 2。 Flood 填充算法检测是否存在由 1s 和 2s 形成的循环，并且当它通过 1s 时，它将它们变成 3s。示例：

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

将成为：

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

随着算法遍历矩阵，它会创建顶点（它遇到的每个 1）和边（在两个连续点之间）。这是算法，它从矩阵中的点 (2,7) 开始：

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

所以每个点 object/vertex 没有我可以使用的标识符：

directedGraph.outDegreeOf(firstPoint);
directedGraph.outDegreeOf(secondPoint);

我想打印每个顶点向外的边数。我在 jgrapht 库中找到了这个函数：

directedGraph.outDegreeOf(Point);

所以我尝试像遍历列表一样遍历顶点集（在我的 Draw 方法中，它在 Processing 中不断循环，这意味着当程序运行时，Draw 方法一直在执行）。这是我的 draw 方法和启动 Flood Fill 的 circuitState() 方法（我通常使用 Reactivision 向矩阵添加元素：检测到的每个标记在矩阵中显示为 1，但为了测试它我创建了一个矩阵）：

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

但是它找不到我用这个 class 创建的 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+"]");
  }

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

有更简单的方法吗？如果不是，我缺少什么来允许其他方法使用 Point 对象？（奇怪的是我使用 Point 对象是其他方法并且它工作正常所以为什么 Draw 方法无法访问它？）我使用基于 Java

的处理

Answer 1

看看你的 for 循环：

for (int z= 0; z < directedGraph.vertexSet().size(); z++)
{
    directedGraph.outDegreeOf(Point);
}

这个语法没有任何意义：

directedGraph.outDegreeOf(Point);

Point 是一个 class。您需要将 class 的实例传递给 outDegreeOf() 函数。它可能看起来像这样：

Point p = new Point(1, 6);
int degree = directedGraph.outDegreeOf(p);

Answer 2

需要添加：

for(Point myPoint : directedGraph.vertexSet()){
   int degree = directedGraph.outDegreeOf(myPoint);
   System.out.println("Degree of " myPoint.toString() + ": " + degree);
}

用这个很好

检索有向图的每个顶点的 "out degree" (jgrapht)

Retrieve the "out degree" of every vertex of a digraph (jgrapht)

java

processing

jgrapht

digraphs