This is an automated email from the ASF dual-hosted git repository.
jin pushed a commit to branch master
in repository
https://gitbox.apache.org/repos/asf/incubator-hugegraph-computer.git
The following commit(s) were added to refs/heads/master by this push:
new 192ef3b4 feat(algorithm): support single source shortest path
algorithm (#285)
192ef3b4 is described below
commit 192ef3b4b99f21fb97578542b94be4bddf2082be
Author: diaohancai <[email protected]>
AuthorDate: Tue Mar 12 14:49:36 2024 +0800
feat(algorithm): support single source shortest path algorithm (#285)
Add single source shortest path algorithm.
There are 3 types of `target vertex`：
1. single target:
```yaml
single_source_shortest_path.source_id="\"A\""
single_source_shortest_path.target_id="\"E\""
```
2. multiple target:
```yaml
single_source_shortest_path.source_id="\"A\""
single_source_shortest_path.target_id="\"E\", \"C\""
```
3. all target:
```yaml
single_source_shortest_path.source_id="\"A\""
single_source_shortest_path.target_id=*
```
---------
Co-authored-by: imbajin <[email protected]>
---
.../algorithm/path/shortest/QuantityType.java | 25 ++
.../path/shortest/SingleSourceShortestPath.java | 281 +++++++++++++++++++++
.../shortest/SingleSourceShortestPathCombiner.java | 30 +++
.../shortest/SingleSourceShortestPathMaster.java | 47 ++++
.../shortest/SingleSourceShortestPathOutput.java | 48 ++++
.../shortest/SingleSourceShortestPathParams.java | 48 ++++
.../shortest/SingleSourceShortestPathValue.java | 103 ++++++++
.../core/combiner/IdListMergeCombiner.java | 39 +++
.../computer/core/combiner/IdSetMergeCombiner.java | 30 +++
.../computer/core/graph/id/IdFactory.java | 17 ++
.../hugegraph/computer/core/graph/value/IdSet.java | 4 +
.../computer/core/graph/value/ListValue.java | 10 +-
.../hugegraph/computer/core/util/IdUtil.java | 53 ++++
.../hugegraph/computer/core/util/JsonUtilExt.java | 46 ++++
.../computer/algorithm/AlgorithmTestSuite.java | 4 +-
.../shortest/SingleSourceShortestPathTest.java | 148 +++++++++++
.../computer/core/graph/id/IdFactoryTest.java | 8 +
.../computer/core/graph/value/ListValueTest.java | 12 +
.../hugegraph/computer/core/util/IdUtilTest.java | 56 ++++
19 files changed, 1004 insertions(+), 5 deletions(-)
diff --git
a/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/QuantityType.java
b/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/QuantityType.java
new file mode 100644
index 00000000..7cf722e7
--- /dev/null
+++
b/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/QuantityType.java
@@ -0,0 +1,25 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hugegraph.computer.algorithm.path.shortest;
+
+public enum QuantityType {
+
+ SINGLE,
+ MULTIPLE,
+ ALL
+}
diff --git
a/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPath.java
b/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPath.java
new file mode 100644
index 00000000..c9b49cfd
--- /dev/null
+++
b/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPath.java
@@ -0,0 +1,281 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hugegraph.computer.algorithm.path.shortest;
+
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.stream.Collectors;
+
+import org.apache.commons.lang3.StringUtils;
+import org.apache.hugegraph.computer.core.common.exception.ComputerException;
+import org.apache.hugegraph.computer.core.config.Config;
+import org.apache.hugegraph.computer.core.graph.edge.Edge;
+import org.apache.hugegraph.computer.core.graph.id.Id;
+import org.apache.hugegraph.computer.core.graph.value.DoubleValue;
+import org.apache.hugegraph.computer.core.graph.value.IdSet;
+import org.apache.hugegraph.computer.core.graph.value.Value;
+import org.apache.hugegraph.computer.core.graph.vertex.Vertex;
+import org.apache.hugegraph.computer.core.util.IdUtil;
+import org.apache.hugegraph.computer.core.worker.Computation;
+import org.apache.hugegraph.computer.core.worker.ComputationContext;
+import org.apache.hugegraph.computer.core.worker.WorkerContext;
+import org.apache.hugegraph.util.Log;
+import org.slf4j.Logger;
+
+public class SingleSourceShortestPath implements
Computation<SingleSourceShortestPathValue> {
+
+ private static final Logger LOG =
Log.logger(SingleSourceShortestPath.class);
+
+ public static final String OPTION_SOURCE_ID =
"single_source_shortest_path.source_id";
+ public static final String OPTION_TARGET_ID =
"single_source_shortest_path.target_id";
+ public static final String OPTION_WEIGHT_PROPERTY =
+ "single_source_shortest_path.weight_property";
+ public static final String OPTION_DEFAULT_WEIGHT =
+ "single_source_shortest_path.default_weight";
+
+ /**
+ * source vertex id.
+ */
+ private Id sourceId;
+
+ /**
+ * target vertex id.
+ * 1. single target: A
+ * 2. multiple target: A, B, C
+ * 3. all: *
+ */
+ private IdSet targetIdSet; // empty when targetId is all
+ /**
+ * target quantity type
+ */
+ private QuantityType targetQuantityType;
+
+ /**
+ * weight property.
+ * weight value must be a positive number.
+ */
+ private String weightProperty;
+
+ /**
+ * default weight.
+ * default 1
+ */
+ private Double defaultWeight;
+
+ //****************** global data ******************//
+ /**
+ * reached targets
+ */
+ private IdSet reachedTargets; // empty when targetId is all
+
+ @Override
+ public String category() {
+ return "path";
+ }
+
+ @Override
+ public String name() {
+ return "single_source_shortest_path";
+ }
+
+ @Override
+ public void init(Config config) {
+ String sourceIdStr = config.getString(OPTION_SOURCE_ID, "");
+ if (StringUtils.isBlank(sourceIdStr)) {
+ throw new ComputerException("The param '%s' must not be blank",
OPTION_SOURCE_ID);
+ }
+ this.sourceId = IdUtil.parseId(sourceIdStr);
+
+ String targetIdStr = config.getString(OPTION_TARGET_ID, "");
+ if (StringUtils.isBlank(targetIdStr)) {
+ throw new ComputerException("The param '%s' must not be blank",
OPTION_TARGET_ID);
+ }
+ // remove spaces
+ targetIdStr = Arrays.stream(targetIdStr.split(","))
+ .map(e -> e.trim())
+ .collect(Collectors.joining(","));
+ this.targetQuantityType = this.getQuantityType(targetIdStr);
+ if (this.targetQuantityType != QuantityType.ALL) {
+ this.targetIdSet = new IdSet();
+ for (String targetId : targetIdStr.split(",")) {
+ targetIdSet.add(IdUtil.parseId(targetId));
+ }
+ }
+
+ this.weightProperty = config.getString(OPTION_WEIGHT_PROPERTY, "");
+
+ this.defaultWeight = config.getDouble(OPTION_DEFAULT_WEIGHT, 1);
+ if (this.defaultWeight <= 0) {
+ throw new ComputerException("The param '%s' must be greater than
0, " +
+ "actual got '%s'",
+ OPTION_DEFAULT_WEIGHT,
this.defaultWeight);
+ }
+ }
+
+ @Override
+ public void compute0(ComputationContext context, Vertex vertex) {
+ SingleSourceShortestPathValue value = new
SingleSourceShortestPathValue();
+ value.unreachable();
+ vertex.value(value);
+
+ // start from source vertex
+ if (!this.sourceId.equals(vertex.id())) {
+ vertex.inactivate();
+ return;
+ }
+ value.zeroDistance(); // source vertex
+
+ // single target && source == target
+ if (this.targetQuantityType == QuantityType.SINGLE &&
+ this.targetIdSet.contains(this.sourceId)) {
+ LOG.debug("source vertex equals target vertex: {}", this.sourceId);
+ vertex.inactivate();
+ return;
+ }
+
+ if (vertex.numEdges() <= 0) {
+ // isolated vertex
+ LOG.debug("The source vertex is isolated: {}", this.sourceId);
+ vertex.inactivate();
+ return;
+ }
+
+ vertex.edges().forEach(edge -> {
+ SingleSourceShortestPathValue message = new
SingleSourceShortestPathValue();
+ message.addToPath(vertex, this.getEdgeWeight(edge));
+
+ context.sendMessage(edge.targetId(), message);
+ });
+
+ vertex.inactivate();
+ }
+
+ @Override
+ public void compute(ComputationContext context, Vertex vertex,
+ Iterator<SingleSourceShortestPathValue> messages) {
+ if (this.isTarget(vertex) &&
!this.reachedTargets.contains(vertex.id())) {
+ // reached targets
+ this.reachedTargets.add(vertex.id());
+ }
+
+ while (messages.hasNext()) {
+ SingleSourceShortestPathValue message = messages.next();
+ SingleSourceShortestPathValue value = vertex.value();
+
+ if (message.totalWeight() < value.totalWeight()) {
+ // find a shorter path
+ value.shorterPath(vertex, message.path(),
message.totalWeight());
+ } else {
+ continue;
+ }
+
+ // target vertex finds all targets reached or nowhere to go
+ if ((this.isTarget(vertex) && this.isAllTargetsReached(vertex)) ||
+ vertex.numEdges() <= 0) {
+ continue;
+ }
+
+ vertex.edges().forEach(edge -> {
+ SingleSourceShortestPathValue forwardMessage = new
SingleSourceShortestPathValue();
+ forwardMessage.addToPath(value.path(),
+ value.totalWeight() +
this.getEdgeWeight(edge));
+
+ context.sendMessage(edge.targetId(), forwardMessage);
+ });
+ }
+
+ vertex.inactivate();
+ }
+
+ @Override
+ public void beforeSuperstep(WorkerContext context) {
+ this.reachedTargets = context.aggregatedValue(
+
SingleSourceShortestPathMaster.SINGLE_SOURCE_SHORTEST_PATH_REACHED_TARGETS);
+ }
+
+ @Override
+ public void afterSuperstep(WorkerContext context) {
+ context.aggregateValue(
+
SingleSourceShortestPathMaster.SINGLE_SOURCE_SHORTEST_PATH_REACHED_TARGETS,
+ this.reachedTargets);
+ }
+
+ /**
+ * get quantityType by targetId
+ */
+ private QuantityType getQuantityType(String targetIdStr) {
+ if (targetIdStr.equals("*")) {
+ return QuantityType.ALL;
+ } else if (targetIdStr.contains(",")) {
+ return QuantityType.MULTIPLE;
+ } else {
+ return QuantityType.SINGLE;
+ }
+ }
+
+ /**
+ * get the weight of an edge by its weight property
+ */
+ private double getEdgeWeight(Edge edge) {
+ double weight = this.defaultWeight;
+
+ Value property = edge.property(this.weightProperty);
+ if (property != null) {
+ if (!property.isNumber()) {
+ throw new ComputerException("The value of %s must be a numeric
value, " +
+ "actual got '%s'",
+ this.weightProperty,
property.string());
+ }
+
+ weight = ((DoubleValue) property).doubleValue();
+ if (weight <= 0) {
+ throw new ComputerException("The value of %s must be greater
than 0, " +
+ "actual got '%s'",
+ this.weightProperty,
property.string());
+ }
+ }
+ return weight;
+ }
+
+ /**
+ * determine whether vertex is one of the target
+ */
+ private boolean isTarget(Vertex vertex) {
+ return this.targetQuantityType != QuantityType.ALL &&
+ this.targetIdSet.contains(vertex.id());
+ }
+
+ /**
+ * determine whether all targets reached
+ */
+ private boolean isAllTargetsReached(Vertex vertex) {
+ if (this.targetQuantityType == QuantityType.ALL) {
+ return false;
+ }
+
+ if (this.targetIdSet.size() == this.reachedTargets.size()) {
+ for (Id targetId : this.targetIdSet.value()) {
+ if (!this.reachedTargets.contains(targetId)) {
+ return false;
+ }
+ }
+ return true;
+ }
+ return false;
+ }
+}
diff --git
a/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPathCombiner.java
b/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPathCombiner.java
new file mode 100644
index 00000000..78ea2cd2
--- /dev/null
+++
b/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPathCombiner.java
@@ -0,0 +1,30 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hugegraph.computer.algorithm.path.shortest;
+
+import org.apache.hugegraph.computer.core.combiner.Combiner;
+
+public class SingleSourceShortestPathCombiner implements
Combiner<SingleSourceShortestPathValue> {
+
+ @Override
+ public void combine(SingleSourceShortestPathValue v1,
SingleSourceShortestPathValue v2,
+ SingleSourceShortestPathValue result) {
+ SingleSourceShortestPathValue shorter = v2.totalWeight() <
v1.totalWeight() ? v2 : v1;
+ result.copy(shorter);
+ }
+}
diff --git
a/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPathMaster.java
b/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPathMaster.java
new file mode 100644
index 00000000..358d77ad
--- /dev/null
+++
b/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPathMaster.java
@@ -0,0 +1,47 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hugegraph.computer.algorithm.path.shortest;
+
+import org.apache.hugegraph.computer.core.combiner.IdSetMergeCombiner;
+import org.apache.hugegraph.computer.core.graph.value.ValueType;
+import org.apache.hugegraph.computer.core.master.MasterComputation;
+import org.apache.hugegraph.computer.core.master.MasterComputationContext;
+import org.apache.hugegraph.computer.core.master.MasterContext;
+
+public class SingleSourceShortestPathMaster implements MasterComputation {
+
+ public static final String SINGLE_SOURCE_SHORTEST_PATH_REACHED_TARGETS =
+ "single_source_shortest_path.reached_targets";
+
+ @Override
+ public void init(MasterContext context) {
+ context.registerAggregator(SINGLE_SOURCE_SHORTEST_PATH_REACHED_TARGETS,
+ ValueType.ID_SET,
+ IdSetMergeCombiner.class);
+ }
+
+ @Override
+ public void close(MasterContext context) {
+ // pass
+ }
+
+ @Override
+ public boolean compute(MasterComputationContext context) {
+ return true;
+ }
+}
diff --git
a/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPathOutput.java
b/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPathOutput.java
new file mode 100644
index 00000000..4a646cf4
--- /dev/null
+++
b/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPathOutput.java
@@ -0,0 +1,48 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hugegraph.computer.algorithm.path.shortest;
+
+import java.util.HashMap;
+import java.util.Map;
+
+import org.apache.hugegraph.computer.core.graph.vertex.Vertex;
+import org.apache.hugegraph.computer.core.output.hg.HugeGraphOutput;
+import org.apache.hugegraph.util.JsonUtil;
+
+public class SingleSourceShortestPathOutput extends HugeGraphOutput<String> {
+
+ @Override
+ protected void prepareSchema() {
+ this.client().schema().propertyKey(this.name())
+ .asText()
+ .writeType(this.writeType())
+ .valueList()
+ .ifNotExist()
+ .create();
+ }
+
+ @Override
+ protected String value(Vertex vertex) {
+ SingleSourceShortestPathValue value = vertex.value();
+
+ Map map = new HashMap();
+ map.put("path", value.path().toString());
+ map.put("total_weight", value.totalWeight());
+ return JsonUtil.toJson(map);
+ }
+}
diff --git
a/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPathParams.java
b/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPathParams.java
new file mode 100644
index 00000000..048f7314
--- /dev/null
+++
b/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPathParams.java
@@ -0,0 +1,48 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hugegraph.computer.algorithm.path.shortest;
+
+import java.util.Map;
+
+import org.apache.hugegraph.computer.algorithm.AlgorithmParams;
+import org.apache.hugegraph.computer.core.config.ComputerOptions;
+
+public class SingleSourceShortestPathParams implements AlgorithmParams {
+
+ @Override
+ public void setAlgorithmParameters(Map<String, String> params) {
+ this.setIfAbsent(params, ComputerOptions.MASTER_COMPUTATION_CLASS,
+ SingleSourceShortestPathMaster.class.getName());
+ this.setIfAbsent(params, ComputerOptions.WORKER_COMPUTATION_CLASS,
+ SingleSourceShortestPath.class.getName());
+ this.setIfAbsent(params, ComputerOptions.ALGORITHM_MESSAGE_CLASS,
+ SingleSourceShortestPathValue.class.getName());
+ this.setIfAbsent(params, ComputerOptions.WORKER_COMBINER_CLASS,
+ SingleSourceShortestPathCombiner.class.getName());
+ this.setIfAbsent(params, ComputerOptions.ALGORITHM_RESULT_CLASS,
+ SingleSourceShortestPathValue.class.getName());
+ this.setIfAbsent(params, ComputerOptions.INPUT_FILTER_CLASS,
+ EXTRACTALLPROPERTYINPUTFILTER_CLASS_NAME);
+ this.setIfAbsent(params, ComputerOptions.OUTPUT_CLASS,
+ SingleSourceShortestPathOutput.class.getName());
+
+ this.setIfAbsent(params, SingleSourceShortestPath.OPTION_SOURCE_ID,
"");
+ this.setIfAbsent(params, SingleSourceShortestPath.OPTION_TARGET_ID,
"");
+ this.setIfAbsent(params,
SingleSourceShortestPath.OPTION_WEIGHT_PROPERTY, "");
+ }
+}
diff --git
a/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPathValue.java
b/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPathValue.java
new file mode 100644
index 00000000..f6ca1c16
--- /dev/null
+++
b/computer-algorithm/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPathValue.java
@@ -0,0 +1,103 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hugegraph.computer.algorithm.path.shortest;
+
+import java.io.IOException;
+import java.util.List;
+
+import org.apache.hugegraph.computer.core.graph.value.DoubleValue;
+import org.apache.hugegraph.computer.core.graph.value.IdList;
+import org.apache.hugegraph.computer.core.graph.value.Value;
+import org.apache.hugegraph.computer.core.graph.vertex.Vertex;
+import org.apache.hugegraph.computer.core.io.RandomAccessInput;
+import org.apache.hugegraph.computer.core.io.RandomAccessOutput;
+
+public class SingleSourceShortestPathValue implements
Value.CustomizeValue<List<Object>> {
+
+ /**
+ * path
+ */
+ private final IdList path;
+
+ /**
+ * total weight.
+ * infinity means unreachable.
+ */
+ private final DoubleValue totalWeight;
+
+ public SingleSourceShortestPathValue() {
+ this.path = new IdList();
+ this.totalWeight = new DoubleValue(0);
+ }
+
+ @Override
+ public void read(RandomAccessInput in) throws IOException {
+ this.path.read(in);
+ this.totalWeight.read(in);
+ }
+
+ @Override
+ public void write(RandomAccessOutput out) throws IOException {
+ this.path.write(out);
+ this.totalWeight.write(out);
+ }
+
+ @Override
+ public List<Object> value() {
+ return this.path.value();
+ }
+
+ public void unreachable() {
+ this.totalWeight.value(Double.POSITIVE_INFINITY);
+ }
+
+ public void zeroDistance() {
+ this.totalWeight.value(0);
+ }
+
+ public void shorterPath(Vertex vertex, IdList path, double weight) {
+ this.path.clear();
+ this.path.addAll(path.copy().values());
+ this.path.add(vertex.id());
+ this.totalWeight.value(weight);
+ }
+
+ public void addToPath(Vertex vertex, double weight) {
+ this.path.add(vertex.id());
+ this.totalWeight.value(weight);
+ }
+
+ public void addToPath(IdList path, double weight) {
+ this.path.addAll(path.copy().values());
+ this.totalWeight.value(weight);
+ }
+
+ public IdList path() {
+ return this.path;
+ }
+
+ public double totalWeight() {
+ return this.totalWeight.doubleValue();
+ }
+
+ public void copy(SingleSourceShortestPathValue value) {
+ this.path.clear();
+ this.path.addAll(value.path().copy().values());
+ this.totalWeight.value(value.totalWeight());
+ }
+}
diff --git
a/computer-api/src/main/java/org/apache/hugegraph/computer/core/combiner/IdListMergeCombiner.java
b/computer-api/src/main/java/org/apache/hugegraph/computer/core/combiner/IdListMergeCombiner.java
new file mode 100644
index 00000000..3cc18444
--- /dev/null
+++
b/computer-api/src/main/java/org/apache/hugegraph/computer/core/combiner/IdListMergeCombiner.java
@@ -0,0 +1,39 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hugegraph.computer.core.combiner;
+
+import org.apache.hugegraph.computer.core.graph.id.Id;
+import org.apache.hugegraph.computer.core.graph.value.IdList;
+
+public class IdListMergeCombiner implements Combiner<IdList> {
+
+ @Override
+ public void combine(IdList v1, IdList v2, IdList result) {
+ // merge
+ for (Id id : v1.values()) {
+ if (!result.contains(id)) {
+ result.add(id);
+ }
+ }
+ for (Id id : v2.values()) {
+ if (!result.contains(id)) {
+ result.add(id);
+ }
+ }
+ }
+}
diff --git
a/computer-api/src/main/java/org/apache/hugegraph/computer/core/combiner/IdSetMergeCombiner.java
b/computer-api/src/main/java/org/apache/hugegraph/computer/core/combiner/IdSetMergeCombiner.java
new file mode 100644
index 00000000..5698da94
--- /dev/null
+++
b/computer-api/src/main/java/org/apache/hugegraph/computer/core/combiner/IdSetMergeCombiner.java
@@ -0,0 +1,30 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hugegraph.computer.core.combiner;
+
+import org.apache.hugegraph.computer.core.graph.value.IdSet;
+
+public class IdSetMergeCombiner implements Combiner<IdSet> {
+
+ @Override
+ public void combine(IdSet v1, IdSet v2, IdSet result) {
+ // merge
+ result.addAll(v1);
+ result.addAll(v2);
+ }
+}
diff --git
a/computer-api/src/main/java/org/apache/hugegraph/computer/core/graph/id/IdFactory.java
b/computer-api/src/main/java/org/apache/hugegraph/computer/core/graph/id/IdFactory.java
index 2f9284e7..106873d6 100644
---
a/computer-api/src/main/java/org/apache/hugegraph/computer/core/graph/id/IdFactory.java
+++
b/computer-api/src/main/java/org/apache/hugegraph/computer/core/graph/id/IdFactory.java
@@ -80,6 +80,23 @@ public final class IdFactory {
}
}
+ public static Id parseId(IdType type, Object value) {
+ try {
+ switch (type) {
+ case LONG:
+ return (Id) BYTES_ID_LONG_METHOD.invoke(null, value);
+ case UTF8:
+ return (Id) BYTES_ID_STRING_METHOD.invoke(null, value);
+ case UUID:
+ return (Id) BYTES_ID_UUID_METHOD.invoke(null, value);
+ default:
+ throw new ComputerException("Unexpected id type %s",
type.name());
+ }
+ } catch (Exception e) {
+ throw new ComputerException("Failed to parse %s Id: '%s'", e,
type, value);
+ }
+ }
+
public static Id createId() {
try {
return (Id) BYTES_ID_CONSTRUCTOR.newInstance();
diff --git
a/computer-api/src/main/java/org/apache/hugegraph/computer/core/graph/value/IdSet.java
b/computer-api/src/main/java/org/apache/hugegraph/computer/core/graph/value/IdSet.java
index 7b4267f8..9e90ad23 100644
---
a/computer-api/src/main/java/org/apache/hugegraph/computer/core/graph/value/IdSet.java
+++
b/computer-api/src/main/java/org/apache/hugegraph/computer/core/graph/value/IdSet.java
@@ -107,4 +107,8 @@ public class IdSet implements Value.Tvalue<Set<Id>> {
public int compareTo(Value o) {
throw new UnsupportedOperationException("compareTo");
}
+
+ public int size() {
+ return this.values.size();
+ }
}
diff --git
a/computer-api/src/main/java/org/apache/hugegraph/computer/core/graph/value/ListValue.java
b/computer-api/src/main/java/org/apache/hugegraph/computer/core/graph/value/ListValue.java
index c9f5d05e..268929dd 100644
---
a/computer-api/src/main/java/org/apache/hugegraph/computer/core/graph/value/ListValue.java
+++
b/computer-api/src/main/java/org/apache/hugegraph/computer/core/graph/value/ListValue.java
@@ -117,6 +117,10 @@ public class ListValue<T extends Tvalue<?>> implements
Tvalue<List<Object>> {
return this.values.size();
}
+ public void clear() {
+ this.values.clear();
+ }
+
@Override
public List<Object> value() {
List<Object> list = new ArrayList<>(this.values.size());
@@ -162,8 +166,7 @@ public class ListValue<T extends Tvalue<?>> implements
Tvalue<List<Object>> {
this.read(in, true);
}
- protected void read(RandomAccessInput in, boolean readElemType)
- throws IOException {
+ protected void read(RandomAccessInput in, boolean readElemType) throws
IOException {
int size = in.readInt();
if (readElemType) {
this.elemType = SerialEnum.fromCode(ValueType.class,
in.readByte());
@@ -187,8 +190,7 @@ public class ListValue<T extends Tvalue<?>> implements
Tvalue<List<Object>> {
this.write(out, true);
}
- protected void write(RandomAccessOutput out, boolean writeElemType)
- throws IOException {
+ protected void write(RandomAccessOutput out, boolean writeElemType) throws
IOException {
out.writeInt(this.values.size());
if (writeElemType) {
out.writeByte(this.elemType.code());
diff --git
a/computer-api/src/main/java/org/apache/hugegraph/computer/core/util/IdUtil.java
b/computer-api/src/main/java/org/apache/hugegraph/computer/core/util/IdUtil.java
new file mode 100644
index 00000000..1963909e
--- /dev/null
+++
b/computer-api/src/main/java/org/apache/hugegraph/computer/core/util/IdUtil.java
@@ -0,0 +1,53 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hugegraph.computer.core.util;
+
+import java.util.UUID;
+
+import org.apache.commons.lang3.StringUtils;
+import org.apache.hugegraph.computer.core.graph.id.Id;
+import org.apache.hugegraph.computer.core.graph.id.IdFactory;
+import org.apache.hugegraph.computer.core.graph.id.IdType;
+import org.apache.hugegraph.util.JsonUtil;
+
+public class IdUtil {
+
+ public static Id parseId(String idStr) {
+ if (StringUtils.isBlank(idStr)) {
+ throw new IllegalArgumentException("Can't parse Id for empty
string");
+ }
+
+ try {
+ if (idStr.startsWith("U\"")) {
+ return IdFactory.parseId(IdType.UUID,
+ UUID.fromString(idStr.substring(1)
+
.replaceAll("\"", "")));
+ }
+
+ Object id = JsonUtil.fromJson(idStr, Object.class);
+ idStr = idStr.replaceAll("\"", "");
+ return id instanceof Number ?
+ IdFactory.parseId(IdType.LONG, Long.valueOf(idStr)) :
+ IdFactory.parseId(IdType.UTF8, idStr);
+ } catch (Exception e) {
+ throw new IllegalArgumentException(String.format(
+ "The vertex id must be formatted as Number/String/UUID" +
+ ", but got '%s'", idStr));
+ }
+ }
+}
diff --git
a/computer-api/src/main/java/org/apache/hugegraph/computer/core/util/JsonUtilExt.java
b/computer-api/src/main/java/org/apache/hugegraph/computer/core/util/JsonUtilExt.java
new file mode 100644
index 00000000..3304881e
--- /dev/null
+++
b/computer-api/src/main/java/org/apache/hugegraph/computer/core/util/JsonUtilExt.java
@@ -0,0 +1,46 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hugegraph.computer.core.util;
+
+import java.io.IOException;
+import java.util.List;
+
+import org.apache.hugegraph.rest.SerializeException;
+
+import com.fasterxml.jackson.databind.JavaType;
+import com.fasterxml.jackson.databind.ObjectMapper;
+
+// TODO: move to org.apache.hugegraph.util.JsonUtil later
+public class JsonUtilExt {
+
+ private static final ObjectMapper MAPPER = new ObjectMapper();
+
+ public static <T> List<T> fromJson2List(String json, Class<T> clazz) {
+ try {
+ return MAPPER.readValue(json, getCollectionType(List.class,
clazz));
+ } catch (IOException e) {
+ throw new SerializeException("Failed to deserialize json '%s'",
+ e, json);
+ }
+ }
+
+ private static JavaType getCollectionType(Class<?> collectionClass,
+ Class<?>... elementClasses) {
+ return
MAPPER.getTypeFactory().constructParametricType(collectionClass,
elementClasses);
+ }
+}
diff --git
a/computer-test/src/main/java/org/apache/hugegraph/computer/algorithm/AlgorithmTestSuite.java
b/computer-test/src/main/java/org/apache/hugegraph/computer/algorithm/AlgorithmTestSuite.java
index 41e9174c..f5124d01 100644
---
a/computer-test/src/main/java/org/apache/hugegraph/computer/algorithm/AlgorithmTestSuite.java
+++
b/computer-test/src/main/java/org/apache/hugegraph/computer/algorithm/AlgorithmTestSuite.java
@@ -28,6 +28,7 @@ import
org.apache.hugegraph.computer.algorithm.community.trianglecount.TriangleC
import org.apache.hugegraph.computer.algorithm.community.wcc.WccTest;
import org.apache.hugegraph.computer.algorithm.path.rings.RingsDetectionTest;
import
org.apache.hugegraph.computer.algorithm.path.rings.RingsDetectionWithFilterTest;
+import
org.apache.hugegraph.computer.algorithm.path.shortest.SingleSourceShortestPathTest;
import org.apache.hugegraph.computer.algorithm.sampling.RandomWalkTest;
import org.junit.runner.RunWith;
import org.junit.runners.Suite;
@@ -45,7 +46,8 @@ import org.junit.runners.Suite;
ClusteringCoefficientTest.class,
ClosenessCentralityTest.class,
BetweennessCentralityTest.class,
- RandomWalkTest.class
+ RandomWalkTest.class,
+ SingleSourceShortestPathTest.class
})
public class AlgorithmTestSuite {
}
diff --git
a/computer-test/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPathTest.java
b/computer-test/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPathTest.java
new file mode 100644
index 00000000..4b2b466a
--- /dev/null
+++
b/computer-test/src/main/java/org/apache/hugegraph/computer/algorithm/path/shortest/SingleSourceShortestPathTest.java
@@ -0,0 +1,148 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hugegraph.computer.algorithm.path.shortest;
+
+import java.util.Map;
+
+import org.apache.hugegraph.computer.algorithm.AlgorithmTestBase;
+import org.apache.hugegraph.computer.core.config.ComputerOptions;
+import org.apache.hugegraph.driver.GraphManager;
+import org.apache.hugegraph.driver.HugeClient;
+import org.apache.hugegraph.driver.SchemaManager;
+import org.apache.hugegraph.structure.constant.T;
+import org.apache.hugegraph.structure.graph.Vertex;
+import org.apache.hugegraph.util.JsonUtil;
+import org.apache.hugegraph.util.Log;
+import org.junit.AfterClass;
+import org.junit.Assert;
+import org.junit.BeforeClass;
+import org.junit.Test;
+import org.slf4j.Logger;
+
+public class SingleSourceShortestPathTest extends AlgorithmTestBase {
+
+ public static final String VL = "city";
+ public static final String EL = "road";
+ public static final String PROPERTY_KEY = "distance";
+
+ public static final String SOURCE_ID = "\"A\"";
+ public static final String TARGET_ID = "\"E\"";
+ public static final String SHORTEST_PATH = "[A, C, B, E]";
+ public static final double TOTAL_WEIGHT = 28;
+
+
+ @BeforeClass
+ public static void setup() {
+ clearAll();
+
+ HugeClient client = client();
+ SchemaManager schema = client.schema();
+
+ schema.propertyKey(PROPERTY_KEY)
+ .asDouble()
+ .ifNotExist()
+ .create();
+ schema.vertexLabel(VL)
+ .useCustomizeStringId()
+ .ifNotExist()
+ .create();
+ schema.edgeLabel(EL)
+ .sourceLabel(VL)
+ .targetLabel(VL)
+ .properties(PROPERTY_KEY)
+ .nullableKeys(PROPERTY_KEY)
+ .ifNotExist()
+ .create();
+
+ GraphManager graph = client.graph();
+ Vertex vA = graph.addVertex(T.LABEL, VL, T.ID, "A");
+ Vertex vB = graph.addVertex(T.LABEL, VL, T.ID, "B");
+ Vertex vC = graph.addVertex(T.LABEL, VL, T.ID, "C");
+ Vertex vD = graph.addVertex(T.LABEL, VL, T.ID, "D");
+ Vertex vE = graph.addVertex(T.LABEL, VL, T.ID, "E");
+ Vertex vF = graph.addVertex(T.LABEL, VL, T.ID, "F");
+
+ Vertex vJ = graph.addVertex(T.LABEL, VL, T.ID, "J");
+ Vertex vK = graph.addVertex(T.LABEL, VL, T.ID, "K");
+
+ vA.addEdge(EL, vC, PROPERTY_KEY, 5);
+ vA.addEdge(EL, vD, PROPERTY_KEY, 30);
+
+ vB.addEdge(EL, vA, PROPERTY_KEY, 2);
+ vB.addEdge(EL, vE, PROPERTY_KEY, 8);
+
+ vC.addEdge(EL, vB, PROPERTY_KEY, 15);
+ vC.addEdge(EL, vF, PROPERTY_KEY, 7);
+
+ vE.addEdge(EL, vB, PROPERTY_KEY, 6);
+ vE.addEdge(EL, vD, PROPERTY_KEY, 4);
+
+ vF.addEdge(EL, vC, PROPERTY_KEY, 8);
+ vF.addEdge(EL, vD, PROPERTY_KEY, 10);
+ vF.addEdge(EL, vE, PROPERTY_KEY, 18);
+
+ vJ.addEdge(EL, vK);
+ }
+
+ @AfterClass
+ public static void clear() {
+ clearAll();
+ }
+
+ @Test
+ public void testRunAlgorithm() throws InterruptedException {
+ runAlgorithm(SingleSourceShortestPathTestParams.class.getName());
+ }
+
+ public static class SingleSourceShortestPathTestParams extends
SingleSourceShortestPathParams {
+
+ @Override
+ public void setAlgorithmParameters(Map<String, String> params) {
+ this.setIfAbsent(params, ComputerOptions.OUTPUT_CLASS,
+
SingleSourceShortestPathTestOutput.class.getName());
+ this.setIfAbsent(params,
SingleSourceShortestPath.OPTION_SOURCE_ID, SOURCE_ID);
+ this.setIfAbsent(params,
SingleSourceShortestPath.OPTION_TARGET_ID, TARGET_ID);
+ this.setIfAbsent(params,
SingleSourceShortestPath.OPTION_WEIGHT_PROPERTY,
+ SingleSourceShortestPathTest.PROPERTY_KEY);
+
+ super.setAlgorithmParameters(params);
+ }
+ }
+
+ public static class SingleSourceShortestPathTestOutput extends
SingleSourceShortestPathOutput {
+
+ private static final Logger LOG =
Log.logger(SingleSourceShortestPathTestOutput.class);
+
+ @Override
+ public String
value(org.apache.hugegraph.computer.core.graph.vertex.Vertex vertex) {
+ String json = super.value(vertex);
+
+ if (vertex.id().value().toString().equals(TARGET_ID)) {
+ Map map = JsonUtil.fromJson(json, Map.class);
+
+ LOG.info("source vertex to target vertex: {}, {}, " +
+ "shortest path: {}, total weight: {}",
+ SOURCE_ID, TARGET_ID,
+ map.get("path"), map.get("total_weight"));
+ Assert.assertEquals(map.get("path"), SHORTEST_PATH);
+ Assert.assertEquals(map.get("total_weight"), TOTAL_WEIGHT);
+ }
+ return json;
+ }
+ }
+}
diff --git
a/computer-test/src/main/java/org/apache/hugegraph/computer/core/graph/id/IdFactoryTest.java
b/computer-test/src/main/java/org/apache/hugegraph/computer/core/graph/id/IdFactoryTest.java
index c95ea8bf..6fa03fc1 100644
---
a/computer-test/src/main/java/org/apache/hugegraph/computer/core/graph/id/IdFactoryTest.java
+++
b/computer-test/src/main/java/org/apache/hugegraph/computer/core/graph/id/IdFactoryTest.java
@@ -51,4 +51,12 @@ public class IdFactoryTest {
Assert.assertEquals(BytesId.of(new UUID(0L, 0L)),
IdFactory.createId(IdType.UUID));
}
+
+ @Test
+ public void testParseId() {
+ UUID uuid = UUID.fromString("3b676b77-c484-4ba6-b627-8c040bc42863");
+ Assert.assertEquals(IdType.LONG, IdFactory.parseId(IdType.LONG,
222).idType());
+ Assert.assertEquals(IdType.UTF8, IdFactory.parseId(IdType.UTF8,
"aaa222").idType());
+ Assert.assertEquals(IdType.UUID, IdFactory.parseId(IdType.UUID,
uuid).idType());
+ }
}
diff --git
a/computer-test/src/main/java/org/apache/hugegraph/computer/core/graph/value/ListValueTest.java
b/computer-test/src/main/java/org/apache/hugegraph/computer/core/graph/value/ListValueTest.java
index 3b5310af..99c61288 100644
---
a/computer-test/src/main/java/org/apache/hugegraph/computer/core/graph/value/ListValueTest.java
+++
b/computer-test/src/main/java/org/apache/hugegraph/computer/core/graph/value/ListValueTest.java
@@ -195,6 +195,18 @@ public class ListValueTest extends UnitTestBase {
Assert.assertEquals(2, value2.size());
}
+ @Test
+ public void testClear() {
+ ListValue<IntValue> value = new ListValue<>(ValueType.INT);
+ value.add(new IntValue(101));
+ value.add(new IntValue(102));
+ value.add(new IntValue(103));
+ Assert.assertEquals(3, value.size());
+
+ value.clear();
+ Assert.assertEquals(0, value.size());
+ }
+
@Test
public void testValues() {
ListValue<IntValue> value1 = new ListValue<>(ValueType.INT);
diff --git
a/computer-test/src/main/java/org/apache/hugegraph/computer/core/util/IdUtilTest.java
b/computer-test/src/main/java/org/apache/hugegraph/computer/core/util/IdUtilTest.java
new file mode 100644
index 00000000..73969082
--- /dev/null
+++
b/computer-test/src/main/java/org/apache/hugegraph/computer/core/util/IdUtilTest.java
@@ -0,0 +1,56 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with this
+ * work for additional information regarding copyright ownership. The ASF
+ * licenses this file to You under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.hugegraph.computer.core.util;
+
+import org.apache.hugegraph.computer.core.graph.id.IdType;
+import org.apache.hugegraph.testutil.Assert;
+import org.junit.Test;
+
+public class IdUtilTest {
+
+ @Test
+ public void testParseId() {
+ String idUtf8WithString = "\"abc\"";
+ String idUtf8WithNumber = "\"222\"";
+ String idLong = "222";
+ String idUuid = "U\"3b676b77-c484-4ba6-b627-8c040bc42863\"";
+
+ String idNull = null;
+ String idEmpty = "";
+ String idDouble = "1.23";
+ String idUuidInvalid = "U\"123\"";
+
+ Assert.assertEquals(IdType.UTF8,
IdUtil.parseId(idUtf8WithString).idType());
+ Assert.assertEquals(IdType.UTF8,
IdUtil.parseId(idUtf8WithNumber).idType());
+ Assert.assertEquals(IdType.LONG, IdUtil.parseId(idLong).idType());
+ Assert.assertEquals(IdType.UUID, IdUtil.parseId(idUuid).idType());
+
+ Assert.assertThrows(IllegalArgumentException.class, () -> {
+ IdUtil.parseId(idNull).idType();
+ });
+ Assert.assertThrows(IllegalArgumentException.class, () -> {
+ IdUtil.parseId(idEmpty).idType();
+ });
+ Assert.assertThrows(IllegalArgumentException.class, () -> {
+ IdUtil.parseId(idDouble).idType();
+ });
+ Assert.assertThrows(IllegalArgumentException.class, () -> {
+ IdUtil.parseId(idUuidInvalid).idType();
+ });
+ }
+}
