492
Q. Xu et al.
The BFS function needs two parameters, one is the searched feature node
and another one is the distance to constrain the search range. Each circulation
between line 5 and line 20, we take out the first node of the queue and push
back its adjacent nodes at the end of the queue unless the adjacent node has not
been visited. In line 7, we check the nodes distance to decide whether the search
should be end. At last, we get all the features whose distance from the searched
feature node is less than the given distance parameter.
For the depth-first search, we can get all the relative paths of two features.
Algorithm 2 shows the overall process of the depth-first search. The search starts
from the start node. The recursion function between line 4 and line 19 compares
the current node with the end node recursively to find the path. At last, we get
all the relative paths of the start and end features by the DFS method.
Algorithm 2 Depth-first search method
1: With the input parameters start node, end node;
2: Initialize a list result list;
3: DFS(start node);
4: Function DFS (current node):
5: current node.visited flag = true;
6: if current node == end node then
7:
result list.push back(current node);
8:
return true;
9: end if
10: Get all the adjacent nodes of current node and put them in a temporary list adjacent list;
11: for each adj node in adjacent list do
12:
if adj node.visited flag is not true then
13:
path is right = DFS(adj node);
14:
if path is right == true then
15:
result list.push back(adj node);
16:
end if
17:
end if
18: end for
19: return false;
4 Experimental Results
The proposed method has been implemented in Java language on a Windows
64-bit workstation (Intel 2.2 GHz, 64 GB RAM).
In this work, we build an ATM knowledge graph which has about 20,000
feature nodes and 100,000 relationship edges.
Q. Xu et al.
The BFS function needs two parameters, one is the searched feature node
and another one is the distance to constrain the search range. Each circulation
between line 5 and line 20, we take out the first node of the queue and push
back its adjacent nodes at the end of the queue unless the adjacent node has not
been visited. In line 7, we check the nodes distance to decide whether the search
should be end. At last, we get all the features whose distance from the searched
feature node is less than the given distance parameter.
For the depth-first search, we can get all the relative paths of two features.
Algorithm 2 shows the overall process of the depth-first search. The search starts
from the start node. The recursion function between line 4 and line 19 compares
the current node with the end node recursively to find the path. At last, we get
all the relative paths of the start and end features by the DFS method.
Algorithm 2 Depth-first search method
1: With the input parameters start node, end node;
2: Initialize a list result list;
3: DFS(start node);
4: Function DFS (current node):
5: current node.visited flag = true;
6: if current node == end node then
7:
result list.push back(current node);
8:
return true;
9: end if
10: Get all the adjacent nodes of current node and put them in a temporary list adjacent list;
11: for each adj node in adjacent list do
12:
if adj node.visited flag is not true then
13:
path is right = DFS(adj node);
14:
if path is right == true then
15:
result list.push back(adj node);
16:
end if
17:
end if
18: end for
19: return false;
4 Experimental Results
The proposed method has been implemented in Java language on a Windows
64-bit workstation (Intel 2.2 GHz, 64 GB RAM).
In this work, we build an ATM knowledge graph which has about 20,000
feature nodes and 100,000 relationship edges.