Java 类it.unimi.dsi.fastutil.ints.IntArrayFIFOQueue 实例源码

private void bfs(Graph graph, int s) {
  IntArrayFIFOQueue queue = new IntArrayFIFOQueue();
  queue.enqueue(s);
  visited[s] = true;

  while (!queue.isEmpty()) {
    int v = queue.dequeueInt();

    IntArrayList adj = graph.adj(v);
    for (int i = 0; i < adj.size(); i++) {
      int w = adj.getInt(i);
      if (!visited[w]) {
        visited[w] = true;
        queue.enqueue(w);
        edgeTo[w] = v;
      }
    }
  }
}

private int[] distancesFrom( final ImmutableGraph graph, final int from ) {
    final IntArrayFIFOQueue queue = new IntArrayFIFOQueue();
    final int n = graph.numNodes();
    final int[] dist = new int[ n ];
    IntArrays.fill( dist, Integer.MAX_VALUE ); // Initially, all distances are infinity.

    queue.enqueue( from );
    dist[ from ] = 0;

    LazyIntIterator successors;

    while( ! queue.isEmpty() ) {
        int curr = queue.dequeueInt();
        successors = graph.successors( curr );
        int d = graph.outdegree( curr );
        while( d-- != 0 ) {
            int succ = successors.nextInt();
            if ( dist[ succ ] == Integer.MAX_VALUE ) {
                dist[ succ ] = dist[ curr ] + 1;
                queue.enqueue( succ );
            }
        }
    }

    return dist;        
}

@Override
public void run() {
    final IntArrayFIFOQueue queue = new IntArrayFIFOQueue();

    IntArrays.fill( dists, Integer.MAX_VALUE ); // Initially, all distances are infinity.

    int curr, succ;
    queue.enqueue( start );
    dists[ start ] = 0;

    LazyIntIterator successors;

    while( ! queue.isEmpty() ) {
        curr = queue.dequeueInt();
        successors = graph.successors( curr );
        int d = graph.outdegree( curr );
        while( d-- != 0 ) {
            succ = successors.nextInt();
            if ( dists[ succ ] == Integer.MAX_VALUE  ) {
                dists[ succ ] = dists[ curr ] + 1;
                queue.enqueue( succ );
            }
        }
    }

    startNewThreadAfter(this);
}

private IterationThread() {
    this.distance = new int[ graph.numNodes() ];
    this.queue = new IntArrayFIFOQueue();
}

public Void call() {
    // We cache frequently used fields.
    final int[] distance = this.distance;
    final IntArrayFIFOQueue queue = this.queue;
    final ImmutableGraph graph = GeometricCentralities.this.graph.copy();

    for( ;; ) {
        final int curr = nextNode.getAndIncrement();
        if ( GeometricCentralities.this.stop || curr >= graph.numNodes() ) return null;
        queue.clear();
        queue.enqueue( curr );
        IntArrays.fill( distance, -1 );
        distance[ curr ] = 0;
        int reachable = 0;

        while( ! queue.isEmpty() ) {
            final int node = queue.dequeueInt();
            reachable++;
            final int d = distance[ node ] + 1;
            final double hd = 1. / d;
            final LazyIntIterator successors = graph.successors( node );
            for( int s; ( s = successors.nextInt() ) != -1; ) {
                if ( distance[ s ] == -1 ) {
                    queue.enqueue( s );
                    distance[ s ] = d;
                    closeness[ curr ] += d;
                    harmonic[ curr ] += hd;
                }
            }
        }

        if ( GeometricCentralities.this.pl != null ) 
            synchronized ( GeometricCentralities.this.pl ) {
                GeometricCentralities.this.pl.update();
            }

        if ( closeness[ curr ] == 0 ) lin[ curr ] = 1; // Terminal node
        else {
            closeness[ curr ] = 1 / closeness[ curr ];
            lin[ curr ] = (double)reachable * reachable * closeness[ curr ];
        }

        GeometricCentralities.this.reachable[ curr ] = reachable;
    }
}