Coverage Report - com.sdmetrics.metrics.StronglyConnectedComponents - www.sdmetrics.com
 
Classes in this File Line Coverage Branch Coverage Complexity
StronglyConnectedComponents
100%
55/55
100%
38/38
3,714
StronglyConnectedComponents$Graph
N/A
N/A
3,714
StronglyConnectedComponents$NodeInfo
100%
4/4
N/A
3,714
 
 1  
 /*
 2  
  * SDMetrics Open Core for UML design measurement
 3  
  * Copyright (c) Juergen Wuest
 4  
  * To contact the author, see <http://www.sdmetrics.com/Contact.html>.
 5  
  * 
 6  
  * This file is part of the SDMetrics Open Core.
 7  
  * 
 8  
  * SDMetrics Open Core is free software: you can redistribute it and/or modify
 9  
  * it under the terms of the GNU Affero General Public License as
 10  
  * published by the Free Software Foundation, either version 3 of the
 11  
  * License, or (at your option) any later version.
 12  
     
 13  
  * SDMetrics Open Core is distributed in the hope that it will be useful,
 14  
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
 15  
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 16  
  * GNU Affero General Public License for more details.
 17  
  *
 18  
  * You should have received a copy of the GNU Affero General Public License
 19  
  * along with SDMetrics Open Core.  If not, see <http://www.gnu.org/licenses/>.
 20  
  *
 21  
  */
 22  
 package com.sdmetrics.metrics;
 23  
 
 24  
 import java.util.ArrayList;
 25  
 import java.util.Collection;
 26  
 import java.util.HashMap;
 27  
 import java.util.LinkedList;
 28  
 
 29  
 /**
 30  
  * Calculates the strongly connected components of a directed graph. The
 31  
  * algorithm used to calculate the strongly connected components is not
 32  
  * self-explanatory, but is described in most "algorithms and data structures
 33  
  * 101" text books. This implementation is based on T. Ottmann, P. Widmayer,
 34  
  * "Algorithmen und Datenstukturen", BI Wissenschaftsverlag, 1991, pp. 566-570.
 35  
  * The complexity of the algorithm is O(|N|+|E|) (N=set of nodes, E=set of
 36  
  * edges).
 37  
  * 
 38  
  * @param <T> Type of the nodes on the graph
 39  
  */
 40  
 
 41  18
 public class StronglyConnectedComponents<T> {
 42  
 
 43  
         /**
 44  
          * Provides the strongly connected components algorithm with the information
 45  
          * it requires about the directed graph.
 46  
          * 
 47  
          * @param <T> Type of the nodes on the graph
 48  
          */
 49  
         public interface Graph<T> {
 50  
                 /**
 51  
                  * Retrieves the set of nodes of the graph.
 52  
                  * 
 53  
                  * @return A collection of objects that constitute the nodes of the
 54  
                  *         graph.
 55  
                  */
 56  
                 Collection<T> getNodes();
 57  
 
 58  
                 /**
 59  
                  * Obtains, for a node, the set of nodes to which it has an outgoing
 60  
                  * edge.
 61  
                  * 
 62  
                  * @param node The node for which to obtain the neighbor nodes.
 63  
                  * @return A collection of the neighbor nodes to which <code>node</code>
 64  
                  *         has an outgoing edge.
 65  
                  * @throws SDMetricsException if the neighbors for a node could not be
 66  
                  *         determined.
 67  
                  */
 68  
                 Collection<T> getNeighbors(T node) throws SDMetricsException;
 69  
         }
 70  
 
 71  
         /** The graph to operate on. */
 72  
         private Graph<T> graph;
 73  
 
 74  
         /** Information the CC algorithm tracks for each node of the graph. */
 75  232
         static class NodeInfo {
 76  
                 /** Indicates if the node is currently stacked. */
 77  116
                 boolean stacked = false;
 78  
                 /**
 79  
                  * Depth-first index (DFI) of each graph node; -1 means not yet visited.
 80  
                  */
 81  116
                 int dfi = -1;
 82  
                 /** minimum DFI of all nodes in a cycle. */
 83  
                 int cmd;
 84  
 
 85  
                 /**
 86  
                  * Index of this node's connected component. Used only for reporting of
 87  
                  * results.
 88  
                  */
 89  116
                 int ccIndex = -1;
 90  
         }
 91  
 
 92  
         /** Stores one node info for each node. */
 93  
         private HashMap<T, NodeInfo> infoMap;
 94  
         /** Stores the connected components. */
 95  
         private ArrayList<Collection<T>> connectedComponents;
 96  
 
 97  
         /** stack of nodes not yet assigned to any SCC */
 98  9
         private LinkedList<T> stack = new LinkedList<T>();
 99  
 
 100  
         /** Current depth-first-index */
 101  
         private int cdfi;
 102  
         /** Minimum size of a connected component to be reported. */
 103  9
         private int minCCSize = 0;
 104  
         /**
 105  
          * Indicates if isolated nodes are to be reported only if they have an edge
 106  
          * to themselves.
 107  
          */
 108  
         private boolean countIsolatedIfSelfref;
 109  
 
 110  
         /**
 111  
          * Gets the number of strongly connected components found.
 112  
          * 
 113  
          * @return The number N of strongly connected components. The components are
 114  
          *         addressed by an index, valid indices run from 0 to N-1.
 115  
          */
 116  
         public int getConnectedComponentCount() {
 117  9
                 return connectedComponents.size();
 118  
         }
 119  
 
 120  
         /**
 121  
          * Gets the node set for a strongly connected component.
 122  
          * 
 123  
          * @param index Index of the strongly connected component.
 124  
          * @return The nodes of the strongly connected component.
 125  
          */
 126  
         public Collection<T> getConnectedComponent(int index) {
 127  16
                 return connectedComponents.get(index);
 128  
         }
 129  
 
 130  
         /**
 131  
          * Gets the index of the strongly connected component of a node.
 132  
          * 
 133  
          * @param node The node of interest.
 134  
          * @return Index of the strongly connected component that contains the node,
 135  
          *         or -1 if the node is not part of a strongly connected component.
 136  
          */
 137  
         public int getIndexFor(T node) {
 138  22
                 NodeInfo ni = infoMap.get(node);
 139  22
                 return ni == null ? -1 : infoMap.get(node).ccIndex;
 140  
         }
 141  
 
 142  
         /**
 143  
          * Calculates the strongly connected components for a graph.
 144  
          * 
 145  
          * @param inputGraph The graph to operate on.
 146  
          * @param minSize The minimum size a strongly connected component must have
 147  
          *        to be reported by the algorithm.
 148  
          * @param isoIfSelfref When this is set to <code>true</code>, isolated nodes
 149  
          *        ("connected components of size one") are reported only if the node
 150  
          *        has an edge to itself. When set to <code>false</code>, such
 151  
          *        connected components are always reported. If minSize is greater
 152  
          *        than one, this parameter is ignored.
 153  
          * @throws SDMetricsException The set of neighbors of a node could not be
 154  
          *         calculated.
 155  
          */
 156  
         public void calculateConnectedComponents(Graph<T> inputGraph, int minSize,
 157  
                         boolean isoIfSelfref) throws SDMetricsException {
 158  11
                 this.graph = inputGraph;
 159  11
                 this.minCCSize = minSize;
 160  11
                 this.countIsolatedIfSelfref = isoIfSelfref;
 161  
 
 162  11
                 Collection<T> nodes = graph.getNodes();
 163  11
                 infoMap = new HashMap<T, NodeInfo>(nodes.size());
 164  138
                 for (T node : nodes) {
 165  116
                         infoMap.put(node, new NodeInfo());
 166  
                 }
 167  11
                 connectedComponents = new ArrayList<Collection<T>>();
 168  
 
 169  11
                 cdfi = 0;
 170  11
                 stack.clear();
 171  
 
 172  138
                 for (T node : nodes)
 173  116
                         searchSCC(node);
 174  
 
 175  
                 // Map each node to its connected component
 176  40
                 for (int i = 0; i < connectedComponents.size(); i++) {
 177  29
                         Collection<T> cc = connectedComponents.get(i);
 178  111
                         for (T node : cc)
 179  53
                                 infoMap.get(node).ccIndex = i;
 180  
                 }
 181  11
         }
 182  
 
 183  
         /**
 184  
          * Searches the SCC of a node.
 185  
          * 
 186  
          * @param node The node whose SCC to search.
 187  
          * @throws SDMetricsException The neighbors of the node could not be
 188  
          *         calculated.
 189  
          */
 190  
         private void searchSCC(T node) throws SDMetricsException {
 191  153
                 NodeInfo ni = infoMap.get(node);
 192  153
                 if (ni.dfi >= 0)
 193  37
                         return; // already visited => do nothing
 194  
 
 195  116
                 cdfi++;
 196  116
                 ni.dfi = cdfi;
 197  116
                 ni.cmd = cdfi;
 198  116
                 stack.add(node);
 199  116
                 ni.stacked = true;
 200  116
                 boolean selfReferential = false;
 201  
 
 202  
                 // iterate over connected nodes, depth-first search
 203  319
                 for (T neighbor : graph.getNeighbors(node)) {
 204  87
                         if (neighbor == node)
 205  16
                                 selfReferential = true;
 206  
 
 207  87
                         NodeInfo neighborInfo = infoMap.get(neighbor);
 208  
 
 209  87
                         if (neighborInfo != null) { // ignore links leading outside the node
 210  
                                                                                 // set
 211  78
                                 if (neighborInfo.dfi < 0) { // node not yet visited
 212  37
                                         searchSCC(neighbor);
 213  37
                                         ni.cmd = Math.min(ni.cmd, neighborInfo.cmd);
 214  37
                                 } else if (neighborInfo.dfi < ni.dfi && neighborInfo.stacked) {
 215  19
                                         ni.cmd = Math.min(ni.cmd, neighborInfo.dfi);
 216  
                                 }
 217  
                         }
 218  
                 }
 219  
 
 220  116
                 if (ni.cmd == ni.dfi) {
 221  
                         // have the root of an SCC, its nodes are on the stack
 222  88
                         ArrayList<T> newSCC = new ArrayList<T>();
 223  
                         T sccMember;
 224  
                         do {
 225  116
                                 sccMember = stack.removeLast();
 226  116
                                 newSCC.add(sccMember);
 227  116
                                 infoMap.get(sccMember).stacked = false;
 228  116
                         } while (sccMember != node);
 229  
 
 230  
                         // if the SCC is large enough, report it
 231  88
                         boolean countCC = newSCC.size() >= minCCSize;
 232  88
                         if (minCCSize == 1 && newSCC.size() == 1 && countIsolatedIfSelfref)
 233  24
                                 countCC = selfReferential;
 234  88
                         if (countCC)
 235  29
                                 connectedComponents.add(newSCC);
 236  
                 }
 237  116
         }
 238  
 }