dynamic_graph.hpp

// FEAT3: Finite Element Analysis Toolbox, Version 3
// Copyright (C) 2010 by Stefan Turek & the FEAT group
// FEAT3 is released under the GNU General Public License version 3,
// see the file 'copyright.txt' in the top level directory for details.
 
#pragma once
 
// includes, FEAT
#include <kernel/adjacency/base.hpp>
#include <kernel/adjacency/adjactor.hpp>
 
// includes, system
#include <algorithm>
#include <vector>
#include <set>
 
namespace FEAT
{
  namespace Adjacency
  {
    class DynamicGraph
    {
    protected:
      typedef std::set<Index> IdxSet;
      typedef std::vector<IdxSet> IdxSetVec;
 
    public:
      typedef IdxSet::const_iterator ImageIterator;
 
    protected:
      Index _num_nodes_domain;
      Index _num_nodes_image;
      IdxSetVec _indices;
 
    public:
      DynamicGraph() :
        _num_nodes_domain(0),
        _num_nodes_image(0)
      {
      }
 
      explicit DynamicGraph(
        Index num_nodes_domain,
        Index num_nodes_image)
         :
        _num_nodes_domain(num_nodes_domain),
        _num_nodes_image(num_nodes_image),
        _indices(num_nodes_domain)
      {
      }
 
      template<typename Adjactor_>
      explicit DynamicGraph(
        RenderType render_type,
        const Adjactor_& adjactor)
         :
        _num_nodes_domain(0),
        _num_nodes_image(0),
        _indices()
      {
        switch(render_type)
        {
        case RenderType::as_is:
        case RenderType::as_is_sorted:
        case RenderType::injectify:
        case RenderType::injectify_sorted:
          _render_as_is(adjactor);
          break;
 
        case RenderType::transpose:
        case RenderType::transpose_sorted:
        case RenderType::injectify_transpose:
        case RenderType::injectify_transpose_sorted:
          _render_transpose(adjactor);
          break;
        }
      }
 
      template<
        typename Adjactor1_,
        typename Adjactor2_>
      explicit DynamicGraph(
        RenderType render_type,
        const Adjactor1_& adjactor1,
        const Adjactor2_& adjactor2)
         :
        _num_nodes_domain(0),
        _num_nodes_image(0),
        _indices()
      {
        switch(render_type)
        {
        case RenderType::as_is:
        case RenderType::as_is_sorted:
        case RenderType::injectify:
        case RenderType::injectify_sorted:
          _render_as_is(adjactor1, adjactor2);
          break;
 
        case RenderType::transpose:
        case RenderType::transpose_sorted:
        case RenderType::injectify_transpose:
        case RenderType::injectify_transpose_sorted:
          _render_transpose(adjactor1, adjactor2);
          break;
        }
      }
 
      DynamicGraph(DynamicGraph&& other) :
        _num_nodes_domain(other._num_nodes_domain),
        _num_nodes_image(other._num_nodes_image),
        _indices(std::move(other._indices))
      {
      }
 
      DynamicGraph& operator=(DynamicGraph&& other)
      {
        // avoid self-move
        if(this == &other)
          return *this;
 
        _num_nodes_domain = other._num_nodes_domain;
        _num_nodes_image = other._num_nodes_image;
        _indices = std::move(other._indices);
 
        other._num_nodes_domain = other._num_nodes_image = Index(0);
 
        return *this;
      }
 
      virtual ~DynamicGraph()
      {
      }
 
      DynamicGraph clone() const
      {
        DynamicGraph graph(_num_nodes_domain, _num_nodes_image);
        graph._indices = _indices;
        return graph;
      }
 
      Index degree(Index domain_node) const
      {
        ASSERTM(domain_node < _num_nodes_domain, "Domain node index out of range");
        return Index(_indices[domain_node].size());
      }
 
      Index degree() const
      {
        Index deg(0);
        for(Index i(0); i < _num_nodes_domain; ++i)
        {
          deg = std::max(deg, Index(_indices[i].size()));
        }
        return deg;
      }
 
      Index get_num_indices() const
      {
        Index nidx(0);
        for(Index i(0); i < _num_nodes_domain; ++i)
        {
          nidx += Index(_indices[i].size());
        }
        return nidx;
      }
 
      void clear()
      {
        for(Index i(0); i < _num_nodes_domain; ++i)
        {
          _indices[i].clear();
        }
      }
 
      bool exists(Index domain_node, Index image_node) const
      {
        ASSERTM(domain_node < _num_nodes_domain, "Domain node index out of range");
        ASSERTM(image_node < _num_nodes_image, "Image node index out of range");
        return _indices[domain_node].find(image_node) != _indices[domain_node].end();
      }
 
      bool insert(Index domain_node, Index image_node)
      {
        ASSERTM(domain_node < _num_nodes_domain, "Domain node index out of range");
        ASSERTM(image_node < _num_nodes_image, "Image node index out of range");
        return _indices[domain_node].insert(image_node).second;
      }
 
      bool erase(Index domain_node, Index image_node)
      {
        ASSERTM(domain_node < _num_nodes_domain, "Domain node index out of range");
        ASSERTM(image_node < _num_nodes_image, "Image node index out of range");
        // note: std::set.erase() returns the number of deleted elements
        return _indices[domain_node].erase(image_node) > 0;
      }
 
      template<typename Adjactor_>
      void compose(const Adjactor_& adjactor)
      {
        XASSERTM(_num_nodes_image == adjactor.get_num_nodes_domain(), "Adjactor dimension mismatch!");
 
        typedef typename Adjactor_::ImageIterator AImIt;
 
        // image index buffer vector
        std::vector<Index> img_idx;
 
        // loop over all domain nodes
        for(Index i(0); i < _num_nodes_domain; ++i)
        {
          // clear image index buffer
          img_idx.clear();
 
          // loop over all image indices of this adjactor and make a backup of them
          {
            ImageIterator it(_indices[i].begin());
            ImageIterator jt(_indices[i].end());
            for(; it != jt; ++it)
            {
              img_idx.push_back(*it);
            }
          }
 
          // clear the current domain node
          _indices[i].clear();
 
          // loop over all entries of the index buffer vector
          for(Index j(0); j < img_idx.size(); ++j)
          {
            // iterator over all adjacent nodes
            AImIt it(adjactor.image_begin(img_idx[j]));
            AImIt jt(adjactor.image_end(img_idx[j]));
            for(; it != jt; ++it)
            {
              _indices[i].insert(*it);
            }
          }
        }
 
        // store new image node count
        _num_nodes_image = adjactor.get_num_nodes_image();
      }
 
      /* *************************************************** */
      /*  R E N D E R   F U N C T I O N   T E M P L A T E S  */
      /* *************************************************** */
    private:
      // renders adjactor
      template<typename Adjactor_>
      void _render_as_is(const Adjactor_& adj)
      {
        typedef typename Adjactor_::ImageIterator AImIt;
 
        // set counts
        _num_nodes_domain = adj.get_num_nodes_domain();
        _num_nodes_image = adj.get_num_nodes_image();
        _indices.resize(_num_nodes_domain);
 
        // loop over all domain nodes
        for(Index i(0); i < _num_nodes_domain; ++i)
        {
          AImIt cur(adj.image_begin(i));
          AImIt end(adj.image_end(i));
          for(; cur != end; ++cur)
          {
            insert(i, *cur);
          }
        }
      }
 
      // renders transposed adjactor
      template<typename Adjactor_>
      void _render_transpose(const Adjactor_& adj)
      {
        typedef typename Adjactor_::ImageIterator AImIt;
 
        // set counts
        _num_nodes_domain = adj.get_num_nodes_image();
        _num_nodes_image = adj.get_num_nodes_domain();
        _indices.resize(_num_nodes_domain);
 
        // loop over all image nodes
        for(Index i(0); i < _num_nodes_image; ++i)
        {
          AImIt cur(adj.image_begin(i));
          AImIt end(adj.image_end(i));
          for(; cur != end; ++cur)
          {
            insert(*cur, i);
          }
        }
      }
 
      // renders adjactor composition
      template<
        typename Adjactor1_,
        typename Adjactor2_>
      void _render_as_is(
        const Adjactor1_& adj1,
        const Adjactor2_& adj2)
      {
        // validate adjactor dimensions
        XASSERTM(adj1.get_num_nodes_image() == adj2.get_num_nodes_domain(), "Adjactor dimension mismatch!");
 
        typedef typename Adjactor1_::ImageIterator AImIt1;
        typedef typename Adjactor2_::ImageIterator AImIt2;
 
        // set counts
        _num_nodes_domain = adj1.get_num_nodes_domain();
        _num_nodes_image = adj2.get_num_nodes_image();
        _indices.resize(_num_nodes_domain);
 
        // loop over all domain nodes
        for(Index i(0); i < _num_nodes_domain; ++i)
        {
          AImIt1 cur1(adj1.image_begin(i));
          AImIt1 end1(adj1.image_end(i));
          for(; cur1 != end1; ++cur1)
          {
            AImIt2 cur2(adj2.image_begin(*cur1));
            AImIt2 end2(adj2.image_end(*cur1));
            for(; cur2 != end2; ++cur2)
            {
              insert(i, *cur2);
            }
          }
        }
      }
 
      template<
        typename Adjactor1_,
        typename Adjactor2_>
      void _render_transpose(
        const Adjactor1_& adj1,
        const Adjactor2_& adj2)
      {
        // validate adjactor dimensions
        XASSERTM(adj1.get_num_nodes_image() == adj2.get_num_nodes_domain(), "Adjactor dimension mismatch!");
 
        typedef typename Adjactor1_::ImageIterator AImIt1;
        typedef typename Adjactor2_::ImageIterator AImIt2;
 
        // set counts
        _num_nodes_domain = adj2.get_num_nodes_image();
        _num_nodes_image = adj1.get_num_nodes_domain();
        _indices.resize(_num_nodes_domain);
 
        // loop over all domain nodes
        for(Index i(0); i < _num_nodes_image; ++i)
        {
          AImIt1 cur1(adj1.image_begin(i));
          AImIt1 end1(adj1.image_end(i));
          for(; cur1 != end1; ++cur1)
          {
            AImIt2 cur2(adj2.image_begin(*cur1));
            AImIt2 end2(adj2.image_end(*cur1));
            for(; cur2 != end2; ++cur2)
            {
              insert(*cur2, i);
            }
          }
        }
      }
 
      /* ******************************************************************* */
      /*  A D J A C T O R   I N T E R F A C E   I M P L E M E N T A T I O N  */
      /* ******************************************************************* */
    public:
      inline Index get_num_nodes_domain() const
      {
        return _num_nodes_domain;
      }
 
      inline Index get_num_nodes_image() const
      {
        return _num_nodes_image;
      }
 
      inline ImageIterator image_begin(Index domain_node) const
      {
        ASSERTM(domain_node < _num_nodes_domain, "Domain node index out of range");
        return _indices[domain_node].begin();
      }
 
      inline ImageIterator image_end(Index domain_node) const
      {
        ASSERTM(domain_node < _num_nodes_domain, "Domain node index out of range");
        return _indices[domain_node].end();
      }
    }; // class DynamicGraph
  } // namespace Adjacency
} // namespace FEAT