include/Structs/Graphs/adjacencyListImpl.h

#ifndef ADJACENCYLISTIMPL_H
#define ADJACENCYLISTIMPL_H

#include <Structs/Graphs/dynamicGraph.h>
#include <Utilities/mersenneTwister.h>
#include <list>

template<typename Vtype, typename Etype>
class ALNode;
template<typename Vtype, typename Etype>
class ALEdge;
template<typename Vtype, typename Etype>
class ALInEdge;


template<typename Vtype, typename Etype>
class AdjacencyListImpl
{
public:
    
    typedef unsigned int                                                SizeType;
    typedef typename std::list< ALNode< Vtype, Etype> >::iterator       NodeIterator;
    typedef typename std::list< ALEdge< Vtype, Etype> >::iterator       EdgeIterator;
    typedef typename std::list< ALInEdge< Vtype, Etype> >::iterator     InEdgeIterator;
    typedef NodeIterator*                                               NodeDescriptor;
    typedef EdgeIterator*                                               EdgeDescriptor;

    AdjacencyListImpl():m_numNodes(0),m_numEdges(0)
    {
    }

    ~AdjacencyListImpl() 
    {
        NodeIterator end = m_nodes.end();
        EdgeIterator e, end_edges;

        for( NodeIterator u = m_nodes.begin(); u != end; ++u)
        {
            delete u->getDescriptor();
            for( e = beginEdges(u), end_edges = endEdges(u); e != end_edges; ++e)
            {
                delete e->getDescriptor();
            }
        }        
    }

    NodeDescriptor insertNode() 
    { 
        //create empty node
        ALNode<Vtype,Etype> newNode;
        //create descriptor
        NodeDescriptor m_auxNodeDescriptor = new NodeIterator();
        newNode.setDescriptor( m_auxNodeDescriptor);

        //insert node
        m_nodes.push_back( newNode);
        NodeIterator m_auxNodeIterator = m_nodes.end();
        --m_auxNodeIterator;
        
        //update descriptor
        *m_auxNodeDescriptor = m_auxNodeIterator;
        ++m_numNodes;
        return m_auxNodeDescriptor;
    }
    
    EdgeDescriptor insertEdge( const NodeDescriptor& uD, const NodeDescriptor& vD) 
    { 
        NodeIterator u = getNodeIterator( uD);
        NodeIterator v = getNodeIterator( vD);
        
        //create empty edge
        ALEdge<Vtype, Etype> newEdge;
        //create empty back edge
        ALInEdge<Vtype, Etype> newInEdge;
    
        //create descriptor
        EdgeDescriptor m_auxEdgeDescriptor = new EdgeIterator();
        newEdge.setDescriptor(m_auxEdgeDescriptor);

        //insert forward edge
        (*u).m_edges.push_back( newEdge);
        
        //insert backward edge
        (*v).m_InEdges.push_back( newInEdge);
        
        //get iterators on edges
        EdgeIterator e = u->m_edges.end();
        --e;
        InEdgeIterator k = v->m_InEdges.end();
        --k;

        //insert edge info
        e->m_adjacentNode = v;
        e->m_InEdge = k;

        k->m_adjacentNode = u;        
        k->m_edge = e;

        *m_auxEdgeDescriptor = e;

        ++m_numEdges;
        return m_auxEdgeDescriptor;
    }

    void eraseNode( const NodeIterator& u) 
    { 
        NodeDescriptor descriptor = u->getDescriptor();
        delete descriptor;
        descriptor = 0;
        m_nodes.erase(u);
        --m_numNodes;
    }
    
    void eraseEdge( const InEdgeIterator& k)
    {
        eraseEdge( getEdgeIterator(k));
    }

    void eraseEdge( const EdgeIterator& e) 
    { 
        InEdgeIterator k = e->m_InEdge;
        NodeIterator u = k->m_adjacentNode;
        NodeIterator v = e->m_adjacentNode;
        EdgeDescriptor descriptor = e->getDescriptor();
        delete descriptor;
        descriptor = 0;
        (*v).m_InEdges.erase(k);
        (*u).m_edges.erase(e);
        --m_numEdges;
    }

    NodeIterator beginNodes()
    { 
        return m_nodes.begin();
    }
    
    NodeIterator endNodes() 
    { 
        return m_nodes.end();
    }

    EdgeIterator beginEdges( const NodeIterator& u) 
    { 
        return u->m_edges.begin();
    }
    
    EdgeIterator endEdges( const NodeIterator& u) 
    { 
        return u->m_edges.end();
    }
    
    InEdgeIterator beginInEdges( const NodeIterator& u) 
    { 
        return u->m_InEdges.begin();
    }
        
    InEdgeIterator endInEdges( const NodeIterator& u) 
    { 
        return u->m_InEdges.end();
    }
    
        NodeIterator chooseNode()  
        { 
            double random = m_random.getRandomNormalizedDouble();
        SizeType pos = m_nodes.size() * random;
        
        NodeIterator m_auxNodeIterator = m_nodes.begin();
        
        std::advance( m_auxNodeIterator, pos);
        return m_auxNodeIterator;
        }
        
    EdgeDescriptor getDescriptor( const InEdgeIterator& k) const
    {
        return getEdgeIterator(k)->getDescriptor();
    }

        EdgeDescriptor getDescriptor( const EdgeIterator& e) const
    {
        return e->getDescriptor();
    }
    
    NodeDescriptor getDescriptor( const NodeIterator& u) const
    {
        return u->getDescriptor();
    }
        
    EdgeIterator getEdgeIterator( const EdgeDescriptor& descriptor) const
    { 
        return *descriptor;
    }

    NodeIterator getNodeIterator( const NodeDescriptor& descriptor) const
    { 
        return *descriptor;
    }

    NodeIterator getAdjacentNodeIterator( const EdgeIterator& e)
    {
        return e->m_adjacentNode;
    }

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

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

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

    /*const bool& isInEdge( const EdgeIterator& e) const
    {
        return e->m_isInEdge;
    }*/

    bool hasEdges( const NodeIterator& u)
    {
        return !(*u).m_edges.empty();
    }

    bool hasInEdges( const NodeIterator& u)
    {
        return !(*u).m_InEdges.empty();
    }

    bool hasEdge( const EdgeDescriptor& descriptor)
    {
        return descriptor != 0;
    }
  
    bool hasNode( const NodeDescriptor& descriptor)
    {
        return descriptor != 0;
    }

    NodeIterator nilNode() const 
    {
        return m_nodes.end();
    }   
    
    EdgeIterator nilEdge() const 
    { 
        return (*m_nodes.begin()).m_edges.end();
    }

    SizeType memUsage()   
    { 
        std::cout << "Nodes:\t\t" << m_numNodes << "\n"; 
        std::cout << "Edges:\t\t" << m_numEdges << "\n"; 
        std::cout << "InEdges:\t" << m_numEdges << "\n";
        std::cout << "Node Size:\t" << ALNode< Vtype, Etype>::memUsage() << "bytes" << std::endl;
        std::cout << "Edge Size:\t" << ALEdge< Vtype, Etype>::memUsage() << "bytes" << std::endl;
        std::cout << "BWEdge Size:\t" << ALInEdge< Vtype, Etype>::memUsage() << "bytes" << std::endl;

        return m_numNodes * ALNode< Vtype, Etype>::memUsage() + m_numEdges * (ALEdge< Vtype, Etype>::memUsage() + ALInEdge< Vtype, Etype>::memUsage());
    }

    SizeType getId( const NodeIterator& u) 
    {
        return distance( m_nodes.begin(), u);
    }

    void reserve( const SizeType& numNodes, const SizeType& numEdges)
    {
        return;
    }

    SizeType indeg( const NodeIterator& u)
    {
        return distance( beginInEdges(u), endInEdges(u));
    }

    SizeType outdeg( const NodeIterator& u)
    {
        return distance( beginEdges(u), endEdges(u));
    }
    
    void clear()
    {
        m_nodes.clear();
        m_numNodes = 0;
        m_numEdges = 0;
    }

private:
    std::list< ALNode< Vtype, Etype> >  m_nodes;
    MersenneTwister                     m_random;
    SizeType                            m_numNodes;
    SizeType                            m_numEdges;
};


template<typename Vtype, typename Etype>
class ALEdge : public GraphElement< Etype, typename AdjacencyListImpl<Vtype,Etype>::EdgeDescriptor>
{

public:
    typedef typename AdjacencyListImpl<Vtype,Etype>::InEdgeIterator InEdgeIterator;
    typedef typename AdjacencyListImpl<Vtype,Etype>::NodeIterator NodeIterator;
    typedef typename AdjacencyListImpl<Vtype,Etype>::EdgeDescriptor EdgeDescriptor;
    typedef typename AdjacencyListImpl<Vtype,Etype>::NodeDescriptor NodeDescriptor;

    ALEdge( unsigned int init = 0): GraphElement< Etype, EdgeDescriptor>()
    {
    }
   
    ALEdge( NodeIterator adjacentNode , InEdgeIterator oppositeEdge , NodeDescriptor descriptor = 0, Etype data = Etype()):
            GraphElement< Etype, EdgeDescriptor>( descriptor),
                    m_adjacentNode(adjacentNode),
                        m_InEdge(oppositeEdge)
    {
    }
    
    static unsigned int memUsage() 
    {   
        //std::cout << GraphElement< Etype, EdgeDescriptor>::memUsage() + sizeof(NodeIterator) + sizeof(EdgeIterator) + sizeof(bool) << std::endl;
        return sizeof(ALEdge);
    }

    NodeIterator              m_adjacentNode;
    InEdgeIterator              m_InEdge;
};


template<typename Vtype, typename Etype>
class ALInEdge : public Etype
{

public:
    typedef typename AdjacencyListImpl<Vtype,Etype>::EdgeIterator EdgeIterator;
    typedef typename AdjacencyListImpl<Vtype,Etype>::NodeIterator NodeIterator;
    typedef typename AdjacencyListImpl<Vtype,Etype>::EdgeDescriptor EdgeDescriptor;
    typedef typename AdjacencyListImpl<Vtype,Etype>::NodeDescriptor NodeDescriptor;

    ALInEdge( unsigned int init = 0): Etype()
    {
    }
   
    ALInEdge( NodeIterator adjacentNode , EdgeIterator oppositeEdge , NodeDescriptor descriptor = 0, Etype data = Etype()):
            Etype(),
                    m_adjacentNode(adjacentNode),
                        m_edge(oppositeEdge)
    {
    }
    
    static unsigned int memUsage() 
    {   
        //std::cout << GraphElement< Etype, EdgeDescriptor>::memUsage() + sizeof(NodeIterator) + sizeof(EdgeIterator) + sizeof(bool) << std::endl;
        return sizeof(ALInEdge);
    }

    NodeIterator              m_adjacentNode;
    EdgeIterator              m_edge;
};

template<typename Vtype, typename Etype>
class ALNode : public GraphElement< Vtype, typename AdjacencyListImpl<Vtype,Etype>::NodeDescriptor>
{
public:
    typedef typename AdjacencyListImpl<Vtype,Etype>::NodeDescriptor NodeDescriptor;
    typedef typename std::list<ALEdge< Vtype, Etype> >::iterator iterator;
    typedef typename std::list<ALInEdge< Vtype, Etype> >::iterator backIterator;

    ALNode():GraphElement< Vtype, NodeDescriptor>()
    {
    }

    ALNode( NodeDescriptor descriptor):GraphElement< Vtype, NodeDescriptor>( descriptor)
    {
    }

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

    std::list< ALEdge< Vtype, Etype> >              m_edges;
    std::list< ALInEdge< Vtype, Etype> >          m_InEdges;
    
};



#endif //ADJACENCYLISTIMPL_H

---