Algorithme de gestion de dépendance [2/2]

Voic donc un exemple d'implémentation. A la différence de l'algorithme, l'implémentation ci-dessous prend la première entrée sans dépendance et la supprimer, puis recommence.

import java.util.ArrayList;
import java.util.List;

public class Graph {
    /**
     * List of file and dependency
     */
    private List vertexList = new ArrayList();

    /**
     * Dependancy matrix
     */
    private boolean matrix[][] ;

    public Graph() {
    }

    /**
     * Add artefact or dependency
     */
    public void addItem(String label) {
        vertexList.add(label);
    }

    /**
     * Add link of dependency
     */
    public void addDependency(final String artefact, final String dependency) {

        int artefactIndex = vertexList.indexOf(artefact);
        int dependencyIndex = vertexList.indexOf(dependency);

        if (matrix == null) {
            matrix = new boolean[vertexList.size()][vertexList.size()];
        }

        matrix[artefactIndex][dependencyIndex] = true ;
    }

    /**
     * Return list to include
     */
    public List getDependencyList() throws Exception
    {
        // List of dependency to be include
        final List dependencyList = new ArrayList(vertexList.size()) ;
        // Current item without dependency
        int currentItem ;
        
        // Check all item
        while (vertexList.size() > 0)
        {
            // Get a vertex with no successors, or -1
            currentItem= getIndexOfItemWithoutDependency() ;
            
            // must be a cycle
            if (currentItem == -1) 
            {
                throw new Exception("ERROR: Graph has cycles") ;
            }
            
            dependencyList.add(vertexList.get(currentItem)) ;

            // delete vertex
            removeItem(currentItem) ; 
        }

        return dependencyList ;
    }

    /**
     * Return first item without any dependency
     * 
     * @return -1 if error (cycles) or index of item
     */
    public int getIndexOfItemWithoutDependency() 
    {
        boolean hasDependency = false ;

        final int numVerts = vertexList.size();

        for (int row = 0; row < numVerts; row++) {
        
            // If no dependency, hasDependency = false
            for (int col = 0; col < numVerts && !hasDependency; col++) {
                hasDependency = matrix[row][col] ;
            }
            
            if (!hasDependency) {
                return row;
            }
        }
        
        // All item have dependency. Error !
        return -1 ;
    }

    /**
     * Remove item
     */
    public void removeItem(final int itemIndex) {
        final int numVerts = vertexList.size();

        vertexList.remove(itemIndex);

        // Because we are in array, don't move last cal/row
        if (itemIndex < numVerts - 1) 
        {
            for (int row = itemIndex; row < numVerts; row++) {
                moveRowUp(row, numVerts) ;
            }

            for (int col = itemIndex; col < numVerts; col++) {
                moveColLeft(col, numVerts) ;
            }
        }
    }

    /**
     * Remove row, and copy all in up
     */
    private void moveRowUp(int row, int length) {
        for (int col = 0; col < length; col++) {
            matrix[row][col] = matrix[row + 1][col] ;
        }
    }

    /**
     * Remove col and remove left
     */
    private void moveColLeft(int col, int length) {
        for (int row = 0; row < length; row++) {
            matrix[row][col] = matrix[row][col + 1] ;
        }
    }

    public static void main(String[] args) throws Exception {
        Graph g = new Graph();
        g.addItem("A"); // 0
        g.addItem("B"); // 1
        g.addItem("C"); // 2
        g.addItem("D"); // 3
        g.addItem("E"); // 4
        g.addItem("F"); // 5
        g.addItem("G"); // 6
        g.addItem("H"); // 7

        g.addDependency("A", "D"); // AD
        g.addDependency("A", "E"); // AE
        g.addDependency("B", "E"); // BE
        g.addDependency("C", "F"); // CF
        g.addDependency("D", "G"); // DG
        g.addDependency("E", "G"); // EG
        g.addDependency("F", "H"); // FH
        g.addDependency("G", "H"); // GH

        for (String s : g.getDependencyList()) {
            System.out.println(s);
        }
    }
}