btl_graph_with_edges.h

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

    typedef BTL_Edge<VertexDereferencer,EdgeDereferencer>   Edge;
    typedef BTL_TYPENAME Edge::container_type    	EdgeContainer;
    typedef BTL_TYPENAME Edge::iterator  	    	EdgeDataIterator;
    typedef BTL_TYPENAME Edge::const_iterator  	    	EdgeDataConstIterator;
    typedef BTL_TYPENAME Edge::value_type 	    	EdgeData;
    typedef BTL_TYPENAME Edge::reference_type    	EdgeReference;
    typedef BTL_TYPENAME VertexDereferencer::value_type value_type;
    typedef BTL_Graph<VertexDereferencer>	Base;
    typedef Edge*   	    	    	    	EdgePtr;
    typedef BTL_PtrSet<Edge>        	    	EdgePtrStore;
    typedef BTL_II<Edge>       			EdgeIterator;
    typedef BTL_CII<Edge>      			ConstEdgeIterator;

    typedef BTL_VertexWithEdges<VertexDereferencer,EdgeDereferencer> VertexWE;
    typedef VertexWE* VertexWEPtr;

private:

    EdgeDereferencer	deref;
    EdgeContainer  	data;
    EdgePtrStore	edges;

    // Delete pointer to edge from edge store (but don't delete object).
    //
	    	/**#: [Hidden] */
    bool
    RemoveEdgePtrFromStore(EdgePtr edge)
    {
    	EdgePtrStore::iterator i = edges.find(edge);
    	if (i == edges.end()) return false;
    	edges.erase(i);
    	return true;
    }


	    	/**#: [Hidden] */
    void
    ConnectNewEdge(EdgePtr e, VertexWEPtr left, VertexWEPtr right)
    {
    	// Connect the two vertices to the new edge
    	//
    	left->AddEdge(e);
    	right->AddEdge(e);
    }

    // Delete all edges connected to a particular vertex
    //
	    	/**#: [Hidden] */
    void
    DeleteVertexEdges(VertexWEPtr v)
    {
    	typedef BTL_TYPENAME VertexWE::EdgeIterator EIterator;
	EdgePtrStore vertex_edges;
	
	// Store pointers to edges connected to the vertex. Edges are deleted
	// from the vertex's own container by DeleteEdge
	//
    	for (EIterator i = v->begin_edge(); i!= v->end_edge(); i++)
    	{
    	    EdgePtr edgePtr = i.GetPointer();
	    vertex_edges.insert(vertex_edges.end(),edgePtr);
    	}
	for (EdgePtrStore::iterator i=vertex_edges.begin();
	                           i!=vertex_edges.end(); i++)
    	    DeleteEdge((EdgePtr) *i);
    }

    // Delete Edge
    //
	    	/**#: [Hidden] */
    void
    DeleteEdge(EdgePtr edgePtr)
    {
    	// Remove pointers to this edge from connected vertices
	//
        edgePtr->leftVertex->RemoveEdge(edgePtr);
        edgePtr->rightVertex->RemoveEdge(edgePtr);
	
	// Remove this edge from the list of edges in this graph
	//
    	RemoveEdgePtrFromStore(edgePtr);

	// Update references from edges 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 (EdgeIterator i=begin_edge(); i!=end_edge(); i++)
    	    (*i).UpdateReference(edgePtr);
	    
    	// Remove edge data item
    	//
   	deref.Remove(edgePtr->ref);

    	// Delete edge object
	//
    	delete edgePtr;
    }


    // Make link functions private to enforce use of edge functions

	    	/**#: [Hidden] */
    bool
    AddLink(VertexIterator i1, VertexIterator i2) 
    { 
    	return Base::AddLink(i1,i2);
    }

	    	/**#: [Hidden] */
    bool
    RemoveLink(VertexIterator i1, VertexIterator i2)
    { 
    	return Base::RemoveLink(i1,i2);
    }

public:


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

    BTL_GraphWithEdges() : Base() { deref.SetContainer(&data); }

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

    BTL_GraphWithEdges(const Directionality& e) : Base(e) 
    {
    	deref.SetContainer(&data);
    }


	    	/**#: [Description="Delete graph and all vertices and edges in
	    	       it."] */
    virtual
    ~BTL_GraphWithEdges()
    {
    	// Delete all the Edges before the Graph itself is deleted.
    	//
    	EdgePtrStore::iterator i;
    	for (i=edges.begin(); i!=edges.end(); i++)
    	    delete *i;
    }

	    	/**#: [Description="Add new vertex to graph."] */
    virtual VertexIterator
    AddVertex(const value_type& v)
    {
    	// Insert data item into vertex data container
	//
	reference_type ref = InsertVertexItem(v);

     	// Create new VertexWithEdges object with no links.
    	//
    	VertexWEPtr p = new VertexWE(GetDerefObj(),ref);
    	if (p == NULL) FATAL_ERROR("No more memory.");

	// Insert new VertexWithEdges into vertex store (implicit up cast from
	// VertexWithEdge* to Vertex*).
	//
    	return InsertVertex(p);
    }

	    	/**#: [Description="Delete vertex from graph. Return false
	    	       if vertex not found in this graph."] */
    virtual bool
    RemoveVertex(VertexIterator in)
    {
    	VertexPtr v = in.GetPointer();

    	// Check that input is valid
    	//
    	if (!ValidVertexPointer(v)) return false;

    	// Delete connected edges
    	//
#if defined(GCC_272)
	VertexWEPtr vwe = (VertexWEPtr) v;
#else
	VertexWEPtr vwe = dynamic_cast<VertexWEPtr>(v);
#endif
    	DeleteVertexEdges(vwe);

    	// Delete vertex.
    	//
    	Base::RemoveVertex(v);

    	return true;
    }

	    	/**#: [Description="Insert edge into this graph. Return
	    	       endEdge() if input is invalid."] */
    EdgeIterator
    AddEdge(VertexIterator i1, VertexIterator i2, const EdgeData& d)
    {
    	// Add link(s) between vertices. This returns false if both iterators
	// reference the same vertex.
    	//
    	if (!AddLink(i1,i2)) return edges.end();

    	VertexPtr v1 = i1.GetPointer(), v2 = i2.GetPointer();

#if defined(GCC_272)
	VertexWEPtr vwe1 = (VertexWEPtr) v1;
	VertexWEPtr vwe2 = (VertexWEPtr) v2;
#else
	VertexWEPtr vwe1 = dynamic_cast<VertexWEPtr>(v1);
	VertexWEPtr vwe2 = dynamic_cast<VertexWEPtr>(v2);
#endif

     	// Create new Edge object.
    	//
   	EdgeReference ref = deref.Insert(d);
    	EdgePtr e = new Edge(deref,ref,vwe1,vwe2);
    	if (e == NULL) FATAL_ERROR("No more memory.");

    	// Make connection from connected vertices to this edge
	//
     	ConnectNewEdge(e, vwe1, vwe2);

    	// Store pointer to edge
    	//
    	return edges.insert(edges.end(),e);
    }


	    	/**#: [Description="Remove edge from this graph. Return
	    	       false if input is invalid."] */
    bool
    RemoveEdge(EdgeIterator edgeIter)
    {
    	// Convert iterator to pointer
    	//
    	EdgePtr edgePtr = edgeIter.GetPointer();

    	// Check edge belongs to this graph
	//
	if (edges.find(edgePtr) == edges.end()) return false;

    	// Find the two vertices connected by edge
    	//
    	VertexWEPtr v1 = edgePtr->leftVertex,
    	            v2 = edgePtr->rightVertex;

    	// Remove link in BTL_Graph (implicit up cast of vertex pointers)
    	//
    	if (!Base::RemoveLink(v1,v2))
    	    FATAL_ERROR("Unexpected occurrence.");

    	// Delete edge
    	//
      	DeleteEdge(edgePtr);

    	return true;
    }

	    	/**#: [Description="Return iterator that references first
	    	       edge data item. (There is a const version of this
		       function as well)"] */
    EdgeDataIterator
    BeginEdgeData() { return data.begin(); }

    EdgeDataConstIterator
    BeginEdgeData() const { return data.begin(); }

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

    EdgeDataConstIterator
    EndEdgeData() const { return data.end(); }

	    	/**#: [Description="Return EdgeIterator that references first
	    	       edge in graph. (There is a const version of this function
		       as well)"] */
    EdgeIterator
    begin_edge() { return edges.begin(); }

    ConstEdgeIterator
    begin_edge() const { return edges.begin(); }

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

    ConstEdgeIterator
    end_edge() const { return edges.end(); }


    	    	// Print details of all vertices and edges in graph and the
    	    	// connections betwen them.
    	    	//
	    	/**#: [Hidden] */
    virtual void
    Print(ostream& os) const
    {
    	Base::Print(os);

    	os << "EDGES:\n";
    	for (ConstEdgeIterator i=begin_edge(); i!=end_edge(); i++)
    	    os << *i;
    	os << '\n';
    }

}; // class BTL_GraphWithEdges

// Graph where vertex data and edge data are be stored in the same type
// of container which is neither a vector or a deque

	    	/**#: [Hidden] */

template <class Container>
class BTL_Graph3 : public
BTL_GraphWithEdges< BTL_ItD<Container>, BTL_ItD<Container> >
{};

// Graph where vertex data and edge data are be stored in the same type
// of container which is either a vector or a deque

	    	/**#: [Hidden] */

template <class Container>
class BTL_Graph4 : public
BTL_GraphWithEdges< BTL_InD<Container>, BTL_InD<Container> >
{};

// Graph where vertices and edges can be stored in different types of containers
// as long as NEITHER are STL vectors or the like.

	    	/**#: [Hidden] */

template <class Container1, class Container2>
class BTL_Graph5 : public
BTL_GraphWithEdges< BTL_ItD<Container1>, BTL_ItD<Container2> >
{};

// Graph where vertices and edges can be stored in different types of containers
// as long as BOTH are STL vectors or the like.

	    	/**#: [Hidden] */

template <class Container1, class Container2>
class BTL_Graph6 : public
BTL_GraphWithEdges< BTL_InD<Container1>, BTL_InD<Container2> >
{};

_BTL_END_NAMESPACE

#endif // GraphWithEdges.h

unsigned int BTL_EdgeBase::nextId = 1;