math/graph.cpp

Go to the documentation of this file.

#include "graph.h"
#include "math2.h"

namespace Graph
{
    //-----------------------------------------------------------------------------
    // Node::AddEdge
    //-----------------------------------------------------------------------------
    void Node::AddEdge( const int edgeNum )
    {
        m_Edges.push_back( edgeNum );
    }

    //-----------------------------------------------------------------------------
    // Node::GetNumEdges 
    //-----------------------------------------------------------------------------
    int Node::GetEdgeNumber( const int index ) const
    {
        int returnMe = m_Edges[ index ];
        return returnMe;
    }

    //-----------------------------------------------------------------------------
    // Node::GetNumEdges 
    //-----------------------------------------------------------------------------
    unsigned int Node::GetNumEdges() const
    {
        return m_Edges.size();
    }

    //-----------------------------------------------------------------------------
    // Node::OffsetEdgeNumbers
    //-----------------------------------------------------------------------------
    void Node::OffsetEdgeNumbers( const int offset )
    {
        int size = m_Edges.size();
        int i;
        for( i = 0; i < size; ++i )
        {
            m_Edges[ i ] += offset;
        }
    }

    //-----------------------------------------------------------------------------
    // Edge - constructor
    //-----------------------------------------------------------------------------
    Edge::Edge( const int n0, const int n1 ):
        m_Node0( n0 ),
        m_Node1( n1 )
    {
    }

    //-----------------------------------------------------------------------------
    // Edge - copy constructor
    //-----------------------------------------------------------------------------
        Edge::Edge( const Edge& e ):
        m_Node0( e.m_Node0 ),
        m_Node1( e.m_Node1 )
    {
    }

    //-----------------------------------------------------------------------------
    // Edge - Assignment operator
    //-----------------------------------------------------------------------------
    Edge& Edge::operator=( const Edge& e )
    {
        m_Node0 = e.m_Node0;
        m_Node1 = e.m_Node1;
        return *this;
    }

    //-----------------------------------------------------------------------------
    // GraphBase
    //-----------------------------------------------------------------------------
    GraphBase::GraphBase()
    {
        //nothing
    }

    //-----------------------------------------------------------------------------
    // GraphBase - copy constructor
    //-----------------------------------------------------------------------------
    GraphBase::GraphBase( const GraphBase& right )
    {
        IJG_Assert( right.GetNumNodes() == 0 );
        IJG_Assert( right.GetNumEdges() == 0 );
    }

    //-----------------------------------------------------------------------------
    // GraphBase - destructor
    //-----------------------------------------------------------------------------
    GraphBase::~GraphBase()
    {
        //nothing
    }

    //-----------------------------------------------------------------------------
    // Add - appends two graphs together
    //-----------------------------------------------------------------------------
    void GraphBase::Add( const GraphBase& right )
    {
        int originalNodes = GetNumNodes();
        int originalEdges = GetNumEdges();
        m_Nodes.insert( m_Nodes.end(), right.m_Nodes.begin(), right.m_Nodes.end() );
        m_Edges.insert( m_Edges.end(), right.m_Edges.begin(), right.m_Edges.end() );
        int newNodes = GetNumNodes();
        int newEdges = GetNumEdges();

        //
        // Update the edge values
        //
        int i;
        int size = m_Edges.size();
        for( i = originalEdges; i < size; ++i )
        {
            Edge& e = m_Edges[ i ];
            e.m_Node0 += originalNodes;
            e.m_Node1 += originalNodes;
        }

        //
        // Need to update the node values too
        //
        size = m_Nodes.size();
        for( i = originalNodes; i < size; ++i )
        {
            Node& n = GetNode( i );
            n.OffsetEdgeNumbers( originalEdges );
        }
    }

    //-----------------------------------------------------------------------------
    // AddEdge - adds an edge to the graph
    //-----------------------------------------------------------------------------
    int GraphBase::AddEdge( const int n0, const int n1 )
    {
        IJG_Assert( n0 != n1 );
        #ifdef _DEBUG
            int numNodes = m_Nodes.size();
            IJG_Assert( n0 < numNodes );
            IJG_Assert( n1 < numNodes );
        #endif

        m_Edges.push_back( Edge( n0, n1 ) );
        int edgeNum = m_Edges.size() - 1;
        Edge e = m_Edges[ edgeNum ];

        // add the edge to the two nodes
        Node& node0 = m_Nodes[ n0 ];
        node0.AddEdge( edgeNum );
        Node& node1 = m_Nodes[ n1 ];
        node1.AddEdge( edgeNum );
        return edgeNum;
    }

    //-----------------------------------------------------------------------------
    // AddNode - adds a node to the graph
    //-----------------------------------------------------------------------------
    int GraphBase::AddNode()
    {
        m_Nodes.push_back( Node() );
        return m_Nodes.size();
    }

    //-----------------------------------------------------------------------------
    // CheckIntegrity - checks to see if all the edges attached to a node point to 
    // the node
    //-----------------------------------------------------------------------------
    bool GraphBase::CheckIntegrity() const
    {
        int nodes = GetNumNodes();
        int i;
        for( i = 0; i < nodes; ++i )
        {
            const Node& n = GetNode( i );
            int numEdges = n.GetNumEdges();
            int j;
            for( j = 0; j < numEdges; ++j )
            {
                int edgeNumber = n.GetEdgeNumber( j );
                const Edge& edge = GetEdge( edgeNumber );
                if( ( edge.m_Node0 != i ) && ( edge.m_Node1 != i ) )
                {
                    return false;
                }
            }
        }
        return true;
    }

    //-----------------------------------------------------------------------------
    // Clear - removes all nodes and edges from a graph
    //-----------------------------------------------------------------------------
    void GraphBase::Clear()
    {
        m_Nodes.clear();
        m_Edges.clear();
    }

    //-----------------------------------------------------------------------------
    // GetNode
    //-----------------------------------------------------------------------------
    Node& GraphBase::GetNode( const int node )
    {
        return m_Nodes[ node ];
    }

    //-----------------------------------------------------------------------------
    // GetNode
    //-----------------------------------------------------------------------------
    const Node& GraphBase::GetNode( const int node ) const
    {
        return m_Nodes[ node ];
    }

    //-----------------------------------------------------------------------------
    // GetEdge
    //-----------------------------------------------------------------------------
    const Edge& GraphBase::GetEdge( const unsigned int edge ) const
    {
        return m_Edges[ edge ];
    }

    //-----------------------------------------------------------------------------
    // GetNeighbors
    //-----------------------------------------------------------------------------
    std::vector< int > GraphBase::GetNeighbors( const int nodeNum ) const
    {
        std::vector< int > returnMe;
        int numNodes = m_Nodes.size();
        IJG_Assert( numNodes > nodeNum );
        const Node& node = m_Nodes[ nodeNum ];
        int numEdges = node.GetNumEdges();
        int i;
        for( i = 0; i < numEdges; i++ )
        {
            int edgeNumber = node.GetEdgeNumber( i );
            const Edge& edge = m_Edges[ edgeNumber ];
            int neighbor = OddOneOut( nodeNum, edge.m_Node0, edge.m_Node1 );
            returnMe.push_back( neighbor );
        }
        return returnMe;
    }

    //-----------------------------------------------------------------------------
    // GetNumEdges
    //-----------------------------------------------------------------------------
    unsigned int GraphBase::GetNumEdges() const
    {
        return m_Edges.size();
    }
    
    //-----------------------------------------------------------------------------
    // GetNumNodes
    //-----------------------------------------------------------------------------
    unsigned int GraphBase::GetNumNodes() const
    {
        return m_Nodes.size();
    }

    //-----------------------------------------------------------------------------
    // operator =
    //-----------------------------------------------------------------------------
    GraphBase& GraphBase::operator=( const GraphBase& right )
    {
        IJG_Assert( false );
        return *this;
    }
} //namespace Graph

---