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 */
020package org.sonar.graph;
021
022public 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}