btl_graph.h

利用这个模板可以分析基因表达数据

//
// btl_graph.h
//
// This file contains the initiation of the static member of BTL_VertexBase.
// This code is part of the Bioinformatics Template Library (BTL).
//
// Copyright (C) 1997, 1998 Birkbeck College, Malet Street, London WC1E 7HX,
// U.K. ([e-mail])
//
// This library is free software; you can redistribute it and/or modify 
// it under the terms of the GNU Library General Public License as published 
// by the Free Software Foundation; either version 2 of the License, or 
// (at your option) any later version.  This library 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 Library General Public License for more details.
// You should have received a copy of the GNU Library General Public
// License along with this library; if not, write to the Free Software
// Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
///////////////////////////////////////////////////////////////////////////


#if !defined(BTL_GRAPH_H)
#define BTL_GRAPH_H


#include "BTL.h"
#include "VoidPtrStore.h"
#include "Dereferencer.h"

using namespace std;

_BTL_BEGIN_NAMESPACE

//VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
//||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
//AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

// Compare 'object' used for sorting vertices and edges by their id.
// Should be a member function but template member
// functions are not supported by many compilers..

                /**#: [Hidden] */

template <class T>
struct BTL_ById : binary_function<T, T, bool> {
    bool operator()(T x, T y) const { return x->GetId() < y->GetId(); }
};


//VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
//||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
//AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

//     [Description ="This abstract base class is used to generate an individual integer
//       identifier for BTL_Vertex objects."]
//      [Summary = "base class for BTL_Vertex. Provides access to each object's
//       id."]
//      [Authors = "W.R.Pitt"]
//      [Files = "<A HREF=./btl/btl_graph.h>btl_graph.h</A>"]
//      [Friends="operator&lt&lt and operator=="]
//      [Dependencies="None."]

	    	/**#: [Hidden] */

class BTL_VertexBase
{
private:

    static unsigned int nextId;     // The id number for the next vertex
    unsigned int    	id; 	    // The id number for this vertex

	    	/**#: [Hidden] */
    virtual void
    Print(ostream& os) const = 0;

public:

	    	/**#: [Description="Construct vertex with a new id."] */

    BTL_VertexBase() { id = nextId++; }

	    	/**#: [Description="Copy constructor"] */

    BTL_VertexBase(const BTL_VertexBase& v) { id = v.id; }

	    	/**#: [Description="Read the id of this vertex."] */

    unsigned int
    GetId() const { return id; }

	    	/**#: [Description="Equality operator."] */

    friend bool
    operator==(const BTL_VertexBase& v1, const BTL_VertexBase& v2) 
    { return v1.GetId() == v2.GetId(); }

	    	/**#: [Description="Output operator."] */

    friend ostream& operator<<(ostream& os, const BTL_VertexBase& v)
    	{ v.Print(os); return os; }

};


//VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
//||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
//AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

/**#: [Description ="
    This class encapsulates a graph vertex and is designed for use with the
    graph class. Each vertex contains a reference to a data object and
    pointers to other vertices. It is a template class the single template
    parameter is a type of dereferencer."]
    [Summary = "a template graph vertex for use with graph"] 
    [Authors = "W.R.Pitt"]
    [Files = "<A HREF=./btl/btl_graph.h>btl_graph.h</A>"]
    [Dependencies="<A HREF=#BTL_II>BTL_II</A>, and 
                   <A HREF=#BTL_II>BTL_IteratorDerefencer</A>, or 
		   <A HREF=#BTL_II>BTL_InDencer</A>"]

*/

template <class T> class BTL_Graph;

template <class Dereferencer> 
class BTL_Vertex : public BTL_VertexBase
{
public:

#if !defined(SGI_CC)
    typedef BTL_TYPENAME Dereferencer::container_type   container_type;
    typedef BTL_TYPENAME Dereferencer::value_type 	    value_type;
    typedef BTL_TYPENAME Dereferencer::reference_type   reference_type;
    typedef BTL_TYPENAME Dereferencer::iterator  	    iterator;
    typedef BTL_TYPENAME Dereferencer::const_iterator   const_iterator; 
#else
    typedef Dereferencer::container_type   	    container_type;
    typedef Dereferencer::value_type	   	    value_type;
    typedef Dereferencer::reference_type   	    reference_type;
    typedef Dereferencer::iterator	   	    iterator;
    typedef Dereferencer::const_iterator    	    const_iterator;
#endif
    typedef BTL_Vertex<Dereferencer>   	    	    Vertex;
    typedef Vertex* 	    	    	    	    VertexPtr;
    typedef BTL_PtrSet<Vertex>	    	    	    VertexPtrStore;
    typedef BTL_II<Vertex>     	    	    	    VertexIterator;
    typedef BTL_CII<Vertex>  	    	    	    ConstVertexIterator;

    friend class BTL_Graph<Dereferencer>;
    
private:

    Dereferencer    	*deref;     // Pointer to deferencer object stored in
    	    	    	    	    // graph object that this vertex is a part
    reference_type   	ref;	    // Reference to a data item - the contents
    	    	    	    	    // of this vertex
    VertexPtrStore    	links;	    // container of pointers to vertices which
    	    	    	    	    // are linked to this vertex via edges of
				    // a graph
    bool    	    	visited;    // visited flag used by depth first search
    	    	    	    	    // algorithms and the like
        
protected:
		// function	    	
	    	// Add pointer/link to another vertex. Return false if link
	    	// already there or if it points to this  vertex. Takes O(logN)

	    	/**#: [Hidden] */
    bool
    AddLink(VertexPtr p) 
    {
	if (p == this) return false; 	// Avoids self links.
	return links.insert(links.end(), p) != links.end(); 
    }
    	    	// Remove all links to this vertex present in other vertices
		// N.B. This should be used for undirected graphs only.
		
	    	/**#: [Hidden] */
    void
    RemoveLinks()
    {
    	for (VertexIterator i = begin_vertex(); i!= end_vertex(); i++)
    	    (*i).RemoveLink(this);
    }
	    	// Remove pointer/link to other vertex. Return false if link 
	    	// not found. Takes O(logN). 
	    
	    	/**#: [Hidden] */
    bool
    RemoveLink(VertexPtr p) 
    {
	VertexPtrStore::iterator search = links.find(p);
	if (search == links.end()) return false;
	links.erase(search);
	return true;
    }
    	    	// Update reference to vertex data item. This is only necessary
		// for vertices using an InDencer
    
	    	/**#: [Hidden] */
    void
    UpdateReference(VertexPtr p) 
    {
	deref->Update(ref,p->ref);
    }
    
    	    	// Return the reference to the data item associated with this
		// vertex. The type of reference could be an iterator or an
		// index number.
		    
	    	/**#: [Hidden] */
    reference_type
    GetRef()
    {
    	return ref;
    }
    	    	// Print vertex contents and links
    	    	//
		
	    	/**#: [Hidden] */
    virtual void
    Print(ostream& os) const
    {
    	os << "\nVertex " << GetId()
    	   << "\nContents: " << *GetIterator()
    	   << "\nConnected to vertices: ";

    	typedef set<unsigned int, less<unsigned int> > Ids;
    	Ids ids;
    	for (ConstVertexIterator i=begin_vertex(); i!= end_vertex(); i++)
    	    ids.insert(ids.end(),(*i).GetId());
	    
    	for (Ids::iterator i=ids.begin(); i!=ids.end(); i++)
    	    os << *i << " ";
    	os << '\n';
    }

	    	// Construct Vertex belonging particular graph and associated
		// with a particular data item stored within this graph

	    	/**#: [Hidden] */
	    	
    BTL_Vertex(Dereferencer& d, reference_type r) : BTL_VertexBase() 
    { 
    	visited = false;
    	deref = &d; 
	ref = r; 
    }
    

public:

	    	/**#: [Description="Construct new empty Vertex"] */

    BTL_Vertex() : BTL_VertexBase() { visited = false; }


	    	/**#: [Description="Copy constructor."] */

    BTL_Vertex(const BTL_Vertex& v) : BTL_VertexBase(v) 
    {  
    	deref = v.deref;
    	ref = v.ref;
    	links = v.links;
    	visited = v.visited;
    }
    	    	    	       
    // N.B. The Graph deletes the data item referenced by this vertex. 

	    	/**#: [Description="Destructor"] */
    virtual
    ~BTL_Vertex() {}
    
    
	    	/**#: [Description="Get an iterator that references the data
		item associated with this vertex. With graphs that use STL
		an vector or deque to store data items this iterator may become
		invalid after insertions or deletions of vertices. (There is also a
      const version of this function.)"] */
    iterator
    GetIterator() { return deref->GetIterator(ref); }

    const_iterator
    GetIterator() const { return deref->GetIterator(ref); }

	    	/**#: [Description="Read/write access to visited flag. This
	    	       can be used in Graph searching routines."] */
    bool&
    Visited() { return visited; }

	    	/**#: [Description="Return iterator that references first
	    	       vertex connected to this vertex.(There is a
                       const version of this function as well)"] */
    virtual VertexIterator
    begin_vertex() { return links.begin(); }

    virtual ConstVertexIterator
    begin_vertex() const { return links.begin(); }

	    	/**#: [Description="Return iterator that references the
	    	       position in memory after the last vertex connected to
		       this vertex.(There is a const version of this function
		       as well)"] */
    virtual VertexIterator
    end_vertex() { return links.end(); }

    virtual ConstVertexIterator
    end_vertex() const { return links.end(); }

	    	/**#: [Description="Return iterator that references first
	    	       vertex connected to this vertex. (There is a
                       const version of this function as well)"] */
    VertexIterator
    begin() { return links.begin(); }

    ConstVertexIterator
    begin() const { return links.begin(); }

	    	/**#: [Description="Return iterator that references the
	    	       position in memory after the last vertex connected to
		       this vertex.(There is a const version of this function
		       as well)"] */
    VertexIterator
    end() { return links.end(); }