1 /*
2 * Copyright (c) 2002-2020, City of Paris
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright notice
10 * and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright notice
13 * and the following disclaimer in the documentation and/or other materials
14 * provided with the distribution.
15 *
16 * 3. Neither the name of 'Mairie de Paris' nor 'Lutece' nor the names of its
17 * contributors may be used to endorse or promote products derived from
18 * this software without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
21 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE
24 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
25 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
26 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
27 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
28 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
30 * POSSIBILITY OF SUCH DAMAGE.
31 *
32 * License 1.0
33 */
34 package fr.paris.lutece.plugins.utils.algo;
35
36 import java.util.ArrayList;
37 import java.util.List;
38 import java.util.Map;
39
40 /**
41 * Algorithm that will detect if a directed graph has a cycle. <br>
42 * A -> B -> C : OK <br>
43 * A -> B -> A : KO <br>
44 */
45 public class DetectCycleAlgo
46 {
47 private final Map<Integer, List<Integer>> _graph;
48
49 public DetectCycleAlgo( Map<Integer, List<Integer>> graph )
50 {
51 this._graph = graph;
52 }
53
54 public boolean hasCycle( )
55 {
56 List<Integer> visited = new ArrayList<>( );
57 for ( Integer i : _graph.keySet( ) )
58 {
59 if ( hasCycle( i, visited ) )
60 {
61 return true;
62 }
63 }
64 return false;
65 }
66
67 /**
68 * Check to see if the current node has already been visisted. <br>
69 * If not, it will check the children of the current node.
70 *
71 * @param node
72 * current node
73 * @param visited
74 * list of already visited nodes
75 * @return true if a cycle is detected
76 */
77 private boolean hasCycle( int node, List<Integer> visited )
78 {
79 if ( visited.contains( node ) )
80 {
81 return true;
82 }
83 visited.add( node );
84 if ( _graph.get( node ) != null )
85 {
86 for ( Integer nextNode : _graph.get( node ) )
87 {
88 if ( hasCycle( nextNode, visited ) )
89 {
90 return true;
91 }
92 }
93 }
94 visited.remove( visited.size( ) - 1 );
95 return false;
96 }
97 }