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