graph.h

/**************************************************************************
 * Copyright (c) 2002-2011 T. M. Murali                                   *
 * Copyright (c) 2007-2011 Naveed Massjouni                               *
 * Copyright (c) 2009-2011 Christopher L. Poirel                          *
 * Copyright (c) 2010-2011 Ahsanur Rahman                                 *
 * Copyright (c) 2011 David Badger                                        *
 * Copyright (c) 2005 Shivaram Narayanan                                  *
 *                                                                        *
 * This file is part of Biorithm.                                         *
 *                                                                        *
 * Biorithm is free software: 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 3 of the License, or      *
 * (at your option) any later version.                                    *
 *                                                                        *
 * Biorithm 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 General Public License      *
 * along with Biorithm.  If not, see <http://www.gnu.org/licenses/>.      *
 *                                                                        *
 **************************************************************************/

#ifndef _GRAPH_H
#define _GRAPH_H

#include <algorithm>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <stack>
#include <vector>

#include <math.h>

// for converting integer to string
#include <sstream>

#ifdef HAVE_GLPK
extern "C"
{
#include <glpk.h>
}
#endif

#include "graph-global.h"
#include "histogram.h"
#include "myiterator.h"
#include "setTemplates.C"
//#include "generic.h"
//using namespace myNamespace;
//#include "reporter.h"

using namespace std;

// this string is a separator between node ids and types in the string
// representing an edge. this string is used in MyEdge::getEdge() and
// in _getEdge() in active-networks.C
//
// "_" is a bad idea for a separator because
// sometimes node names may have "_" in them. in that case, parsing
// the node names and types from edge string becomes problematic.
const string EDGE_STRING_SEPARATOR = "~@@~";

// a small value to use in MyNode::updateTotalEdgeWeight(). 
const MyNT EDGE_WEIGHT_EPSILON = 1E-05;

struct negativeLogTransform : public unary_function< MyNT, MyNT > 
{
  MyNT operator()(const MyNT __x) const
    {
      return(-log(__x));
    }
  
};

struct exponentNegativeTransform : public unary_function< MyNT, MyNT > 
{
  MyNT operator()(const MyNT __x) const
    {
      return(exp(- __x));
    }
};

struct oneMinusTransform : public unary_function< MyNT, MyNT > 
{
  MyNT operator()(const MyNT __x) const
    {
      return(1 - __x);
    }
};

struct oneMinusExponentNegativeTransform : public unary_function< MyNT, MyNT > 
{
  MyNT operator()(const MyNT __x) const
    {
      return(1 - exp(- __x));
    }
};



// typedef int MyNodeId;
typedef string MyNodeId;
typedef vector< string > MyNodeIdList;
typedef set< string > MyNodeIdSet;

// forward declaration
class MyGraph;
class MyEdge;

// i cannot use MyInfo since that class is defined in libexpression.
class MyGraphInfo
{
public:
  // murali, sep 12, 2007. incredibly, i did not have a constructor
  // (or a destructor) for this class. weight got assigned weird
  // values sometimes.
  MyGraphInfo()
      :  _evidence(),  _hidden(false), _weight(0), _types()
    {}
  virtual ~MyGraphInfo()
    {}

  void clear()
    {
      _evidence.clear();
    }
  void setWeight(MyNT w)
    {
      _weight = w;
    }
  MyNT getWeight() const
    {
      return(_weight);
    }

  // functions related to edge types.
  bool hasType(string type)
    {
      return(_types.end() != _types.find(type));
    }
  
  void addType(string type)
    {
      _types.insert(type);
    }
  void addTypes(const set< string > &types)
    {
      _types = types;
    }
  void getTypes(set< string > &types) const
    {
      types = _types;
    }
private:
  // source of evidence for this interaction.
  vector< string > _evidence;
  // is this edge hidden or not.
  bool _hidden;
  // weight of the edge.
  MyNT _weight;
  // edge types. 
  set< string > _types;
};

// function objects for combining weights.
struct combineAND : public binary_function< MyNT, MyNT, MyNT> 
{
  MyNT operator()(const MyNT __x, const MyNT __y) const
    {
      return(__x*__y);
    }
};


// assumes but does not check that bith arguments are between 0 and 1.
struct combineOR : public binary_function< MyNT, MyNT, MyNT> 
{
  MyNT operator()(const MyNT __x, const MyNT __y) const
    {
      return(1 - (1 -__x)*(1 - __y));
    }
};

typedef MyGraphInfo MyNodeInfo;

class MyNode
{
public:
  // this typedef is just to make sure i define MyEdgeList exactly as
  // in MyGraph. i do not create any variables of this type in MyNode.
  typedef list< MyEdge > MyEdgeList;
  typedef MyEdgeList::iterator MyEdgePtr;
  typedef MyEdgeList::const_iterator MyConstEdgePtr;
  
  // nested class
  template< typename Object, typename ObjectPtr > class EdgeObjectIterator;
  
  typedef  EdgeObjectIterator< MyEdgePtr, map< MyNodeId, MyEdgePtr >::iterator > MyEdgeIterator;
  typedef  EdgeObjectIterator< MyConstEdgePtr, map< MyNodeId, MyConstEdgePtr >::iterator > MyConstEdgeIterator;

//  class MyEdgeIterator;

  typedef MyEdgeIterator EdgeIterator;
  typedef MyConstEdgeIterator ConstEdgeIterator;
  
  
private:
  MyNodeId _id;
  MyNodeInfo _nodeInfo;
  
  int _index;
  // the set of functions associated with a node.
  vector< string > _functions;
  bool _hidden;

  // weight of the node.
  MyNT _weight;

  // _edges is a (hash)map< MyNodeId, iterator >, where the iterator
  // points to the global list of edges in the graph. iterator is like
  // "position" in goodrich+tamassia. the list of edges in MyGraph is
  // a list< MyEdge > so that iterators do not get invalidated by edge
  // deletion.
//   set< MyNodeId > _edges;
//   MyEdgeList _edgeList;
  map< MyNodeId, MyEdgePtr > _edges;


  
//  MyNodeEdgeWeights _edgeWeights;
  MyNT _totalEdgeWeight;
  // edge weights may be negative. this variable stores the sum of the
  // absolute values of these weights.
  MyNT _totalAbsoluteEdgeWeight;
  unsigned int _numHiddenEdges;
  
  map< string, bool > _status;


  // the graph the node belongs to.
//  const MyGraph *_graph;


private:
  // private methods.

  
public:
  
template< typename Object, typename ObjectPtr >
class EdgeObjectIterator: public MyIterator< Object >
{
private:
  ObjectPtr start, end, current;

public:
  EdgeObjectIterator()
  {}
  EdgeObjectIterator(ObjectPtr _start, ObjectPtr _end)
  {
    start = _start;
    current = _start;
    end = _end;
  }
    
  virtual bool hasNext()
  {
    return(current != end);
  }
  Object& next()
  {
    Object& _next = (*current).second;
    current++;
    return(_next);
  }
};

public:
  
  MyNode()
      : _id(), _nodeInfo(),_index(), _functions(), _hidden(false), _weight(0),
        _edges(), _totalEdgeWeight(0), _totalAbsoluteEdgeWeight(0),
      _numHiddenEdges(0),
    _status()
    {}

  MyNode(MyNodeId name)
      : _id(name), _nodeInfo(),_index(), _functions(), _hidden(false),  _weight(0),
        _edges(), _totalEdgeWeight(0), _totalAbsoluteEdgeWeight(0),
        _numHiddenEdges(0),
        _status()
    {}

  MyNode(const MyNode &copy)
      : _id(copy._id), _nodeInfo(copy._nodeInfo),
        _index(copy._index), _functions(copy._functions),
        _hidden(copy._hidden), _weight(copy._weight),  
        _edges(copy._edges), _totalEdgeWeight(copy._totalEdgeWeight),
        _totalAbsoluteEdgeWeight(copy._totalAbsoluteEdgeWeight),
        _numHiddenEdges(copy._numHiddenEdges), _status(copy._status)
    {}

  // copy certain aspects of copy into *this.
  void copy(const MyNode &copy);
  
  bool operator==(const MyNode &rhs)
    {
      return(_id == rhs._id);
    }
  
  const MyNode &operator=(const MyNode &rhs)
    {
#ifdef DEBUG
//       cout << "\tIn MyNode::operator= for node "
//            << rhs.getId() << "!" << endl;
#endif
      if (this != &rhs)
        {
          clear();
          _id = rhs._id;
          _nodeInfo = rhs._nodeInfo;
          _index = rhs._index;
          _functions = rhs._functions;
          _hidden = rhs._hidden;
          _weight = rhs._weight; 
//          _edges.clear();
          _edges = rhs._edges; 
          _numHiddenEdges = rhs._numHiddenEdges;
//          _status.clear();
          _status = rhs._status;
          
        }
      return(*this);
    }
  
  virtual ~MyNode()
    {}

// free all the memory used by the node.
  virtual void clear()
  {
    _nodeInfo.clear();
    _functions.clear();
    _edges.clear();
    _status.clear();
  }

  // functions related to node types.
  bool hasType(string type)
    {
      return(_nodeInfo.hasType(type));
    }
  
  void addType(string type)
    {
      _nodeInfo.addType(type);
    }
  void addTypes(set< string > types)
    {
      _nodeInfo.addTypes(types);
    }
  void getTypes(set< string > &types) const
    {
      _nodeInfo.getTypes(types);
    }
  set< string > getTypes() const
    {
      set< string > types;
      _nodeInfo.getTypes(types);
      return(types);
    }

  MyNodeId getId() const
    {
      return(_id);
    }

  void setStatus(string statusType)
    {
      _status[statusType] = true;
    }
  void clearStatus(string statusType)
    {
      _status[statusType] = false;
    }
  bool getStatus(string statusType) //const
    {
#ifdef DEBUG
      // check if statusType exists.
      if (_status.end() == _status.find(statusType))
        {
          cerr << "\tnode " << getId() << " has no status flag called "
               << statusType << endl;
          // set the statusType to false since that is the default.
          _status[statusType] = false;
        }
      
#endif      
      return(_status[statusType]);
    }
  
  bool addFunction(string fn)
    {
      // add a function only if i have not seen it before.
      if (_functions.end() == find(_functions.begin(), _functions.end(), fn))
        _functions.push_back(fn);
      return(true);
    }
  
  void functions(vector <string> &fns) const
    {
      fns = _functions;
    }

  // functions to get and set hidden status.
  bool isHidden() const
    {
      return(_hidden);
    }
  
  bool isVisible() const
    {
      return(!_hidden);
    }
  
  void hide()
    {
      _hidden = true;
    }

  void unhide()
    {
      _hidden = false;
    }

  MyNT getWeight() const
  {
    return(_weight);
  }
  void setWeight(MyNT wt)
  {
    _weight = wt;
  }

  virtual MyEdgeIterator incidentEdges()
  {
    MyEdgeIterator itr(_edges.begin(), _edges.end());
    return(itr);
  }

//   virtual MyConstEdgeIterator incidentEdges() const
//     {
//       MyConstEdgeIterator itr(_edges.begin(), _edges.end());
//       return(itr);
//     }

  unsigned int degree() const
    {
      return(_edges.size() - numHiddenEdges());
    }

  MyNT getWeightedDegree() const
    {
      return(_totalAbsoluteEdgeWeight);
//      return(_totalEdgeWeight);
    }

  // murali, sep 12, 2007.
  // Subtract oldWeight and add newWeight to the total edge weight of the node.
  //
  // TODO: It is ugly to make this function public. How do I make it private?
  void updateTotalEdgeWeight(MyNT oldWeight, MyNT newWeight)
    {
#ifdef DEBUG
      MyNT _old, _oldAbs;
      _old = _totalEdgeWeight;
      _oldAbs = _totalAbsoluteEdgeWeight;
#endif      
      _totalEdgeWeight += -oldWeight + newWeight;
      _totalAbsoluteEdgeWeight += -fabs(oldWeight) + fabs(newWeight);
#ifdef DEBUG
      if (_totalAbsoluteEdgeWeight < 0 - EDGE_WEIGHT_EPSILON)
        cerr << "MyEdge::updateTotalEdgeWeight(): total absolute edge weight = "
             << _totalAbsoluteEdgeWeight << " is < " << 0 - EDGE_WEIGHT_EPSILON
             << ", old weight = " << oldWeight
             << ", new weight = " << newWeight << "." << endl;
#endif      
    }

  unsigned int numHiddenEdges() const
    {
      return(_numHiddenEdges);
    }
  
  // is otherNode adjacent to *this? true only if otherNode is in
  // adjacency list and both nodes are visible. but i can't check if
  // the other node is visible so i am going to drop that check.
  //
  // TODO: BUGBUGBUG!
  bool isAdjacent(MyNodeId otherNode) const
    {
      return((_edges.end() != _edges.find(otherNode)) && isVisible());
    }
  
  bool isAdjacent(const MyNode &otherNode) const
    {
      return((_edges.end() != _edges.find(otherNode.getId())) && isVisible());
    }

//   bool getEdge(MyNodeId otherNode, MyEdge &edge);
//   bool getEdgePtr(MyNodeId otherNode, MyEdgePtr &ptr);

  MyEdge *getEdge(MyNodeId otherNode) const;
  bool getEdgePtr(MyNodeId otherNode, MyEdgePtr &ptr);
      
  
  // no default value for weight since i want only MyGraph::addEdge()
  // to contain a default value.
  bool addEdge(MyNodeId otherNode, MyEdgePtr edgePtr);
  MyEdgePtr deleteEdge(MyNodeId otherNode);


  // functions to get and set hidden status of an edge.

  // hide an edge. currently, this function only increments
  // _numHiddenEdges for *this if *this is not already hidden. a
  // complete implementation would store which edge is hidden.
  void hideEdge(MyNodeId other)
    {
      if (isVisible())
        _numHiddenEdges++;
    }
  // make an edge visible. if the node is visible, decrement
  // _numHiddenEdges.
  void unhideEdge(MyNodeId other)
    {
      if (isVisible())
        _numHiddenEdges--;
    }

  unsigned int computeCommonNeighbours(const MyNode &other, set< MyNodeId > &common);
  
private:
  int _get_index() const
    {
      return(_index);
    }
  void _set_index(int i)
    {
      _index = i;
    }

};


typedef MyGraphInfo MyEdgeInfo;

class MyEdge
{
private:
  // can't have these as references. if i do, inserting a MyEdge into
  // an STL vector causes problems.
  MyNode *node1;
  MyNode *node2;
  MyEdgeInfo _edgeInfo;
  map< string, bool > _status;
  
public:
  // i have a MyNode() constructor. is there a harm in a MyEdge() constructor?
  MyEdge()
      : node1(), node2()
    {}
  MyEdge(MyNode &n1, MyNode &n2)
      : node1(&n1), node2(&n2), _edgeInfo(), _status()
    {}

  MyEdge(const MyEdge &other)
      : node1(other.node1), node2(other.node2), _edgeInfo(other._edgeInfo),
        _status(other._status)
    {}
  const MyEdge& operator=(const MyEdge& rhs)
    {
      if (this != &rhs)
        {
          node1 = rhs.node1;
          node2 = rhs.node2;
          _edgeInfo.clear();
          _edgeInfo = rhs._edgeInfo;
          _status.clear();
          _status = rhs._status;
        }
      return(*this);
    }

  //
  // Defined operator '<' for MyEdge for map of edges. 
  //
  bool operator<(const MyEdge& rhs) const
    {
      MyNode *n1 = rhs.node1;
      MyNode *n2 = (*this).node1;
      MyNode *n3 = rhs.node2;
      MyNode *n4 = (*this).node2;
      return (((*n1).getId() > (*n2).getId())||(((*n1).getId()==(*n2).getId())&&((*n3).getId() > (*n4).getId())));
    } 
  // return true iff edge is incident on node.
  bool incident(string node) const
    {
      return((node1->getId() == node) || (node2->getId() == node));
    }
  
  // return true iff edge connects n1 and n2.
  bool incident(string n1, string n2)
    {
      return(incident(n1) && incident(n2));
    }

  // return the "head" (node1) of the edge.
  MyNode &head() const
    {
      return(*node1);
    }
  
  // return the "tail" (node2) of the edge.
  MyNode &tail() const
    {
      return(*node2);
    }
  
  // return the node incident on *this that is opposite to "node."
  MyNode *opposite(const MyNode &node) const
    {
      // BUG? when i copy a graph, i copy a node's _edgeList but the
      // node1 and node2 pointers in each MyEdge in the _edgeList
      // still point to the original graph. when i call opposite for
      // an edge in the copy, node points to a node in the copy but
      // node1 and node2 to a node in the original!
      
      if (node.getId() == node1->getId())
        return(node2);
      if (node.getId() == node2->getId())
        return(node1);
      cerr << "MyEdge::opposite(): passed node " << node.getId()
           << " but this edge connects nodes " << node1->getId()
           << " and " << node2->getId() << ". Exiting." << endl;
      exit(-1);
    }
  void setStatus(string statusType)
    {
      _status[statusType] = true;
    }
  void clearStatus(string statusType)
    {
      _status[statusType] = false;
    }
  bool getStatus(string statusType) //const
    {
      return(_status[statusType]);
    }

  void setWeight(MyNT w)
    {
      // murali, sep 12, 2007
      MyNT oldWeight = getWeight();
      _edgeInfo.setWeight(w);
      // update total edge weights of incident nodes.
      head().updateTotalEdgeWeight(oldWeight, w);
      tail().updateTotalEdgeWeight(oldWeight, w);
    }

  MyNT getWeight() const
    {
      return(_edgeInfo.getWeight());
    }

  // functions related to edge types.
  bool hasType(string type)
    {
      return(_edgeInfo.hasType(type));
    }
  
  void addType(string type)
    {
      _edgeInfo.addType(type);
    }
  void addTypes(const set< string > &types)
    {
      _edgeInfo.addTypes(types);
    }
  void getTypes(set< string > &types) const
    {
      _edgeInfo.getTypes(types);
    }
  set< string > getTypes() const
    {
      set< string > types;
      _edgeInfo.getTypes(types);
      return(types);
    }

  void getEdgeStrings(vector< string > &edgeStrings) const;

   string getEdgeString() const
    {
      string headId = head().getId();
      string tailId = tail().getId();
      return(getEdgeString(headId, tailId));
    }


  static string getEdgeString(string headId, string tailId) 
    {
      string temp;
      if (headId > tailId)
        {
          temp = headId;
          headId = tailId;
          tailId = temp;
        }
      return(headId + string("_____") + tailId);
    }
  
    
//   pair< string, string > getEdgeString() const
//     {
//       string head = head().getId();
//       string tail = tail().getId();
//       if (head > tail)
//         {
//           temp = head;
//           head = tail;
//           tail = temp;
//         }
//       return(pair<string, string>(head, tail));
//     }
  
};





// when nodes and edges are hidden, the function operates only on the
// visible nodes and edges.

class MyGraph
{

public:

  typedef map< MyNodeId, MyNode > MyNodeList;
  typedef MyNodeList::const_iterator MyConstNodePtr;
  typedef MyNodeList::iterator MyNodePtr;

  typedef list< MyEdge > MyEdgeList;
  typedef MyEdgeList::iterator MyEdgePtr;
  typedef MyEdgeList::const_iterator MyConstEdgePtr;


  // nested classes.
  class MyNodeIterator;
  // why am i declaring these classes here? i want the definition of
  // the nested class to be private but i want instances of these
  // templates (e.g., MyConstNodeIterator) to be public. i also want
  // all public typedefs to be in one place in the file.
  template< typename Object, typename ObjectPtr > class NodeObjectIterator;
  
  typedef  MyGraph::NodeObjectIterator< const MyNode, MyConstNodePtr > MyConstNodeIterator;

  template< typename Object, typename ObjectPtr > class EdgeObjectIterator;
  
  typedef  MyGraph::EdgeObjectIterator< MyEdge, MyEdgePtr > MyEdgeIterator;
  typedef  MyGraph::EdgeObjectIterator< const MyEdge, MyConstEdgePtr > MyConstEdgeIterator;


  
  typedef MyNode Node;
  typedef MyEdge Edge;
  typedef MyNodeIterator NodeIterator;
  typedef MyEdgeIterator EdgeIterator;
  typedef Node::EdgeIterator IncidentEdgeIterator;
  typedef Node::ConstEdgeIterator ConstIncidentEdgeIterator;
  

  

  
public:


  // next() will return a MyNode.
  class MyNodeIterator: public MyIterator<MyNode>
  {
  private:
    MyGraph::MyNodePtr start;
    MyGraph::MyNodePtr end;
    MyGraph::MyNodePtr current;
    
  public:
    MyNodeIterator()
      {}
    MyNodeIterator(MyGraph::MyNodePtr _start, MyGraph::MyNodePtr _end)
      {
        start = _start;
        current = _start;
        end = _end;
      }
    
    virtual bool hasNext()
      {
        return(current != end);
      }
    MyNode& next()
      {
        MyNode& _next = (*current).second;
        current++;
        return(_next);
      }
  };
  
  template< typename Object, typename ObjectPtr >
  class NodeObjectIterator: public MyIterator< Object >
  {
  private:
    ObjectPtr start, end, current;
    
  public:
    NodeObjectIterator()
      {}
    NodeObjectIterator(ObjectPtr _start, ObjectPtr _end)
      {
        start = _start;
        current = _start;
        end = _end;
      }
    
    virtual bool hasNext()
      {
        return(current != end);
      }
    Object& next()
      {
        Object& _next = (*current).second;
        current++;
        return(_next);
      }
  };

  template< typename Object, typename ObjectPtr >
  class EdgeObjectIterator: public MyIterator< Object >
  {
  private:
    ObjectPtr start, end, current;
    
  public:
    EdgeObjectIterator()
      {}
    EdgeObjectIterator(ObjectPtr _start, ObjectPtr _end)
      {
        start = _start;
        current = _start;
        end = _end;
  }
    
    virtual bool hasNext()
      {
        return(current != end);
      }
    Object& next()
      {
        Object& _next = *current;
        current++;
        return(_next);
      }
  };

private:
//  static int globalGraphId;

  string _name;
  
  // i store nodes by name. another possibility is to store a vector
  // of MyNodes and a map of strings to ints to iterators but
  // maintaining that second map is a nightmare.
  MyNodeList _nodes;
  MyNodePtr _internalNodePtr;
  
//  vector< MyNode > nodes;

  MyEdgeList _edgeList;

  // various graph quantities.
  int _numEdges;

  int _numHiddenNodes;
  int _numHiddenEdges;

  // the sum of the squares of the degrees of the nodes.
  unsigned int _totalSquaredNodeDegrees;
  // the sum of the squares of the weighted degrees of the nodes.
  MyNT _totalSquaredNodeWeightedDegrees;
  
  MyNT _totalEdgeWeight;
  MyNT _totalAbsoluteEdgeWeight;
  
  int _id;

  map< string, string > _edgeTypeGroups;

  // private methods
  void _computeDenseSubgraphs(ostream &logStream, vector< MyGraph >&denseSubgraphs,
                              bool computeDenseSubgraphsTillTheBitterEnd,
                              bool splitDenseSubgraphsIntoComponents,
                              bool suppressDetails);

  void _updateUponEdgeInsertion(MyNodeId node1, MyNodeId node2, MyNT edgeWeight);
  
  void _updateUponEdgeDeletion(MyNodeId node1, MyNodeId node2, MyNT edgeWeight,                                // when I invoke this method from
                                // MyGraph::deleteNode, node1's degree
                                // is not decremented by 1 before i
                                // invoke this method. therefore, i
                                // pass the decrement in this
                                // variable.
                               int correctionForGrossHack = 0);
  

public:

  MyGraph()
      : _name(), _nodes(), _internalNodePtr(), _edgeList(),
        _numEdges(0), _numHiddenNodes(0), _numHiddenEdges(0),
        _totalSquaredNodeDegrees(0), _totalSquaredNodeWeightedDegrees(0),
        _totalEdgeWeight(0), _totalAbsoluteEdgeWeight(0), _id(-1)
    {}
  // ignore edges with weight < minEdgeWeight.
  MyGraph(string infile, string type, MyNT minEdgeWeight = 0)
      : _name(), _nodes(), _internalNodePtr(), _edgeList(),
        _numEdges(0), _numHiddenNodes(0), _numHiddenEdges(0),
        _totalSquaredNodeDegrees(0), _totalSquaredNodeWeightedDegrees(0),
        _totalEdgeWeight(0), _totalAbsoluteEdgeWeight(0), _id(-1)
    {
      if ("" == infile)
        return;

      read(infile, "", minEdgeWeight, cout);
      _checkDegree();
    }
  
  MyGraph(const MyGraph &copy);

  void setName(string name)
    {
      _name = name;
    }
  string getName() const
    {
      return(_name);
    }

  virtual MyGraph::MyNodeIterator nodes()
  {
    MyNodeIterator itr(_nodes.begin(), _nodes.end());
    return(itr);
  }

  virtual MyGraph::MyConstNodeIterator nodes() const
  {
    MyConstNodeIterator itr(_nodes.begin(), _nodes.end());
    return(itr);
  }

  virtual MyGraph::MyEdgeIterator edges()
  {
    MyEdgeIterator itr(_edgeList.begin(), _edgeList.end());
    return(itr);
  }

  virtual MyGraph::MyConstEdgeIterator edges() const
  {
    MyConstEdgeIterator itr(_edgeList.begin(), _edgeList.end());
    return(itr);
  }

  virtual MyNode::MyEdgeIterator incidentEdges(MyNodeId nodeId)
  {
    MyNode &node = _getNode(nodeId);
    return(node.incidentEdges());
  }
  
  virtual MyNode::MyEdgeIterator incidentEdges(MyNode &node)
  {
    return(node.incidentEdges());
  }

  void computeBinaryVector(const map< string, unsigned int > &edgeToColumn,
                           vector< unsigned int > &binaryVector) const;

  void computeEdgeTypeCounts(map< string, unsigned int > &counts) const;
  
  unsigned int computeCommonNeighbours(MyNode &node1, MyNode &node2, set< MyNodeId > &common);

  MyNT computeSegregation(MyNodeIdList &nodes)
  {
          MyNT internalSum(0), externalSum(0);
          for (MyNodeIdList::iterator nitr = nodes.begin(); nitr != nodes.end(); nitr++)
          {
                  if (!isNode(*nitr))
                          continue;
                  MyNode::MyEdgeIterator eitr = incidentEdges(*nitr);
                  while (eitr.hasNext())
                  {
                          MyEdge &edge = *(eitr.next());
                          MyNodeId otherId = edge.opposite(*nitr)->getId();
                          if (nodes.end() != find(nodes.begin(), nodes.end(), otherId))
                                  internalSum += edge.getWeight();
                          else
                                  externalSum += edge.getWeight();
                  }
          }

#ifdef FALSE
          cout << "\t" << internalSum/2 << "\t" << externalSum << "\t" << internalSum/(internalSum + 2*externalSum);
#endif
          // 2*externalSum corrects for the double-counting of internal edges, which happens
          // because we are looping over the input nodes rather than the edges between them.
          return (internalSum/(internalSum + 2*externalSum));
  }

  void printEdgeTypeCounts(ostream &ostr) const;


  virtual void construct(const map< string, map< string, MyNT > > &allEdgeWeights);

  virtual void read(string fileName, string type="", MyNT minEdgeWeight=0, ostream &logStream=cout);

  
  virtual void read2(string fileName, string type="", MyNT minEdgeWeight=0, ostream &logstream=cout);

  virtual void readNodeTypes(string file);

  virtual void print(ostream &fstr=cout, string name="");

  virtual void printNodes(ostream &fstr=cout, string name="");

  virtual void printEdges(ostream &fstr=cout, string name="") const;

  // types is a vector of "experiment" types.
  virtual void printEdgesItemset(ostream &fstr, vector< string > types); //const;
  
  virtual void readEdgeWeights(string weightsFile);


  virtual void transformEdgeWeightsString(string transform);

  template < typename _Transform >
  void transformEdgeWeights(_Transform function);//unary_function< MyNT, MyNT> transform);

  // clear up space used.
  virtual void clear();
  
  virtual ~MyGraph()
    {
      // TODO: BUG/DESIGN. do i need this clear operation?
      clear();
    }


  // add other's nodes and edges to *this. making other a const
  // reference causes a strange compilation error.
  virtual void add(MyGraph &other);

  virtual void addInduced(MyGraph &other);

  void copyEdgeWeights(MyGraph &other);
  

  // add other's nodes and edges to *this. making other a const
  // reference causes a strange compilation error.
  virtual void subtract(MyGraph &other);


  int getId() const
    {
      return(_id);
    }

  MyGraph &operator=(const MyGraph &rhs);

  bool operator<(const MyGraph &rhs) const;

  //ahsanur: commenting out...
  // *this < other if #nodes is less or both have equal #nodes and
  // *this has fewer edges.
/*  bool operator<(const MyGraph& other) const
    {
      return((numNodes() < other.numNodes()) ||
             ((numNodes() == other.numNodes()) &&
              (numEdges() < other.numEdges())));
    }

  bool operator>(const MyGraph& other) const
    {
      return(other < *this);
    }
*/

  void getEdgeSet(set< string > &edgeSet) const
    {
      MyConstEdgeIterator eitr = edges();
      while (eitr.hasNext())
        {
          edgeSet.insert(eitr.next().getEdgeString());
        }      
    }

  void getNodeSet(set< MyNodeId > &nodeSet) const
    {
      MyConstNodeIterator nitr = nodes();
      while (nitr.hasNext())
        nodeSet.insert(nitr.next().getId());
    }
  
  void getNodeVec(vector< MyNodeId > &nodeVec) const
      {
        MyConstNodeIterator nitr = nodes();
        while (nitr.hasNext())
          nodeVec.push_back(nitr.next().getId());
      }

  unsigned int numNodes() const
    {
      return(_nodes.size() - numHiddenNodes());
    }

  unsigned int numHiddenNodes() const
    {
      return(_numHiddenNodes);
    }
  
  unsigned int numEdges() const
    {
      return(_numEdges - numHiddenEdges());
    }

  unsigned int numHiddenEdges() const
    {
      return(_numHiddenEdges);
    }

  bool isConnected();
  
  MyNT computeDensity() const;

  MyNT computeWeightedDensity();

  MyNT computeStouffersZScore() const;

  MyNT computeStouffersZScoreSlowly() const;
  
  MyNT getAverageNodeWeight();
  
  MyNT getTotalNodeWeight() const;

  MyNT getTotalSquaredNodeDegrees() const;
  
  MyNT getTotalAbsoluteNodeWeight() const;

  MyNT getTotalEdgeWeight() const ;

  MyNT getTotalAbsoluteEdgeWeight() const;
  
  

  

  MyNT computeCompleteness() const
    {
      if (numEdges() == 0)
        return 0;
      return(numEdges()*2.0/(numNodes()*(numNodes() - 1)));
    }

  MyNT computeExpansionNodeBased(MyGraph &superGraph);
  
  
  int degree(MyNodeId nid) const
    {
      MyConstNodePtr itr = _nodes.find(nid);
      if (_nodes.end() == itr)
        {
          cerr << "MyGraph::degree(): node " << nid << " is not in the graph." << endl;
          return(-1);
        }
      return((*itr).second.degree());
    }

  MyNT weightedDegree(MyNodeId nid) const
    {
      MyConstNodePtr itr = _nodes.find(nid);
      if (_nodes.end() == itr)
        {
          cerr << "MyGraph::weightedDegree(): node " << nid << " is not in the graph." << endl;
          return(-1);
        }
      return((*itr).second.getWeightedDegree());
    }

  void degrees(map< unsigned int, unsigned int > &distribution) const;

  // compute the power of a graph, i.e., connect each node to every
  // node that is <= distance edges away.
  void power(unsigned int distance);


  bool isNode(const MyNode &node) const
    {
      return(isNode(node.getId()));
    }

  bool isNode(MyNodeId id) const
    {
      return(_nodes.end() != _nodes.find(id));
    }

  bool isVisibleNode(MyNodeId id) const
    {
      MyConstNodePtr np = _nodes.find(id);
      return((_nodes.end() != np) && (!_getNode(np).isHidden()));
    }
  
  bool isHiddenNode(MyNodeId id) const
    {
      MyConstNodePtr np = _nodes.find(id);
      return((_nodes.end() != np) && (_getNode(np).isHidden()));
    }

  void addNodes(set<MyNodeId> ids)
  {
          for(set<MyNodeId>::iterator it = ids.begin(); it != ids.end(); it ++)
                  addNode(*it);
  }

  // add an empty node.
  MyNode *addNode(MyNodeId id)
    {
 //     _nodes[id] = MyNode(id, g);
      //
      // see p 108, item 24 of effective STL. the insert call is more
      // efficient plus in this case it doesn't force me to create the
      // default constructor for _nodes[id], which i disallow because
      // of the initialisation issue with MyNode::_graph.
      //
      // remember to pass this to the node so that the node knows
      // which graph it belongs to.
      MyNodeList::iterator itr
        = _nodes.insert(MyNodeList::value_type(id, MyNode(id))).first;
      // itr is a pair<MyNodeId, MyNode>
      return(&(*itr).second);
//      return(true);
    }

  // add an empty node.
  MyNode *addNode(const MyNode &node)
    {
      MyNode *addedNode = addNode(node.getId());
      // add other aspects of node to addedNode.
      addedNode->copy(node);
      return(addedNode);
    }

  // return the functions of _nodes[id] in fns.
  void nodeFunctions(MyNodeId id, vector< string > &fns) const
    {
      if (!isNode(id))
        {
          cerr << "MyGraph::nodeFunctions(): Node with id = " << id
               << " is not in the graph." << endl;
          return;
        }
      _getNode(id).functions(fns);
    }
  
  // add function to a node.
  bool addNodeFunction(MyNodeId id, string function)
    {
      if (_nodes.end() == _nodes.find(id))
        cerr << "Adding function " << function << " to a non-existing node " << id << endl;
      _nodes[id].addFunction(function);
      return(true);
    }

  bool deleteNode(MyNodeId id, set< MyNodeId > *neighbours = NULL);

  void deleteNodeSet(const set< MyNodeId > ids);
  
  MyEdge *getEdge(MyNodeId node1, MyNodeId node2) const
    {
      return(_getNode(node1).getEdge(node2));
    }
  
  bool getEdge(MyNodeId node1, MyNodeId node2, MyEdgePtr &ptr) 
    {
      return(_getNode(node1).getEdgePtr(node2, ptr));
    }

  bool isValidEdge(const MyEdgePtr &eptr) const
    {
      return(_edgeList.end() != eptr);
    }
  
  /*bool isEdge(const MyEdge &edge) const
    {
      MyNodeId headId = edge.head().getId();
      MyNodeId tailId = edge.tail().getId();
      return(isEdge(headId, tailId));
    }*/
  

  /* \brief Check if an edge connecting node1 and node2 is in the
     invocant.
     
   * \note This function checks for adjacency between two nodes if
     they both exist in this graph.

   */
  bool isEdge(MyNodeId node1, MyNodeId node2) const
    {
        map< MyNodeId, MyNode >::const_iterator nitr1 = _nodes.find(node1), nitr2 = _nodes.find(node2);
        if ((nitr1 != _nodes.end())&&(nitr2 != _nodes.end()))
        return(nitr1->second.isAdjacent(node2) && nitr2->second.isAdjacent(node1));
      return(0);
      //return(_getNode(node1).isAdjacent(node2) && _getNode(node2).isAdjacent(node1));
    }

  // this function is faster than the one with ids as parameters since
  // i don't need to access the _nodes map.

  bool isEdge(const MyNode &node1, const MyNode &node2) const
    {
      return(node1.isAdjacent(node2) && node2.isAdjacent(node1));
    }
  
  MyEdgePtr addEdge(const MyEdge &edge);

  MyEdgePtr addEdge(MyNodeId nodeId1, MyNodeId nodeId2, MyNT weight = 1,
                    set< string > *types = NULL, bool keepGraphSimple = true);

  bool deleteEdge(MyNodeId node1, MyNodeId node2);

  bool isEdgeValid(MyEdgePtr eptr)
    {
      return(_edgeList.end() != eptr);
    }
  
  /* Set the weight of the edge connecting node1 and node2.

     \param[in] node1 identifier of the first node.

     \param[in] node2 identifier of the second node.

     \param[in] weight the weight of the edge.
     
     This method performs no action if the edge connecting the nodes
     does not exist.
   */
  void setEdgeWeight(MyNodeId node1, MyNodeId node2, MyNT weight);
  
  /* Set the weight of the edge.

     \param[in] edge the edge whose weight to set.

     \param[in] weight the weight of the edge.
     
     This method performs no action if the edge connecting the nodes
     does not exist.
   */
  void setEdgeWeight(MyEdge *edge, MyNT weight);

  // murali, sep 12, 2007. check if the total edge weight of each node
  // is correct. this method is useful to invoke after changing edge
  // weights. this method should really be protected but how else will
  // i invoke it from GAIN algorithms?
  bool _checkNodeTotalEdgeWeight();

  void computeEdgeTypeOverlaps() const;
  
  void computeEdgeTypeSubgraphs(ostream &logStream,
                                map< string, MyGraph>&edgeTypeSubgraphs, bool useShared = 1);

  //  from largest to smallest in terms of the number of nodes.
  //
  //  \param[in] comps The resulting components will be placed here
  void components(vector< MyGraph > *comps = NULL); //const;


  MyNT computeClosestNode(const MyNode &rootNode, MyNodeIdSet &nodeSet,
                          MyNodeId &closest);


  void computeHistogramNodeWeights(MyHistogram &hist, bool cumulative = false,
                                   bool reverse = false);
  
  void computeHistogramEdgeWeights(MyHistogram &hist, bool cumulative = false,
                                   bool reverse = false);
  
  
  void computeMinimumSpanningTreePrim(MyGraph &mst);

  void computeMaximumSpanningTreePrim(MyGraph &mst);

  // generic version of Prim's to compute either minimum or maximum
  // spanning tree based on the compare method.
  template< typename Compare > // StrictWeakOrdering
  void computeMSTPrim(MyGraph &mst);//, Compare compare);
  
  // computeNumCommonEdges() and computeNumCommonNodes() are helpers
  // for computeSimilarityEdges() and computeSimilarityNodes(),
  // respectively, since they easily allow asymmetric similarity to be
  // computed.
  
  unsigned int computeNumCommonEdges(const MyGraph &other) const;

  MyNT computeNumCommonEdgesWeighted(const MyGraph &other) const;
  
  unsigned int computeNumCommonNodes(const MyGraph &other) const;
  
  MyNT computeNumCommonNodesWeighted(const MyGraph &other) const;
  

  //  different versions of compute shortest path DAG. NOTE: these
  //  methods and printAllPairsShortestPathDistances() cannot be const
  //  since the underlying Dijkstra's algorithm modifies the graph,
  //  specifically node's visitation status.
  
  void computeShortestPathDAG(const MyNode &node, map<MyNodeId,MyNT> &distance,
                              map<MyNodeId, unsigned int> &count);

  void computeShortestPathDAG(const MyNodeId nodeid, map<MyNodeId,MyNT> &distance,
                              map<MyNodeId, unsigned int> &count);

  void computeShortestPathDAG(const MyNode &node, map<MyNodeId,MyNT> &distance,
                              map<MyNodeId, unsigned int> &count,
                              stack<MyNodeId> &descendents,
                              map< MyNodeId,vector<MyNodeId> > &predecessors);

  void computeShortestPathDAG(const MyNode &node, map<MyNodeId,MyNT> &distance,
                              map<MyNodeId, unsigned int> &count,
                              stack<MyNodeId> &descendents,
                              map< MyNodeId,vector<MyNodeId> > &predecessors,
                              map< MyNodeId,vector<MyNodeId> > &successors);

  void printAllPairsShortestPathDistances(ostream &ostr);
  
  void printAllPairsShortestPathDistances(string outfile);

  MyNT computeSimilarityEdges(const MyGraph &other, bool jacquard = true, bool asymmetric = false) const;

  MyNT computeSimilarityEdgesWeighted(const MyGraph &other, bool jacquard = true, bool asymmetric = false) const;
  
  MyNT computeMostSimilarGraphEdges(const vector< MyGraph >& others, unsigned int &bestIndex) const;
  
  MyNT computeSimilarityNodes(const MyGraph &other, bool jacquard = true, bool asymmetric = false) const;

  MyNT computeSimilarityNodesWeighted(const MyGraph &other, bool jacquard = true, bool asymmetric = false) const;
  
  MyNT computeMostSimilarGraphNodes(const vector< MyGraph >& others, unsigned int &bestIndex) const;
  
//   //Compute betweeness of each node(old algorithm, O(n^2)
//   //invocations of Dijkstra's algorithm).
//   void computeBetweeness(ostream &fstr);

  //Compute betweeness of each node (fast algorithm by Brandes).
  void computeNodeBetweenessCentrality(ostream *fstr, map< MyNodeId, MyNT> *bets);
  //Compute betweeness of each edge (fast algorithm by Newman).
  void computeEdgeBetweenessCentrality(ostream *fstr, map< MyEdge, MyNT> *bets);
 
  // functions to create random graphs.
  
  void computeEdgeFSWeights();

  void computeEdgeCDWeights();

  // create a random graph with the same degree distribution. 
  void randomise(MyGraph &random, map<MyNodeId,bool> *vertexcover = NULL);

  void randomiseVectorOfEdges(MyGraph& random, unsigned int numIterations);


  void randomiseErdosRenyiSubgraph(MyGraph& random, const vector<MyNodeId> &subgraphNodes, MyNT prob = 0.5);


  void randomiseErdosRenyiSubgraph(MyGraph& random, const set<MyNodeId> &subgraphNodes, MyNT prob = 0.5);
/*
  void randomiseErdosRenyiSubgraph(MyGraph& random, const set<MyNodeId> &subgraphNodes, MyNT prob,
                  MultiRandSeqGenerator &multiRandSeq, NaturalNumber randIndex);
*/
  void randomiseErdosRenyiSubgraph(const set<MyNodeId> &subgraphNodes, MyNT prob);

  static void createErdosRenyiNPGraph(MyGraph& graph, unsigned long numNodes, MyNT prob = 0.5);


  unsigned int deleteDisconnectedNodes();

  void createSubgraph(const vector< MyNodeId >& deletedNodes,
                       MyGraph& subgraph) const;

  void deleteSubgraphNodes(MyGraph& subgraph);

  void deleteSubgraphEdges(MyGraph& subgraph);
  
  // hide all the nodes in subgraph and the edges incident on these nodes. 
//  void hideSubgraphNodes(MyGraph& subgraph);
  // hide only the edges induced by the nodes in subgraph.
//  void hideSubgraphEdges(MyGraph& subgraph);

  void computeInducedSubgraph(const set< MyNodeId > &subgraphNodes,
                              MyGraph &subgraph) const;

  bool isInduced(const MyGraph &subgraph);
  

  // dense subgraph functions.
  //
  // find 1 core of given degree.
  void core(unsigned int k, MyGraph &subgraph, bool hide, ostream *fstr = NULL) const;
  // find all cores.
  void find_cores(vector< MyGraph > &cores) const;

  
#ifdef HAVE_GLPK
  // exact algorithm using Charikar's LP formulation.
  void computeDensestSubgraph(MyGraph &subgraph) const;
#endif // HAVE_GLPK

  // factor of 2 approximation using greedy algorithm.
  void computeDensestSubgraphApprox(MyGraph &subgraph, bool optimiseStouffersZscore = false,
                                    ostream *fstr = NULL) const;


  void computeDenseSubgraphs(ostream &logStream, vector< MyGraph >&denseSubgraphs,
                             bool computeDenseSubgraphsTillTheBitterEnd = false,
                             bool splitDenseSubgraphsIntoComponents = false,
                             bool suppressDetails = false);

  void computeMostPerturbedSubgraph(MyGraph &subgraph,
                                    unsigned int numIterationsFactor,
                                    ostream &logStream,
                                    bool runOnCopy = true);

  // find all cliques in the graph.
  void findCliques(vector< MyGraph > &cliques, ostream &ostr) const;


  virtual void sparsify(string method);

  // return the node with id = id. ALWAYS CALL IT WHEN YOU ARE SURE
  // THE NODE EXISTS.
  const MyNode& _getNode(MyNodeId id) const
    {
#ifdef DEBUG
      if ("" == id)
        cerr << "MyGraph::_getNode(): node id is a null string." << endl;
      if (_nodes.end() == _nodes.find(id))
        cerr << "MyGraph::_getNode(): node with id \"" << id
             << "\" is not the in graph!" << endl;
#endif      
      return((*_nodes.find(id)).second);
    }
  // i need this non-const version for hiding the node, for instance.
  MyNode& _getNode(MyNodeId id) 
    {
#ifdef DEBUG
      if ("" == id)
        cerr << "MyGraph::_getNode(): node id is a null string." << endl;
#endif      
      return((*_nodes.find(id)).second);
    }

//    MyEdgePtr _getEdge(MyNodeId id1, MyNodeId id2)
//    {
//      MyNode::MyEdgeIterator inEdges = incidentEdges(_getNode(id1));
//      while (inEdges.hasNext()) 
//        {
//                      // try all the edges incident on *node.
//                      Edge &e = inEdges.next();
//                      Node *w = e.opposite(_getNode(id1));
//                      if((*w).getId() == id2)
//                      {
//                              return e;
//                      }
//              }
//    }

        // compute the subgraph induced by each edge type
  //void computeEdgeTypeSubgraphs(ostream &logStream, map< string, MyGraph >&edgeTypeSubgraphs);
  // generate a weight for every edge from its corresponding type weights
  void assignEdgeWeightsFromEdgeTypeWeights(const map< string, MyNT > &edgeTypeWeights);
  
  MyGraph computeIntersection(const vector< MyGraph > &others);

  // read edge type group mappings from a file
        void readEdgeTypeGroups(string fileName);
        // group types according to edgeTypeGroups and put them in workingTypes
        void translateTypes(const set< string > &types, set< string > &workingTypes, bool useShared = 1);


  void computeSeparator(const set< MyNodeId > &nodes, set< MyNodeId > &separator);
  
  MyNT computeSeparatorRatio(MyGraph subgraph);

  // functions used in MyGraph::_computeDensestSubgraphApprox() and MyGraph::core(). also in treedex, so made public now (Apr 4, 2007)
  void _createDegreeLists(unsigned int &minDegree,
                          vector< list< MyNodeId > > &degreeLists,
                          map< MyNodeId, list< MyNodeId >::iterator > &nodePositions) const;
  void _decrementDegrees(vector< list< MyNodeId > > &degreeLists,
                         map< MyNodeId, list< MyNodeId >::iterator > &nodePositions,
                         const set< MyNodeId > &neighbours) const;

  
protected:
  // protected functions so that subclasses can access them.

  void _copyNodes(const MyGraph &copy);

  // const argument gives weird compilation error with MyConstEdgeIterator
  void _copyEdges(const MyGraph &copy);

  
  // check that the graph is "valid."
  // const gives weird compilation error with MyConstEdgeIterator.
  bool _check() const;
// check if a node exists.
//bool _checkNode(

  
  // check the average degree of the graph.
  bool _checkDegree() const;

  


  
  // aaaghhhh! i have to write one version for both the const and
  // non-const versions of MyNodePtr. it seems to make sense for the
  // non-const versions *not* to return a const class.
  MyNodeId _getNodeId(MyNodePtr &nptr) 
    {
      return((*nptr).first);
    }
  MyNodeId _getNodeId(MyConstNodePtr &nptr) const
    {
      return((*nptr).first);
    }
  MyNode& _getNode(MyNodePtr &nptr) 
    {
      return((*nptr).second);
    }
  const MyNode& _getNode(MyConstNodePtr &nptr) const
    {
      return((*nptr).second);
    }
  

  // function to do the real work of finding a k-core by deleting all
  // the nodes with degree > k.
  void _core(unsigned int k, bool hide, ostream *fstr);
  void _find_cores(vector< MyGraph > &cores);

  bool _tryAddingNode(MyNodeId nid,
                      const set< MyNodeId >& currentClique);
  
  void _findCliques(vector< MyGraph > &cliques, ostream &ostr);
  
  // this function does all the real work by working on a copy of the
  // original graph. i have to give it a different name (starting with
  // an underscore here) otherwise i can call
  // MyGraph::computeDensestSubgraphApprox() only on a const MyGraph.
  void _computeDensestSubgraphApprox(MyGraph &subgraph, bool hide = false,
                                     ostream *fstr = NULL);
void _computeDensestWeightedSubgraphApprox(MyGraph &subgraph,
                                           bool optimiseStouffersZscore = false,
                                           bool hide = false,
                                           ostream *fstr = NULL);


  
#ifdef HAVE_GLPK
void _computeDensestSubgraph(MyGraph &subgraph, bool hide);

  void _get_subgraph_from_lp(MyGraph &subgraph, LPX *lp);
#endif // HAVE_GLPK

};

typedef MyEdge*  MyEdgePQNode;



template< typename Compare >
void MyGraph::computeMSTPrim(MyGraph &mst)//, Compare comp)
{
  typedef priority_queue< MyEdgePQNode, vector< MyEdgePQNode >, Compare > MyEdgePQ;
  MyEdgePQ epq;//(comp);
  set< string > edgeTypes;

//   // find the components. run the algorithm for each component.
//   vector< MyGraph > comps;
//   vector< MyGraph >::iterator compItr;
//   components(&comps);
//   for (compItr = comps.begin(); compItr != comps.end(); compItr++)
//     {
      
//  MyNodeIterator nitr = compItr->nodes(); 
  MyNodeIterator nitr = nodes(); 
  MyNode::MyEdgeIterator eitr;
  // loop over all the nodes so that i process all components.
  while (nitr.hasNext())
    {
      // making this variable a reference has ghastly consequences in
      // the when i assign the head or tail of a popped edge to
      // nodeNotInMST at the end of the main PQ loop below: *head* and
      // *tail* become the same!
      MyNode *nodeNotInMST = &nitr.next();
      string id = nodeNotInMST->getId();
      if (!mst.isNode(id))
        mst.addNode(id);
      else
        // node is already in the MST, which means i have processed
        // its connected component.
        continue;
      // start constructing the MST for a brand-new component.
      while (true)
        {
          // reset id at the beginning of the loop.
          id = nodeNotInMST->getId();
          // add the edges incident on nodeNotInMST to the PQ.
          eitr = nodeNotInMST->incidentEdges();
          while (eitr.hasNext())
            {
              MyEdge &edge = *(eitr.next());
              // get neighbour.
              MyNode &neighbour = *(edge.opposite(id));
#ifdef DEBUG
              cout << "MyGraph::computeMSTPrim(): processing edge between nodes "
                   << edge.head().getId() << " and " << edge.tail().getId() << endl;
#endif 
              // ignore edge connecting nodes in the MST.
              if (mst.isNode(neighbour.getId()))
                continue;
              // add edge to PQ.
              epq.push(&edge);
#ifdef DEBUG
              cout << "MyGraph::computeMSTPrim(): adding to the PQ edge between nodes "
                   << edge.head().getId() << " and " << edge.tail().getId() << endl;
#endif 
            }
          if (epq.empty())
            break;
          // get the edge with smallest weight in the PQ.
          MyEdge *edge = epq.top();
          epq.pop();
          
          // ignore the edge if both endpoints are in tree.
          MyNode &head = edge->head();
          MyNode &tail = edge->tail();
#ifdef DEBUG
          cout << "MyGraph::computeMSTPrim(): popped edge between nodes "
               << head.getId() << " and " << tail.getId()
               << " with weight " << edge->getWeight() << endl;
#endif 
          if ((mst.isNode(head.getId())) && (mst.isNode(tail.getId())))
            continue;
#ifdef DEBUG
          // at least one endpoint must be in the tree.
          if (!(mst.isNode(head.getId())) && !(mst.isNode(tail.getId())))
            cerr << "MyGraph::computeMSTPrim(): trying to add an edge to the MST "
                 << "but neither of its endpoints " << head.getId()
                 << " and " << tail.getId()
                 << " are in the MST!" << endl;
#endif
          // find the node not in the tree. that is the new nodeNotInMST. 
          // add the node and the edge just found.
          if (mst.isNode(head.getId()))
            nodeNotInMST = &tail;
          else
            nodeNotInMST = &head;
          mst.addNode(nodeNotInMST->getId());
          // add the edge.
          MyEdgePtr newEdge = mst.addEdge(head.getId(), tail.getId(), edge->getWeight());
          // add the edge types too.
          edgeTypes.clear();
          edge->getTypes(edgeTypes);
          newEdge->addTypes(edgeTypes);
          
          // epq modified at the beginning of the loop.
        }
    } // end of loop over all nodes (in a component)
//    } // end of loop over all components.
  
}


template < typename _Transform >
void MyGraph::transformEdgeWeights(_Transform transformFunction)
{
  MyEdgeIterator itr = edges();
  MyNT weight;
  while (itr.hasNext())
    {
      MyEdge &edge = itr.next();
      weight = edge.getWeight();
      edge.setWeight(transformFunction(weight));
    }
}


#endif // _GRAPH_H