001    /*
002     * Sonar, open source software quality management tool.
003     * Copyright (C) 2008-2012 SonarSource
004     * mailto:contact AT sonarsource DOT com
005     *
006     * Sonar is free software; you can redistribute it and/or
007     * modify it under the terms of the GNU Lesser General Public
008     * License as published by the Free Software Foundation; either
009     * version 3 of the License, or (at your option) any later version.
010     *
011     * Sonar is distributed in the hope that it will be useful,
012     * but WITHOUT ANY WARRANTY; without even the implied warranty of
013     * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014     * Lesser General Public License for more details.
015     *
016     * You should have received a copy of the GNU Lesser General Public
017     * License along with Sonar; if not, write to the Free Software
018     * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
019     */
020    package org.sonar.graph;
021    
022    public final class DsmTopologicalSorter<V> {
023    
024      private final Dsm<V> dsm;
025      private int leftOrderedIndex;
026      private int rightOrderedIndex;
027    
028      private DsmTopologicalSorter(Dsm<V> dsm) {
029        this.dsm = dsm;
030        leftOrderedIndex = 0;
031        rightOrderedIndex = dsm.getDimension() - 1;
032      }
033    
034      public static <V> void sort(Dsm<V> dsm) {
035        DsmTopologicalSorter<V> partitionner = new DsmTopologicalSorter<V>(dsm);
036        boolean dsmCanBeSorted = true;
037        while (dsmCanBeSorted) {
038          boolean dsmCanBeSortedOnLeft = partitionner.pushToLeftVerticesWithoutIncomingEdges();
039          boolean dsmCanBeSortedOnRight = partitionner.pushToRightVerticesWithoutOutgointEdges();
040          dsmCanBeSorted = dsmCanBeSortedOnLeft || dsmCanBeSortedOnRight;
041        }
042        boolean isCyclicGraph = (partitionner.leftOrderedIndex < partitionner.rightOrderedIndex);
043        if (isCyclicGraph) {
044          throw new IllegalStateException("Can't sort a cyclic graph.");
045        }
046      }
047    
048      private boolean pushToLeftVerticesWithoutIncomingEdges() {
049        boolean permutationsDone = false;
050        for (int i = leftOrderedIndex; i <= rightOrderedIndex; i++) {
051          if (dsm.getNumberOfIncomingEdges(i, leftOrderedIndex, rightOrderedIndex) == 0) {
052            dsm.permute(i, leftOrderedIndex);
053            leftOrderedIndex++;
054            permutationsDone = true;
055          }
056        }
057        return permutationsDone;
058      }
059    
060      private boolean pushToRightVerticesWithoutOutgointEdges() {
061        boolean permutationsDone = false;
062        for (int i = leftOrderedIndex; i <= rightOrderedIndex; i++) {
063          if (dsm.getNumberOfOutgoingEdges(i, leftOrderedIndex, rightOrderedIndex) == 0) {
064            dsm.permute(i, rightOrderedIndex);
065            rightOrderedIndex--;
066            permutationsDone = true;
067          }
068        }
069        return permutationsDone;
070      }
071    }