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 import java.util.Collection;
023 import java.util.Collections;
024 import java.util.Set;
025
026 public class Dsm<V> {
027
028 private V[] vertices;
029 private DsmCell[][] cells;
030 private int dimension;
031 private DirectedGraphAccessor<V, ? extends Edge<V>> graph;
032
033 public Dsm(DirectedGraphAccessor<V, ? extends Edge<V>> graph, Collection<V> vertices, Set<Edge> feedbackEdges) {
034 this.graph = graph;
035 this.dimension = vertices.size();
036 this.cells = new DsmCell[dimension][dimension];
037 initVertices(vertices);
038 initCells(feedbackEdges);
039 }
040
041 public Dsm(DirectedGraphAccessor<V, ? extends Edge<V>> acyclicGraph, Set<Edge> feedbackEdges) {
042 this(acyclicGraph, acyclicGraph.getVertices(), feedbackEdges);
043 }
044
045 public Dsm(DirectedGraphAccessor<V, ? extends Edge<V>> acyclicGraph) {
046 this(acyclicGraph, acyclicGraph.getVertices(), Collections.<Edge>emptySet());
047 }
048
049 private void initCells(Set<Edge> feedbackEdges) {
050 for (int x = 0; x < dimension; x++) {
051 for (int y = 0; y < dimension; y++) {
052 V from = vertices[x];
053 V to = vertices[y];
054
055 Edge<V> edge = graph.getEdge(from, to);
056 boolean isFeedbackEdge = (edge != null && feedbackEdges.contains(edge));
057 DsmCell cell = new DsmCell(edge, isFeedbackEdge);
058 cells[x][y] = cell;
059 }
060 }
061 }
062
063 private void initVertices(Collection<V> verticesCol) {
064 this.vertices = (V[]) new Object[dimension];
065 int i = 0;
066 for (V vertex : verticesCol) {
067 vertices[i] = vertex;
068 i++;
069 }
070 }
071
072 public V getVertex(int rowIndex) {
073 return vertices[rowIndex];
074 }
075
076 public int getDimension() {
077 return dimension;
078 }
079
080 public void permute(int fromIndex, int toIndex) {
081 if (fromIndex != toIndex) {
082 checkIndicesBoudaries(fromIndex, toIndex);
083 permuteVertice(fromIndex, toIndex);
084 permuteColumns(fromIndex, toIndex);
085 permuteRows(fromIndex, toIndex);
086 }
087 }
088
089 private void checkIndicesBoudaries(int... indices) {
090 for (int index : indices) {
091 if (index < 0 || index >= dimension) {
092 StringBuilder builder = new StringBuilder("DSM contains the following vertices : ");
093 for (V vertex : vertices) {
094 builder.append(vertex.toString()).append(" | ");
095 }
096 builder.append(". Trying to reach index ").append(index);
097 throw new ArrayIndexOutOfBoundsException(builder.toString());
098 }
099 }
100 }
101
102 private void permuteVertice(int fromIndex, int toIndex) {
103 V fromVertex = vertices[fromIndex];
104 V toVertex = vertices[toIndex];
105 vertices[fromIndex] = toVertex;
106 vertices[toIndex] = fromVertex;
107 }
108
109 private void permuteRows(int fromYIndex, int toYIndex) {
110 for (int x = 0; x < dimension; x++) {
111 permuteCells(x, fromYIndex, x, toYIndex);
112 }
113 }
114
115 private void permuteColumns(int fromXIndex, int toXIndex) {
116 for (int y = 0; y < dimension; y++) {
117 permuteCells(fromXIndex, y, toXIndex, y);
118 }
119 }
120
121 private void permuteCells(int fromXIndex, int fromYIndex, int toXIndex, int toYIndex) {
122 DsmCell fromCell = cells[fromXIndex][fromYIndex];
123 DsmCell toCell = cells[toXIndex][toYIndex];
124 cells[toXIndex][toYIndex] = fromCell;
125 cells[fromXIndex][fromYIndex] = toCell;
126 }
127
128 public int getNumberOfIncomingEdges(int y, int from, int to) {
129 int incomingEdges = 0;
130 for (int x = from; x <= to; x++) {
131 DsmCell cell = cells[x][y];
132 if (cell.getWeight() != 0 && !cell.isFeedbackEdge()) {
133 incomingEdges++;
134 }
135 }
136 return incomingEdges;
137 }
138
139 public int getNumberOfOutgoingEdges(int x, int from, int to) {
140 int outgoingEdges = 0;
141 for (int y = from; y <= to; y++) {
142 DsmCell cell = cells[x][y];
143 if (cell.getWeight() != 0 && !cell.isFeedbackEdge()) {
144 outgoingEdges++;
145 }
146 }
147 return outgoingEdges;
148 }
149
150 public DsmCell getCell(int x, int y) {
151 return cells[x][y];
152 }
153
154 public V[] getVertices() {
155 V[] verticesCopy = (V[]) new Object[vertices.length];
156 System.arraycopy(vertices, 0, verticesCopy, 0, vertices.length);
157 return verticesCopy;
158 }
159 }