0

次を使用して作成された有向グラフがあります。

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 しかありません。フラッド フィル アルゴリズムは、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 つの連続する点の間) を作成します。行列の点 (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 メソッドでは、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);
    }
  }
}

しかし、このクラスで作成した 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 ベースの処理を使用しています。

4

2 に答える 2

2

あなたの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);
于 2015-07-28T17:32:14.280 に答える
-1

追加する必要があります:

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

これでうまく動作します

于 2015-07-29T21:19:31.133 に答える