guava
guava copied to clipboard
google
Depth of the nodes
Hi @Rokshan2016, as far am I'm aware, there isn't such a method for Guava Graphs.
Maybe my thinking is misguided here, but I think that getting the "depth" of a node would only make sense for a graph where every node has at most one parent node (i.e. where the graph is a "tree" or a "forest").
To give the following example non-tree graph, where the edges are directed pointing downwards:
a b
| |
c |
\ /
\ /
d
Should the depth of node "d" be 2 or 3? As far I can tell, it's not clear which result is desirable.
If or when JUNG 3.0 is released (which I'm contributing towards albeit sporadically), it will most likely have a Tree class that extends Guava's Graph and has a depth method. But sadly it'll be a long way away before 3.0 is released.
My best guess is that by "depth of a node" you mean "unweighted shortest-path distance from a given start node to a given target node". (If that's not what you mean, please clarify.)
If that's what you want, then we have a utility method we haven't released yet which does that. It's unreleased mostly because there are some definitional questions that we haven't sorted out yet.
@Rokshan2016 Cool! Are you at liberty and willing to share with us what you figured out exactly and what your solution was? :)
@jbduncan Hi I am basically working with FHIR bundle resources . Each bundle has some resources and they are dependent on each other. So I was using Mutable Graph to get the graph obj, I created a method to get the parents (Method 1). If any resource does not have any parent/dependency that means its depth is 0 , if it has parent then I am checking if that parent has parent or not. So basically I am looping it until parent is empty. And each time adding "1" to the depth. Hope it helps! Thanks!
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 Thanks for posting your solution.
I can't tell if this is correct because I don't know what parentResourceCheckHelper does.
A few comments on the code that I can see:
(0) It's a bit weird that your graph seems to be defined such that the successors of a node are defined to be its parents (I would normally expect it to be predecessors). Is that intentional, or possibly a bug in your code?
(1) Graph.successors()--and, in fact, all of the Set-returning methods on Graph and related interfaces--will never return null. That is, they are contractually forbidden from doing so, so if you ever see one of those methods returning null, then it's a bug.
This means that you don't need the helper method.
(2) Your helper method will never return null, so you don't need to do a null check on that.
(3) This is redundant:
if (parents.isEmpty()) {
return 0;
} else if (!parents.isEmpty()) {
int count = 1;
...
}
and can be more concisely expressed as:
if (parents.isEmpty()) {
return 0;
}
int count = 1;
...
(4) You can probably get rid of that if statement entirely if you initialize count to 0.
My best guess is that by "depth of a node" you mean "unweighted shortest-path distance from a given start node to a given target node". (If that's not what you mean, please clarify.) If that's what you want, then we have a utility method we haven't released yet which does that. It's unreleased mostly because there are some definitional questions that we haven't sorted out yet.
Is this utility method still in the works? Or is abandoned code publicly available? Pathfinding is a common graph use case so weighted shortest path algo (e.g. Dijkstra) would be useful as well. Incidentally, it'd be easier for users to "roll their own" [unweighted] solutions if Traverser returned paths instead of nodes (i.e. Iterable<List<N>> breadthFirst(N startNode)).
