Page MenuHomeSoftware Heritage
Files F7066583

D1854.id6236.diff
No OneTemporary
Actions

D1854.id6236.diff
View Options

diff --git a/java/server/src/main/java/org/softwareheritage/graph/algo/Traversal.java b/java/server/src/main/java/org/softwareheritage/graph/algo/Traversal.java
--- a/java/server/src/main/java/org/softwareheritage/graph/algo/Traversal.java
+++ b/java/server/src/main/java/org/softwareheritage/graph/algo/Traversal.java
@@ -2,12 +2,13 @@
import java.util.ArrayList;
import java.util.Collections;
+import java.util.HashMap;
import java.util.LinkedList;
+import java.util.Map;
import java.util.Queue;
import java.util.Stack;
import it.unimi.dsi.bits.LongArrayBitVector;
-import it.unimi.dsi.fastutil.longs.LongBigArrays;
import org.softwareheritage.graph.AllowedEdges;
import org.softwareheritage.graph.Endpoint;
@@ -38,8 +39,8 @@
/** Bit array storing if we have visited a node */
LongArrayBitVector visited;
- /** LongBigArray storing parent node id for each nodes during a traversal */
- long[][] nodeParent;
+ /** Hash map storing parent node id for each nodes during a traversal */
+ Map<Long, Long> parentNode;
/** Number of edges accessed during traversal */
long nbEdgesAccessed;
@@ -62,7 +63,7 @@
long nbNodes = graph.getNbNodes();
this.visited = LongArrayBitVector.ofLength(nbNodes);
- this.nodeParent = LongBigArrays.newBigArray(nbNodes);
+ this.parentNode = new HashMap<>();
this.nbEdgesAccessed = 0;
}
@@ -252,7 +253,7 @@
if (!visited.getBoolean(neighborNodeId)) {
stack.push(neighborNodeId);
visited.set(neighborNodeId);
- LongBigArrays.set(nodeParent, neighborNodeId, currentNodeId);
+ parentNode.put(neighborNodeId, currentNodeId);
}
}
}
@@ -286,7 +287,7 @@
if (!visited.getBoolean(neighborNodeId)) {
queue.add(neighborNodeId);
visited.set(neighborNodeId);
- LongBigArrays.set(nodeParent, neighborNodeId, currentNodeId);
+ parentNode.put(neighborNodeId, currentNodeId);
}
}
}
@@ -325,7 +326,7 @@
long currentNodeId = dstNodeId;
while (currentNodeId != srcNodeId) {
path.add(currentNodeId);
- currentNodeId = LongBigArrays.get(nodeParent, currentNodeId);
+ currentNodeId = parentNode.get(currentNodeId);
}
path.add(srcNodeId);
Collections.reverse(path);

File Metadata

Mime Type
text/plain
Expires
Nov 5 2024, 3:27 PM (12 w, 4 d ago)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
3218756

Event Timeline

About · Developer information · Legal