MergeVertices


1   /*
2    * Generic graph library
3    * Copyright (C) 2000,2003,2004 University of Maryland
4    * 
5    * This library is free software; you can redistribute it and/or
6    * modify it under the terms of the GNU Lesser General Public
7    * License as published by the Free Software Foundation; either
8    * version 2.1 of the License, or (at your option) any later version.
9    * 
10   * This library is distributed in the hope that it will be useful,
11   * but WITHOUT ANY WARRANTY; without even the implied warranty of
12   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13   * Lesser General Public License for more details.
14   * 
15   * You should have received a copy of the GNU Lesser General Public
16   * License along with this library; if not, write to the Free Software
17   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18   */
19  
20  // $Revision: 1.12 $
21  
22  package edu.umd.cs.findbugs.graph;
23  
24  import java.util.Iterator  ;
25  import java.util.Set  ;
26  import java.util.TreeSet  ;
27  
28  /**
29   * Algorithm to merge a set of vertices into a single vertex.
30   * Note that the graph is modified as part of this process.
31   */
32  public class MergeVertices
33          <
34          GraphType extends Graph<EdgeType, VertexType>,
35          EdgeType extends GraphEdge<EdgeType, VertexType>,
36          VertexType extends GraphVertex<VertexType>
37          > {
38  
39      /**
40       * Constructor.
41       */
42      public MergeVertices() {
43      }
44  
45      /**
46       * Merge the specified set of vertices into a single vertex.
47       *
48       * @param vertexSet  the set of vertices to be merged
49       * @param g          the graph to be modified
50       * @param combinator object used to combine vertices
51       * @param toolkit    GraphToolkit used to copy auxiliary information for edges
52       */
53      public void mergeVertices(Set  <VertexType> vertexSet, GraphType g, VertexCombinator<VertexType> combinator,
54                                GraphToolkit<GraphType, EdgeType, VertexType> toolkit) {
55  
56          // Special case: if the vertex set contains a single vertex
57          // or is empty, there is nothing to do
58          if (vertexSet.size() <= 1)
59              return;
60  
61          // Get all vertices to which we have outgoing edges
62          // or from which we have incoming edges, since they'll need
63          // to be fixed
64          TreeSet  <EdgeType> edgeSet = new TreeSet  <EdgeType>();
65          for (Iterator  <EdgeType> i = g.edgeIterator(); i.hasNext();) {
66              EdgeType e = i.next();
67              if (vertexSet.contains(e.getSource()) || vertexSet.contains(e.getTarget()))
68                  edgeSet.add(e);
69          }
70  
71          // Combine all of the vertices into a single composite vertex
72          VertexType compositeVertex = combinator.combineVertices(vertexSet);
73  
74          // For each original edge into or out of the vertex set,
75          // create an equivalent edge referencing the composite
76          // vertex
77          for (EdgeType e : edgeSet) {
78              VertexType source = vertexSet.contains(e.getSource()) ? compositeVertex : e.getSource();
79              VertexType target = vertexSet.contains(e.getTarget()) ? compositeVertex : e.getTarget();
80  
81  //            if (source != compositeVertex && target != compositeVertex)
82  //                System.out.println("BIG OOPS!");
83  
84              // Don't create a self edge for the composite vertex
85              // unless one of the vertices in the vertex set
86              // had a self edge
87              if (source == compositeVertex && target == compositeVertex &&
88                      e.getSource() != e.getTarget())
89                  continue;
90  
91              // Don't create duplicate edges.
92              if (g.lookupEdge(source, target) != null)
93                  continue;
94  
95              EdgeType compositeEdge = g.createEdge(source, target);
96              // FIXME: we really should have an EdgeCombinator here
97              toolkit.copyEdge(e, compositeEdge);
98          }
99  
100         // Remove all of the vertices in the vertex set; this will
101         // automatically remove the edges into and out of those
102         // vertices
103         for (VertexType aVertexSet : vertexSet) {
104             g.removeVertex(aVertexSet);
105         }
106 
107     }
108 
109 }
110 
111 // vim:ts=4
112
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags