@Test public void testPopularityWalker2() throws Exception { GraphWalker<VocabWord> walker = new PopularityWalker.Builder<>(graph).setWalkDirection(WalkDirection.FORWARD_ONLY) .setNoEdgeHandling(NoEdgeHandling.CUTOFF_ON_DISCONNECTED).setWalkLength(10) .setPopularityMode(PopularityMode.MINIMUM).setPopularitySpread(3).build(); System.out.println("Connected [3] size: " + graph.getConnectedVertices(3).size()); System.out.println("Connected [4] size: " + graph.getConnectedVertices(4).size()); Sequence<VocabWord> sequence = walker.next(); assertEquals("0", sequence.getElements().get(0).getLabel()); System.out.println("Position at 1: [" + sequence.getElements().get(1).getLabel() + "]"); assertTrue(sequence.getElements().get(1).getLabel().equals("8") || sequence.getElements().get(1).getLabel().equals("3") || sequence.getElements().get(1).getLabel().equals("9") || sequence.getElements().get(1).getLabel().equals("7")); }
@Override public Sequence<T> next() { Sequence<T> sequence = new Sequence<>(); int[] visitedHops = new int[walkLength]; Arrays.fill(visitedHops, -1); int startPosition = position.getAndIncrement(); int lastId = -1; int startPoint = order[startPosition]; startPosition = startPoint; for (int i = 0; i < walkLength; i++) { Vertex<T> vertex = sourceGraph.getVertex(startPosition); int currentPosition = startPosition; sequence.addElement(vertex.getValue()); visitedHops[i] = vertex.vertexID(); int cSpread = 0; if (alpha > 0 && lastId != startPoint && lastId != -1 && alpha > rng.nextDouble()) { startPosition = startPoint; continue; } switch (walkDirection) { case RANDOM: case FORWARD_ONLY: case FORWARD_UNIQUE: case FORWARD_PREFERRED: { int[] connections = ArrayUtils.removeElements( sourceGraph.getConnectedVertexIndices(vertex.vertexID()), visitedHops); PriorityQueue<Node<T>> queue = new PriorityQueue<>(Math.max(10, connections.length), new NodeComparator()); int start = 0; int stop = 0; int cnt = 0; if (connections.length > 0) { for (int connected : connections) { Node<T> tNode = new Node<>(connected, sourceGraph.getConnectedVertices(connected).size()); queue.add(tNode); } cSpread = spread > connections.length ? connections.length : spread; switch (popularityMode) { case MAXIMUM: start = 0; stop = start + cSpread - 1; break; case MINIMUM: start = connections.length - cSpread; stop = connections.length - 1; break; case AVERAGE: int mid = connections.length / 2; start = mid - (cSpread / 2); stop = mid + (cSpread / 2); break; } cnt = 0; List<Node<T>> list = new ArrayList<>(); double[] weights = new double[cSpread]; int fcnt = 0; while (!queue.isEmpty()) { Node<T> node = queue.poll(); if (cnt >= start && cnt <= stop) { list.add(node); weights[fcnt] = node.getWeight(); fcnt++; } connections[cnt] = node.getVertexId(); cnt++; } int con = -1; switch (spectrum) { case PLAIN: { con = RandomUtils.nextInt(start, stop + 1); Vertex<T> nV = sourceGraph.getVertex(connections[con]); startPosition = nV.vertexID(); lastId = vertex.vertexID(); } break; case PROPORTIONAL: { double norm[] = MathArrays.normalizeArray(weights, 1); double prob = rng.nextDouble(); double floor = 0.0; for (int b = 0; b < weights.length; b++) { if (prob >= floor && prob < floor + norm[b]) { startPosition = list.get(b).getVertexId(); lastId = startPosition; break; } else { floor += norm[b]; } } } break; } } else { switch (noEdgeHandling) { case EXCEPTION_ON_DISCONNECTED: throw new NoEdgesException("No more edges at vertex [" + currentPosition + "]"); case CUTOFF_ON_DISCONNECTED: i += walkLength; break; case SELF_LOOP_ON_DISCONNECTED: startPosition = currentPosition; break; case RESTART_ON_DISCONNECTED: startPosition = startPoint; break; default: throw new UnsupportedOperationException( "Unsupported noEdgeHandling: [" + noEdgeHandling + "]"); } } } break; default: throw new UnsupportedOperationException("Unknown WalkDirection: [" + walkDirection + "]"); } } return sequence; }
PopularityWalker extends RandomWalker<T> implements GraphWalker<T> { @Override public Sequence<T> next() { Sequence<T> sequence = new Sequence<>(); int[] visitedHops = new int[walkLength]; Arrays.fill(visitedHops, -1); int startPosition = position.getAndIncrement(); int lastId = -1; int startPoint = order[startPosition]; startPosition = startPoint; for (int i = 0; i < walkLength; i++) { Vertex<T> vertex = sourceGraph.getVertex(startPosition); int currentPosition = startPosition; sequence.addElement(vertex.getValue()); visitedHops[i] = vertex.vertexID(); int cSpread = 0; if (alpha > 0 && lastId != startPoint && lastId != -1 && alpha > rng.nextDouble()) { startPosition = startPoint; continue; } switch (walkDirection) { case RANDOM: case FORWARD_ONLY: case FORWARD_UNIQUE: case FORWARD_PREFERRED: { int[] connections = ArrayUtils.removeElements( sourceGraph.getConnectedVertexIndices(vertex.vertexID()), visitedHops); PriorityQueue<Node<T>> queue = new PriorityQueue<>(Math.max(10, connections.length), new NodeComparator()); int start = 0; int stop = 0; int cnt = 0; if (connections.length > 0) { for (int connected : connections) { Node<T> tNode = new Node<>(connected, sourceGraph.getConnectedVertices(connected).size()); queue.add(tNode); } cSpread = spread > connections.length ? connections.length : spread; switch (popularityMode) { case MAXIMUM: start = 0; stop = start + cSpread - 1; break; case MINIMUM: start = connections.length - cSpread; stop = connections.length - 1; break; case AVERAGE: int mid = connections.length / 2; start = mid - (cSpread / 2); stop = mid + (cSpread / 2); break; } cnt = 0; List<Node<T>> list = new ArrayList<>(); double[] weights = new double[cSpread]; int fcnt = 0; while (!queue.isEmpty()) { Node<T> node = queue.poll(); if (cnt >= start && cnt <= stop) { list.add(node); weights[fcnt] = node.getWeight(); fcnt++; } connections[cnt] = node.getVertexId(); cnt++; } int con = -1; switch (spectrum) { case PLAIN: { con = RandomUtils.nextInt(start, stop + 1); Vertex<T> nV = sourceGraph.getVertex(connections[con]); startPosition = nV.vertexID(); lastId = vertex.vertexID(); } break; case PROPORTIONAL: { double norm[] = MathArrays.normalizeArray(weights, 1); double prob = rng.nextDouble(); double floor = 0.0; for (int b = 0; b < weights.length; b++) { if (prob >= floor && prob < floor + norm[b]) { startPosition = list.get(b).getVertexId(); lastId = startPosition; break; } else { floor += norm[b]; } } } break; } } else { switch (noEdgeHandling) { case EXCEPTION_ON_DISCONNECTED: throw new NoEdgesException("No more edges at vertex [" + currentPosition + "]"); case CUTOFF_ON_DISCONNECTED: i += walkLength; break; case SELF_LOOP_ON_DISCONNECTED: startPosition = currentPosition; break; case RESTART_ON_DISCONNECTED: startPosition = startPoint; break; default: throw new UnsupportedOperationException( "Unsupported noEdgeHandling: [" + noEdgeHandling + "]"); } } } break; default: throw new UnsupportedOperationException("Unknown WalkDirection: [" + walkDirection + "]"); } } return sequence; } }
PopularityWalker extends RandomWalker<T> implements GraphWalker<T> { @Override public Sequence<T> next() { Sequence<T> sequence = new Sequence<>(); int[] visitedHops = new int[walkLength]; Arrays.fill(visitedHops, -1); int startPosition = position.getAndIncrement(); int lastId = -1; int startPoint = order[startPosition]; startPosition = startPoint; for (int i = 0; i < walkLength; i++) { Vertex<T> vertex = sourceGraph.getVertex(startPosition); int currentPosition = startPosition; sequence.addElement(vertex.getValue()); visitedHops[i] = vertex.vertexID(); int cSpread = 0; if (alpha > 0 && lastId != startPoint && lastId != -1 && alpha > rng.nextDouble()) { startPosition = startPoint; continue; } switch (walkDirection) { case RANDOM: case FORWARD_ONLY: case FORWARD_UNIQUE: case FORWARD_PREFERRED: { int[] connections = ArrayUtils.removeElements( sourceGraph.getConnectedVertexIndices(vertex.vertexID()), visitedHops); PriorityQueue<Node<T>> queue = new PriorityQueue<>(Math.max(10, connections.length), new NodeComparator()); int start = 0; int stop = 0; int cnt = 0; if (connections.length > 0) { for (int connected : connections) { Node<T> tNode = new Node<>(connected, sourceGraph.getConnectedVertices(connected).size()); queue.add(tNode); } cSpread = spread > connections.length ? connections.length : spread; switch (popularityMode) { case MAXIMUM: start = 0; stop = start + cSpread - 1; break; case MINIMUM: start = connections.length - cSpread; stop = connections.length - 1; break; case AVERAGE: int mid = connections.length / 2; start = mid - (cSpread / 2); stop = mid + (cSpread / 2); break; } cnt = 0; List<Node<T>> list = new ArrayList<>(); double[] weights = new double[cSpread]; int fcnt = 0; while (!queue.isEmpty()) { Node<T> node = queue.poll(); if (cnt >= start && cnt <= stop) { list.add(node); weights[fcnt] = node.getWeight(); fcnt++; } connections[cnt] = node.getVertexId(); cnt++; } int con = -1; switch (spectrum) { case PLAIN: { con = RandomUtils.nextInt(start, stop + 1); Vertex<T> nV = sourceGraph.getVertex(connections[con]); startPosition = nV.vertexID(); lastId = vertex.vertexID(); } break; case PROPORTIONAL: { double norm[] = MathArrays.normalizeArray(weights, 1); double prob = rng.nextDouble(); double floor = 0.0; for (int b = 0; b < weights.length; b++) { if (prob >= floor && prob < floor + norm[b]) { startPosition = list.get(b).getVertexId(); lastId = startPosition; break; } else { floor += norm[b]; } } } break; } } else { switch (noEdgeHandling) { case EXCEPTION_ON_DISCONNECTED: throw new NoEdgesException("No more edges at vertex [" + currentPosition + "]"); case CUTOFF_ON_DISCONNECTED: i += walkLength; break; case SELF_LOOP_ON_DISCONNECTED: startPosition = currentPosition; break; case RESTART_ON_DISCONNECTED: startPosition = startPoint; break; default: throw new UnsupportedOperationException( "Unsupported noEdgeHandling: [" + noEdgeHandling + "]"); } } } break; default: throw new UnsupportedOperationException("Unknown WalkDirection: [" + walkDirection + "]"); } } return sequence; }  }
PopularityWalker extends RandomWalker<T> implements GraphWalker<T> { @Override public Sequence<T> next() { Sequence<T> sequence = new Sequence<>(); int[] visitedHops = new int[walkLength]; Arrays.fill(visitedHops, -1); int startPosition = position.getAndIncrement(); int lastId = -1; int startPoint = order[startPosition]; startPosition = startPoint; for (int i = 0; i < walkLength; i++) { Vertex<T> vertex = sourceGraph.getVertex(startPosition); int currentPosition = startPosition; sequence.addElement(vertex.getValue()); visitedHops[i] = vertex.vertexID(); int cSpread = 0; if (alpha > 0 && lastId != startPoint && lastId != -1 && alpha > rng.nextDouble()) { startPosition = startPoint; continue; } switch (walkDirection) { case RANDOM: case FORWARD_ONLY: case FORWARD_UNIQUE: case FORWARD_PREFERRED: { int[] connections = ArrayUtils.removeElements( sourceGraph.getConnectedVertexIndices(vertex.vertexID()), visitedHops); PriorityQueue<Node<T>> queue = new PriorityQueue<>(Math.max(10, connections.length), new NodeComparator()); int start = 0; int stop = 0; int cnt = 0; if (connections.length > 0) { for (int connected : connections) { Node<T> tNode = new Node<>(connected, sourceGraph.getConnectedVertices(connected).size()); queue.add(tNode); } cSpread = spread > connections.length ? connections.length : spread; switch (popularityMode) { case MAXIMUM: start = 0; stop = start + cSpread - 1; break; case MINIMUM: start = connections.length - cSpread; stop = connections.length - 1; break; case AVERAGE: int mid = connections.length / 2; start = mid - (cSpread / 2); stop = mid + (cSpread / 2); break; } cnt = 0; List<Node<T>> list = new ArrayList<>(); double[] weights = new double[cSpread]; int fcnt = 0; while (!queue.isEmpty()) { Node<T> node = queue.poll(); if (cnt >= start && cnt <= stop) { list.add(node); weights[fcnt] = node.getWeight(); fcnt++; } connections[cnt] = node.getVertexId(); cnt++; } int con = -1; switch (spectrum) { case PLAIN: { con = RandomUtils.nextInt(start, stop + 1); Vertex<T> nV = sourceGraph.getVertex(connections[con]); startPosition = nV.vertexID(); lastId = vertex.vertexID(); } break; case PROPORTIONAL: { double norm[] = MathArrays.normalizeArray(weights, 1); double prob = rng.nextDouble(); double floor = 0.0; for (int b = 0; b < weights.length; b++) { if (prob >= floor && prob < floor + norm[b]) { startPosition = list.get(b).getVertexId(); lastId = startPosition; break; } else { floor += norm[b]; } } } break; } } else { switch (noEdgeHandling) { case EXCEPTION_ON_DISCONNECTED: throw new NoEdgesException("No more edges at vertex [" + currentPosition + "]"); case CUTOFF_ON_DISCONNECTED: i += walkLength; break; case SELF_LOOP_ON_DISCONNECTED: startPosition = currentPosition; break; case RESTART_ON_DISCONNECTED: startPosition = startPoint; break; default: throw new UnsupportedOperationException( "Unsupported noEdgeHandling: [" + noEdgeHandling + "]"); } } } break; default: throw new UnsupportedOperationException("Unknown WalkDirection: [" + walkDirection + "]"); } } return sequence; }  @Override boolean hasNext(); @Override boolean isLabelEnabled(); @Override Sequence<T> next(); @Override void reset(boolean shuffle); }
PopularityWalker extends RandomWalker<T> implements GraphWalker<T> { @Override public Sequence<T> next() { Sequence<T> sequence = new Sequence<>(); int[] visitedHops = new int[walkLength]; Arrays.fill(visitedHops, -1); int startPosition = position.getAndIncrement(); int lastId = -1; int startPoint = order[startPosition]; startPosition = startPoint; for (int i = 0; i < walkLength; i++) { Vertex<T> vertex = sourceGraph.getVertex(startPosition); int currentPosition = startPosition; sequence.addElement(vertex.getValue()); visitedHops[i] = vertex.vertexID(); int cSpread = 0; if (alpha > 0 && lastId != startPoint && lastId != -1 && alpha > rng.nextDouble()) { startPosition = startPoint; continue; } switch (walkDirection) { case RANDOM: case FORWARD_ONLY: case FORWARD_UNIQUE: case FORWARD_PREFERRED: { int[] connections = ArrayUtils.removeElements( sourceGraph.getConnectedVertexIndices(vertex.vertexID()), visitedHops); PriorityQueue<Node<T>> queue = new PriorityQueue<>(Math.max(10, connections.length), new NodeComparator()); int start = 0; int stop = 0; int cnt = 0; if (connections.length > 0) { for (int connected : connections) { Node<T> tNode = new Node<>(connected, sourceGraph.getConnectedVertices(connected).size()); queue.add(tNode); } cSpread = spread > connections.length ? connections.length : spread; switch (popularityMode) { case MAXIMUM: start = 0; stop = start + cSpread - 1; break; case MINIMUM: start = connections.length - cSpread; stop = connections.length - 1; break; case AVERAGE: int mid = connections.length / 2; start = mid - (cSpread / 2); stop = mid + (cSpread / 2); break; } cnt = 0; List<Node<T>> list = new ArrayList<>(); double[] weights = new double[cSpread]; int fcnt = 0; while (!queue.isEmpty()) { Node<T> node = queue.poll(); if (cnt >= start && cnt <= stop) { list.add(node); weights[fcnt] = node.getWeight(); fcnt++; } connections[cnt] = node.getVertexId(); cnt++; } int con = -1; switch (spectrum) { case PLAIN: { con = RandomUtils.nextInt(start, stop + 1); Vertex<T> nV = sourceGraph.getVertex(connections[con]); startPosition = nV.vertexID(); lastId = vertex.vertexID(); } break; case PROPORTIONAL: { double norm[] = MathArrays.normalizeArray(weights, 1); double prob = rng.nextDouble(); double floor = 0.0; for (int b = 0; b < weights.length; b++) { if (prob >= floor && prob < floor + norm[b]) { startPosition = list.get(b).getVertexId(); lastId = startPosition; break; } else { floor += norm[b]; } } } break; } } else { switch (noEdgeHandling) { case EXCEPTION_ON_DISCONNECTED: throw new NoEdgesException("No more edges at vertex [" + currentPosition + "]"); case CUTOFF_ON_DISCONNECTED: i += walkLength; break; case SELF_LOOP_ON_DISCONNECTED: startPosition = currentPosition; break; case RESTART_ON_DISCONNECTED: startPosition = startPoint; break; default: throw new UnsupportedOperationException( "Unsupported noEdgeHandling: [" + noEdgeHandling + "]"); } } } break; default: throw new UnsupportedOperationException("Unknown WalkDirection: [" + walkDirection + "]"); } } return sequence; }  @Override boolean hasNext(); @Override boolean isLabelEnabled(); @Override Sequence<T> next(); @Override void reset(boolean shuffle);  }