parametric/bundles/org.eclipse.papyrus.moka.parametric/src/org/eclipse/papyrus/moka/parametric/utils/Graph.java

/*****************************************************************************
 * Copyright (c) 2017 CEA LIST.
 *
 *
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License 2.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-2.0/
 *
 * SPDX-License-Identifier: EPL-2.0
 *
 * Contributors:
 *  CEA LIST - Initial API and implementation
 *
 *****************************************************************************/
package org.eclipse.papyrus.moka.parametric.utils;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class Graph<T> {
	private int v;
	private LinkedList<Integer> adj[];
	protected Map<Integer, T> index2Object = new HashMap<Integer, T>() ;
	protected Map<T, Integer> object2Index = new HashMap<T, Integer>() ;

	public Graph(Set<T> vertices, Map<T, Set<T>> edges) {
		this.v = vertices.size() ;
		adj = new LinkedList[v];
		for (int i=0; i<this.v; ++i) {
			adj[i] = new LinkedList();
		} 
		int i = 0 ;
		for (T obj : vertices) {
			index2Object.put(i, obj) ;
			object2Index.put(obj, i) ;
			i++ ;
		}
		for (T obj : vertices) {
			int objIndex = object2Index.get(obj) ;
			if (edges.get(obj) != null) {
				for (T connectedTo : edges.get(obj)) {
					addEdge(objIndex, object2Index.get(connectedTo));
				}
			}
		}

	}

	//Constructor
	public Graph(int v) {
		this.v = v;
		adj = new LinkedList[v];
		for (int i=0; i<v; ++i) {
			adj[i] = new LinkedList();
		}
	}

	// Function to add an edge into the graph
	void addEdge(int v,int w) {
		adj[v].add(w);
	}

	// A recursive function used by topologicalSort
	void topologicalSortUtil(int v, boolean visited[], Stack<Integer> stack) {
		// Mark the current node as visited.
		visited[v] = true;
		Integer i;

		// Recur for all the vertices adjacent to this
		// vertex
		Iterator<Integer> it = adj[v].iterator();
		while (it.hasNext()) {
			i = it.next();
			if (!visited[i]) {
				topologicalSortUtil(i, visited, stack);
			}
		}

		// Push current vertex to stack which stores result
		stack.push(new Integer(v));
	}

	// The function to do Topological Sort. It uses
	// recursive topologicalSortUtil()
	public List<T> topologicalSort() {
		Stack<Integer> stack = new Stack<Integer>();

		// Mark all the vertices as not visited
		boolean visited[] = new boolean[this.v];
		for (int i = 0; i < this.v; i++)
			visited[i] = false;

		// Call the recursive helper function to store
		// Topological Sort starting from all vertices
		// one by one
		for (int i = 0; i < this.v; i++) {
			if (visited[i] == false) {
				topologicalSortUtil(i, visited, stack);
			}
		}

		// Print contents of stack
		//while (stack.empty()==false) {
		//	System.out.print(stack.pop() + " ");
		//}
		List<T> sorted = new ArrayList<T>() ;
		while (stack.empty()==false) {
			int index = stack.pop() ;
			T obj = index2Object.get(index) ;
			sorted.add(obj) ;
		}
		return sorted ;
	}
	
	// This function is a variation of DFSUytil() in http://www.geeksforgeeks.org/archives/18212
	public boolean isCyclicUtil(int v, boolean visited[], boolean recStack[])
	{
		Integer i ;
	    if(visited[v] == false)
	    {
	        // Mark the current node as visited and part of recursion stack
	        visited[v] = true;
	        recStack[v] = true;
	 
	        // Recur for all the vertices adjacent to this vertex
	        Iterator<Integer> it = adj[v].iterator();
			while (it.hasNext()) {
				i = it.next();
	            if ( !visited[i] && isCyclicUtil(i, visited, recStack) )
	                return true;
	            else if (recStack[i])
	                return true;
	        }
	 
	    }
	    recStack[v] = false;  // remove the vertex from recursion stack
	    return false;
	}
	 
	// Returns true if the graph contains a cycle, else false.
	// This function is a variation of DFS() in http://www.geeksforgeeks.org/archives/18212
	public boolean isCyclic()
	{
	    // Mark all the vertices as not visited and not part of recursion
	    // stack
	    boolean[] visited = new boolean[v];
	    boolean[] recStack = new boolean[v];
	    for(int i = 0; i < v; i++)
	    {
	        visited[i] = false;
	        recStack[i] = false;
	    }
	 
	    // Call the recursive helper function to detect cycle in different
	    // DFS trees
	    for(int i = 0; i < v; i++)
	        if (isCyclicUtil(i, visited, recStack))
	            return true;
	 
	    return false;
	}
	
}