KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > alg > BronKerboschCliqueFinder


1 /* ==========================================
2  * JGraphT : a free Java graph-theory library
3  * ==========================================
4  *
5  * Project Info: http://jgrapht.sourceforge.net/
6  * Project Creator: Barak Naveh (http://sourceforge.net/users/barak_naveh)
7  *
8  * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
9  *
10  * This library is free software; you can redistribute it and/or modify it
11  * under the terms of the GNU Lesser General Public License as published by
12  * the Free Software Foundation; either version 2.1 of the License, or
13  * (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful, but
16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18  * License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this library; if not, write to the Free Software Foundation,
22  * Inc.,
23  * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
24  */
25 /* -------------------
26  * BronKerboschCliqueFinder.java
27  * -------------------
28  * (C) Copyright 2005-2006, by Ewgenij Proschak and Contributors.
29  *
30  * Original Author: Ewgenij Proschak
31  * Contributor(s): John V. Sichi
32  *
33  * $Id: BronKerboschCliqueFinder.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  * 21-Jul-2005 : Initial revision (EP);
38  * 26-Jul-2005 : Cleaned up and checked in (JVS);
39  *
40  */
41 package org.jgrapht.alg;
42
43 import java.util.*;
44
45 import org.jgrapht.*;
46
47
48 /**
49  * This class implements Bron-Kerbosch clique detection algorithm as it is
50  * described in [Samudrala R.,Moult J.:A Graph-theoretic Algorithm for
51  * comparative Modeling of Protein Structure; J.Mol. Biol. (1998); vol 279; pp.
52  * 287-302]
53  *
54  * @author Ewgenij Proschak
55  */
56 public class BronKerboschCliqueFinder<V, E>
57 {
58
59     //~ Instance fields -------------------------------------------------------
60
61     private final Graph<V, E> graph;
62
63     private Collection<Set<V>> cliques;
64
65     //~ Constructors ----------------------------------------------------------
66
67     /**
68      * Creates a new clique finder.
69      *
70      * @param graph the graph in which cliques are to be found; graph must be
71      * simple
72      */
73     public BronKerboschCliqueFinder(Graph<V, E> graph)
74     {
75         this.graph = graph;
76     }
77
78     //~ Methods ---------------------------------------------------------------
79
80     /**
81      * Finds all maximal cliques of the graph. A clique is maximal if it is
82      * impossible to enlarge it by adding another vertex from the graph. Note
83      * that a maximal clique is not necessarily the biggest clique in the graph.
84      *
85      * @return Collection of cliques (each of which is represented as a Set of
86      * vertices)
87      */
88     public Collection<Set<V>> getAllMaximalCliques()
89     {
90         // TODO jvs 26-July-2005: assert that graph is simple
91
92         cliques = new ArrayList<Set<V>>();
93         List<V> potential_clique = new ArrayList<V>();
94         List<V> candidates = new ArrayList<V>();
95         List<V> already_found = new ArrayList<V>();
96         candidates.addAll(graph.vertexSet());
97         findCliques(potential_clique, candidates, already_found);
98         return cliques;
99     }
100
101     /**
102      * Finds the biggest maximal cliques of the graph.
103      *
104      * @return Collection of cliques (each of which is represented as a Set of
105      * vertices)
106      */
107     public Collection<Set<V>> getBiggestMaximalCliques()
108     {
109         // first, find all cliques
110 getAllMaximalCliques();
111
112         int maximum = 0;
113         Collection<Set<V>> biggest_cliques = new ArrayList<Set<V>>();
114         for (Set<V> clique : cliques) {
115             if (maximum < clique.size()) {
116                 maximum = clique.size();
117             }
118         }
119         for (Set<V> clique : cliques) {
120             if (maximum == clique.size()) {
121                 biggest_cliques.add(clique);
122             }
123         }
124         return biggest_cliques;
125     }
126
127     private void findCliques(
128         List<V> potential_clique,
129         List<V> candidates,
130         List<V> already_found)
131     {
132         List<V> candidates_array = new ArrayList<V>(candidates);
133         if (!end(candidates, already_found)) {
134             // for each candidate_node in candidates do
135 for (V candidate : candidates_array) {
136                 List<V> new_candidates = new ArrayList<V>();
137                 List<V> new_already_found = new ArrayList<V>();
138
139                 // move candidate node to potential_clique
140 potential_clique.add(candidate);
141                 candidates.remove(candidate);
142
143                 // create new_candidates by removing nodes in candidates not
144 // connected to candidate node
145 for (V new_candidate : candidates) {
146                     if (graph.containsEdge(candidate, new_candidate)) {
147                         new_candidates.add(new_candidate);
148                     } // of if
149 } // of for
150
151                 // create new_already_found by removing nodes in already_found
152 // not connected to candidate node
153 for (V new_found : already_found) {
154                     if (graph.containsEdge(candidate, new_found)) {
155                         new_already_found.add(new_found);
156                     } // of if
157 } // of for
158
159                 // if new_candidates and new_already_found are empty
160 if (new_candidates.isEmpty() && new_already_found.isEmpty()) {
161                     // potential_clique is maximal_clique
162 cliques.add(new HashSet<V>(potential_clique));
163                 } // of if
164 else {
165                     // recursive call
166 findCliques(
167                         potential_clique,
168                         new_candidates,
169                         new_already_found);
170                 } // of else
171
172                 // move candidate_node from potential_clique to already_found;
173 already_found.add(candidate);
174                 potential_clique.remove(candidate);
175             } // of for
176 } // of if
177 }
178
179     private boolean end(List<V> candidates, List<V> already_found)
180     {
181         // if a node in already_found is connected to all nodes in candidates
182 boolean end = false;
183         int edgecounter;
184         for (V found : already_found) {
185             edgecounter = 0;
186             for (V candidate : candidates) {
187                 if (graph.containsEdge(found, candidate)) {
188                     edgecounter++;
189                 } // of if
190 } // of for
191 if (edgecounter == candidates.size()) {
192                 end = true;
193             }
194         } // of for
195 return end;
196     }
197 }
198
Popular Tags