EGTGraph.h

Go to the documentation of this file.

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

$Id: EGTGraph.h,v 1.10 2003/01/27 10:11:46 miyabi Exp $
Copyright (C) 2002 Higuchi Lab. All rights reserved.

*****************************************************************************/
#ifndef INCLUDE__GRAPH_H__FILE
#define INCLUDE__GRAPH_H__FILE

#include "defs.h"
#include "env.h"
#include "EGException.h"
#include "EGRandom.h"
#include "EGTVector.h"
#include <fstream>
#include <iterator>  // for advance(), distance()
#include <algorithm> // for find()
template<class TSG, class TF>
class EGTGraph {
public:
  typedef TSG                     SubGraph;
  typedef EGTVector<TSG*>         SubGraphs;
  typedef typename SubGraphs::Iterator SubGraphsIterator;
  typedef typename SubGraphs::ConstIterator SubGraphsConstIterator;
  typedef TF                      Fitness;
  typedef typename SubGraph::Node Node;
  typedef EGTVector<Node*>        Nodes;
  typedef typename Nodes::Iterator NodesIterator;
  typedef typename Nodes::ConstIterator NodesConstIterator;
  typedef EGTGraph<TSG, TF>  Self;

  static Node* m_tCreator;

  EGTGraph();
  EGTGraph(const Self&);
  virtual ~EGTGraph();

  virtual bool InitGraph();
  virtual bool InitGraph(const SubGraph&);
  virtual bool InitGraph(const SubGraph&, const SubGraph&, UInt ope = 0);
  virtual bool LoadGraph(const char* pFileName);
  virtual void SaveGraph(std::ostream&) const;
  virtual void Display(std::ostream&) const;
  virtual void DisplayDot(std::ostream&) const;

  SubGraph* CreateComplementarySubGraph(UInt uNum, UInt uMax = 0) const;
  SubGraph* GetSubGraph(UInt);
  const SubGraph* GetSubGraph(UInt) const;
  const SubGraph* GetSubGraph(const SubGraph&, UInt*) const;
  UInt GetNumSubGraphs() const;

  bool GetEvaluated() const   { return m_bEvaluated; }
  void SetEvaluated(bool ret) { m_bEvaluated = ret;  }
  UInt GetGraphID() const   { return m_uGraphID; }
  void SetGraphID(UInt ret) { m_uGraphID = ret; }
  UInt GetNumNodes() const { return m_tNodes.Size(); }
  const Node* GetNode(UInt uNodeID) const { return m_tNodes[uNodeID]; }
  Node* GetNode(UInt uNodeID)             { return m_tNodes[uNodeID]; }
  Float GetFitness() const { return m_tFitness.GetFitness(); }
  void DisplayFitness(std::ostream&, bool) const;
  UInt GetOperator() const { return m_uOperator; }
  void SetOperator(UInt n) { m_uOperator = n; }
  UInt GetMother() const { return m_uMother; }
  void SetMother(UInt n) { m_uMother = n; }
  UInt GetFather() const { return m_uFather; }
  void SetFather(UInt n) { m_uFather=n; }
  void SetOrigin(UInt n);

protected:
  void CreateSubGraphs() const;
  void CreateSubGraphsPowerSet() const;
  void CreateSubGraphsRandomly() const;
  SubGraph* CreateSubGraph() const;
  SubGraph* CreateSubGraphConstraint() const;
  bool IsConnected(Nodes nodes) const;

  Nodes GetCandidates() const;
  void CreatePowerSet(UInt) const;
  void ClearSubGraphs();
  void AssignNodeID();
  bool IsSubGraphRegistered(const SubGraph&) const;

  UInt m_uGraphID;                 
  Nodes m_tNodes;
  Fitness m_tFitness;
  bool m_bEvaluated;

  mutable SubGraphs m_tSubGraphs;

  static EGTVector<EGTVector<UInt> > m_tPowerSet;
  static bool m_bConstraint;

  enum {POWERSET_LIMIT = 6};

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

  UInt m_uOperator; 
  UInt m_uMother;   
  // Father's Graph ID number
  UInt m_uFather;   
};


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

//============================================================================
template<class TSG, class TF>
UInt EGTGraph<TSG, TF>::GetNumSubGraphs() const
{
  if (m_tSubGraphs.Empty()) {
    CreateSubGraphs();
  }
  return m_tSubGraphs.Size();
}

//============================================================================
template<class TSG, class TF>
void EGTGraph<TSG, TF>::ClearSubGraphs()
{
  SubGraphsIterator it = m_tSubGraphs.Begin();
  SubGraphsIterator itEnd = m_tSubGraphs.End();
  for (; it != itEnd; ++it) {
    delete (*it);
  }
  m_tSubGraphs.Clear();
}

//============================================================================
template<class TSG, class TF>
EGTGraph<TSG, TF>::EGTGraph()
  : m_uGraphID(0), m_bEvaluated(false), m_uOperator(OP_UNDEF), m_uMother(0), m_uFather(0)
{
  if (m_tPowerSet.Empty()) {
    CreatePowerSet(POWERSET_LIMIT);
  }
}

//============================================================================
template<class TSG, class TF>
EGTGraph<TSG, TF>::EGTGraph(const Self& graph)
  : m_tFitness(graph.m_tFitness), m_bEvaluated(graph.m_bEvaluated), 
  m_uOperator(OP_UNDEF), m_uMother(0), m_uFather(0)
{
  //Copies all the Nodes 
  NodesConstIterator itEnd = graph.m_tNodes.End();
  for (NodesConstIterator it = graph.m_tNodes.Begin(); it != itEnd; ++it) {
    m_tNodes.PushBack(new Node(**it));
  }

  //Copies all the information about directed edges
  UInt uTermNum, uNodeID;
  NodesIterator      itDest   = m_tNodes.Begin();
  NodesConstIterator itSrc    = graph.m_tNodes.Begin();
  NodesConstIterator itSrcEnd = graph.m_tNodes.End();
  for (; itSrc != itSrcEnd; ++itSrc, ++itDest) {
    for (UInt i=0; i<(*itSrc)->GetNumInTerms(); ++i) {
      if ((*itSrc)->GetInTerm(i)->GetTerm()) {
        uNodeID = (*itSrc)->GetInTerm(i)->GetDestNodeID();
        uTermNum = (*itSrc)->GetInTerm(i)->GetDestTermNum();
        (*itDest)->ConnectSrc(i, GetNode(uNodeID)->GetOutTerm(uTermNum));
      }
    }
  }

  //Copies all the SubGraphs.
  SubGraphsConstIterator itSubGraph    = graph.m_tSubGraphs.Begin();
  SubGraphsConstIterator itSubGraphEnd = graph.m_tSubGraphs.End();
  for (; itSubGraph != itSubGraphEnd; ++itSubGraph) {
    Nodes ptSrcNodes;
    for (NodesConstIterator it2 = (*itSubGraph)->GetNodes()->Begin();
         it2 != (*itSubGraph)->GetNodes()->End(); ++it2) {
      ptSrcNodes.PushBack(GetNode((*it2)->GetNodeID()));
    }
    SubGraph* pTmpSubGraph = new SubGraph(ptSrcNodes, false);
    m_tSubGraphs.PushBack(pTmpSubGraph);
  }
}

//============================================================================
template<class TSG, class TF>
EGTGraph<TSG, TF>::~EGTGraph()
{
  NodesIterator itEnd = m_tNodes.End();
  for (NodesIterator it = m_tNodes.Begin(); it != itEnd; ++it) {
    delete (*it);
  }
  SubGraphsIterator itEnd2 = m_tSubGraphs.End();
  for (SubGraphsIterator it = m_tSubGraphs.Begin(); it != itEnd2; ++it) {
    delete (*it);
  }
}

//============================================================================
template<class TSG, class TF>
bool EGTGraph<TSG, TF>::InitGraph()
{
  UInt uIn = Env::Instance().NumIn();
  UInt uOut = Env::Instance().NumOut();

  SubGraph* psg = new SubGraph;
  if ((psg->InitSubGraph(uIn, uOut) == false) ||
      (InitGraph(*psg) == false)) {
    delete psg;
    return false;
  }
  delete psg;
  return true;
}

//============================================================================
template<class TSG, class TF>
bool EGTGraph<TSG, TF>::InitGraph(const SubGraph& subgraph)
{
  UInt uMaxNodeSize = Env::Instance().MaxNodeSize();
  if ((subgraph.GetNumNodes() == 0) ||
      (subgraph.GetNumNodes() +
       subgraph.GetNumInTerms() +
       subgraph.GetNumOutTerms() > 2 * uMaxNodeSize)) {
    return false;
  }
  SubGraph* psg = new SubGraph(subgraph);

  Node* pn;
  // Generates input Nodes.
  UInt uIn = psg->GetNumInTerms();
  for (UInt i=0; i<uIn; ++i) {
    pn = m_tCreator->CreateInputNode(i+1);
    pn->ConnectDest(0, psg->GetInTerm(i));
    m_tNodes.PushBack(pn);
  }
  // Generates output Nodes.
  UInt uOut = psg->GetNumOutTerms();
  for (UInt i=0; i<uOut; ++i) {
    pn = m_tCreator->CreateOutputNode(i+1);
    pn->ConnectSrc(0, psg->GetOutTerm(i));
    m_tNodes.PushBack(pn);
  }
  //Copies all Nodes.
  psg->Release(&m_tNodes);
  delete psg;
  AssignNodeID();
  return true;
}

//============================================================================
template<class TSG, class TF>
bool EGTGraph<TSG, TF>::InitGraph(const SubGraph& sub1,
                                  const SubGraph& sub2,
                                  UInt ope)
{
  UInt uMaxNodeSize = Env::Instance().MaxNodeSize();

  if ((sub1.GetNumNodes() == 0) ||
      (sub2.GetNumNodes() == 0) ||
      (sub1.GetNumNodes() + sub2.GetNumNodes() > 2*uMaxNodeSize)) {
    return false;
  }

  //Combines the SubGraphs.
  SubGraph* psg1 = new SubGraph(sub1);
  SubGraph* psg2 = new SubGraph(sub2);

  if (ope == OP_CROSSOVER) { // crossover
    psg1->SetOrigin(ORI_CROSSOVER_A);
    psg2->SetOrigin(ORI_CROSSOVER_B);
  }
  else if (ope == OP_MUTATION) { // mutation
    psg1->SetOrigin(ORI_MUTATION_A);
    psg2->SetOrigin(ORI_MUTATION_B);
  }
  else {
    psg1->SetOrigin(ORI_UNDEF);
    psg2->SetOrigin(ORI_UNDEF);
  }

  psg1->ConnectSubGraph(*psg2);
  psg1->Release(&m_tNodes);
  psg2->Release(&m_tNodes);
  AssignNodeID();
  delete psg1;
  delete psg2;
  return true;
}

//============================================================================
template<class TSG, class TF>
void EGTGraph<TSG, TF>::SaveGraph(std::ostream& out) const
{
  //Number of Nodes
  const UInt uNumNodes = m_tNodes.Size();
  out << uNumNodes << ' ';

  //Functional ID numbers
  for (UInt i=0; i<uNumNodes; ++i) {
    out << GetNode(i)->GetFuncID() << ' ';
  }
  out << "\n\n";

  //Edge information
  for (UInt i=0; i<uNumNodes; ++i) {
    const Node* pn = GetNode(i);
    UInt uIn = pn->GetNumInTerms();
    for (UInt j=0; j<uIn; ++j) {
      out << pn->GetInTerm(j)->GetDestNodeID()  << ' ';
      out << pn->GetInTerm(j)->GetDestTermNum() << ' ';
    }
    UInt uOut = pn->GetNumOutTerms();
    for (UInt j=0; j<uOut; ++j) {
      out << pn->GetOutTerm(j)->GetDestNodeID()  << ' ';
      out << pn->GetOutTerm(j)->GetDestTermNum() << ' ';
    }
    out << pn->GetNO() << ' ';
    pn->SaveExtraData(out);
    out << '\n';
  }
  out << '\n';
  //SubGraphs
  if (m_tSubGraphs.Size() == 0) {
    out << "0\n";
  }
  else {
    SubGraphsConstIterator it    = m_tSubGraphs.Begin();
    SubGraphsConstIterator itEnd = m_tSubGraphs.End();
    for (; it != itEnd; ++it) {
      (*it)->SaveSubGraph(out);
    }
  }
}

//============================================================================
template<class TSG, class TF>
bool EGTGraph<TSG, TF>::LoadGraph(const char* pFileName)
{
  std::ifstream fin(pFileName);
  if (!fin) {
    throw EGException("EGTGraph::LoadGraph(), Can't open file",
                      __FILE__, __LINE__);
  }
  //Nodes
  UInt FuncID, NodeID, TermNum, uNO;
  UInt uNumNodes;
  fin >> uNumNodes;
  for (UInt i=0; i<uNumNodes; ++i) {
    fin >> FuncID;
    if (fin.eof()) {
      break;
    }
    Node* newNode = m_tCreator->CreateNode(FuncID);
    newNode->SetNodeID(i);
    m_tNodes.PushBack(newNode);
  }
  //Edge information
  for (UInt i=0; i<uNumNodes; ++i) {
    for (UInt j=0; j<GetNode(i)->GetNumInTerms(); ++j) {
      fin >> NodeID;
      fin >> TermNum;
      GetNode(i)->GetInTerm(j)->SetTerm(GetNode(NodeID)->GetOutTerm(TermNum));
    }
    for (UInt j=0; j<GetNode(i)->GetNumOutTerms(); ++j) {
      fin >> NodeID;
      fin >> TermNum;
      GetNode(i)->GetOutTerm(j)->SetTerm(GetNode(NodeID)->GetInTerm(TermNum));
    }
    fin >> uNO;
    GetNode(i)->SetNO(uNO);
    if (GetNode(i)->LoadExtraData(fin) == false) {
      throw EGException("LoadExtraData() == false", __FILE__, __LINE__);
    }
  }
  //SubGraphs.
  Nodes tmpNodes;
  SubGraph* tmpSubGraph;
  while (1) {
    fin >> uNumNodes;
    if (uNumNodes == 0 || fin.eof()) {
      break;
    }
    tmpNodes.Clear();
    for (UInt i=0; i<uNumNodes; ++i) {
      fin >> NodeID;
      tmpNodes.PushBack(GetNode(NodeID));
    }
    tmpSubGraph = new SubGraph(tmpNodes, false);
    m_tSubGraphs.PushBack(tmpSubGraph);
  }
  return true;
}
//============================================================================
template<class TSG, class TF>
typename EGTGraph<TSG, TF>::Nodes
EGTGraph<TSG, TF>::GetCandidates() const
{
  Nodes ret;
  NodesConstIterator it    = m_tNodes.Begin();
  NodesConstIterator itEnd = m_tNodes.End();
  for (; it != itEnd; ++it) {
    if ((*it)->IsCandidate()) {
      ret.PushBack(*it);
    }
  }
  return ret;
}

//============================================================================
template<class TSG, class TF>
TSG* EGTGraph<TSG, TF>::CreateSubGraph() const
{
  //Gets the set of Nodes.
  Nodes tUnSelList = GetCandidates();
  if (tUnSelList.Empty()) {
    return 0;
  }
  UInt uMaxNodeSize = Env::Instance().MaxNodeSize();
  //Determines the number of Nodes.
  UInt uNumNodes = EGRandom::NextInt(1, tUnSelList.Size());
  if (uNumNodes > uMaxNodeSize) {
    uNumNodes = uMaxNodeSize;
  }

  UInt uSelNum;
  Nodes tSelList;
  while (tSelList.Size() < uNumNodes) {
    uSelNum = EGRandom::NextInt(0, tUnSelList.Size()-1);
    NodesIterator it = tUnSelList.Begin();
    std::advance(it, uSelNum);
    tSelList.PushBack(*it);
    tUnSelList.Erase(it);
  }

  SubGraph* psg = new SubGraph(tSelList, false);
  return psg;
}

//============================================================================
template<class TSG, class TF>
void EGTGraph<TSG, TF>::CreateSubGraphs() const
{
  Nodes tCandidates = GetCandidates();
  if (tCandidates.Size() <= POWERSET_LIMIT) {
    CreateSubGraphsPowerSet();
  }
  else {
    CreateSubGraphsRandomly();
  }
}

//============================================================================
template<class TSG, class TF>
void EGTGraph<TSG, TF>::CreateSubGraphsRandomly() const
{
  //Number of SubGraphs to be generated
  const UInt uSubGraphSize = Env::Instance().SubGraphSize();
  //Maximum number of iterations
  const UInt uSubGraphTrySize = uSubGraphSize * 2; 

  UInt count = 0;
  for (UInt i=0; i<uSubGraphTrySize; ++i) {
    SubGraph* psg;
    if (m_bConstraint) {
      psg = CreateSubGraphConstraint();
    }
    else {
      psg = CreateSubGraph();
    }
    if (psg) { 
      if (IsSubGraphRegistered(*psg) == true) {
        delete psg;
      }
      else {
        m_tSubGraphs.PushBack(psg);
        ++count;
        if (uSubGraphSize == count) {
          return;
        }
      }
    }
  }
}

//============================================================================
template<class TSG, class TF>
typename EGTGraph<TSG, TF>::SubGraph* 
EGTGraph<TSG, TF>::CreateSubGraphConstraint() const
{
  Nodes offNodes = GetCandidates();
  Nodes onNodes, fixedNodes;

  UInt uMaxNodeSize = Env::Instance().MaxNodeSize();
  //Determines the number of Nodes.
  UInt uNumNodes = EGRandom::NextInt(1, offNodes.Size());
  if (uNumNodes > uMaxNodeSize) {
    uNumNodes = uMaxNodeSize;
  }

  UInt n = EGRandom::NextInt(0, offNodes.Size()-1);
  NodesIterator it = offNodes.Begin();
  NodesIterator itTemp;
  std::advance(it, n);
  Node* pn = *it;
  onNodes.PushBack(pn);
  offNodes.Erase(it);

  do {
    UInt m = EGRandom::NextInt(0, onNodes.Size()-1);
    it = onNodes.Begin();
    std::advance(it, m);
    pn = *it;
    fixedNodes.PushBack(pn);
    onNodes.Erase(it);

    for (UInt i=0; i<pn->GetNumInTerms(); ++i) {
      Node* destNode = pn->GetInTerm(i)->GetDestNode();
      itTemp = std::find(offNodes.Begin(), offNodes.End(), destNode);
      if (itTemp != offNodes.End()) {
        onNodes.PushBack(*itTemp);
        offNodes.Erase(itTemp);
      }
    }
    for (UInt i=0; i<pn->GetNumOutTerms(); ++i) {
      Node* destNode = pn->GetOutTerm(i)->GetDestNode();
      itTemp = std::find(offNodes.Begin(), offNodes.End(), destNode);
      if (itTemp != offNodes.End()) {
        onNodes.PushBack(*itTemp);
        offNodes.Erase(itTemp);
      }
    }
  } while (fixedNodes.Size() < uNumNodes && onNodes.Size() > 0);
  
  SubGraph* psg = new SubGraph(fixedNodes, false);
  return psg;
}

//============================================================================
template<class TSG, class TF>
bool EGTGraph<TSG, TF>::IsSubGraphRegistered(const SubGraph& subgraph) const
{
  SubGraphsConstIterator it    = m_tSubGraphs.Begin();
  SubGraphsConstIterator itEnd = m_tSubGraphs.End();
  for (; it != itEnd; ++it) {
    if (subgraph == **it) {
      return true;
    }
  }
  return false;
}

//============================================================================
template<class TSG, class TF>
void EGTGraph<TSG, TF>::CreateSubGraphsPowerSet() const
{
  //Gets the set of Nodes.
  Nodes ptFuncNodes = GetCandidates();

  Nodes ptSelNodes;
  const UInt uNumNodes = ptFuncNodes.Size();
  const UInt uLimit = (1 << uNumNodes) - 1;
  for (UInt i=0; i<uLimit; ++i) {
    ptSelNodes.Clear();
    EGTVector<UInt>::Iterator it2    = m_tPowerSet[i].Begin();
    EGTVector<UInt>::Iterator it2End = m_tPowerSet[i].End();
    for (; it2 != it2End; ++it2) {
      ptSelNodes.PushBack(ptFuncNodes[*it2]);
    }
    if ((m_bConstraint == true && IsConnected(ptSelNodes) == true) || 
        (m_bConstraint == false)) {
      SubGraph* psg = new SubGraph(ptSelNodes, false);
      m_tSubGraphs.PushBack(psg);
    }
  }
}

//============================================================================
template<class TSG, class TF>
bool EGTGraph<TSG, TF>::IsConnected(Nodes nodes) const
{
  if (nodes.Size() == 0) {
    return false;
  }
  else if (nodes.Size() == 1) {
    return true;
  }
  NodesIterator it, itTemp;
  Nodes onNodes;
  itTemp = nodes.Begin();
  onNodes.PushBack(*itTemp);
  nodes.Erase(itTemp);

  while (!onNodes.Empty()) {
    it = onNodes.Begin();
    Node* theNode = *it;
    onNodes.Erase(it);

    UInt uNumIn = theNode->GetNumInTerms();
    for (UInt i=0; i<uNumIn; ++i) {
      if (theNode->GetInTerm(i)->GetTerm()) {
        Node* node = theNode->GetInTerm(i)->GetDestNode();
        itTemp = std::find(nodes.Begin(), nodes.End(), node);
        if (itTemp != nodes.End()) {
          onNodes.PushBack(*itTemp);
          nodes.Erase(itTemp);
          if (nodes.Empty()) {
            return true;
          }
        }
      }
    }
    UInt uNumOut = theNode->GetNumOutTerms();
    for (UInt i=0; i<uNumOut; ++i) {
      if (theNode->GetOutTerm(i)->GetTerm()) {
        Node* node = theNode->GetOutTerm(i)->GetDestNode();
        itTemp = std::find(nodes.Begin(), nodes.End(), node);
        if (itTemp != nodes.End()) {
          onNodes.PushBack(*itTemp);
          nodes.Erase(itTemp);
          if (nodes.Empty()) {
            return true;
          }
        }
      }
    }
  }
  return false;
}

//============================================================================
template<class TSG, class TF>
void EGTGraph<TSG, TF>::CreatePowerSet(UInt to) const
{
  // Generates subsets.
  EGTVector<UInt> temp;
  temp.PushBack(0);
  m_tPowerSet.PushBack(temp);
  
  if (to <= 1) {
    return;
  }
  for (UInt i=1; i<to; ++i) {
    EGTVector<UInt> temp2;
    temp2.PushBack(i);
    m_tPowerSet.PushBack(temp2);
    UInt uLimit = (1 << i) - 1;
    for (UInt j=0; j<uLimit; ++j) {
      EGTVector<UInt> tVec = m_tPowerSet[j];
      tVec.PushBack(i);
      m_tPowerSet.PushBack(tVec);
    }
  }
}

//============================================================================
template<class TSG, class TF>
void EGTGraph<TSG, TF>::AssignNodeID()
{
  UInt i = 0;
  NodesIterator it    = m_tNodes.Begin();
  NodesIterator itEnd = m_tNodes.End();
  for (; it != itEnd; ++it) {
    (*it)->SetNodeID(i++);
  }
}

//============================================================================
template<class TSG, class TF>
TSG* EGTGraph<TSG, TF>::CreateComplementarySubGraph(UInt uNum, UInt uMax) const
{
  if (uMax == 0) {
    uMax = Env::Instance().MaxNodeSize();
  }

  const SubGraph* ptSelSubGraph = GetSubGraph(uNum);
  if ((ptSelSubGraph == 0) ||
      (GetNumNodes() - ptSelSubGraph->GetNumNodes() > uMax)) {
    return 0;
  }

  Nodes tRestNodes;              //Set of remaining nodes
  NodesConstIterator itSel;    //Set of selected nodes
  UInt uNodeID;
  bool bFind = false;

  const Nodes* ptSelNodes = ptSelSubGraph->GetNodes();
  //For each Node of this Graph
  NodesConstIterator itEnd = m_tNodes.End();
  for (NodesConstIterator it = m_tNodes.Begin(); it != itEnd; ++it) {
    //If the Node is not composed of the SubGraph, adds it to "tRestNodes".
    uNodeID = (*it)->GetNodeID();
    for (itSel = ptSelNodes->Begin(); itSel != ptSelNodes->End(); ++itSel) {
      if (uNodeID == (*itSel)->GetNodeID()) {
        bFind = true;
        break;
      }
    }
    if (bFind == true) {
      bFind = false;
    }
    else {
      tRestNodes.PushBack(*it);
    }
  }
  SubGraph* ptNewSubGraph = new SubGraph(tRestNodes, false);
  return ptNewSubGraph;
}

//============================================================================
template<class TSG, class TF>
const TSG* EGTGraph<TSG, TF>::GetSubGraph(const SubGraph& subgraph,
  UInt* uNum) const
{
  if (m_tSubGraphs.Empty()) {
    CreateSubGraphs();
  }
  
#ifdef DISPLAY_NUM_COMPATIBLE
  UInt n = 0;
  SubGraphsConstIterator it0    = m_tSubGraphs.Begin();
  SubGraphsConstIterator itEnd0 = m_tSubGraphs.End();
  for (; it0 != itEnd0; ++it0) {
    if (subgraph.IsCompatible(**it0) == true) {
      ++n;
    }
  }
  std::cout << n << '/' << m_tSubGraphs.Size() << '\n';
#endif // DISPLAY_NUM_COMPATIBLE

  UInt uFrom = EGRandom::NextInt(0, m_tSubGraphs.Size()-1);
  SubGraphsConstIterator itBegin = m_tSubGraphs.Begin();
  SubGraphsConstIterator it = itBegin;
  std::advance(it, uFrom);
  SubGraphsConstIterator itFrom = it;
  SubGraphsConstIterator itEnd = m_tSubGraphs.End();
  for (; it != itEnd; ++it) {
    if (subgraph.IsCompatible(**it) == true) {
      *uNum = std::distance(itBegin, it);
      return *it;
    }
  }
  for (it = m_tSubGraphs.Begin(); it != itFrom; ++it) {
    if (subgraph.IsCompatible(**it) == true) {
      *uNum = std::distance(itBegin, it);
      return *it;
    }
  }
  return 0;
}

//============================================================================
template<class TSG, class TF>
TSG* EGTGraph<TSG, TF>::GetSubGraph(UInt uNum)
{
  if (m_tSubGraphs.Empty()) {
    CreateSubGraphs();
  }
  if (uNum >= m_tSubGraphs.Size()) {
    return 0;
  }
  else {
    return m_tSubGraphs[uNum];
  }
}

//============================================================================
template<class TSG, class TF>
const TSG* EGTGraph<TSG, TF>::GetSubGraph(UInt uNum) const
{
  if (m_tSubGraphs.Empty()) {
    CreateSubGraphs();
  }
  if (uNum >= m_tSubGraphs.Size()) {
    return 0;
  }
  else {
    return m_tSubGraphs[uNum];
  }
}

//============================================================================
template<class TSG, class TF>
void EGTGraph<TSG, TF>::Display(std::ostream& out) const
{
  out << "Fitness  : " << GetFitness() << '\n';
  out << "NodeSize : " << m_tNodes.Size() << '\n';
  NodesConstIterator itEnd = m_tNodes.End();
  for (NodesConstIterator it = m_tNodes.Begin(); it != itEnd; ++it) {
    (*it)->Display(out);
  }
  if (!m_tSubGraphs.Empty()) {
    out << "\nSubGraphList\n";
    UInt i = 0;
    SubGraphsConstIterator itEnd2 = m_tSubGraphs.End();
    for (SubGraphsConstIterator it = m_tSubGraphs.Begin(); it!=itEnd2; ++it) {
      out << "*****SubGraph " << ++i << "*****\n";
      (*it)->Display(out);
    }
  }
  out << '\n';
  SaveGraph(out);
  m_tFitness.Display(out, true);
  out << '\n';
  m_tFitness.Display(out, false);
}

//============================================================================
template<class TSG, class TF>
void EGTGraph<TSG, TF>::DisplayFitness(std::ostream& out, bool title = false) const
{
  m_tFitness.Display(out, title);
}

//============================================================================
template<class TSG, class TF>
void EGTGraph<TSG, TF>::DisplayDot(std::ostream& out) const
{
  out << "digraph circuit_graph {\n";
  out << "rankdir=\"LR\";\n";
  NodesConstIterator itEnd = m_tNodes.End();

  for (NodesConstIterator it = m_tNodes.Begin(); it != itEnd; ++it) {
    out << (*it)->GetName() << " [style=filled,fillcolor=";
    switch ((*it)->GetOrigin()) {
    case ORI_UNDEF:       out << "gray90"; break;      // undef
    case ORI_CROSSOVER_A: out << "aquamarine"; break;  // crossover a
    case ORI_CROSSOVER_B: out << "yellow"; break;      // crossover b
    case ORI_MUTATION_A:  out << "gray90"; break;      // mutation a
    case ORI_MUTATION_B:  out << "violet"; break;      // mutation b
    case ORI_SELECTION:   out << "gray90"; break;      // selection
    default: out << "gray90"; break;
    }
    out << "];\n";
  }

  for (NodesConstIterator it = m_tNodes.Begin(); it != itEnd; ++it) {
    UInt uNumOut = (*it)->GetNumOutTerms();
    for (UInt i=0; i<uNumOut; ++i) {
      out << (*it)->GetName() << " -> ";
      out << (*it)->GetOutTerm(i)->GetDestNode()->GetName();

      out << " [label=\"";
      out << (*it)->GetOutLabel(i);
      UInt in = (*it)->GetOutTerm(i)->GetTerm()->GetTermNum();
      out << (*it)->GetOutTerm(i)->GetDestNode()->GetInLabel(in);
      out << "\"];\n";
    }
  }
  out << "};\n";
}

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

template<class TSG, class TF>
typename EGTGraph<TSG, TF>::Node*
EGTGraph<TSG, TF>::m_tCreator = 0;

template<class TSG, class TF>
EGTVector<EGTVector<UInt> > EGTGraph<TSG, TF>::m_tPowerSet;

template<class TSG, class TF>
bool EGTGraph<TSG, TF>::m_bConstraint = false;

#endif //INCLUDE__GRAPH_H__FILE