package de.peeeq.datastructures; import com.google.common.collect.Multimap; import java.util.HashSet; import java.util.List; import java.util.Set; import java.util.stream.Collectors; import java.util.stream.Stream; /** * */ public class TransitiveClosure { private final Multimap base; public TransitiveClosure(Multimap base) { this.base = base; } /** * returns all elements reachable from start (start is only included if it is reachable with > 0 steps) */ public List getAsList(T start) { return get(start).collect(Collectors.toList()); } /** * returns all elements reachable from start (start is only included if it is reachable with > 0 steps) */ public Stream get(T start) { Set visited = new HashSet<>(); return base.get(start).stream() .flatMap(c -> visit(c, visited)); } private Stream visit(T start, Set visited) { if (visited.contains(start)) { return Stream.empty(); } visited.add(start); return Stream.concat(Stream.of(start), base.get(start).stream() .flatMap(c -> visit(c, visited))); } }