code: package it.unibz.inf.ontop.spec.ontology.impl;
  
  /*
   * #%L
   * ontop-reformulation-core
   * %%
   * Copyright (C) 2009 - 2014 Free University of Bozen-Bolzano
   * %%
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   * 
   *      http://www.apache.org/licenses/LICENSE-2.0
   * 
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   * #L%
   */
  
  
  import com.google.common.collect.ImmutableSet;
  import it.unibz.inf.ontop.spec.ontology.Equivalences;
  import org.jgrapht.DirectedGraph;
  
  import java.util.*;
  
  
  /**
   * Allows obtaining the strongly connected components of a directed graph.
   *
   * The implemented algorithm follows Cheriyan-Mehlhorn/Gabow's algorithm
   * Presented in Path-based depth-first search for strong and biconnected components by Gabow (2000).
   * The running time is order of O(|V|+|E|)
   *
   * TODO: replace by GabowStrongConnectivityInspector (from an updated JGraphT)
   *
   *
   */
  
  public class GabowSCC<V, E>
  {
      //~ Instance fields --------------------------------------------------------
  
      // the graph to compute the strongly connected sets 
      private final DirectedGraph<V, E> graph;
  
      // stores the vertices
      private Deque<VertexNumber<V>> stack = new ArrayDeque<VertexNumber<V>>();
      
      // the result of the computation, cached for future calls
      private List<Equivalences<V>> stronglyConnectedSets;
  
      // maps vertices to their VertexNumber object
      private Map<V, VertexNumber<V>> vertexToVertexNumber;
      
      //store the numbers
      private Deque<Integer> B = new ArrayDeque<Integer>();
      
      //number of vertexes
      private int c; 
  
      //~ Constructors -----------------------------------------------------------
  
      /**
       * The constructor of  GabowSCC class.
       *
       * @param directedGraph the graph to inspect
       *
       * @throws IllegalArgumentException
       */
      public GabowSCC(DirectedGraph<V, E> directedGraph)
      {
          assert (directedGraph != null);
          
          graph = directedGraph;
          vertexToVertexNumber = null;
          
          stronglyConnectedSets = null;        
      }
  
      //~ Methods ----------------------------------------------------------------
  
      /**
       * Returns the graph inspected 
       *
       * @return the graph inspected 
       */
      public DirectedGraph<V, E> getGraph() {
          return graph;
      }
  
      /**
       * Returns true if the graph instance is strongly connected.
       *
       * @return true if the graph is strongly connected, false otherwise
       */
      public boolean isStronglyConnected() {
          return stronglyConnectedSets().size() == 1;
      }
  
      /**
       * Computes a {@link List} of {@link Set}s, where each set contains vertices
       * which together form a strongly connected component within the given
       * graph.
       *
       * @return <code>List</code> of <code>EquivalanceClass</code>es containing the strongly
       * connected components
       */
      public List<Equivalences<V>> stronglyConnectedSets()
      {
          if (stronglyConnectedSets == null) {
              
              stronglyConnectedSets = new Vector<>();
  
              // create VertexData objects for all vertices, store them
              createVertexNumber();
  
              // perform  DFS
              for (VertexNumber<V> data : vertexToVertexNumber.values()) {           	
                  if (data.getNumber() == 0) {
                      dfsVisit(graph, data);
                  }
              }
                    
              vertexToVertexNumber = null;
              stack = null;
              B = null;
          }
  
          return stronglyConnectedSets;
      }
  
     
      /*
       * Creates a VertexNumber object for every vertex in the graph and stores
       * them in a HashMap.
       */
      
      private void createVertexNumber()
      {
      	c = graph.vertexSet().size();
          vertexToVertexNumber = new HashMap<>(c);
  
          for (V vertex : graph.vertexSet()) {
              vertexToVertexNumber.put(vertex, new VertexNumber<V>(vertex, 0));            
          }
          
          stack = new ArrayDeque<>(c);
          B = new ArrayDeque<>(c);
      }
  
      /*
       * The subroutine of DFS. 
       */
      private void dfsVisit(DirectedGraph<V, E> visitedGraph, VertexNumber<V> v) 
      {	
      	 VertexNumber<V> w;
      	 stack.add(v);
      	 B.add(v.setNumber(stack.size() - 1));
      	
           // follow all edges
           for (E edge : visitedGraph.outgoingEdgesOf(v.getVertex())) {
          	 
          	 w =  vertexToVertexNumber.get(visitedGraph.getEdgeTarget(edge));
  
               if (w.getNumber() == 0) {
              	 dfsVisit(graph, w);
               }
               else { /*contract if necessary*/
              	 while (w.getNumber() < B.getLast()) 
              		 B.removeLast(); 
               } 
           }
           
           ImmutableSet.Builder<V> L = new ImmutableSet.Builder<>(); 
           if (v.getNumber() == (B.getLast())) { 
          	 /* number vertices of the next strong component */
          	 B.removeLast(); 
                
               c++;
               while (v.getNumber() <= (stack.size()-1)) {
              	 VertexNumber<V> r = stack.removeLast();
                   L.add(r.getVertex()); 
                   r.setNumber(c);
               } 
               stronglyConnectedSets.add(new Equivalences<V>(L.build())); 
           } 
      }
  
    
     
      
      private static final class VertexNumber<V>
      {
      	V vertex;
      	int number;
      	
      	private VertexNumber(V vertex, int number) {
      		this.vertex = vertex;
      		this.number = number;
      	}
  
      	int getNumber() {
      		return number;
      	}
  
      	V getVertex() {
      		return vertex;
      	}
      	
      	Integer setNumber(int n) {
      		return number=n;
      	}
      }
  }
  
  // End 
  