gspan_tpl.h

Go to the documentation of this file.

/**
 *
 *   Copyright 2005-2020 Pierre-Henri WUILLEMIN(@LIP6) & Christophe GONZALES(@AMU)
 *   info_at_agrum_dot_org
 *
 *  This library is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with this library.  If not, see <http://www.gnu.org/licenses/>.
 *
 */


/**
 * @file
 * @brief Inline implementation of gspan.
 *
 * @author Lionel TORTI and Pierre-Henri WUILLEMIN(@LIP6)
 */
#include <agrum/PRM/gspan/edgeGrowth.h>
#include <agrum/PRM/inference/gspan.h>

namespace gum {
  namespace prm {

    template < typename GUM_SCALAR >
    void GSpan< GUM_SCALAR >::discoverPatterns() {
      Timer t;
      sortNodesAndEdges__();
      gspan::InterfaceGraph< GUM_SCALAR > graph(*graph__);

      for (auto root = tree__.roots().begin(); root != tree__.roots().end();
           ++root) {
        if (tree__.strategy().accept_root(&(tree__.pattern(*root)))) {
          gspan::Pattern& p = tree__.pattern(*root);
          subgraph_mining__(graph, p);

          for (const auto node: tree__.iso_graph(p).nodes()) {
            PRMInstance< GUM_SCALAR >* u = tree__.iso_map(p, node).atPos(0);
            PRMInstance< GUM_SCALAR >* v = tree__.iso_map(p, node).atPos(1);
            graph.graph().eraseEdge(Edge(graph.id(u), graph.id(v)));
          }
        }
      }

      sortPatterns__();
    }

    template < typename GUM_SCALAR >
    void GSpan< GUM_SCALAR >::sortNodesAndEdges__() {
      for (auto iter = graph__->labels().begin(); iter != graph__->labels().end();
           ++iter) {
        try {
          if (graph__->nodes(iter.second()).size() >= 2) {
            cost__.insert(iter.second(),
                          cost_func__(iter.second()->tree_width,
                                      graph__->nodes(iter.second()).size()));
            nodes__.push_back(const_cast< gspan::LabelData* >(iter.second()));
          }
        } catch (NotFound&) {
          // It's a label over edges
          if (isEdgeEligible__(*(graph__->edges(iter.second()).begin()))) {
            cost__.insert(iter.second(),
                          cost_func__(iter.second()->tree_width,
                                      graph__->edges(iter.second()).size()));
            edges__.push_back(iter.second());
          }
        }
      }

      Bijection< Idx, gspan::LabelData* >* new_labels
         = new Bijection< Idx, gspan::LabelData* >();
      GSpan< GUM_SCALAR >::LabelSort my_sort(this);
      std::sort(nodes__.begin(), nodes__.end(), my_sort);
      std::sort(edges__.begin(), edges__.end(), my_sort);
      Size idx = 0;

      for (auto iter = nodes__.begin(); iter != nodes__.end(); ++iter) {
        (*iter)->id = ++idx;
        new_labels->insert(idx, *iter);
      }

      for (auto iter = edges__.begin(); iter != edges__.end(); ++iter) {
        (*iter)->id = ++idx;
        new_labels->insert(idx, *iter);
        tree__.addRoot(**iter);
      }

      delete graph__->labels__;
      graph__->labels__ = new_labels;
    }

    template < typename GUM_SCALAR >
    void GSpan< GUM_SCALAR >::subgraph_mining__(
       gspan::InterfaceGraph< GUM_SCALAR >& ig,
       gspan::Pattern&                      pat) {
      std::vector< gspan::Pattern* > stack;
      stack.push_back(&pat);
      // Pointers used in the following while
      gspan::Pattern*                                             p = nullptr;
      HashTable< std::string, gspan::EdgeGrowth< GUM_SCALAR >* >* edge_count
         = nullptr;
      gspan::EdgeGrowth< GUM_SCALAR >*        edge_growth = nullptr;
      Sequence< PRMInstance< GUM_SCALAR >* >* seq         = nullptr;
      PRMInstance< GUM_SCALAR >*              current     = nullptr;
      PRMInstance< GUM_SCALAR >*              neighbor    = nullptr;

      // Neighbor_id is the neighbor's id in the interface graph and
      // neighbor_node
      // is its id in the rightmost path in the case of a backward edge growth
      NodeId            current_id     = 0;
      NodeId            neighbor_node  = 0;
      gspan::LabelData* neighbor_label = 0;

      typename gspan::EdgeData< GUM_SCALAR >* edge_data = nullptr;

      size_t                     idx;
      const std::list< NodeId >* children = 0;

      while (!stack.empty()) {
        // Getting next pattern
        p = stack.back();
        stack.pop_back();

        if (p->code().codes.size() < depth_stop__) {
          // We need the rightmost path of p
          std::list< NodeId > r_path;
          p->rightmostPath(r_path);
          // Mapping used to count each possible child of p, the position in the
          // vector
          // matches the one in the rightmost path
          std::vector<
             HashTable< std::string, gspan::EdgeGrowth< GUM_SCALAR >* >* >
             count_vector;

          for (size_t i = 0; i < r_path.size(); ++i)
            count_vector.push_back(
               new HashTable< std::string, gspan::EdgeGrowth< GUM_SCALAR >* >());

          // For each subgraph represented by p, we look for a valid edge growth
          // for
          // each instance match of p in its isomorphism graph.
          for (const auto iso_node: tree__.iso_graph(*p).nodes()) {
            seq = &(tree__.iso_map(*p, iso_node));
            idx = 0;

            for (const auto node: r_path) {
              edge_count = count_vector[idx];
              // Retrieving the equivalent instance in the current match
              current    = seq->atPos((Idx)(node - 1));
              current_id = ig.id(current);
              // Checking for edges not in p

              for (const auto neighbor_id: ig.graph().neighbours(current_id)) {
                neighbor = ig.node(neighbor_id).n;

                // We want a forward edge in any case or a backward edge if
                // current
                // is the rightmost vertex
                if ((!seq->exists(neighbor)) || (node == r_path.back())) {
                  // Things we need to know: the LabelData data of the neighbour
                  // and,
                  // if it's a backward edge, its node id in the rightmost path
                  edge_data      = &(ig.edge(current_id, neighbor_id));
                  neighbor_label = (neighbor == edge_data->u) ? edge_data->l_u
                                                              : edge_data->l_v;
                  neighbor_node
                     = (seq->exists(neighbor)) ? seq->pos(neighbor) + 1 : 0;
                  // Adding the edge growth to the edge_growth hashtable
                  gspan::EdgeGrowth< GUM_SCALAR > temp_growth(node,
                                                              edge_data->l,
                                                              neighbor_label,
                                                              neighbor_node);

                  try {
                    edge_growth = (*edge_count)[temp_growth.toString()];
                    edge_growth->insert(current, neighbor);
                  } catch (NotFound&) {
                    edge_growth
                       = new gspan::EdgeGrowth< GUM_SCALAR >(node,
                                                             edge_data->l,
                                                             neighbor_label,
                                                             neighbor_node);
                    edge_growth->insert(current, neighbor);
                    edge_count->insert(edge_growth->toString(), edge_growth);
                  }
                }
              }
            }
          }

          // Removing any infrequent child
          for (size_t node = 0; node < count_vector.size(); ++node) {
            edge_count = count_vector[node];

            for (const auto& elt: *edge_count) {
              try {
                tree__.growPattern(*p, *elt.second, 2);
              } catch (OperationNotAllowed&) {
                // The child was not minimal or was not worth considering
              }

              delete elt.second;
            }

            delete edge_count;
          }

          // Calling subgraph_mining__ over children of p
          children = &(tree__.children(*p));

          for (std::list< NodeId >::const_reverse_iterator child
               = children->rbegin();
               child != children->rend();
               ++child)
            stack.push_back(&(tree__.pattern(*child)));
        }
      }
    }

    template < typename GUM_SCALAR >
    void GSpan< GUM_SCALAR >::sortPatterns__() {
      // First we put all the patterns in patterns__.
      std::vector< NodeId > stack;

      for (std::list< NodeId >::reverse_iterator root = tree().roots().rbegin();
           root != tree().roots().rend();
           ++root)
        stack.push_back(*root);

      NodeId               id       = 0;
      std::list< NodeId >* children = nullptr;

      while (!stack.empty()) {
        id = stack.back();
        stack.pop_back();
        patterns__.push_back(&(tree().pattern(id)));
        children = &(tree().children(tree().pattern(id)));

        for (std::list< NodeId >::reverse_iterator child = children->rbegin();
             child != children->rend();
             ++child)
          stack.push_back(*child);
      }

      if (!patterns__.empty()) {
        // We sort patterns__.
        GSpan< GUM_SCALAR >::PatternSort my_sort(this);
        std::sort(patterns__.begin(), patterns__.end(), my_sort);
        // Now we need to find all the matches we can, using patterns__.
        // We start by the best Pattern and add it's maximal independent set to
        // chosen__
        GSpan< GUM_SCALAR >::MatchedInstances* matches
           = new GSpan< GUM_SCALAR >::MatchedInstances();
        Sequence< PRMInstance< GUM_SCALAR >* >* match = nullptr;

        for (const auto node: tree().max_indep_set(*(patterns__.front()))) {
          match = &(tree().iso_map(*(patterns__.front()), node));

          for (const auto i: *match)
            chosen__.insert(i);

          matches->insert(match);
        }

        matched_instances__.insert(patterns__.front(), matches);
        // Now we see what kind of pattern we can still use
        bool       found;
        UndiGraph* iso_graph = nullptr;

        for (auto patt = patterns__.begin() + 1; patt != patterns__.end();
             ++patt) {
          UndiGraph             reduced_iso_graph;
          std::vector< NodeId > degree_list;
          iso_graph = &(tree().iso_graph(**patt));

          for (const auto node: iso_graph->nodes()) {
            found = false;
            match = &(tree().iso_map(**patt, node));

            for (const auto i: *match)
              if (chosen__.exists(i)) {
                found = true;
                break;
              }

            if (!found) {
              // We add the pattern to the reduced isomorphism graph to compute
              // the
              // max independent set
              // over the remaining matches
              reduced_iso_graph.addNodeWithId(node);

              for (const auto iso: reduced_iso_graph.nodes())
                if (iso_graph->existsEdge(node, iso))
                  reduced_iso_graph.addEdge(node, iso);

              degree_list.push_back(node);
            }
          }

          // We create a new set to hold all the chosen matches of patt
          matches = new GSpan< GUM_SCALAR >::MatchedInstances();
          // We can compute the max independent set and the matches belonging to
          // it
          typename gspan::DFSTree< GUM_SCALAR >::NeighborDegreeSort my_sort(
             reduced_iso_graph);
          std::sort(degree_list.begin(), degree_list.end(), my_sort);
          Set< NodeId > removed;

          for (const auto node: degree_list)
            if (!removed.exists(node)) {
              // First we update removed to follow the max independent set
              // algorithm
              removed.insert(node);

              for (const auto neighbor: reduced_iso_graph.neighbours(node))
                removed.insert(neighbor);

              // Second we update match and matches to keep track of the current
              // match
              match = &(tree().iso_map(**patt, node));
              matches->insert(match);

              for (const auto elt: *match)
                chosen__.insert(elt);
            }

          matched_instances__.insert(*patt, matches);
        }

        // // We remove patterns with 0 matches
        std::vector< size_t > trash;

        for (size_t idx = 0; idx < patterns__.size(); ++idx)
          if (matched_instances__[patterns__[idx]]->size() < 2)
            trash.push_back(idx);

        while (trash.size()) {
          delete matched_instances__[patterns__[trash.back()]];
          matched_instances__.erase(patterns__[trash.back()]);
          // delete patterns__[trash.back()];
          patterns__[trash.back()] = patterns__.back();
          patterns__.pop_back();
          trash.pop_back();
        }
      }
    }

    template < typename GUM_SCALAR >
    INLINE
       GSpan< GUM_SCALAR >::GSpan(const PRM< GUM_SCALAR >&             prm,
                                  const PRMSystem< GUM_SCALAR >&       sys,
                                  gspan::SearchStrategy< GUM_SCALAR >* strategy) :
        graph__(new gspan::InterfaceGraph< GUM_SCALAR >(sys)),
        tree__(*graph__, strategy), depth_stop__(INT_MAX) {
      GUM_CONSTRUCTOR(GSpan);
    }

    template < typename GUM_SCALAR >
    INLINE GSpan< GUM_SCALAR >::~GSpan() {
      GUM_DESTRUCTOR(GSpan);

      for (const auto& elt: matched_instances__)
        delete elt.second;

      delete graph__;
    }

    template < typename GUM_SCALAR >
    INLINE Size GSpan< GUM_SCALAR >::getMaxDFSDepth() const {
      return depth_stop__;
    }

    template < typename GUM_SCALAR >
    INLINE void GSpan< GUM_SCALAR >::setMaxDFSDepth(Size depth) {
      depth_stop__ = depth;
    }

    template < typename GUM_SCALAR >
    INLINE gspan::DFSTree< GUM_SCALAR >& GSpan< GUM_SCALAR >::tree() {
      return tree__;
    }

    template < typename GUM_SCALAR >
    INLINE const gspan::DFSTree< GUM_SCALAR >& GSpan< GUM_SCALAR >::tree() const {
      return tree__;
    }

    template < typename GUM_SCALAR >
    INLINE Idx GSpan< GUM_SCALAR >::cost_func__(Size interface_size,
                                                Size frequency) {
      return Idx(interface_size * frequency);
    }

    template < typename GUM_SCALAR >
    INLINE std::vector< gspan::Pattern* >& GSpan< GUM_SCALAR >::patterns() {
      return patterns__;
    }

    template < typename GUM_SCALAR >
    INLINE const std::vector< gspan::Pattern* >&
                 GSpan< GUM_SCALAR >::patterns() const {
      return patterns__;
    }

    template < typename GUM_SCALAR >
    INLINE typename GSpan< GUM_SCALAR >::MatchedInstances&
       GSpan< GUM_SCALAR >::matches(const gspan::Pattern& p) {
      return *(matched_instances__[const_cast< gspan::Pattern* >(&p)]);
    }

    template < typename GUM_SCALAR >
    INLINE const typename GSpan< GUM_SCALAR >::MatchedInstances&
       GSpan< GUM_SCALAR >::matches(const gspan::Pattern& p) const {
      return *(matched_instances__[const_cast< gspan::Pattern* >(&p)]);
    }

    template < typename GUM_SCALAR >
    INLINE gspan::InterfaceGraph< GUM_SCALAR >&
           GSpan< GUM_SCALAR >::interfaceGraph() {
      return *graph__;
    }

    template < typename GUM_SCALAR >
    INLINE const gspan::InterfaceGraph< GUM_SCALAR >&
                 GSpan< GUM_SCALAR >::interfaceGraph() const {
      return *graph__;
    }

    template < typename GUM_SCALAR >
    INLINE bool
       GSpan< GUM_SCALAR >::isEdgeEligible__(gspan::EdgeData< GUM_SCALAR >* e) {
      return (graph__->edges(e->l).size() >= 2)
          && (graph__->nodes(e->l_u).size() >= 2)
          && (graph__->nodes(e->l_v).size() >= 2);
    }

    // LalbeSort

    template < typename GUM_SCALAR >
    INLINE GSpan< GUM_SCALAR >::LabelSort::LabelSort(GSpan* my_gspan) :
        gspan(my_gspan) {
      GUM_CONSTRUCTOR(GSpan< GUM_SCALAR >::LabelSort);
    }

    template < typename GUM_SCALAR >
    INLINE GSpan< GUM_SCALAR >::LabelSort::LabelSort(const LabelSort& source) :
        gspan(source.gspan) {
      GUM_CONS_CPY(GSpan< GUM_SCALAR >::LabelSort);
    }

    template < typename GUM_SCALAR >
    INLINE GSpan< GUM_SCALAR >::LabelSort::~LabelSort() {
      GUM_DESTRUCTOR(GSpan< GUM_SCALAR >::LabelSort);
    }

    template < typename GUM_SCALAR >
    INLINE bool GSpan< GUM_SCALAR >::LabelSort::operator()(gspan::LabelData* i,
                                                           gspan::LabelData* j) {
      // We want a descending order
      // return gspan->cost__[i] > gspan->cost__[j];
      return gspan->tree__.strategy()(i, j);
    }

    // PatternSort

    template < typename GUM_SCALAR >
    INLINE GSpan< GUM_SCALAR >::PatternSort::PatternSort(GSpan* my_gspan) :
        gspan(my_gspan) {
      GUM_CONSTRUCTOR(GSpan< GUM_SCALAR >::PatternSort);
    }

    template < typename GUM_SCALAR >
    INLINE
       GSpan< GUM_SCALAR >::PatternSort::PatternSort(const PatternSort& source) :
        gspan(source.gspan) {
      GUM_CONS_CPY(GSpan< GUM_SCALAR >::PatternSort);
    }

    template < typename GUM_SCALAR >
    INLINE GSpan< GUM_SCALAR >::PatternSort::~PatternSort() {
      GUM_DESTRUCTOR(GSpan< GUM_SCALAR >::PatternSort);
    }

    template < typename GUM_SCALAR >
    INLINE bool GSpan< GUM_SCALAR >::PatternSort::operator()(gspan::Pattern* i,
                                                             gspan::Pattern* j) {
      // We want a descending order
      return gspan->tree().strategy().operator()(i, j);
    }

  } /* namespace prm */
} /* namespace gum */