00001 #include "graph.h"
00002 #include "math2.h"
00003
00004 namespace Graph
00005 {
00006
00007
00008
00009 void Node::AddEdge( const int edgeNum )
00010 {
00011 m_Edges.push_back( edgeNum );
00012 }
00013
00014
00015
00016
00017 int Node::GetEdgeNumber( const int index ) const
00018 {
00019 int returnMe = m_Edges[ index ];
00020 return returnMe;
00021 }
00022
00023
00024
00025
00026 unsigned int Node::GetNumEdges() const
00027 {
00028 return m_Edges.size();
00029 }
00030
00031
00032
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
00046
00047 Edge::Edge( const int n0, const int n1 ):
00048 m_Node0( n0 ),
00049 m_Node1( n1 )
00050 {
00051 }
00052
00053
00054
00055
00056 Edge::Edge( const Edge& e ):
00057 m_Node0( e.m_Node0 ),
00058 m_Node1( e.m_Node1 )
00059 {
00060 }
00061
00062
00063
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
00074
00075 GraphBase::GraphBase()
00076 {
00077
00078 }
00079
00080
00081
00082
00083 GraphBase::GraphBase( const GraphBase& right )
00084 {
00085 IJG_Assert( right.GetNumNodes() == 0 );
00086 IJG_Assert( right.GetNumEdges() == 0 );
00087 }
00088
00089
00090
00091
00092 GraphBase::~GraphBase()
00093 {
00094
00095 }
00096
00097
00098
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
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
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
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
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
00158
00159 int GraphBase::AddNode()
00160 {
00161 m_Nodes.push_back( Node() );
00162 return m_Nodes.size();
00163 }
00164
00165
00166
00167
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
00193
00194 void GraphBase::Clear()
00195 {
00196 m_Nodes.clear();
00197 m_Edges.clear();
00198 }
00199
00200
00201
00202
00203 Node& GraphBase::GetNode( const int node )
00204 {
00205 return m_Nodes[ node ];
00206 }
00207
00208
00209
00210
00211 const Node& GraphBase::GetNode( const int node ) const
00212 {
00213 return m_Nodes[ node ];
00214 }
00215
00216
00217
00218
00219 const Edge& GraphBase::GetEdge( const unsigned int edge ) const
00220 {
00221 return m_Edges[ edge ];
00222 }
00223
00224
00225
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
00247
00248 unsigned int GraphBase::GetNumEdges() const
00249 {
00250 return m_Edges.size();
00251 }
00252
00253
00254
00255
00256 unsigned int GraphBase::GetNumNodes() const
00257 {
00258 return m_Nodes.size();
00259 }
00260
00261
00262
00263
00264 GraphBase& GraphBase::operator=( const GraphBase& right )
00265 {
00266 IJG_Assert( false );
00267 return *this;
00268 }
00269 }