btl_graph.h

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

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

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


/**#: [Description ="
    Graph container with any type of data at vertices of the graph and no data
    associated with edges. The default behaviour is have undirected edges.
    This can be changed to directed if specified in the constructor. No
    self links (edges from one vertex to itself) are allowed."]
    [Summary = "A template graph with edges as simple pointers to vertices."]
    [Authors = "W.R.Pitt"]
    [Files = "<A HREF=./btl/Graph.h>Graph.h</A>"]
    [Friends="operator&lt&lt"]
    [Dependencies="<A HREF=#BTL_Vertex>BTL_VertexBase and its subclasses.</A>"]

*/

template<class Dereferencer>
class BTL_Graph
{
public:

    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;
    typedef BTL_Vertex<Dereferencer>  	    	    Vertex;
    typedef BTL_VertexBase*  	    	    	    VertexBasePtr;
    typedef Vertex* 	    	    	    	    VertexPtr;
    typedef BTL_PtrSet<Vertex>      	    	    VertexPtrStore;
    typedef BTL_II<Vertex>   	    		    VertexIterator;
    typedef BTL_CII<Vertex>  	    		    ConstVertexIterator;
    typedef VertexPtrStore::size_type	    	    size_type;

    enum Directionality { directed, undirected };   // The two types
    	    	    	    	    	    	    // graph allowed
private:

    Dereferencer	deref;	    	// Object used to reference vertex data
    container_type  	vertexData;	// Vertex data
    Directionality      directionality; // Type of edges
    VertexPtrStore  	vertices;       // Vertices within this graph

protected:

    // Check that a pointer points to a vertex in this graph O(logN)
    //
	    	/**#: [Hidden] */
    bool
    ValidVertexPointer(VertexPtr v)
    {
    	return vertices.find(v) != vertices.end();
    }
    
    // Remove link between two vertices. Return false if vertices are not part
    // of this graph or if no edge exists between them.
    //
	    	/**#: [Hidden] */
    bool
    RemoveLink(VertexPtr p1, VertexPtr p2)
    {
    	if (p1 == p2) return false;
   	if (!ValidVertexPointer(p1) || !ValidVertexPointer(p2)) return false;
    	if (!p1->RemoveLink(p2)) return false; 
    	if (directionality == undirected) p2->RemoveLink(p1);
    	return true;
    }
    
    // Remove vertex from this graph. Return false if vertex is not part of this
    // graph.
	    	/**#: [Hidden] */
    bool
    RemoveVertex(VertexPtr p)
    {
    	// Check that vertex is in this graph
    	//
    	VertexPtrStore::iterator target = vertices.find(p);
    	if (target == vertices.end()) return false;
    	
    	// Remove all links to the vertex
    	//	
    	if (directionality==undirected)
    	    p->RemoveLinks();
    	else
    	{
    	    for (VertexIterator i=begin_vertex(); i!=end_vertex(); i++)
    	    	(*i).RemoveLink(p);
    	}    	
    	
	// Update references from vertices to data. This is needed only when
	// indices are used instead of iterators. Does nothing (over and over
	// again when iterator references are used)
    	
    	for (VertexIterator i=begin_vertex(); i!=end_vertex(); i++)
    	    (*i).UpdateReference(p);
	    
    	// Remove data item
    	//
   	deref.Remove(p->GetRef());
    	
    	// Delete vertex object
    	//    
    	delete p;
	
	// Remove vertex from list of vertices within this graph
	//    
    	vertices.erase(target);
    	
    	return true;
    }	
     
	    	/**#: [Hidden] */
    reference_type
    InsertVertexItem(const value_type& v)
    {
   	 return deref.Insert(v);
    }

	    	/**#: [Hidden] */
    Dereferencer&
    GetDerefObj()
    {
    	return deref;
    }

	    	/**#: [Hidden] */
    VertexIterator
    InsertVertex(VertexPtr p)
    {
    	return vertices.insert(vertices.end(),p);
    }

	    	// Virtual method from actually doing the printing
	    	//
	    	/**#: [Hidden] */
    virtual void
    Print(ostream& os) const
    {
    	os << "\nVERTICES:\n";

    	// Print each vertex in the order they were created
    	//
	typedef set< VertexBasePtr, BTL_ById<VertexBasePtr> > SortedSet;
	SortedSet sortedSet;

    	for (ConstVertexIterator i = begin_vertex(); i!=end_vertex();i++)
	    sortedSet.insert(sortedSet.end(),i.GetPointer());

	for (SortedSet::iterator i=sortedSet.begin(); i!=sortedSet.end(); i++)
    	    os << **i;

    	os << '\n';
    }

public:

	    	/**#: [Description="Construct new undirected graph"] */

    BTL_Graph() { deref.SetContainer(&vertexData); directionality = undirected; }

	    	/**#: [Description="Construct new undirected or 
	    	       directed graph i.e. BTL_Graph g1(directed); or BTL_Graph
	    	       g2(undirected); "] */

    BTL_Graph(const Directionality& e) : directionality(e) 
    { 
    	deref.SetContainer(&vertexData); 
    }

	    	/**#: [Description="Delete Graph and all the vertices in it"] */
    virtual 
    ~BTL_Graph() 
    { 
    	VertexPtrStore::iterator i;
    	for (i=vertices.begin(); i != vertices.end(); i++)
    	    delete *i;
    }

	    	/**#: [Description="Get the edge directionality of this
		       graph."] */
    Directionality
    GetDirectionality() const { return directionality; }

	    	/**#: [Description="Add new vertex to graph."] */
    virtual VertexIterator
    AddVertex(const value_type& v)
    {
     	// Create new Vertex object with no links.
    	//
	reference_type ref = InsertVertexItem(v);
    	VertexPtr p = new Vertex(deref,ref);
    	if (p == NULL) FATAL_ERROR("No more memory.");
    	return vertices.insert(vertices.end(),p);
    }

	    	/**#: [Description="Remove a vertex (and all pointers to it)
	    	       from the graph. Return false if vertex was not found
	    	       in the graph."] */
    virtual bool
    RemoveVertex(VertexIterator in)
    {

    	VertexPtr p = in.GetPointer();
	return RemoveVertex(p);
    }

	    	/**#: [Description="Add a pointer between two vertices.
	    	       Return false if either vertex is not in this graph or
	    	       is link already present"] */
    bool
    AddLink(VertexIterator i1, VertexIterator i2)
    {
    	VertexPtr p1 = i1.GetPointer(), p2 = i2.GetPointer();
    	if (!ValidVertexPointer(p1) || !ValidVertexPointer(p2)) return false;

    	// Try add link(s) return false if it is already present or if
    	// p1 == p2
	//
    	if (!p1->AddLink(p2)) return false;
    	if (directionality == undirected) p2->AddLink(p1);
    	return true;
    }
	    	/**#: [Description="Remove pointer/link between two vertices.
	    	       Return false if link not there"] */
    bool
    RemoveLink(VertexIterator i1, VertexIterator i2)
    {
     	VertexPtr p1 = i1.GetPointer(), p2 = i2.GetPointer();
	return RemoveLink(p1,p2);
    }

	    	/**#: [Description="Set the visited field of all vertices in
	    	       this graph."] */
    virtual void
    SetAllVisited(bool truth)
    {
    	for (VertexIterator i=begin_vertex(); i!=end_vertex(); i++)
    	    (*i).Visited() = truth;
    }
	    	/**#: [Description="Find a vertex within this Graph.(There is a
		       const version of this function as well)"] */
    virtual VertexIterator
    find(Vertex& v)
    {
    	return vertices.find(&v);
    }

    virtual ConstVertexIterator
    find(Vertex& v) const
    {
    	return vertices.find(&v);
    }
	    	/**#: [Description="Return iterator that references first
	    	       data item.(There is a const version of this function
		       as well)"] */
    iterator
    begin() { return vertexData.begin(); }

    const_iterator
    begin() const { return vertexData.begin(); }

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

    const_iterator
    end() const { return vertexData.end(); }

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

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

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

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

	    	/**#: [Description="Give the number of vertices within the
	    	       Graph"] */
    size_type
    size() const { return vertices.size(); }

	    	/**#: [Description="Print list of vertices in this graph and
		       their connections."] */
    friend ostream&
    operator<<(ostream& os, const BTL_Graph& g) { g.Print(os); return os; }

};
	    	/**#: [Hidden] */

template <class Container>
class BTL_Graph1 : public
BTL_Graph< BTL_ItD<Container> >
{};
	    	/**#: [Hidden] */

template <class Container>
class BTL_Graph2 : public
BTL_Graph< BTL_InD<Container> >
{};

_BTL_END_NAMESPACE

#endif // Graph.h

unsigned int BTL_VertexBase::nextId = 1;