Class NaiveLcaFinder<V,E>
- java.lang.Object
-
- org.jgrapht.alg.NaiveLcaFinder<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
public class NaiveLcaFinder<V,E> extends java.lang.Object
Find the Lowest Common Ancestor of a directed graph.Find the LCA, defined as Let G = (V, E) be a DAG, and let x, y ∈ V . Let G x,y be the subgraph of G induced by the set of all common ancestors of x and y. Define SLCA (x, y) to be the set of out-degree 0 nodes (leafs) in G x,y . The lowest common ancestors of x and y are the elements of SLCA (x, y). This naive algorithm simply starts at a and b, recursing upwards to the root(s) of the DAG. Wherever the recursion paths cross we have found our LCA. from http://www.cs.sunysb.edu/~bender/pub/JALG05-daglca.pdf. The algorithm:
1. Start at each of nodes you wish to find the lca for (a and b) 2. Create sets aSet containing a, and bSet containing b 3. If either set intersects with the union of the other sets previous values (i.e. the set of notes visited) then that intersection is LCA. if there are multiple intersections then the earliest one added is the LCA. 4. Repeat from step 3, with aSet now the parents of everything in aSet, and bSet the parents of everything in bSet 5. If there are no more parents to descend to then there is no LCA
The rationale for this working is that in each iteration of the loop we are considering all the ancestors of a that have a path of length n back to a, where n is the depth of the recursion. The same is true of b.We start by checking if a == b.
if not we look to see if there is any intersection between parents(a) and (parents(b) union b) (and the same with a and b swapped)
if not we look to see if there is any intersection between parents(parents(a)) and (parents(parents(b)) union parents(b) union b) (and the same with a and b swapped)
continuesThis means at the end of recursion n, we know if there is an LCA that has a path of <=n to a and b. Of course we may have to wait longer if the path to a is of length n, but the path to b>n. at the first loop we have a path of 0 length from the nodes we are considering as LCA to their respective children which we wish to find the LCA for.
-
-
Field Summary
Fields Modifier and Type Field Description private DirectedGraph<V,E>
graph
-
Constructor Summary
Constructors Constructor Description NaiveLcaFinder(DirectedGraph<V,E> graph)
Create a new instance of the native LCA finder.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private java.util.Set<V>
allParents(java.util.Set<V> vertexSet)
Find the immediate parents of every item in the given set, and return a set containing all those parentsprivate V
findLca(java.util.Set<V> aSet, java.util.Set<V> bSet, java.util.LinkedHashSet<V> aSeenSet, java.util.LinkedHashSet<V> bSeenSet)
Recurse through the descendants of aSet and bSet looking for the LCA of a and b, which are members of sets aSeenSet and bSeenSet respectively, along with all elements on the paths from every member of aSet and bSetV
findLca(V a, V b)
Return the first found LCA of a and bjava.util.Set<V>
findLcas(V a, V b)
Return all the LCA of a and b.private V
overlappingMember(java.util.Set<V> x, java.util.Set<V> y)
Return a single vertex that is both in x and y.
-
-
-
Field Detail
-
graph
private DirectedGraph<V,E> graph
-
-
Constructor Detail
-
NaiveLcaFinder
public NaiveLcaFinder(DirectedGraph<V,E> graph)
Create a new instance of the native LCA finder.- Parameters:
graph
- the input graph
-
-
Method Detail
-
findLca
public V findLca(V a, V b)
Return the first found LCA of a and b- Parameters:
a
- the first element to find LCA forb
- the other element to find the LCA for- Returns:
- the first found LCA of a and b, or null if there is no LCA.
-
findLcas
public java.util.Set<V> findLcas(V a, V b)
Return all the LCA of a and b. Currently not implemented- Parameters:
a
- the first element to find LCA forb
- the other element to find the LCA for- Returns:
- the set of all LCA of a and b, or empty set if there is no LCA.
-
findLca
private V findLca(java.util.Set<V> aSet, java.util.Set<V> bSet, java.util.LinkedHashSet<V> aSeenSet, java.util.LinkedHashSet<V> bSeenSet)
Recurse through the descendants of aSet and bSet looking for the LCA of a and b, which are members of sets aSeenSet and bSeenSet respectively, along with all elements on the paths from every member of aSet and bSet
-
allParents
private java.util.Set<V> allParents(java.util.Set<V> vertexSet)
Find the immediate parents of every item in the given set, and return a set containing all those parents- Parameters:
vertexSet
- the set of vertex to find parents of- Returns:
- a set of every parent of every vertex passed in
-
overlappingMember
private V overlappingMember(java.util.Set<V> x, java.util.Set<V> y)
Return a single vertex that is both in x and y. If there is more than one then select the first element from the iterator returned from y, after all the elements of x have been removed. this allows an orderedSet to be passed in to give predictable results.- Parameters:
x
- set containing vertexy
- set containing vertex, which may be ordered to give predictable results- Returns:
- the first element of y that is also in x, or null if no such element
-
-