include/Structs/Graphs/dynamicGraph.h

#ifndef DYNAMICGRAPH_H
#define DYNAMICGRAPH_H

#include <Structs/Arrays/packedMemoryArray.h>
#include <Utilities/mersenneTwister.h>
#include <Utilities/graphIO.h>
#include <Utilities/graphGenerators.h>
#include <vector>
#include <algorithm>


class DefaultGraphItem
{
public:
    DefaultGraphItem()
    {
    }

    void print( std::ofstream& out)
    {
        return;
    }

    static unsigned int memUsage()   
    { 
        return sizeof( DefaultGraphItem);
    }

    void setProperty( const std::string& name, const std::string& value)
    {

    }

    void writeProperties( std::ofstream& out, const std::string& propertyDelimiter = "\n", const std::string& valueDelimiter = " ")
    {
    }
    
    void writeJSON( std::ofstream& out)
    {
    }    
};


template<template <typename vtype,typename etype> class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem >
class DynamicGraph
{
public:
    
    typedef typename GraphImplementation<Vtype,Etype>::SizeType         SizeType;
    typedef typename GraphImplementation<Vtype,Etype>::NodeDescriptor   NodeDescriptor;
    typedef typename GraphImplementation<Vtype,Etype>::EdgeDescriptor   EdgeDescriptor;
    typedef typename GraphImplementation<Vtype,Etype>::NodeIterator     NodeIterator;
    typedef typename GraphImplementation<Vtype,Etype>::EdgeIterator     EdgeIterator;
    typedef typename GraphImplementation<Vtype,Etype>::InEdgeIterator   InEdgeIterator;
    typedef Vtype                                                       NodeData;
    typedef Etype                                                       EdgeData;
    typedef unsigned int                                                PropertyType;

    DynamicGraph()
    {
        impl = new GraphImplementation<Vtype,Etype>();
    }

    ~DynamicGraph() 
    { 
        delete impl;
    }
    

    EdgeIterator beginEdges( const NodeIterator& u) const 
    { 
        return impl->beginEdges( u);
    }
    
    InEdgeIterator beginInEdges( const NodeIterator& u) const 
    { 
        return impl->beginInEdges(u);
    }

    NodeIterator beginNodes() const 
    { 
        return impl->beginNodes();
    }

        NodeIterator chooseNode() const 
        { 
            return impl->chooseNode();
        }

    void clear()
    {
        impl->clear();
        m_numNodes = 0;
        m_numEdges = 0;
    }

    SizeType degree( NodeIterator& u) const 
    { 
        return indeg(u) + outdeg(u);
    }

    bool edgeExists( const EdgeDescriptor& descriptor)
    {
        return impl->edgeExists( descriptor);
    }

    EdgeIterator endEdges( const NodeIterator& u) const 
    { 
        return impl->endEdges( u);
    }

    InEdgeIterator endInEdges( const NodeIterator& u) const 
    { 
        return impl->endInEdges(u);
    }

    NodeIterator endNodes() const 
    { 
        return impl->endNodes();
    }

    void eraseEdge( EdgeDescriptor descriptor) 
    { 
        assert( edgeExists(descriptor));
        impl->eraseEdge( getEdgeIterator(descriptor));
         --m_numEdges;
    }
    
    void eraseNode( NodeDescriptor descriptor) 
    { 
        assert( hasNode(descriptor));
        NodeIterator u = getNodeIterator(descriptor);
        EdgeIterator e;
        InEdgeIterator k;          

        while( hasEdges(u))
        {
            e = beginEdges(u);
            impl->eraseEdge(e);
        }

        while( hasInEdges(u))
        {
            k = beginInEdges(u);
            impl->eraseEdge( k);
        }

        impl->eraseNode( u);
         --m_numNodes;
         assert(hasValidInEdges());
    }

    void generateFrom( GraphGenerator< DynamicGraph>* generator)
    {
        this->clear();
        generator->generate(*this);
    }

    EdgeDescriptor getEdgeDescriptor( const NodeDescriptor& uD, const NodeDescriptor& vD)
    {
        assert( hasEdge(uD,vD));
        return getEdgeDescriptor( getNodeIterator(uD),getNodeIterator(vD) );
    }

    EdgeDescriptor getEdgeDescriptor( const NodeIterator& u, const NodeIterator& v)
    {
        assert( hasEdge(u,v));
        return getEdgeDescriptor(getEdgeIterator(u,v));
    }  
    
    EdgeDescriptor getEdgeDescriptor( const EdgeIterator& e)
    {
        return impl->getDescriptor(e);
    }

    EdgeDescriptor getEdgeDescriptor( const InEdgeIterator& k)
    {
        return impl->getDescriptor(k);
    }

    EdgeIterator getEdgeIterator( const EdgeDescriptor& descriptor) 
    { 
        return impl->getEdgeIterator(descriptor);
    }

    EdgeIterator getEdgeIterator( const NodeIterator& u, const NodeIterator& v) const
    {
        EdgeIterator e, end;
        NodeIterator neigh;        
        for( e = beginEdges(u), end = endEdges(u); e != end; ++e)
        {
            neigh = target(e);
            if( neigh == v)
            {
                break;
            }
        }
        return e;
    }

    EdgeIterator getEdgeIterator( const InEdgeIterator& k) const
    {
        return impl->getEdgeIterator(k);
    }

    InEdgeIterator getInEdgeIterator( const EdgeIterator& e) const
    {
        return impl->getInEdgeIterator(e);
    }

    NodeDescriptor getNodeDescriptor( const NodeIterator& u)
    {
        return impl->getDescriptor(u);
    }

    NodeIterator getNodeIterator( const NodeDescriptor& descriptor) 
    { 
        return impl->getNodeIterator(descriptor);
    }

    NodeIterator getNodeIterator( const void* descriptor) 
    { 
        return impl->getNodeIterator( (NodeDescriptor)descriptor);
    }

    SizeType getNumEdges() const 
    { 
        return m_numEdges;
    }

    SizeType getNumNodes() const 
    { 
        return m_numNodes;
    }

    SizeType getRelativePosition( const NodeIterator& u) const
    {
        return impl->getId(u);
    }

    bool hasEdge( const NodeDescriptor& uD, const NodeDescriptor& vD)
    {
        assert( hasNode( uD) && hasNode( vD));
        return hasEdge( getNodeIterator( uD), getNodeIterator( vD));
    }

    bool hasEdge( const NodeIterator& u, const NodeIterator& v)
    {
        EdgeIterator e, end;
        NodeIterator neigh;        
        for( e = beginEdges(u), end = endEdges(u); e != end; ++e)
        {
            if( target(e) == v) return true;
        }
        return false;
    }
    
    bool hasEdges( const NodeIterator& u) const
    {
        return impl->hasEdges(u);
    }

    bool hasInEdges( const NodeIterator& u) const
    {
        return impl->hasInEdges(u);
    }

    bool hasNode( const NodeDescriptor& descriptor)
    {
        return impl->hasNode( descriptor);
    }

    bool hasValidInEdges()
    {
        NodeIterator u, end_nodes;
        EdgeIterator e, end_edges;
        for( u = beginNodes(), end_nodes = endNodes(); u != end_nodes; ++u)
        {
            for( e = beginEdges(u), end_edges = endEdges(u); e != end_edges; ++e)
            {
                if( getEdgeDescriptor(e) != getEdgeDescriptor(getInEdgeIterator(e)))
                {
                    return false;
                }
            }
        }
        return true;
    }

    SizeType indeg( NodeIterator& u) const 
    { 
        return impl->indeg(u);
    }
    
    EdgeDescriptor insertEdge( const NodeDescriptor& uD, const NodeDescriptor& vD) 
    { 
        //std::cout << "Inserting edge " << uD << "->" << vD << std::endl;
        assert( uD != vD);
        assert( hasNode(uD));
        assert( hasNode(vD));
        if( hasEdge( uD, vD)) return getEdgeDescriptor( uD, vD);
        ++m_numEdges;
        return impl->insertEdge( uD, vD);
    }
    
    NodeDescriptor insertNode() 
    {
        ++m_numNodes;
        return impl->insertNode();
    }
    
    SizeType memUsage() const   
    { 
        return impl->memUsage() + 2 * sizeof(SizeType) + 2 * sizeof (std::vector< std::string>);
    }

    NodeDescriptor nilNodeDescriptor() const 
    { 
        return 0;
    } 

    SizeType outdeg( NodeIterator& u) const 
    { 
        return impl->outdeg(u);
    }

    void printInternalDot(const std::string& filename)
    {
        std::ofstream out( filename.c_str());
        impl->printDot( out);
        out.close();      
    }

    void read( GraphReader< DynamicGraph>* reader)
    {
        this->clear();
        reader->read(*this);
    }

    void reserve( const SizeType& numNodes, const SizeType& numEdges)
    {
        impl->reserve( numNodes, numEdges);
    }

    NodeIterator source( EdgeIterator& e) const 
    {
        return impl->getAdjacentNodeIterator( getInEdgeIterator(e));
    }

    NodeIterator source( InEdgeIterator& k) const
    {
        return impl->getAdjacentNodeIterator( k);  
    }

    NodeIterator target( EdgeIterator& e) const 
    { 
        return impl->getAdjacentNodeIterator( e);
    }
     
    NodeIterator target( InEdgeIterator& k) const 
    { 
        return impl->getAdjacentNodeIterator( getEdgeIterator(k) );
    }

    void write( GraphWriter< DynamicGraph>* writer)
    {
        writer->write(*this);
    }

private:
    GraphImplementation<Vtype,Etype>*   impl;
    SizeType                            m_numNodes;
    SizeType                            m_numEdges;
};



template<typename DataType, typename DescriptorType, typename PropertyType = unsigned int>
class GraphElement : public DataType
{
public:  
    GraphElement():m_descriptor( 0)
    {
    }

    GraphElement( DescriptorType descriptor):m_descriptor( descriptor)
    {
    }
    
    DescriptorType getDescriptor() const
    {
        return m_descriptor;
    }

    bool operator ==( const GraphElement& other) const
        {
        return ( m_descriptor == other.m_descriptor );
        }
        
        bool operator !=( const GraphElement& other) const
        {
                return (m_descriptor != other.m_descriptor);
        }

    static unsigned int memUsage()   
    { 
        return sizeof( GraphElement);
    }
    
    void setDescriptor( const DescriptorType& descriptor)
    {
        m_descriptor = descriptor;
    }

protected:
    DescriptorType              m_descriptor; 
};


#endif // DYNAMICGRAPH_H

---