rdkit/Code/GraphMol/Substruct/ullmann.hpp

// morpho/cdl/bgl_expansions/algorithms/ullmann.hpp header file//
// Copyright (c) 2003-2008 Vladimir J. Sykora
// Copyright (c) 2007-2008 Vladimir J. Sykora and NCU Studies Ltd
// Modifications by Greg Landrum, January 2009
//
//*****************************************************************************
// Permission is hereby granted, free of charge, to any person or organization
// obtaining a copy of the software and accompanying documentation covered by
// this license (the "Software") to use, reproduce, display, distribute,
// execute, and transmit the Software, and to prepare derivative works of the
// Software, and to permit third-parties to whom the Software is furnished to
// do so, all subject to the following:
//
// The copyright notices in the Software and this entire statement, including
// the above license grant, this restriction and the following disclaimer,
// must be included in all copies of the Software, in whole or in part, and
// all derivative works of the Software, unless such copies or derivative
// works are solely in the form of machine-executable object code generated by
// a source language processor.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
// SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
// FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
// DEALINGS IN THE SOFTWARE.

//*****************************************************************************

//-----------------------------------------------------------------------------

// Algorithm due to JR Ullmann. "An Algorithm for Subgraph
// Isomorphism". Journal of the Association for
// Computing Machinery, Vol 23, No.1, January 1976, pp 31-42.

#ifndef MORPHO_CDL_BGL_EXP_ULLMANN_HPP
#define MORPHO_CDL_BGL_EXP_ULLMANN_HPP

// -------- boost
#include <boost/numeric/ublas/matrix.hpp>
#include <boost/graph/graph_traits.hpp>
// -------- std
#include <utility>  // for std::pair<>
#include <algorithm>

namespace boost {
namespace detail {

template <class Graph, class UblasMatrix, class BackInsertionSequence,
          class EdgeLabeling>
bool forward_checking(const Graph& g1, const Graph& g2, UblasMatrix& M,
                      size_t count, BackInsertionSequence& F,
                      size_t num_vert_g1, size_t num_vert_g2,
                      EdgeLabeling& edge_labeling) {
  typedef std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
      edge_presence;
  typename BackInsertionSequence::iterator fi, fi_end = F.end();
  for (size_t k = count + 1; k < num_vert_g1; ++k) {
    for (size_t l = 0; l < num_vert_g2; ++l) {
      if (!M(k, l)) continue;
      // check mapping:
      fi = F.begin();
      while (fi != fi_end) {
        bool flag1(0), flag1_1(0), flag2(0), flag2_1(0);
        edge_presence ep1 = edge(k, fi->first, g1);
        if (ep1.second) {
          flag1_1 = true;
          edge_presence ep2 = edge(l, fi->second, g2);
          if (ep2.second) flag1 = edge_labeling(ep1.first, ep2.first);
        }
        if (flag1_1 && flag1) {
          M(k, l) = 1;
          ++fi;
          continue;
        }
        edge_presence ep2 = edge(l, fi->second, g2);
        if (ep2.second) {
          flag2_1 = true;
          ep1 = edge(k, fi->first, g1);
          if (ep1.second) {
            flag2 = edge_labeling(ep1.first, ep2.first);
          } else {
            // ring closed in main structure, not closed in query. This should
            // pass
            flag2 = true;
          }
        }
        if (flag2_1 && flag2) {  // if one edge exists, there must be a mapping
          M(k, l) = 1;
        } else if (!flag1_1 && !flag2_1) {  // or both edges are not present
          M(k, l) = 1;
        } else {
          M(k, l) = 0;  // if not, there's no mapping
        }
        ++fi;
      }
    }
  }
  // TODO: change the data structure of the M matrix to sparse matrix. This
  // wouldn't be necessary
  size_t cero_row(0);
  for (size_t k = 0; k < num_vert_g1; ++k) {
    for (size_t l = 0; l < num_vert_g2; ++l) {
      if (M(k, l)) {
        break;
      } else {
        ++cero_row;
      }
    }
    if (cero_row == num_vert_g2) {
      return false;  // if there is a cero row
    }
    cero_row = 0;
  }
  return true;
}

template <class Graph, class EdgeLabeling, class UblasMatrix,
          class BackInsertionSequence>
bool backtrack(const Graph& g1, const Graph& g2, size_t count,
               const UblasMatrix& M, BackInsertionSequence& F,
               const size_t num_vert_g1, const size_t num_vert_g2,
               EdgeLabeling& edge_labeling) {
  if (count == num_vert_g1) return true;
  for (size_t i = 0; i < num_vert_g2; ++i) {
    if (M(count, i)) {
      F.push_back(std::make_pair(count, i));
      UblasMatrix M_prime(M);
      for (size_t m = count + 1; m < num_vert_g1; ++m) {
        M_prime(m, i) = 0;
      }

      if (forward_checking(g1, g2, M_prime, count, F, num_vert_g1, num_vert_g2,
                           edge_labeling)) {
        if (backtrack(g1, g2, count + 1, M_prime, F, num_vert_g1, num_vert_g2,
                      edge_labeling)) {
          return true;
        }
      }
      F.erase(std::remove(F.begin(), F.end(), std::make_pair(count, i)),
              F.end());
    }
  }
  return false;
}

template <class Graph, class EdgeLabeling, class UblasMatrix,
          class DoubleBackInsertionSequence>
void backtrack_all(const Graph& g1, const Graph& g2, size_t count,
                   const UblasMatrix& M, DoubleBackInsertionSequence& FF,
                   const size_t num_vert_g1, const size_t num_vert_g2,
                   EdgeLabeling& edge_labeling) {
  if (count == num_vert_g1) return;
  DoubleBackInsertionSequence holdFF;
  holdFF.insert(holdFF.begin(), FF.begin(), FF.end());
  FF.clear();
  for (size_t i = 0; i < num_vert_g2; ++i) {
    if (M(count, i)) {
      DoubleBackInsertionSequence tFF;

      UblasMatrix M_prime(M);
      for (size_t m = count + 1; m < num_vert_g1; ++m) {
        M_prime(m, i) = 0;
      }

      if (holdFF.size()) {
        for (typename DoubleBackInsertionSequence::const_iterator iter =
                 holdFF.begin();
             iter != holdFF.end(); ++iter) {
          typename DoubleBackInsertionSequence::value_type F = *iter;
          F.push_back(std::make_pair(count, i));
          if (forward_checking(g1, g2, M_prime, count, F, num_vert_g1,
                               num_vert_g2, edge_labeling)) {
            tFF.push_back(F);
          }
        }
      } else {
        typename DoubleBackInsertionSequence::value_type F;
        F.push_back(std::make_pair(count, i));
        if (forward_checking(g1, g2, M_prime, count, F, num_vert_g1,
                             num_vert_g2, edge_labeling)) {
          tFF.push_back(F);
        }
      }
      backtrack_all(g1, g2, count + 1, M_prime, tFF, num_vert_g1, num_vert_g2,
                    edge_labeling);
      if (tFF.size()) {
        for (typename DoubleBackInsertionSequence::const_iterator iter =
                 tFF.begin();
             iter != tFF.end(); ++iter) {
          FF.push_back(*iter);
        }
      }
    }
  }
}

template <class Graph, class VertexLabeling  // binary predicate
          ,
          class UblasMatrix>
void prepareM(const Graph& g1, const Graph& g2, VertexLabeling& vertex_labeling,
              UblasMatrix& M) {
  size_t rows(num_vertices(g1));
  size_t cols(num_vertices(g2));
  M.resize(rows, cols);
  // initialize the matrix:
  for (size_t i = 0; i < rows; ++i) {
    for (size_t j = 0; j < cols; ++j) {
      if (out_degree(j, g2) >= out_degree(i, g1) && vertex_labeling(i, j)) {
        M(i, j) = 1;
      } else {
        M(i, j) = 0;
      }
    }
  }
}
}  // namespace detail

// test if g1 is a subgraph of g2. mapped vertices are returned in F
// Mapping : first: g1 vertices, second : g2 vertices
// O( num_vertices(g1)! num_vertices(g1) ^ 3 )
// This function doesnt Work with filtered graphs!
// The size of F doesn't indicate match!
template <
    class Graph, class VertexLabeling  // binary predicate
    ,
    class EdgeLabeling  // binary predicate
    ,
    class
    BackInsertionSequence  // contains
                           // std::pair<vertex_descriptor,vertex_descriptor>
    >
bool ullmann(const Graph& g1, const Graph& g2, VertexLabeling& vertex_labeling,
             EdgeLabeling& edge_labeling, BackInsertionSequence& F) {
  typedef ::boost::numeric::ublas::matrix<int> matrix_t;
  size_t rows(num_vertices(g1));
  size_t cols(num_vertices(g2));
  matrix_t M;
  detail::prepareM(g1, g2, vertex_labeling, M);
  size_t count(0);
  return detail::backtrack(g1, g2, count, M, F, rows, cols, edge_labeling);
}

// test if g1 is a subgraph of g2.
// F returns all mappings of g1 in g2. mapping in separate containers
template <class Graph, class VertexLabeling  // binary predicate
          ,
          class EdgeLabeling  // binary predicate
          ,
          class DoubleBackInsertionSequence  // contains a back insertion
                                             // sequence
          >
bool ullmann_all(const Graph& g1, const Graph& g2,
                 VertexLabeling& vertex_labeling, EdgeLabeling& edge_labeling,
                 DoubleBackInsertionSequence& F) {
  typedef ::boost::numeric::ublas::matrix<int> matrix_t;
  size_t rows(num_vertices(g1));
  size_t cols(num_vertices(g2));
  matrix_t M;
  detail::prepareM(g1, g2, vertex_labeling, M);
  size_t count(0);
  detail::backtrack_all(g1, g2, count, M, F, rows, cols, edge_labeling);
  return !F.empty();
}

}  // namespace boost

#endif  // MORPHO_CDL_BGL_EXP_ULLMANN_HPP