[google/guava]节点深度

5

嗨@Rokshan2016，据我所知，Guava 没有这样的方法Graph。

也许我的想法在这里被误导了，但我认为获取节点的“深度”仅对于每个节点最多有一个父节点的图才有意义（即图是一棵“树”或“森林”））。

给出以下示例非树图，其中边指向下方：

a   b
|   |
c   |
\   /
 \ /
  d

节点“d”的深度应该是2还是3？据我所知，尚不清楚哪种结果是理想的。

如果或当JUNG 3.0 发布时（我正在为它做出贡献，尽管是零星的），它很可能会有一个Tree扩展 Guava 的类Graph并有一个depth方法。但遗憾的是距离 3.0 发布还有很长的路要走。

jbduncan

1

我最好的猜测是，“节点深度”的意思是“从给定起始节点到给定目标节点的未加权最短路径距离”。（如果这不是您的意思，请澄清。）

如果这就是您想要的，那么我们有一个尚未发布的实用方法可以做到这一点。它尚未发布主要是因为我们还没有解决一些定义问题。

jrtom

8

感谢您的建议。我想到了

Rokshan2016

8

@Rokshan2016 酷！您是否愿意与我们分享您的确切想法以及您的解决方案是什么？ :)

jbduncan

6

@jbduncan 你好，我基本上正在使用 FHIR 捆绑资源。每个包都有一些资源，并且它们相互依赖。所以我使用 Mutable Graph 来获取图形 obj，我创建了一个方法来获取父级（方法 1）。如果任何资源没有任何父级/依赖项，这意味着它的深度为 0 ，如果它有父级，那么我将检查该父级是否有父级。所以基本上我会循环它直到父级为空。并且每次将深度加“1”。希望能帮助到你！谢谢！

public Set<IBaseResource> getParentResources(IBaseResource child) {
        Set<IBaseResource> parents = graph.successors(child);
        return parents == null ? Collections.emptySet() : parents;
    }

public int getResourceDepth(IBaseResource iBaseResource, FhirReferenceDependencyChainResolver chainResolver) {

        Set<IBaseResource> parents = chainResolver.getParentResources(iBaseResource);
        if(parents!=null) {
            if(parents.isEmpty()) {
                return 0;
            }else if(!parents.isEmpty()) {
                int count = 1;
                List<IBaseResource> list = new ArrayList<>();
                list.addAll(parents);

                List<IBaseResource> list2 = parentResourceCheckHelper(list, chainResolver);
                label1 :if(list2.size()>0) {
                    count++;
                    list2 = parentResourceCheckHelper(list, chainResolver);
                    break label1;
                }
                return count;
            }
        }
        return 0;
    }

Rokshan2016

7

@Rokshan2016 感谢您发布您的解决方案。

我无法判断这是否正确，因为我不知道这parentResourceCheckHelper是什么。

我可以看到的代码的一些评论：

(0) 这有点奇怪，你的图似乎被定义为successors节点的被定义为其父节点（我通常期望它是predecessors）。这是故意的，还是您的代码中可能存在错误？

(1) Graph.successors()——事实上，相关接口Set上的所有返回方法——永远不会返回 null。Graph也就是说，根据合同，它们被禁止这样做，因此，如果您看到其中一个方法返回 null，那么它就是一个错误。这意味着您不需要辅助方法。

(2) 你的辅助方法永远不会返回 null，所以你不需要对此进行 null 检查。

(3) 这是多余的：

if (parents.isEmpty()) {
  return 0;
} else if (!parents.isEmpty()) {
  int count = 1;
  ...
}

并可以更简洁地表示为：

if (parents.isEmpty()) {
  return 0;
}
int count = 1;
...

if(4)如果初始化count为 0，您可能可以完全摆脱该语句。

jrtom

6

我最好的猜测是，“节点深度”的意思是“从给定起始节点到给定目标节点的未加权最短路径距离”。（如果这不是您的意思，请澄清。）如果这就是您想要的，那么我们有一个尚未发布的实用方法可以做到这一点。它尚未发布主要是因为我们还没有解决一些定义问题。

这个实用方法还在吗？或者废弃的代码是否公开可用？寻路是一种常见的图形用例，因此加权最短路径算法（例如 Dijkstra）也很有用。顺便说一句，如果 Traverser 返回路径而不是节点（即Iterable<List<N>> breadthFirst(N startNode)），用户会更容易“推出自己的”[未加权]解决方案。

hwaite

[google/guava]节点深度

回答