CMappedDirGraph.hpp

/* This file is part of sUtil, a random collection of utilities.

sUtil 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.

Alternatively, you can redistribute it and/or
modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of
the License, or (at your option) any later version.

sUtil 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 General Public License for more details.

You should have received a copy of the GNU Lesser General Public
License and a copy of the GNU General Public License along with
sUtil. If not, see <http://www.gnu.org/licenses/>.
 */
/* \file CMappedDirGraph.hpp
 *
 *  Created on: Jul 7, 2014
 *
 *  Copyright (C) 2014, Samir Menon <smenon@stanford.edu>
 */

#ifndef CMAPPEDDIRGRAPH_HPP_
#define CMAPPEDDIRGRAPH_HPP_

#include <sutil/CMappedTree.hpp>
#include <limits>

#ifdef DEBUG
#include <iostream>
#include <cassert>
#endif

namespace sutil
{
  template <typename TIdx, typename TNode>
  class CMappedDirGraph : public sutil::CMappedTree<TIdx,TNode>
  {
  public:
    std::vector<std::pair<TNode*, TNode*> > st_broken_edges_;

    struct SMGNodeBase;

    CMappedDirGraph() : CMappedTree<TIdx,TNode>::CMappedTree() { st_broken_edges_.clear(); }
    virtual ~CMappedDirGraph() { }

    virtual bool linkNodes();

    virtual bool genSpanningTree();
  }; //End of template class

  template <typename TIdx, typename TNode>
  struct CMappedDirGraph<TIdx,TNode>::SMGNodeBase : public CMappedTree<TIdx,TNode>::SMTNodeBase
  {
  public:
    std::vector<TIdx> gr_parent_names_;
    std::vector<TNode*> gr_parent_addrs_;
    std::vector<TNode*> gr_child_addrs_;

    SMGNodeBase() : CMappedTree<TIdx,TNode>::SMTNodeBase()
    {
      gr_parent_names_.clear();
      gr_parent_addrs_.clear();
      gr_child_addrs_.clear();
    }
  };

  /***************************************************************
   *******************************Function Definitions*************
   ****************************************************************
   */
  template <typename TIdx, typename TNode>
  bool CMappedDirGraph<TIdx,TNode>::linkNodes()
  {
    //Clear previous links (if any)
    typename CMappedList<TIdx,TNode>::iterator it,ite;
    for(it = CMappedList<TIdx,TNode>::begin(),
        ite = CMappedList<TIdx,TNode>::end();
        it != ite; ++it)
    {
      TNode& tmp_node = *it;

      //Clear the graph
      tmp_node.gr_parent_addrs_.clear();
      tmp_node.gr_child_addrs_.clear();
    }

    //Form the new links for the graph
    for(it = CMappedList<TIdx,TNode>::begin(), ite = CMappedList<TIdx,TNode>::end();
        it != ite; ++it)
    {
      TNode& tmp_node = *it;
      //Iterate over all nodes and connect them to their
      //parents
      if(&tmp_node == CMappedTree<TIdx,TNode>::root_node_)
      {//No parents
        continue;
      }
      else
      {
        typename std::vector<TIdx>::iterator itp,itpe; //Each TIdx corresponds to an entry in : std::vector<TNode*> parent_addrs_;
        for(itp = tmp_node.gr_parent_names_.begin(), itpe = tmp_node.gr_parent_names_.end();
            itp!=itpe;++itp)
        {
          TNode * tmp_node2add = sutil::CMappedList<TIdx,TNode>::at(*itp);
          if(tmp_node2add == NULL)
          {//No parent -- Ignore this node
#ifdef DEBUG
            std::cerr<<"\nCBranchingStructure::linkNodes(): Warning.";
            std::cerr<<"Orphan node found: "<<*itp<<". Ignoring.";
#endif
            continue;
          }
          //Link the node
          tmp_node.gr_parent_addrs_.push_back(tmp_node2add);
          tmp_node2add->child_addrs_.push_back(&tmp_node);

#ifdef DEBUG
          std::cerr<<"\n\tAdding child "<<tmp_node.name_
              <<" to (parent) "<<tmp_node2add->name_;
          std::cerr<<std::flush;
#endif
        }
      }
    }//End of while loop

    //Now set up the spanning tree and affirm initialization is complete.
    bool flag = genSpanningTree();
    CMappedTree<TIdx,TNode>::has_been_init_ = false; //Not done yet.

    //Now compute the broken edges.
    st_broken_edges_.clear();
    for(it = CMappedList<TIdx,TNode>::begin(), ite = CMappedList<TIdx,TNode>::end();
        it != ite; ++it)
    {
      TNode &tmp_node = *it;
      typename std::vector<TIdx>::iterator itp,itpe; //Each TIdx corresponds to an entry in : std::vector<TNode*> parent_addrs_;
      for(itp = tmp_node.gr_parent_names_.begin(), itpe = tmp_node.gr_parent_names_.end();
          itp!=itpe;++itp)
      {
        TIdx &pidx = *itp;
        TNode* test_parent = CMappedList<TIdx,TNode>::at(pidx);
        if(test_parent != tmp_node.parent_addr_)
        {//Found a parent who is disconnected in the spanning tree
          std::pair<TNode*, TNode*> tmp_broken_edge;
          tmp_broken_edge.first = test_parent;
          tmp_broken_edge.second = &tmp_node;
          st_broken_edges_.push_back(tmp_broken_edge);
        }
      }
    }

    CMappedTree<TIdx,TNode>::has_been_init_ = true; //Finally done.

    //Return the end result
    return CMappedTree<TIdx,TNode>::has_been_init_;
  }

  template <typename TIdx, typename TNode>
  bool CMappedDirGraph<TIdx,TNode>::genSpanningTree()
  {
    // Must have a root node to be able to create the spanning tree.
    // NOTE TODO : Potentially eliminate this requirement and pick a suitable root node.
    TNode* root = CMappedTree<TIdx,TNode>::getRootNode();
    if(NULL == root)
    { return false; }

    int graph_sz = CMappedList<TIdx,TNode>::size();

    struct SSTreeStruct{  bool in_stree_; TNode* node_; };
    SSTreeStruct *in_stree = new SSTreeStruct[graph_sz];

    //First populate the node pointers (create a temp data struct to store stuff).
    typename CMappedTree<TIdx,TNode>::iterator it,ite;
    int i=0;
    for(it = CMappedTree<TIdx,TNode>::begin(), ite = CMappedTree<TIdx,TNode>::end(); it!=ite; ++it)
    {
      //Get the node's numeric index in the underlying mapped list.
      i = CMappedList<TIdx,TNode>::getIndexNumericAt(&(*it));
      //Set values at corresponding position in the data struct array
      in_stree[i].node_ = &(*it);
      if(CMappedTree<TIdx,TNode>::getRootNodeConst() == in_stree[i].node_)
      { in_stree[i].in_stree_ = true; }
      else
      { in_stree[i].in_stree_ = false;  }
    }

    //Now compute the spanning tree.
    bool complete = false;
    int nodes_in_stree_pre = 1, nodes_in_stree_curr = 1;//Only root so far.
    while(false == complete)
    {
      //Update distances from the spanning tree for each node
      for(int i=0; i<graph_sz; ++i)
      {
        if(in_stree[i].in_stree_){  continue; } //I'm already in.

        // Else try to find a parent for me.
        typename std::vector<TIdx>::iterator itp, itpe;
        for(itp = in_stree[i].node_->gr_parent_names_.begin(),itpe = in_stree[i].node_->gr_parent_names_.end();
            itp!=itpe;++itp)
        {
          TIdx &pidx = *itp;
          int pnidx = CMappedList<TIdx,TNode>::getIndexNumericAt(pidx); //numeric parent index
#ifdef DEBUG
          assert(-1 != pnidx);
#endif
          if(in_stree[pnidx].in_stree_)
          {//Parent is in the spanning tree. Then add me as a child and forget about other parents.
            in_stree[i].node_->parent_name_ = in_stree[pnidx].node_->name_;
            in_stree[i].in_stree_ = true;
            nodes_in_stree_curr++;
            break;
          }
        }
      }

      // Check if all nodes have been added to the spanning tree.
      complete = true;
      for(int i=0; complete && i<graph_sz; ++i)
      { complete = (complete && in_stree[i].in_stree_); }

      if(false == complete && nodes_in_stree_curr == nodes_in_stree_pre)
      { return false; }//Could not add any node this time. And not complete. Algo is stuck.
      else
      { nodes_in_stree_pre = nodes_in_stree_curr; }
    }

    //Start at the root node (which has, presumably, been set)
    return CMappedTree<TIdx,TNode>::linkNodes();
  }

}//End of namespace sutil

#endif /*CMAPPEDDIRGRAPH_HPP_*/