As I've pointed out in the comment, this task is similar to the problem of finding the Lowest common ancestor, but according to the provided data sample the result not necessarily should be an ancestor, it could be one of the given nodes itself.
The solution provided below is based on the assumption that the provided example is correct.
Another important issue is that more than one Lowest common ancestor in the directed acyclic graph (see LCA article in Wikipedia)
Illustration from the Wikipedia:
Nodes (vertices) X and Y have two lowest common ancestors.
For that reason, I've the return type of the method getLCA to be the List<GraphNode> instead of GraphNode.
Algorithm
The overall approach is based on the Breadth first search algorithm. Until no common nodes has been found and there are still some unvisited ancestor nodes, the process of graph traversal continues.
The algorithm can be divided into the following steps:
Create a list of Queue (a separate queue for each given node) and populate every queue with a single node.
Similarly, create a list of Set (each set will correspond to a particular given node) and populate every set with a single node.
Then check whether result already present the sets (which would be the case if all provided initial nodes are identical). For that, we need to find an intersection of all sets.
Then a then in a loop lists of queues and sets would be updated and then a new attempt to generate the result will follow. Each set will contain one of the given node and all its encountered ancestors. And each will a single generation of ancestors generated at the previous cycle of BFS.
The graph traversal will continue until the resulting list is empty and at one of the queues is not empty.
Implementation
Graph class:
public class Graph {
private Map<String, GraphNode> nodeByValue = new HashMap<>();
public List<GraphNode> getLCA(GraphNode... nodes) {
List<GraphNode> commonNodes = new ArrayList<>();
if (nodes.length <= 1) return Arrays.asList(nodes);
List<Set<GraphNode>> seen = generateSets(nodes);
List<Queue<GraphNode>> queues = generateQueues(nodes);
updateCommonNodes(seen, commonNodes);
while (commonNodes.isEmpty() && hasNonEmptyQueue(queues)) {
addParentNodes(queues, seen);
updateCommonNodes(seen, commonNodes);
}
return commonNodes;
}
public void updateCommonNodes(List<Set<GraphNode>> sets,
List<GraphNode> commonNodes) {
commonNodes.addAll(sets.get(0)); // populating the list with elements contained in the first set
for (int i = 1; i < sets.size(); i++) {
if (commonNodes.isEmpty()) break; // there are no common nodes, no need to process other sets
commonNodes.retainAll(sets.get(i)); // generating intersection with other sets
}
}
public void addParentNodes(List<Queue<GraphNode>> queues,
List<Set<GraphNode>> sets) {
for (int i = 0; i < queues.size(); i++) {
Set<GraphNode> seen = sets.get(i);
Queue<GraphNode> currentGeneration = queues.get(i);
Queue<GraphNode> immediateAncestors = new ArrayDeque<>();
while (!currentGeneration.isEmpty()) {
GraphNode current = currentGeneration.remove();
for (GraphNode parent: current.getParents()) {
immediateAncestors.add(parent);
seen.add(parent);
}
}
// replacing current generation with ancestors
queues.set(i, immediateAncestors);
}
}
public boolean hasNonEmptyQueue(List<Queue<GraphNode>> queues) {
boolean hasNonEmpty = false;
for (Queue<GraphNode> queue: queues) {
if (!queue.isEmpty()) {
hasNonEmpty = true;
break;
}
}
return hasNonEmpty;
// or make use of the Stream IPA
// return queues.stream().anyMatch(queue -> !queue.isEmpty());
}
private List<Set<GraphNode>> generateSets(GraphNode[] nodes) {
List<Set<GraphNode>> sets = new ArrayList<>();
for (int i = 0; i < nodes.length; i++) {
Set<GraphNode> set = new HashSet<>();
set.add(nodes[i]);
sets.add(set);
}
return sets;
// or make use the Stream IPA
// return Arrays.stream(nodes).<Set<GraphNode>>map(node -> new HashSet<>(List.of(node))).toList();
}
private List<Queue<GraphNode>> generateQueues(GraphNode[] nodes) {
List<Queue<GraphNode>> queues = new ArrayList<>();
for (int i = 0; i < nodes.length; i++) {
Queue<GraphNode> queue = new ArrayDeque<>();
queue.add(nodes[i]);
queues.add(queue);
}
return queues;
// or make use of the Stream IPA
// return Arrays.stream(nodes).<Queue<GraphNode>>map(node -> new ArrayDeque<>(List.of(node))).toList();
}
// convinience method used in testing
public List<GraphNode> getLCA(String... nodes) {
GraphNode[] graphNodes = new GraphNode[nodes.length];
for (int i = 0; i < nodes.length; i++) {
graphNodes[i] = nodeByValue.get(nodes[i]);
}
return getLCA(graphNodes);
}
public void addNode(String nodeValue, String[] parents, String[] children) {
GraphNode[] parentNodes = new GraphNode[parents.length];
GraphNode[] childrenNodes = new GraphNode[children.length];
int pos = 0;
for (String parent: parents) {
nodeByValue.computeIfAbsent(parent, GraphNode::new);
parentNodes[pos++] = nodeByValue.get(parent);
}
pos = 0;
for (String child: children) {
nodeByValue.computeIfAbsent(child, GraphNode::new);
childrenNodes[pos++] = nodeByValue.get(child);
}
nodeByValue.computeIfAbsent(nodeValue, GraphNode::new)
.setParents(parentNodes)
.setChildren(childrenNodes);
}
static class GraphNode {
private final String value;
private GraphNode[] parents;
private GraphNode[] children;
public GraphNode(String value) {
this.value = value;
}
public GraphNode(String value, GraphNode[] parents, GraphNode[] children) {
this.value = value;
this.parents = parents;
this.children = children;
}
public String getValue() {
return value;
}
public GraphNode[] getParents() {
return parents;
}
public GraphNode[] getChildren() {
return children;
}
public GraphNode setParents(GraphNode[] parents) {
this.parents = parents;
return this;
}
public GraphNode setChildren(GraphNode[] children) {
this.children = children;
return this;
}
@Override
public String toString() {
return "GraphNode{ " + "val='" + value + " }";
}
}
}
main()
public static void main(String[] args) {
Graph graph = new Graph();
// initializing the graph
graph.addNode("A", new String[]{}, new String[]{"B", "D", "E"});
graph.addNode("B", new String[]{"A"}, new String[]{"C"});
graph.addNode("C", new String[]{"B", "D"}, new String[]{"D"});
graph.addNode("D", new String[]{"A"}, new String[]{"C", "E"});
graph.addNode("E", new String[]{"A", "D"}, new String[]{"F"});
graph.addNode("F", new String[]{"E"}, new String[]{});
System.out.println(graph.getLCA("C", "E"));
System.out.println(graph.getLCA("C", "E", "B"));
System.out.println(graph.getLCA("E", "F"));
System.out.println(graph.getLCA("A", "B", "C", "D"));
}
Output:
[GraphNode{ val='D }] // C, E
[GraphNode{ val='A }] // C, E, B
[GraphNode{ val='E }] // E, F
[GraphNode{ val='A }] // A, B, C, D
A link to Online Demo
