Differential D1822 Diff 6149 java/server/src/main/java/org/softwareheritage/graph/algo/Traversal.java
Changeset View
Changeset View
Standalone View
Standalone View
java/server/src/main/java/org/softwareheritage/graph/algo/Traversal.java
package org.softwareheritage.graph.algo; | package org.softwareheritage.graph.algo; | ||||
import java.util.ArrayList; | import java.util.ArrayList; | ||||
import java.util.Collections; | import java.util.Collections; | ||||
import java.util.LinkedList; | import java.util.LinkedList; | ||||
import java.util.Queue; | import java.util.Queue; | ||||
import java.util.Stack; | import java.util.Stack; | ||||
import it.unimi.dsi.bits.LongArrayBitVector; | import it.unimi.dsi.bits.LongArrayBitVector; | ||||
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.Endpoint; | |||||
import org.softwareheritage.graph.Graph; | import org.softwareheritage.graph.Graph; | ||||
import org.softwareheritage.graph.Neighbors; | import org.softwareheritage.graph.Neighbors; | ||||
import org.softwareheritage.graph.Node; | import org.softwareheritage.graph.Node; | ||||
/** | /** | ||||
* Traversal algorithms on the compressed graph. | * Traversal algorithms on the compressed graph. | ||||
* <p> | |||||
* Internal implementation of the traversal API endpoints. These methods only input/output internal | |||||
* long ids, which are converted in the {@link Endpoint} higher-level class to Software Heritage | |||||
* PID. | |||||
* | * | ||||
* @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.Endpoint | |||||
*/ | */ | ||||
public class Traversal { | public class Traversal { | ||||
/** Graph used in the traversal */ | /** Graph used in the traversal */ | ||||
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 */ | ||||
AllowedEdges edges; | AllowedEdges edges; | ||||
/** | /** Bit array storing if we have visited a node */ | ||||
* Bit array storing if we have visited a node | |||||
* @see it.unimi.dsi.bits.LongArrayBitVector | |||||
*/ | |||||
LongArrayBitVector visited; | LongArrayBitVector visited; | ||||
/** | /** LongBigArray storing parent node id for each nodes during a traversal */ | ||||
* Array storing parent node id for each nodes during a traversal | |||||
* @see it.unimi.dsi.fastutil.longs.LongBigArrays | |||||
*/ | |||||
long[][] nodeParent; | long[][] nodeParent; | ||||
/** | /** | ||||
* Constructor. | * Constructor. | ||||
* | * | ||||
* @param graph graph used in the traversal | * @param graph graph used in the traversal | ||||
* @param direction a string (either "forward" or "backward") specifying edge orientation | * @param direction a string (either "forward" or "backward") specifying edge orientation | ||||
* @param edgesFmt a formatted string describing allowed edges (TODO: link API doc) | * @param edgesFmt a formatted string describing <a | ||||
* href="https://docs.softwareheritage.org/devel/swh-graph/api.html#terminology">allowed edges</a> | |||||
*/ | */ | ||||
public Traversal(Graph graph, String direction, String edgesFmt) { | public Traversal(Graph graph, String direction, String edgesFmt) { | ||||
if (!direction.matches("forward|backward")) { | if (!direction.matches("forward|backward")) { | ||||
throw new IllegalArgumentException("Unknown traversal direction: " + direction); | throw new IllegalArgumentException("Unknown traversal direction: " + direction); | ||||
} | } | ||||
this.graph = graph; | this.graph = graph; | ||||
this.useTransposed = (direction.equals("backward")); | this.useTransposed = (direction.equals("backward")); | ||||
▲ Show 20 Lines • Show All 252 Lines • Show Last 20 Lines |