Returns true iff graph has at least one cycle.
(Graph<?> graph)
| 42 | |
| 43 | |
| 44 | public static boolean isCyclic(Graph<?> graph) { |
| 45 | // TODO(user): Implement an algorithm that also works on undirected graphs. |
| 46 | // For instance, we should keep track of the edge used to reach a node to avoid |
| 47 | // reusing it (making a cycle by getting back to that node). Also, parallel edges |
| 48 | // will need to be carefully handled for undirected graphs. |
| 49 | checkArgument(graph.isDirected(), "isCyclic() currently only works on directed graphs"); |
| 50 | Map<Object, NodeVisitState> nodeToVisitState = Maps.newHashMap(); |
| 51 | for (Object node : graph.nodes()) { |
| 52 | if (nodeToVisitState.get(node) == null) { |
| 53 | if (isSubgraphCyclic(graph, nodeToVisitState, node)) { |
| 54 | return true; |
| 55 | } |
| 56 | } |
| 57 | } |
| 58 | return false; |
| 59 | } |
| 60 | |
| 61 | /** |
| 62 | * Returns true iff there is a cycle in the subgraph of {@code graph} reachable from |
nothing calls this directly
no test coverage detected