StrongComponentAnalyser


1   /*
2    * Copyright (c) 2003-2006, Franz-Josef Elmer, All rights reserved.
3    *
4    * Redistribution and use in source and binary forms, with or without 
5    * modification, are permitted provided that the following conditions are met:
6    * 
7    * - Redistributions of source code must retain the above copyright notice, 
8    *   this list of conditions and the following disclaimer.
9    * - Redistributions in binary form must reproduce the above copyright notice, 
10   *   this list of conditions and the following disclaimer in the documentation 
11   *   and/or other materials provided with the distribution.
12   *
13   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
14   * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 
15   * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 
16   * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 
17   * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 
18   * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 
19   * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
20   * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 
21   * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 
22   * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, 
23   * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24   */
25  package classycle.graph;
26  
27  import java.util.HashMap  ;
28  import java.util.Map  ;
29  
30  /**
31   * Analyser of a directed graph for finding its strong components.
32   * 
33   * @author  Franz-Josef Elmer
34   */
35  public class StrongComponentAnalyser
36  {
37    private final AtomicVertex[] _graph;
38    private StrongComponent[] _components;
39    private HashMap   _layerMap;
40    
41    /**
42     * Creates an instance for the specified graph.
43     */
44    public StrongComponentAnalyser(AtomicVertex[] graph)
45    {
46      _graph = graph;
47      //Arrays.sort(_graph, null);
48    }
49    
50    /** Returns the original graph. That is, the argument of the constructor. */
51    public AtomicVertex[] getGraph()
52    {
53      return _graph;
54    }
55  
56    /** Returns the graph of strong components. */  
57    public StrongComponent[] getCondensedGraph()
58    {
59      if (_components == null)
60      {
61        StrongComponentProcessor processor = new StrongComponentProcessor(true);
62        processor.deepSearchFirst(_graph);
63        _components = processor.getStrongComponents();
64      }
65      return _components;
66    }
67    
68    /**
69     * Returns the maping of the nodes of the original graph onto a layer index
70     * (i.e.&nbsp;length of the longest path of the condensed graph). 
71     * @return a map where the keys are instances of {@link AtomicVertex}
72     *         and the values are instances of <tt>Integer</tt>.
73     */
74    public Map   getLayerMap() 
75    {
76      if (_layerMap == null)
77      {
78        StrongComponent[] components = getCondensedGraph();
79        new LongestWalkProcessor().deepSearchFirst(components);
80        _layerMap = new HashMap  ();
81        for (int i = 0; i < components.length; i++) 
82        {
83          StrongComponent component = components[i];
84          Integer   layer = new Integer  (component.getLongestWalk());
85          for (int j = 0, n = component.getNumberOfVertices(); j < n; j++) 
86          {
87            _layerMap.put(component.getVertex(j), layer);
88          }
89        }
90      }
91      return _layerMap;
92    }
93  
94  }
95
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags