因为我比ElasticSearch查询语言更习惯于JavaScript,所以我最终只使用了一个DFS实现。(
https://en.wikipedia.org/wiki/Depth-first_search
this.selectedNode
一次是为了得到所有的父母(和其他祖先),另一次是为了得到所有的孩子。代码如下(有点冗长,但需要注意的主要功能是
buildGraph
_dfs
在此获取算法的要点(还要注意,使用字段
async function _getParents(child) {
let data = {
"sort": {"timestamp": {"order": "desc"}},
"query": {
"bool": {
"should": [
{"match": {"currId": child.prevId}},
],
"should": child.sources.map((id) => {return {"match": {"currId": id}}})
}
}
}
let nodes = []
let res = await axios.get("http://myesserver:9200/myindex/mytype/_search", {
params: {
source: JSON.stringify(data),
source_content_type: 'application/json'
}
})
console.log('NEW PARENT NODES')
nodes = res['data']['hits']['hits'].map(record => {return record['_source']} )
console.log(nodes)
return nodes
}
async function _getChildren(parent) {
let data = {
"sort": {"timestamp": {"order": "desc"}},
"query": {
"bool": {
"should": [
{"match": {"prevId": parent.currId}},
{"match": {"sources": parent.currId}}
]
}
}
}
let nodes = []
let res = await axios.get("http://myesserver:9200/myindex/mytype/_search", {
params: {
source: JSON.stringify(data),
source_content_type: 'application/json'
}
})
console.log('NEW CHILD NODES')
nodes = res['data']['hits']['hits'].map(record => {return record['_source']} )
console.log(nodes)
return nodes
}
async function _dfs(root, stopper, visit, getNext) {
console.log('starting wth root node:')
console.log(root)
let s = []
s.push(root)
console.log('initialized stack (FIXME: not showing correctly for some reason):')
console.log(s)
while (s.length > 0) {
let v = s.pop()
console.log('popped:')
console.log(v)
console.log(v.sources)
if (stopper(v)) {
visit(v)
let kids = await getNext(v)
s = s.concat(kids)
console.log('concated stack:')
console.log(s)
}
}
}
async function buildGraph(startn, nodes, edges) {
let discovered = []
await _dfs(startn,
(v)=>{return !discovered.includes(v.currId)},
(v)=>{
discovered.push(v.currId)
nodes.push({id: v.currId, label: v.currLocation})
if (v.prevId != 'NULL') {
edges.push({from: v.prevId, to: v.currId})
}
if (v.sources.length > 0 && v.sources[0] != 'NULL') {
for (let i=0; i < v.sources.length; i++) {
edges.push({from: v.sources[i], to: v.currId})
}
}
},
(v)=>{return _getParents(v)})
console.log('completed collecting ancestor nodes')
console.log(nodes)
for (var i=discovered.length-1; i>=0; i--) {
if (discovered[i] === startn.currId) {
discovered.splice(i, 1);
}
}
await _dfs(startn,
(v)=>{return !discovered.includes(v.currId)},
(v)=>{
discovered.push(v.currId)
if (v.currId != startn.currId) {
nodes.push({id: v.currId, label: v.currLocation})
}
if (v.prevId != 'NULL') {
edges.push({from: v.prevId, to: v.currId})
}
if (v.sources.length > 0 && v.sources[0] != 'NULL') {
for (let i=0; i < v.sources.length; i++) {
edges.push({from: v.sources[i], to: v.currId})
}
}
},
(v)=>{return _getChildren(v)})
console.log('completed collecting child nodes')
console.log(nodes)
}
let nodes = []
let edges = []
buildGraph(this.selectedNode, nodes, edges).then(res => {
console.log('buildGraph promise result:')
console.log(res, nodes, edges)
this.setState({nodes: nodes, edges: edges})
})