Changeset View
Changeset View
Standalone View
Standalone View
java/server/src/main/java/org/softwareheritage/graph/Neighbors.java
package org.softwareheritage.graph; | package org.softwareheritage.graph; | ||||
import java.util.Iterator; | import java.util.Iterator; | ||||
import it.unimi.dsi.fastutil.longs.LongBigArrays; | import it.unimi.dsi.fastutil.longs.LongBigArrays; | ||||
import org.softwareheritage.graph.AllowedEdges; | import org.softwareheritage.graph.AllowedEdges; | ||||
import org.softwareheritage.graph.Graph; | import org.softwareheritage.graph.Graph; | ||||
/** | /** | ||||
* Iterator class to go over a node neighbors in the graph. | * Iterator class to go over a node neighbors in the graph. | ||||
* <p> | |||||
* Wrapper iterator class to easily deal with {@link AllowedEdges} during traversals. | |||||
* | * | ||||
* @author Thibault Allançon | * @author Thibault Allançon | ||||
* @version 0.0.1 | * @version 0.0.1 | ||||
* @since 0.0.1 | * @since 0.0.1 | ||||
* @see org.softwareheritage.graph.AllowedEdges | |||||
*/ | */ | ||||
public class Neighbors implements Iterable<Long> { | public class Neighbors implements Iterable<Long> { | ||||
/** Graph used to explore neighbors */ | /** Graph used to explore neighbors */ | ||||
Graph graph; | Graph graph; | ||||
/** Boolean to specify the use of the transposed graph */ | /** Boolean to specify the use of the transposed graph */ | ||||
boolean useTransposed; | boolean useTransposed; | ||||
/** Graph edge restriction */ | /** Graph edge restriction */ | ||||
Show All 27 Lines | public class Neighbors implements Iterable<Long> { | ||||
* @author Thibault Allançon | * @author Thibault Allançon | ||||
* @version 0.0.1 | * @version 0.0.1 | ||||
* @since 0.0.1 | * @since 0.0.1 | ||||
*/ | */ | ||||
public class NeighborsIterator implements Iterator<Long> { | public class NeighborsIterator implements Iterator<Long> { | ||||
long nextNeighborIdx; | long nextNeighborIdx; | ||||
long nbNeighbors; | long nbNeighbors; | ||||
// LongBigArrays to support 64-bit indexing. | |||||
long[][] neighbors; | long[][] neighbors; | ||||
public NeighborsIterator() { | public NeighborsIterator() { | ||||
this.nextNeighborIdx = -1; | this.nextNeighborIdx = -1; | ||||
this.nbNeighbors = graph.degree(srcNodeId, useTransposed); | this.nbNeighbors = graph.degree(srcNodeId, useTransposed); | ||||
this.neighbors = graph.neighbors(srcNodeId, useTransposed); | this.neighbors = graph.neighbors(srcNodeId, useTransposed); | ||||
} | } | ||||
public boolean hasNext() { | public boolean hasNext() { | ||||
// No edge restriction case: bypass type checks and skip to next neighbor | // Case 1: no edge restriction, bypass type checks and skip to next neighbor | ||||
if (edges.restrictedTo == null) { | if (edges.restrictedTo == null) { | ||||
if (nextNeighborIdx + 1 < nbNeighbors) { | if (nextNeighborIdx + 1 < nbNeighbors) { | ||||
nextNeighborIdx++; | nextNeighborIdx++; | ||||
return true; | return true; | ||||
} else { | } else { | ||||
return false; | return false; | ||||
} | } | ||||
} | } | ||||
// Edge restriction case: look ahead for next neighbor | // Case 2: edge restriction, look ahead for next neighbor | ||||
for (long lookAheadIdx = nextNeighborIdx + 1; lookAheadIdx < nbNeighbors; lookAheadIdx++) { | for (long lookAheadIdx = nextNeighborIdx + 1; lookAheadIdx < nbNeighbors; lookAheadIdx++) { | ||||
long nextNodeId = LongBigArrays.get(neighbors, lookAheadIdx); | long nextNodeId = LongBigArrays.get(neighbors, lookAheadIdx); | ||||
if (edges.isAllowed(srcNodeId, nextNodeId)) { | if (edges.isAllowed(srcNodeId, nextNodeId)) { | ||||
nextNeighborIdx = lookAheadIdx; | nextNeighborIdx = lookAheadIdx; | ||||
return true; | return true; | ||||
} | } | ||||
} | } | ||||
return false; | return false; | ||||
} | } | ||||
public Long next() { | public Long next() { | ||||
long nextNodeId = LongBigArrays.get(neighbors, nextNeighborIdx); | long nextNodeId = LongBigArrays.get(neighbors, nextNeighborIdx); | ||||
return nextNodeId; | return nextNodeId; | ||||
} | } | ||||
} | } | ||||
} | } |