EGTSubGraph.h

Go to the documentation of this file.

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

$Id: EGTSubGraph.h,v 1.7 2002/12/17 10:22:24 motegi Exp $
Copyright (C) 2002 Higuchi Lab. All rights reserved.

*****************************************************************************/
#ifndef INCLUDE__SUBGRAPH_H__FILE
#define INCLUDE__SUBGRAPH_H__FILE

#include "defs.h"
#include "env.h"
#include "EGException.h"
#include "EGRandom.h"
#include "EGTAbstractNode.h"
#include "EGTVector.h"

template<class TN>
class EGTSubGraph: public EGTAbstractNode<typename TN::Term> {
public:
  typedef typename TN::Term     Term;
  typedef EGTVector<Term*>      Terms;
  typedef TN                    Node;
  typedef EGTVector<Node*>      Nodes;
  typedef typename Nodes::Iterator NodesIterator;
  typedef typename Nodes::ConstIterator NodesConstIterator;
  typedef EGTAbstractNode<Term> Base;
  typedef EGTSubGraph<Node>     Self;

  static Node* m_tCreator;

  EGTSubGraph() : Base(0, 0), m_tNodes(0), m_bOwner(false) { }
  EGTSubGraph(const Self&, bool);
  EGTSubGraph(const Nodes&, bool);
  virtual ~EGTSubGraph() { Clear(); }

  virtual bool InitSubGraph(UInt uNumIn, UInt uNumOut, UInt arg = 0);
  virtual bool IsCompatible(const Self&) const;
  virtual bool ConnectSubGraph(Self&);
  virtual void SaveSubGraph(std::ostream&) const;
  virtual void Display(std::ostream&) const;

  void Release(Nodes* dest);
  void SetOrigin(UInt n);

  UInt GetNumNodes() const      { return m_tNodes.Size(); }
  const Nodes* GetNodes() const { return &m_tNodes;       }

  bool operator==(const Self& rhs) const;

protected:
  virtual void DeepCopy(const Nodes&);
  virtual void RegistTerms();
  virtual void ConnectNodes(UInt uNumIn, UInt uNumOut);

  Node* GetNode(UInt uNodeID);
  virtual void AddNode(Node*, UInt);
  void AddNodeNormal(Node*, UInt);                 // for AddNode
  void AddNodeCompleteCircuitForest(Node*, UInt);  // for AddNode

  void AssignNodeID();
  void Clear();

  void RemoveInTerm(UInt uTermNum) {
    CheckNumInTerms(uTermNum, __FILE__, __LINE__);
    m_tInTerms.Erase(m_tInTerms.Begin()+uTermNum);
  }
  void RemoveOutTerm(UInt uTermNum) {
    CheckNumOutTerms(uTermNum, __FILE__, __LINE__);
    m_tOutTerms.Erase(m_tOutTerms.Begin()+uTermNum);
  }
  void AddInTerm(Term* pt)  { m_tInTerms.PushBack(pt);  }
  void AddOutTerm(Term* pt) { m_tOutTerms.PushBack(pt); }
  bool IsTermUnconnected(Term*) const;

  Nodes m_tNodes;          
  bool  m_bOwner;

  enum {LOOP_TIMES = 10};   
  enum {BASE_NODE_SIZE = 5};

private:
  Self& operator=(const Self&);
};


//============================================================================
template<class TN>
void EGTSubGraph<TN>::SetOrigin(UInt n)
{
  NodesIterator itEnd = m_tNodes.End();
  for (NodesIterator it = m_tNodes.Begin(); it != itEnd; ++it) {
    (*it)->SetOrigin(n);
  }
}

//============================================================================
template<class TN>
EGTSubGraph<TN>::EGTSubGraph(const Self& rhs, bool owns = true)
  : Base(0, 0), m_tNodes(0), m_bOwner(owns)
{
  if (owns) {
    DeepCopy(rhs.m_tNodes);
  }
  else {
    m_tNodes = rhs.m_tNodes;
    RegistTerms();
  }
}

//============================================================================
template<class TN>
EGTSubGraph<TN>::EGTSubGraph(const Nodes& rhs, bool owns = true)
  : Base(0, 0), m_tNodes(0), m_bOwner(owns)
{
  if (owns) {
    DeepCopy(rhs);
  }
  else {
    m_tNodes = rhs;
    RegistTerms();
  }
}

//============================================================================
template<class TN>
bool EGTSubGraph<TN>::InitSubGraph(UInt uNumIn, UInt uNumOut, UInt arg)
{
  UInt uMaxNodeSize = Env::Instance().MaxNodeSize();

  Clear();
  Node* pn;
  Int iDiff;
  UInt uTryCount;
  for (uTryCount=0; uTryCount<LOOP_TIMES; ++uTryCount) {
    m_bOwner = true;
    UInt uNumNodes = EGRandom::NextInt(1, BASE_NODE_SIZE);
    for (UInt i=0; i<uNumNodes; ++i) {
      pn = m_tCreator->CreateNode();
      AddNode(pn, uNumOut);
    }
    iDiff = (uNumOut - uNumIn) - (GetNumOutTerms() - GetNumInTerms());
    while (((GetNumInTerms() < uNumIn) || (GetNumOutTerms() < uNumOut) ||
            (iDiff != 0)) && (GetNumNodes() < uMaxNodeSize)) {
      pn = m_tCreator->CreateNodeDiff(iDiff);
      AddNode(pn, uNumOut);
      iDiff = (uNumOut - uNumIn) - (GetNumOutTerms() - GetNumInTerms());
    }
    if (GetNumNodes() < uMaxNodeSize) {
      break;
    }
    else {
      Clear();
    }
  }
  if (uTryCount == LOOP_TIMES) {
    return false;
  }
  AssignNodeID();
  ConnectNodes(uNumIn, uNumOut);
  return true;
}

//============================================================================
template<class TN>
void EGTSubGraph<TN>::Release(Nodes* dest)
{
  NodesIterator itEnd = m_tNodes.End();
  for (NodesIterator it = m_tNodes.Begin(); it != itEnd; ++it) {
    dest->PushBack(*it);
  }
  m_bOwner = false; //Releases ownership
  Clear();          
}

//============================================================================
template<class TN>
bool EGTSubGraph<TN>::ConnectSubGraph(Self& rhs)
{
  UInt uRan;
  UInt uNumIn = GetNumInTerms();
  for (UInt i=0; i<uNumIn; ++i) {
    uRan = EGRandom::NextInt(0, rhs.GetNumOutTerms()-1);
    ConnectSrc(i, rhs.GetOutTerm(uRan));
    rhs.RemoveOutTerm(uRan);
  }
  UInt uNumOut = GetNumOutTerms();
  for (UInt i=0; i<uNumOut; ++i) {
    uRan = EGRandom::NextInt(0, rhs.GetNumInTerms()-1);
    ConnectDest(i, rhs.GetInTerm(uRan));
    rhs.RemoveInTerm(uRan);
  }
  return true;
}

//============================================================================
template<class TN>
bool EGTSubGraph<TN>::IsCompatible(const Self& rhs) const
{
  if ((GetNumInTerms()  == rhs.GetNumInTerms()) &&
      (GetNumOutTerms() == rhs.GetNumOutTerms())) {
    return true;
  }
  else {
    return false;
  }
}

//============================================================================
template<class TN>
bool EGTSubGraph<TN>::operator==(const Self& rhs) const
{
  if (GetNumNodes() != rhs.GetNumNodes()) {
    return false;
  }
  const Nodes* tnodes = &(rhs.m_tNodes);
  bool bFind;
  NodesConstIterator itEnd = m_tNodes.End();
  NodesConstIterator itEnd2 = tnodes->End();
  for (NodesConstIterator it = m_tNodes.Begin(); it != itEnd; ++it) {
    bFind = false;
    for (NodesConstIterator it2 = tnodes->Begin(); it2 != itEnd2; ++it2) {
      if (*it == *it2) {
        bFind = true;
        break;
      }
    }
    if (bFind == false) {
      return false;
    }
  }
  return true;
}

//============================================================================
template<class TN>
void EGTSubGraph<TN>::Display(std::ostream& out) const
{
  out << "NumNode: " << GetNumNodes() << ", ";
  out << "I/O: " << GetNumInTerms() << ',' << GetNumOutTerms() << '\n';
  SaveSubGraph(out);
}

//============================================================================
template<class TN>
void EGTSubGraph<TN>::SaveSubGraph(std::ostream& out) const
{
  out << m_tNodes.Size() << ' ';
  NodesConstIterator itEnd = m_tNodes.End();
  for (NodesConstIterator it = m_tNodes.Begin(); it != itEnd; ++it) {
    out << (*it)->GetNodeID() << ' ';
  }
  out << '\n';
}

//============================================================================
template<class TN>
void EGTSubGraph<TN>::DeepCopy(const Nodes& rhs)
{
  //Makes a deep copy of the array of Nodes.
  NodesConstIterator itSrc    = rhs.Begin();
  NodesConstIterator itSrcEnd = rhs.End();
  for (; itSrc != itSrcEnd; ++itSrc) {
    m_tNodes.PushBack(new Node(**itSrc));
  }
  //Reproduces the edge information.
  UInt uTermNum, uNodeID;
  NodesIterator itDest = m_tNodes.Begin();
  for (itSrc = rhs.Begin(); itSrc != itSrcEnd; ++itSrc, ++itDest){
    for (UInt i=0; i<(*itSrc)->GetNumInTerms(); ++i) {
      if (IsTermUnconnected((*itSrc)->GetInTerm(i)) == true) {
        AddInTerm((*itDest)->GetInTerm(i));
      }
      else {
        uNodeID = (*itSrc)->GetInTerm(i)->GetDestNodeID();
        uTermNum = (*itSrc)->GetInTerm(i)->GetDestTermNum();
        if (GetNode(uNodeID)) {
          (*itDest)->ConnectSrc(i, GetNode(uNodeID)->GetOutTerm(uTermNum));
        }
      }
    }
    for (UInt i=0; i<(*itSrc)->GetNumOutTerms(); ++i) {
      if (IsTermUnconnected((*itSrc)->GetOutTerm(i)) == true) {
        AddOutTerm((*itDest)->GetOutTerm(i));
      }
    }
  }
}

//============================================================================
template<class TN>
void EGTSubGraph<TN>::RegistTerms()
{
  NodesIterator itEnd = m_tNodes.End();
  for (NodesIterator it = m_tNodes.Begin(); it != itEnd; ++it) {
    UInt uNumIn = (*it)->GetNumInTerms();
    for (UInt i=0; i<uNumIn; ++i) {
      if (IsTermUnconnected((*it)->GetInTerm(i))) { 
        AddInTerm((*it)->GetInTerm(i));
      }
    }
    UInt uNumOut = (*it)->GetNumOutTerms();
    for (UInt i=0; i<uNumOut; ++i) {
      if (IsTermUnconnected((*it)->GetOutTerm(i))) {
        AddOutTerm((*it)->GetOutTerm(i));
      }
    }
  }
}

//============================================================================
template<class TN>
bool EGTSubGraph<TN>::IsTermUnconnected(Term* pt) const
{
  if (pt->GetTerm() == 0) {
    return true;
  }
  UInt uNodeID = pt->GetDestNodeID();
  NodesConstIterator itEnd = m_tNodes.End();
  for (NodesConstIterator it = m_tNodes.Begin(); it != itEnd; ++it) {
    if ((*it)->GetNodeID() == uNodeID) {
      return false;
    }
  }
  return true;
}

//============================================================================
template<class TN>
void EGTSubGraph<TN>::AddNode(Node* pn, UInt uOut)
{
  AddNodeNormal(pn, uOut);
}

//============================================================================
template<class TN>
void EGTSubGraph<TN>::AddNodeNormal(Node* pn, UInt uOut)
{
  m_tNodes.PushBack(pn);
  UInt uNumIn = pn->GetNumInTerms();
  for (UInt i=0; i<uNumIn; ++i) {
    AddInTerm(pn->GetInTerm(i));
  }
  UInt uNumOut = pn->GetNumOutTerms();
  for (UInt i=0; i<uNumOut; ++i) {
    AddOutTerm(pn->GetOutTerm(i));
  }  
}

//============================================================================
template<class TN>
void EGTSubGraph<TN>::AddNodeCompleteCircuitForest(Node* pn, UInt uOut) 
{
  UInt uRan;
  m_tNodes.PushBack(pn);
  for (UInt i=0; i<pn->GetNumOutTerms(); ++i) {
    if (GetNumOutTerms() < uOut) {
      AddOutTerm(pn->GetOutTerm(i));
    }
    else if (GetNumInTerms() > 0) {
      uRan = EGRandom::NextInt(0, GetNumInTerms()-1);
      ConnectSrc(uRan, pn->GetOutTerm(i));
      RemoveInTerm(uRan);
    }
    else {
      AddOutTerm(pn->GetOutTerm(i));
    }
  }
  for (UInt i=0; i<pn->GetNumInTerms(); ++i) {
    AddInTerm(pn->GetInTerm(i));
  }
}

//============================================================================
template<class TN>
void EGTSubGraph<TN>::ConnectNodes(UInt uNumIn, UInt uNumOut)
{
  UInt uRanA, uRanB;
  while (GetNumOutTerms() != uNumOut) {
    uRanA = EGRandom::NextInt(0, GetNumInTerms()-1);
    uRanB = EGRandom::NextInt(0, GetNumOutTerms()-1);
    ConnectSrc(uRanA, GetOutTerm(uRanB));   
    RemoveInTerm(uRanA);                    
    RemoveOutTerm(uRanB);
  }
}

//============================================================================
template<class TN>
void EGTSubGraph<TN>::AssignNodeID()
{
  if (m_bOwner == false) {
    throw EGException("EGTSubGraph::AssignNodeID(), "
                      "No ownership of the target Node.",
                      __FILE__, __LINE__);
  }
  UInt i = 0;
  NodesIterator itEnd = m_tNodes.End();
  for (NodesIterator it = m_tNodes.Begin(); it != itEnd; ++it) {
    (*it)->SetNodeID(i++);
  }
}


//============================================================================
template<class TN>
void EGTSubGraph<TN>::Clear()
{
  if (m_bOwner) {
    NodesIterator itEnd = m_tNodes.End();
    for (NodesIterator it = m_tNodes.Begin(); it != itEnd; ++it) {
      delete (*it);
    }
    m_bOwner = false;
  }
  m_tNodes.Clear();
  m_tInTerms.Clear();
  m_tOutTerms.Clear();
}

//============================================================================
template<class TN>
TN* EGTSubGraph<TN>::GetNode(UInt uNodeID)
{
  NodesConstIterator itEnd = m_tNodes.End();
  for (NodesConstIterator it = m_tNodes.Begin(); it != itEnd; ++it) {
    if ((*it)->GetNodeID() == uNodeID) {
      return *it;
    }
  }
  return 0;
}

//============================================================================

template<class TN>
TN* EGTSubGraph<TN>::m_tCreator = 0;

#endif //INCLUDE__SUBGRAPH_H__FILE