math/graph.h

Go to the documentation of this file.

#ifndef _GRAPH_H_
#define _GRAPH_H_


#include <vector>

namespace Graph
{
    
    //=============================================================================
    // class node
    //
    // This is the class for graph nodes
    //
    //=============================================================================
    class Node
    {
    public:
        void         AddEdge( const int edgeNum );
        int          GetEdgeNumber( const int index ) const;
        unsigned int GetNumEdges()   const;
        void         OffsetEdgeNumbers( const int offset );
    protected:
    private:
        std::vector< int > m_Edges;
    };
    
    //=============================================================================
    // class Edge 
    //
    // This is the class for graph edges
    //
    //=============================================================================
    class Edge
    {
    public:
        Edge();
        Edge( const int n0, const int n1 );
        Edge( const Edge& e );
        Edge& operator=( const Edge& e );
        
        int m_Node0;
        int m_Node1;
    };
    
    //=============================================================================
    // class GraphBase 
    //
    // This is the base class for graphs. it includes anything not template based
    //
    //=============================================================================
    class GraphBase
    {
    public:
        GraphBase();
        GraphBase( const GraphBase& right );
        ~GraphBase();

        void            Add( const GraphBase& right );
        int             AddNode();
        int             AddEdge( const int n0, const int n1 );
        bool            CheckIntegrity() const;
        void            Clear();
        Node&           GetNode( const int node );
        const Node&     GetNode( const int node ) const;
        unsigned int    GetNumEdges() const;
        unsigned int    GetNumNodes() const;
        const Edge&     GetEdge( const unsigned int edge ) const;
        std::vector< int > GetNeighbors( const int nodeNum ) const;
        GraphBase&      operator=( const GraphBase& right );
        
    protected:
        std::vector< Node > m_Nodes;
        std::vector< Edge > m_Edges;
    };
    //=============================================================================
    
    //=============================================================================
    // class Graph
    //
    // this is the class for graphs containing arbitrary data
    //
    //=============================================================================
    template< class NodeData, class EdgeData >
    class Graph : public GraphBase
    {
    public:
        void            Add( const Graph& right );
        int                             AddNode( const NodeData& nd );
        int             AddEdge( const int n0, const int n1 );
        int                             AddEdge( const int n0, const int n1, const EdgeData& ed );
        void            Clear();
        bool            ContainsNode( const NodeData& value ) const;
        const NodeData& GetNodeData( const int nodeNum ) const;
        void                    SetEdgeData( const int edgeNum, const EdgeData& ed );
    protected:
        std::vector< NodeData > m_NodeData;
        std::vector< EdgeData > m_EdgeData;
    }; //class Graph
    //=============================================================================

    //-----------------------------------------------------------------------------
    // Add
    //-----------------------------------------------------------------------------
    template< class NodeData, class EdgeData >
        void Graph< NodeData, EdgeData >::Add( const Graph< NodeData, EdgeData >& right )
    {
        GraphBase::Add( right );
        m_NodeData.insert( m_NodeData.end(), right.m_NodeData.begin(), right.m_NodeData.end() );
        m_EdgeData.insert( m_EdgeData.end(), right.m_EdgeData.begin(), right.m_EdgeData.end() );
    }

    //-----------------------------------------------------------------------------
    // AddNode
    //-----------------------------------------------------------------------------
    template< class NodeData, class EdgeData >
        int Graph< NodeData, EdgeData >::AddNode( const NodeData& nd )
    {
        GraphBase::AddNode();
        m_NodeData.push_back( nd );
        return m_NodeData.size() - 1;
    }
    
    //-----------------------------------------------------------------------------
    // AddEdge
    //-----------------------------------------------------------------------------
    template< class NodeData, class EdgeData >
        int Graph< NodeData, EdgeData >::AddEdge( const int n0, const int n1 )
    {
        return GraphBase::AddEdge( n0, n1 );
    }

    //-----------------------------------------------------------------------------
    // AddEdge
    //-----------------------------------------------------------------------------
    template< class NodeData, class EdgeData >
        int     Graph< NodeData, EdgeData >::AddEdge( const int n0, const int n1, const EdgeData& ed )
    {
        int edgeNumber = GraphBase::AddEdge( n0, n1 );
        SetEdgeData( edgeNumber, ed );
        return edgeNumber;
    }
    
    //-----------------------------------------------------------------------------
    // ContainsNode
    //-----------------------------------------------------------------------------
    template< class NodeData, class EdgeData >
        void Graph< NodeData, EdgeData >::Clear()
    {
        GraphBase::Clear();
        m_NodeData.clear();
        m_EdgeData.clear();
    }

    //-----------------------------------------------------------------------------
    // ContainsNode
    //-----------------------------------------------------------------------------
    template< class NodeData, class EdgeData >
        bool Graph< NodeData, EdgeData >::ContainsNode( const NodeData& value ) const
    {
        std::vector< NodeData>::const_iterator found = std::find( m_NodeData.begin(), m_NodeData.end(), value );
        return ( found != m_NodeData.end() );
    }

    //-----------------------------------------------------------------------------
    // GetNodeData
    //-----------------------------------------------------------------------------
    template< class NodeData, class EdgeData >
        const NodeData& Graph< NodeData, EdgeData >::GetNodeData( const int nodeNum ) const
    {
        #ifdef _DEBUG
            int size = m_NodeData.size();
            int numNodes = GetNumNodes();
            IJG_Assert( nodeNum < size );
            IJG_Assert( nodeNum < numNodes );
        #endif
        const NodeData& returnMe = m_NodeData[ nodeNum ];
        return returnMe;
    }
    
    //-----------------------------------------------------------------------------
    // SetEdgeData
    //-----------------------------------------------------------------------------
    template< class NodeData, class EdgeData >
        void Graph< NodeData, EdgeData >::SetEdgeData( const int edgeNum, const EdgeData& ed )
    {
        if( m_EdgeData.size() < edgeNum + 1 )
        {
            m_EdgeData.resize( edgeNum + 1 );
        }
        m_EdgeData[ edgeNum ] = ed;
    }
    
    //-----------------------------------------------------------------------------
} //namespace Graph
#endif

---