interfaceGraph_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 gum::InterfaceGraph.
 *
 * @author Lionel TORTI and Pierre-Henri WUILLEMIN(@LIP6)
 */

namespace gum {
  namespace prm {
    namespace gspan {

      // NodeData

      template < typename GUM_SCALAR >
      INLINE NodeData< GUM_SCALAR >::NodeData() : n(0), l(0) {
        GUM_CONSTRUCTOR(NodeData);
      }

      template < typename GUM_SCALAR >
      INLINE NodeData< GUM_SCALAR >::NodeData(const NodeData< GUM_SCALAR >& from) :
          n(from.n), l(from.l) {
        GUM_CONS_CPY(NodeData);
      }

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

      template < typename GUM_SCALAR >
      INLINE bool NodeData< GUM_SCALAR >::operator==(
         const NodeData< GUM_SCALAR >& from) const {
        return (n == from.n) && (l == from.l);
      }

      template < typename GUM_SCALAR >
      INLINE bool NodeData< GUM_SCALAR >::operator!=(
         const NodeData< GUM_SCALAR >& from) const {
        return (n != from.n) && (l != from.l);
      }

      // EdgeData<GUM_SCALAR>

      template < typename GUM_SCALAR >
      INLINE EdgeData< GUM_SCALAR >::EdgeData() : u(0), v(0), l(0) {
        GUM_CONSTRUCTOR(EdgeData);
      }

      template < typename GUM_SCALAR >
      INLINE EdgeData< GUM_SCALAR >::EdgeData(const EdgeData< GUM_SCALAR >& from) :
          u(from.u), v(from.v), l(from.l) {
        GUM_CONS_CPY(EdgeData);
      }

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

      template < typename GUM_SCALAR >
      INLINE bool EdgeData< GUM_SCALAR >::operator==(
         const EdgeData< GUM_SCALAR >& from) const {
        return (u == from.u) && (l_u == from.l_u) && (v == from.v)
            && (l_v == from.l_v) && (l == from.l);
      }

      template < typename GUM_SCALAR >
      INLINE bool EdgeData< GUM_SCALAR >::operator!=(
         const EdgeData< GUM_SCALAR >& from) const {
        return (u != from.u) && (l_u != from.l_u) && (v != from.v)
            && (l_v != from.l_v) && (l != from.l);
      }

      // InterfaceGraph

      template < typename GUM_SCALAR >
      InterfaceGraph< GUM_SCALAR >::InterfaceGraph(
         const PRMSystem< GUM_SCALAR >& sys) :
          sys__(&sys),
          labels__(new Bijection< Idx, LabelData* >()), counter__(0),
          erase_flag__(true) {
        GUM_CONSTRUCTOR(InterfaceGraph);
        HashTable< std::string, LabelData* > label_map;

        // We need to add each instance in graph__
        for (auto iter = sys.begin(); iter != sys.end(); ++iter) {
          NodeData< GUM_SCALAR >* node = new NodeData< GUM_SCALAR >();
          node->n                      = iter.val();
          label__(node, label_map);
          graph__.addNodeWithId(iter.key());
          idMap__.insert(node->n, iter.key());
          nodes__.insert(iter.key(), node);
        }

        NodeData< GUM_SCALAR >* u = nullptr;
        NodeData< GUM_SCALAR >* v = nullptr;

        for (const auto& elt: nodes__) {
          NodeData< GUM_SCALAR >* data = elt.second;

          for (const auto chain: data->n->type().slotChains()) {
            for (const auto inst: data->n->getInstances(chain->id())) {
              u = (nodes__[idMap__[inst]]->l < data->l) ? nodes__[idMap__[inst]]
                                                        : data;
              v = (u != data) ? data : nodes__[idMap__[inst]];

              if (!graph__.existsEdge(idMap__[u->n], idMap__[v->n])) {
                EdgeData< GUM_SCALAR >* edge = new EdgeData< GUM_SCALAR >();
                edge->u                      = u->n;
                edge->l_u                    = u->l;
                edge->v                      = v->n;
                edge->l_v                    = v->l;
                label__(edge, label_map);
                graph__.addEdge(idMap__[u->n], idMap__[v->n]);
                edges__.insert(Edge(idMap__[u->n], idMap__[v->n]), edge);
              }
            }
          }
        }
      }

      template < typename GUM_SCALAR >
      InterfaceGraph< GUM_SCALAR >::InterfaceGraph(
         const InterfaceGraph< GUM_SCALAR >& source) :
          sys__(source.sys__),
          graph__(source.graph__), nodes__(source.nodes__),
          idMap__(source.idMap__), edges__(source.edges__),
          labels__(new Bijection< Idx, LabelData* >(*(source.labels__))),
          nodeMap__(source.nodeMap__), edgeMap__(source.edgeMap__),
          counter__(source.counter__), erase_flag__(false) {
        GUM_CONS_CPY(InterfaceGraph);
      }

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

        if (erase_flag__) {
          for (const auto& elt: nodes__)
            delete elt.second;

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

          for (const auto& elt: nodeMap__) {
            delete elt.first;
            delete elt.second;
          }

          for (const auto& elt: edgeMap__) {
            delete elt.first;
            delete elt.second;
          }
        }

        delete labels__;
      }

      template < typename GUM_SCALAR >
      InterfaceGraph< GUM_SCALAR >& InterfaceGraph< GUM_SCALAR >::operator=(
         const InterfaceGraph< GUM_SCALAR >& source) {
        GUM_ERROR(FatalError, "not implemented");
      }

      template < typename GUM_SCALAR >
      void InterfaceGraph< GUM_SCALAR >::label__(
         NodeData< GUM_SCALAR >*               node,
         HashTable< std::string, LabelData* >& label_map) {
        Size              size = Size(1);
        std::stringstream sBuff;
        sBuff << node->n->type().name();

        // First we search for multiple inputs
        for (const auto chain: node->n->type().slotChains()) {
          if (chain->isMultiple()) {
            sBuff << "-" << node->n->getInstances(chain->id()).size();
            sBuff << chain->name();
            size *= node->n->getInstances(chain->id()).size()
                  * chain->lastElt().type().variable().domainSize();
          } else {
            size *= chain->lastElt().type().variable().domainSize();
          }
        }

        // Second we search for active outputs
        for (const auto nn: node->n->type().containerDag().nodes()) {
          if (node->n->type().isOutputNode(node->n->type().get(nn))) {
            try {
              sBuff << "-" << node->n->getRefAttr(nn).size()
                    << node->n->get(nn).name();
              size *= node->n->get(nn).type().variable().domainSize();
            } catch (NotFound&) {
              // (nn) is an inactive output node
            }
          }
        }

        // Label is ready
        if (!label_map.exists(sBuff.str())) {
          LabelData* label = new LabelData();
          label_map.insert(sBuff.str(), label);
          label->id         = ++counter__;
          label->tree_width = size;
          label->l          = sBuff.str();
          labels__->insert(label->id, label);
          nodeMap__.insert(label, new Set< NodeData< GUM_SCALAR >* >());
        }

        node->l = label_map[sBuff.str()];
        nodeMap__[node->l]->insert(node);
      }

      template < typename GUM_SCALAR >
      void InterfaceGraph< GUM_SCALAR >::label__(
         EdgeData< GUM_SCALAR >*               edge,
         HashTable< std::string, LabelData* >& label_map) {
        Size              size = Size(1);
        std::stringstream sBuff;
        sBuff << edge->u->type().name() << "-" << edge->v->type().name();

        // First looking for edge->u output nodes in v
        for (const auto chain: edge->u->type().slotChains()) {
          if (edge->u->getInstances(chain->id()).exists(edge->v)) {
            sBuff << "-" << edge->v->type().name() << "."
                  << chain->lastElt().name();
            size *= chain->lastElt().type().variable().domainSize();
          }
        }

        // Second looking for edge->v output nodes in u
        for (const auto chain: edge->v->type().slotChains())
          if (edge->v->getInstances(chain->id()).exists(edge->u)) {
            sBuff << "-" << edge->u->type().name() << "."
                  << chain->lastElt().name();
            size *= chain->lastElt().type().variable().domainSize();
          }

        // Label is ready
        if (!label_map.exists(sBuff.str())) {
          LabelData* label = new LabelData();
          label_map.insert(sBuff.str(), label);
          label->id         = ++counter__;
          label->l          = sBuff.str();
          label->tree_width = size;
          labels__->insert(label->id, label);
          edgeMap__.insert(label, new Set< EdgeData< GUM_SCALAR >* >());
        }

        edge->l = label_map[sBuff.str()];
        edgeMap__[edge->l]->insert(edge);
      }

      template < typename GUM_SCALAR >
      INLINE UndiGraph& InterfaceGraph< GUM_SCALAR >::graph() {
        return graph__;
      }

      template < typename GUM_SCALAR >
      INLINE const UndiGraph& InterfaceGraph< GUM_SCALAR >::graph() const {
        return graph__;
      }

      template < typename GUM_SCALAR >
      INLINE Bijection< Idx, LabelData* >& InterfaceGraph< GUM_SCALAR >::labels() {
        return *labels__;
      }

      template < typename GUM_SCALAR >
      INLINE const Bijection< Idx, LabelData* >&
                   InterfaceGraph< GUM_SCALAR >::labels() const {
        return *labels__;
      }

      template < typename GUM_SCALAR >
      INLINE Size InterfaceGraph< GUM_SCALAR >::size(const LabelData* l) const {
        try {
          return nodeMap__[const_cast< LabelData* >(l)]->size();
        } catch (NotFound&) {
          return edgeMap__[const_cast< LabelData* >(l)]->size();
        }
      }

      template < typename GUM_SCALAR >
      INLINE Set< NodeData< GUM_SCALAR >* >&
             InterfaceGraph< GUM_SCALAR >::nodes(const LabelData* l) {
        return *(nodeMap__[const_cast< LabelData* >(l)]);
      }

      template < typename GUM_SCALAR >
      INLINE const Set< NodeData< GUM_SCALAR >* >&
                   InterfaceGraph< GUM_SCALAR >::nodes(const LabelData* l) const {
        return *(nodeMap__[const_cast< LabelData* >(l)]);
      }

      template < typename GUM_SCALAR >
      INLINE Set< EdgeData< GUM_SCALAR >* >&
             InterfaceGraph< GUM_SCALAR >::edges(const LabelData* l) {
        return *(edgeMap__[const_cast< LabelData* >(l)]);
      }

      template < typename GUM_SCALAR >
      INLINE const Set< EdgeData< GUM_SCALAR >* >&
                   InterfaceGraph< GUM_SCALAR >::edges(const LabelData* l) const {
        return *(edgeMap__[const_cast< LabelData* >(l)]);
      }

      template < typename GUM_SCALAR >
      INLINE LabelData* InterfaceGraph< GUM_SCALAR >::label(Idx id) {
        return labels__->second(id);
      }

      template < typename GUM_SCALAR >
      INLINE NodeId InterfaceGraph< GUM_SCALAR >::id(
         const PRMInstance< GUM_SCALAR >& i) const {
        return idMap__[const_cast< PRMInstance< GUM_SCALAR >* >(&i)];
      }

      template < typename GUM_SCALAR >
      INLINE NodeId InterfaceGraph< GUM_SCALAR >::id(
         const PRMInstance< GUM_SCALAR >* i) const {
        return idMap__[const_cast< PRMInstance< GUM_SCALAR >* >(i)];
      }

      template < typename GUM_SCALAR >
      INLINE NodeData< GUM_SCALAR >&
         InterfaceGraph< GUM_SCALAR >::node(const PRMInstance< GUM_SCALAR >* i) {
        return node(id(i));
      }

      template < typename GUM_SCALAR >
      INLINE const NodeData< GUM_SCALAR >& InterfaceGraph< GUM_SCALAR >::node(
         const PRMInstance< GUM_SCALAR >* i) const {
        return node(id(i));
      }

      template < typename GUM_SCALAR >
      INLINE NodeData< GUM_SCALAR >&
             InterfaceGraph< GUM_SCALAR >::node(NodeId id) {
        return *(nodes__[id]);
      }

      template < typename GUM_SCALAR >
      INLINE const NodeData< GUM_SCALAR >&
                   InterfaceGraph< GUM_SCALAR >::node(NodeId id) const {
        return *(nodes__[id]);
      }

      template < typename GUM_SCALAR >
      INLINE EdgeData< GUM_SCALAR >& InterfaceGraph< GUM_SCALAR >::edge(NodeId u,
                                                                        NodeId v) {
        try {
          return *(edges__[Edge(u, v)]);
        } catch (NotFound&) { return *(edges__[Edge(v, u)]); }
      }

      template < typename GUM_SCALAR >
      INLINE const EdgeData< GUM_SCALAR >&
                   InterfaceGraph< GUM_SCALAR >::edge(NodeId u, NodeId v) const {
        try {
          return *(edges__[Edge(u, v)]);
        } catch (NotFound&) { return *(edges__[Edge(v, u)]); }
      }

      template < typename GUM_SCALAR >
      INLINE std::ostream& operator<<(std::ostream&                 out,
                                      const NodeData< GUM_SCALAR >& data) {
        out << data.n->name() << "(" << data.l->l << ")";
        return out;
      }

      template < typename GUM_SCALAR >
      INLINE std::ostream& operator<<(std::ostream&                 out,
                                      const EdgeData< GUM_SCALAR >& data) {
        out << data.u->name() << " -> " << data.v->name() << "(" << data.l->l
            << ")";
        return out;
      }

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