math/graph.cpp

Go to the documentation of this file.
00001 #include "graph.h"
00002 #include "math2.h"
00003 
00004 namespace Graph
00005 {
00006     //-----------------------------------------------------------------------------
00007     // Node::AddEdge
00008     //-----------------------------------------------------------------------------
00009     void Node::AddEdge( const int edgeNum )
00010     {
00011         m_Edges.push_back( edgeNum );
00012     }
00013 
00014     //-----------------------------------------------------------------------------
00015     // Node::GetNumEdges 
00016     //-----------------------------------------------------------------------------
00017     int Node::GetEdgeNumber( const int index ) const
00018     {
00019         int returnMe = m_Edges[ index ];
00020         return returnMe;
00021     }
00022 
00023     //-----------------------------------------------------------------------------
00024     // Node::GetNumEdges 
00025     //-----------------------------------------------------------------------------
00026     unsigned int Node::GetNumEdges() const
00027     {
00028         return m_Edges.size();
00029     }
00030 
00031     //-----------------------------------------------------------------------------
00032     // Node::OffsetEdgeNumbers
00033     //-----------------------------------------------------------------------------
00034     void Node::OffsetEdgeNumbers( const int offset )
00035     {
00036         int size = m_Edges.size();
00037         int i;
00038         for( i = 0; i < size; ++i )
00039         {
00040             m_Edges[ i ] += offset;
00041         }
00042     }
00043 
00044     //-----------------------------------------------------------------------------
00045     // Edge - constructor
00046     //-----------------------------------------------------------------------------
00047     Edge::Edge( const int n0, const int n1 ):
00048         m_Node0( n0 ),
00049         m_Node1( n1 )
00050     {
00051     }
00052 
00053     //-----------------------------------------------------------------------------
00054     // Edge - copy constructor
00055     //-----------------------------------------------------------------------------
00056         Edge::Edge( const Edge& e ):
00057         m_Node0( e.m_Node0 ),
00058         m_Node1( e.m_Node1 )
00059     {
00060     }
00061 
00062     //-----------------------------------------------------------------------------
00063     // Edge - Assignment operator
00064     //-----------------------------------------------------------------------------
00065     Edge& Edge::operator=( const Edge& e )
00066     {
00067         m_Node0 = e.m_Node0;
00068         m_Node1 = e.m_Node1;
00069         return *this;
00070     }
00071 
00072     //-----------------------------------------------------------------------------
00073     // GraphBase
00074     //-----------------------------------------------------------------------------
00075     GraphBase::GraphBase()
00076     {
00077         //nothing
00078     }
00079 
00080     //-----------------------------------------------------------------------------
00081     // GraphBase - copy constructor
00082     //-----------------------------------------------------------------------------
00083     GraphBase::GraphBase( const GraphBase& right )
00084     {
00085         IJG_Assert( right.GetNumNodes() == 0 );
00086         IJG_Assert( right.GetNumEdges() == 0 );
00087     }
00088 
00089     //-----------------------------------------------------------------------------
00090     // GraphBase - destructor
00091     //-----------------------------------------------------------------------------
00092     GraphBase::~GraphBase()
00093     {
00094         //nothing
00095     }
00096 
00097     //-----------------------------------------------------------------------------
00098     // Add - appends two graphs together
00099     //-----------------------------------------------------------------------------
00100     void GraphBase::Add( const GraphBase& right )
00101     {
00102         int originalNodes = GetNumNodes();
00103         int originalEdges = GetNumEdges();
00104         m_Nodes.insert( m_Nodes.end(), right.m_Nodes.begin(), right.m_Nodes.end() );
00105         m_Edges.insert( m_Edges.end(), right.m_Edges.begin(), right.m_Edges.end() );
00106         int newNodes = GetNumNodes();
00107         int newEdges = GetNumEdges();
00108 
00109         //
00110         // Update the edge values
00111         //
00112         int i;
00113         int size = m_Edges.size();
00114         for( i = originalEdges; i < size; ++i )
00115         {
00116             Edge& e = m_Edges[ i ];
00117             e.m_Node0 += originalNodes;
00118             e.m_Node1 += originalNodes;
00119         }
00120 
00121         //
00122         // Need to update the node values too
00123         //
00124         size = m_Nodes.size();
00125         for( i = originalNodes; i < size; ++i )
00126         {
00127             Node& n = GetNode( i );
00128             n.OffsetEdgeNumbers( originalEdges );
00129         }
00130     }
00131 
00132     //-----------------------------------------------------------------------------
00133     // AddEdge - adds an edge to the graph
00134     //-----------------------------------------------------------------------------
00135     int GraphBase::AddEdge( const int n0, const int n1 )
00136     {
00137         IJG_Assert( n0 != n1 );
00138         #ifdef _DEBUG
00139             int numNodes = m_Nodes.size();
00140             IJG_Assert( n0 < numNodes );
00141             IJG_Assert( n1 < numNodes );
00142         #endif
00143 
00144         m_Edges.push_back( Edge( n0, n1 ) );
00145         int edgeNum = m_Edges.size() - 1;
00146         Edge e = m_Edges[ edgeNum ];
00147 
00148         // add the edge to the two nodes
00149         Node& node0 = m_Nodes[ n0 ];
00150         node0.AddEdge( edgeNum );
00151         Node& node1 = m_Nodes[ n1 ];
00152         node1.AddEdge( edgeNum );
00153         return edgeNum;
00154     }
00155 
00156     //-----------------------------------------------------------------------------
00157     // AddNode - adds a node to the graph
00158     //-----------------------------------------------------------------------------
00159     int GraphBase::AddNode()
00160     {
00161         m_Nodes.push_back( Node() );
00162         return m_Nodes.size();
00163     }
00164 
00165     //-----------------------------------------------------------------------------
00166     // CheckIntegrity - checks to see if all the edges attached to a node point to 
00167     // the node
00168     //-----------------------------------------------------------------------------
00169     bool GraphBase::CheckIntegrity() const
00170     {
00171         int nodes = GetNumNodes();
00172         int i;
00173         for( i = 0; i < nodes; ++i )
00174         {
00175             const Node& n = GetNode( i );
00176             int numEdges = n.GetNumEdges();
00177             int j;
00178             for( j = 0; j < numEdges; ++j )
00179             {
00180                 int edgeNumber = n.GetEdgeNumber( j );
00181                 const Edge& edge = GetEdge( edgeNumber );
00182                 if( ( edge.m_Node0 != i ) && ( edge.m_Node1 != i ) )
00183                 {
00184                     return false;
00185                 }
00186             }
00187         }
00188         return true;
00189     }
00190 
00191     //-----------------------------------------------------------------------------
00192     // Clear - removes all nodes and edges from a graph
00193     //-----------------------------------------------------------------------------
00194     void GraphBase::Clear()
00195     {
00196         m_Nodes.clear();
00197         m_Edges.clear();
00198     }
00199 
00200     //-----------------------------------------------------------------------------
00201     // GetNode
00202     //-----------------------------------------------------------------------------
00203     Node& GraphBase::GetNode( const int node )
00204     {
00205         return m_Nodes[ node ];
00206     }
00207 
00208     //-----------------------------------------------------------------------------
00209     // GetNode
00210     //-----------------------------------------------------------------------------
00211     const Node& GraphBase::GetNode( const int node ) const
00212     {
00213         return m_Nodes[ node ];
00214     }
00215 
00216     //-----------------------------------------------------------------------------
00217     // GetEdge
00218     //-----------------------------------------------------------------------------
00219     const Edge& GraphBase::GetEdge( const unsigned int edge ) const
00220     {
00221         return m_Edges[ edge ];
00222     }
00223 
00224     //-----------------------------------------------------------------------------
00225     // GetNeighbors
00226     //-----------------------------------------------------------------------------
00227     std::vector< int > GraphBase::GetNeighbors( const int nodeNum ) const
00228     {
00229         std::vector< int > returnMe;
00230         int numNodes = m_Nodes.size();
00231         IJG_Assert( numNodes > nodeNum );
00232         const Node& node = m_Nodes[ nodeNum ];
00233         int numEdges = node.GetNumEdges();
00234         int i;
00235         for( i = 0; i < numEdges; i++ )
00236         {
00237             int edgeNumber = node.GetEdgeNumber( i );
00238             const Edge& edge = m_Edges[ edgeNumber ];
00239             int neighbor = OddOneOut( nodeNum, edge.m_Node0, edge.m_Node1 );
00240             returnMe.push_back( neighbor );
00241         }
00242         return returnMe;
00243     }
00244 
00245     //-----------------------------------------------------------------------------
00246     // GetNumEdges
00247     //-----------------------------------------------------------------------------
00248     unsigned int GraphBase::GetNumEdges() const
00249     {
00250         return m_Edges.size();
00251     }
00252     
00253     //-----------------------------------------------------------------------------
00254     // GetNumNodes
00255     //-----------------------------------------------------------------------------
00256     unsigned int GraphBase::GetNumNodes() const
00257     {
00258         return m_Nodes.size();
00259     }
00260 
00261     //-----------------------------------------------------------------------------
00262     // operator =
00263     //-----------------------------------------------------------------------------
00264     GraphBase& GraphBase::operator=( const GraphBase& right )
00265     {
00266         IJG_Assert( false );
00267         return *this;
00268     }
00269 } //namespace Graph

Generated on Sat Apr 1 21:30:38 2006 for Motion Planning Kernel by  doxygen 1.4.6-NO