HDC
概述
图遍历（Graph Traversal）是一种系统性的搜索技术，用于访问和探索图中的所有节点。图遍历的主要目标是发现和检查图的结构和连接关系。图遍历有两种常见的策略：
- 广度优先搜索（Breadth-First Seach, BFS）
- 深度优先搜索（Depth-First Seach, DFS）
深度优先搜索（DFS）算法基于回溯（Backtracking）原则，具体实现步骤如下：
- 创建一个栈（后进先出）来跟踪已访问的节点。
- 从选择的起始节点开始，将其推入栈，并标记该节点为已访问。
- 将位于栈顶的节点的任意一个未访问邻居推入栈，并标记为已访问。如果有多个未访问邻居，任意选择一个或按照某种确定的顺序进行选择。
- 重复第3步，直到没有更多未访问的邻居可以推入栈。
- 当没有新节点可以访问时，通过从栈中弹出顶部节点回溯到前一个节点（即当前节点是从哪个节点探索而来的）。
- 重复第3、4和5步，直到栈为空。
下面是以DFS方式遍历图的示例，以节点A作为起始节点，并假定按字母顺序（A~Z）访问邻居节点：
特殊说明
- 只有与起始节点在同一个连通分量中的节点才能被遍历。不同连通分量中的节点将不会出现在结果中。
示例图
在一个空图中运行以下语句定义图结构并插入数据：
INSERT (A:default {_id: "A"}),
(B:default {_id: "B"}),
(C:default {_id: "C"}),
(D:default {_id: "D"}),
(E:default {_id: "E"}),
(F:default {_id: "F"}),
(G:default {_id: "G"}),
(A)-[:default]->(B),
(A)-[:default]->(D),
(B)-[:default]->(E),
(C)-[:default]->(A),
(E)-[:default]->(F),
(F)-[:default]->(C),
(G)-[:default]->(D);
insert().into(@default).nodes([{_id:"A"}, {_id:"B"}, {_id:"C"}, {_id:"D"}, {_id:"E"}, {_id:"F"}, {_id:"G"}]);
insert().into(@default).edges([{_from:"G", _to:"D"}, {_from:"A", _to:"D"}, {_from:"A", _to:"B"}, {_from:"B", _to:"E"}, {_from:"E", _to:"F"}, {_from:"F", _to:"C"}, {_from:"C", _to:"A"}]);
创建HDC图
将当前图集全部加载到HDC服务器hdc-server-1上，并命名为 my_hdc_graph：
CREATE HDC GRAPH my_hdc_graph ON "hdc-server-1" OPTIONS {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static"
}
hdc.graph.create("my_hdc_graph", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static"
}).to("hdc-server-1")
参数
算法名：traverse
参数名 |
类型 |
规范 |
默认值 |
可选 |
描述 |
|---|---|---|---|---|---|
ids |
_id |
/ | / | 否 | 通过_id指定遍历的起点 |
uuids |
_uuid |
/ | / | 否 | 通过_uuid指定遍历的起点 |
direction |
String | in, out |
/ | 是 | 指定遍历时的边方向，in表示仅遍历入边，out表示仅遍历出边 |
traverse_type |
String | dfs |
bfs |
否 | 以DFS方式遍历图时，设置该项为dfs |
return_id_uuid |
String | uuid, id, both |
uuid |
是 | 在结果中使用_uuid、_id或同时使用两者来表示点 |
文件回写
CALL algo.traverse.write("my_hdc_graph", {
return_id_uuid: "id",
ids: ['B'],
direction: 'in',
traverse_type: 'dfs'
}, {
file: {
filename: "visited_nodes"
}
})
algo(traverse).params({
projection: "my_hdc_graph",
return_id_uuid: "id",
ids: ['B'],
direction: 'in',
traverse_type: 'dfs'
}).write({
file: {
filename: "visited_nodes"
}
})
结果：
nodes
B,A,C,F,E,