Chemical Data Processing Library C++ API - Version 1.1.1
BronKerboschAlgorithm.hpp
Go to the documentation of this file.
1 /*
2  * BronKerboschAlgorithm.hpp
3  *
4  * Copyright (C) 2003 Thomas Seidel <thomas.seidel@univie.ac.at>
5  *
6  * This library is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Lesser General Public
8  * License as published by the Free Software Foundation; either
9  * version 2 of the License, or (at your option) any later version.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public License
17  * along with this library; see the file COPYING. If not, write to
18  * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19  * Boston, MA 02111-1307, USA.
20  */
21 
27 #ifndef CDPL_UTIL_BRONKERBOSCHALGORITHM_HPP
28 #define CDPL_UTIL_BRONKERBOSCHALGORITHM_HPP
29 
30 #include <cstddef>
31 #include <vector>
32 
33 #include "CDPL/Util/APIPrefix.hpp"
34 #include "CDPL/Util/BitSet.hpp"
35 #include "CDPL/Util/Array.hpp"
37 
38 
39 namespace CDPL
40 {
41 
42  namespace Util
43  {
44 
49  {
50 
51  public:
53 
55 
57 
58  void init(const BitSetArray& adj_mtx);
59 
60  bool nextClique(BitSet& clique);
61 
63 
64  private:
65  struct State
66  {
67 
68  BitSet curr;
69  BitSet pool;
70  BitSet excl;
71  std::size_t u;
72  std::size_t v;
73  };
74 
75  typedef std::vector<std::size_t> NodeDegreeTable;
76  typedef std::vector<State*> StateStack;
77  typedef Util::ObjectStack<State> StateCache;
78 
79  const BitSetArray* adjMatrix;
80  StateCache stateCache;
81  NodeDegreeTable nodeDegrees;
82  StateStack states;
83  BitSet pivotCandSet;
84  };
85  } // namespace Util
86 } // namespace CDPL
87 
88 #endif // CDPL_UTIL_BRONKERBOSCHALGORITHM_HPP
ObjectStack.hpp
Definition of the class CDPL::Util::ObjectStack.
CDPL::Util::BronKerboschAlgorithm::operator=
BronKerboschAlgorithm & operator=(const BronKerboschAlgorithm &bka)
CDPL::Util::BitSet
boost::dynamic_bitset BitSet
A dynamic bitset class.
Definition: BitSet.hpp:46
CDPL::Util::BronKerboschAlgorithm::init
void init(const BitSetArray &adj_mtx)
CDPL::Util::BronKerboschAlgorithm
Implementation of the Bron-Kerbosch clique-detection algorithm [BKA].
Definition: BronKerboschAlgorithm.hpp:49
BitSet.hpp
Definition of the type CDPL::Util::BitSet.
Array.hpp
Definition of the class CDPL::Util::Array.
CDPL::Util::BronKerboschAlgorithm::nextClique
bool nextClique(BitSet &clique)
CDPL::Util::BronKerboschAlgorithm::BronKerboschAlgorithm
BronKerboschAlgorithm(const BitSetArray &adj_mtx)
Array< BitSet >
CDPL_UTIL_API
#define CDPL_UTIL_API
Tells the compiler/linker which classes, functions and variables are part of the library API.
CDPL::Util::BronKerboschAlgorithm::BronKerboschAlgorithm
BronKerboschAlgorithm(const BronKerboschAlgorithm &bka)
CDPL
The namespace of the Chemical Data Processing Library.
APIPrefix.hpp
Definition of the preprocessor macro CDPL_UTIL_API.
CDPL::Util::ObjectStack< State >
CDPL::Util::BronKerboschAlgorithm::BronKerboschAlgorithm
BronKerboschAlgorithm()
Definition: BronKerboschAlgorithm.hpp:52