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

Question

我使用以下方法创建了一个有向图:

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

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

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

因此每个 Point 对象/顶点没有我可以使用的标识符，例如:

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

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

directedGraph.outDegreeOf(Point);

因此，我尝试像遍历列表一样遍历顶点集(在我的 Draw 方法中，该方法在处理中不断循环，这意味着在程序运行时，Draw 方法不断执行)。这是我的绘制方法和启动洪水填充的 CircuitState() 方法(我通常使用 Reivision 将元素添加到矩阵中:检测到的每个标记在矩阵中显示为 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);
    }
  }
}

但它找不到我用此类创建的 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 是一个类。您需要将该类的实例传递到outDegreeOf()函数中。它可能看起来像这样:

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