Changeset 824:5764dd9b6e18 in lemon for lemon
 Timestamp:
 09/29/09 12:03:02 (14 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/static_graph.h
r823 r824 196 196 } 197 197 } 198 node_first_out[node_num] = arc_num; 199 } 200 201 template <typename ArcListIterator> 202 void build(int n, ArcListIterator first, ArcListIterator last) { 203 built = true; 204 205 node_num = n; 206 arc_num = std::distance(first, last); 207 208 node_first_out = new int[node_num + 1]; 209 node_first_in = new int[node_num]; 210 211 arc_source = new int[arc_num]; 212 arc_target = new int[arc_num]; 213 arc_next_out = new int[arc_num]; 214 arc_next_in = new int[arc_num]; 215 216 for (int i = 0; i != node_num; ++i) { 217 node_first_in[i] = 1; 218 } 219 220 int arc_index = 0; 221 for (int i = 0; i != node_num; ++i) { 222 node_first_out[i] = arc_index; 223 for ( ; first != last && (*first).first == i; ++first) { 224 int j = (*first).second; 225 LEMON_ASSERT(j >= 0 && j < node_num, 226 "Wrong arc list for StaticDigraph::build()"); 227 arc_source[arc_index] = i; 228 arc_target[arc_index] = j; 229 arc_next_in[arc_index] = node_first_in[j]; 230 node_first_in[j] = arc_index; 231 arc_next_out[arc_index] = arc_index + 1; 232 ++arc_index; 233 } 234 if (arc_index > node_first_out[i]) 235 arc_next_out[arc_index  1] = 1; 236 } 237 LEMON_ASSERT(first == last, 238 "Wrong arc list for StaticDigraph::build()"); 198 239 node_first_out[node_num] = arc_num; 199 240 } … … 329 370 } 330 371 372 /// \brief Build the digraph from an arc list. 373 /// 374 /// This function builds the digraph from the given arc list. 375 /// It can be called more than once, but in such case, the whole 376 /// structure and all maps will be cleared and rebuilt. 377 /// 378 /// The list of the arcs must be given in the range <tt>[begin, end)</tt> 379 /// specified by STL compatible itartors whose \c value_type must be 380 /// <tt>std::pair<int,int></tt>. 381 /// Each arc must be specified by a pair of integer indices 382 /// from the range <tt>[0..n1]</tt>. <i>The pairs must be in a 383 /// nondecreasing order with respect to their first values.</i> 384 /// If the kth pair in the list is <tt>(i,j)</tt>, then 385 /// <tt>arc(k1)</tt> will connect <tt>node(i)</tt> to <tt>node(j)</tt>. 386 /// 387 /// \param n The number of nodes. 388 /// \param begin An iterator pointing to the beginning of the arc list. 389 /// \param end An iterator pointing to the end of the arc list. 390 /// 391 /// For example, a simple digraph can be constructed like this. 392 /// \code 393 /// std::vector<std::pair<int,int> > arcs; 394 /// arcs.push_back(std::make_pair(0,1)); 395 /// arcs.push_back(std::make_pair(0,2)); 396 /// arcs.push_back(std::make_pair(1,3)); 397 /// arcs.push_back(std::make_pair(1,2)); 398 /// arcs.push_back(std::make_pair(3,0)); 399 /// StaticDigraph gr; 400 /// gr.build(4, arcs.begin(), arcs.end()); 401 /// \endcode 402 template <typename ArcListIterator> 403 void build(int n, ArcListIterator begin, ArcListIterator end) { 404 if (built) Parent::clear(); 405 StaticDigraphBase::build(n, begin, end); 406 notifier(Node()).build(); 407 notifier(Arc()).build(); 408 } 409 331 410 /// \brief Clear the digraph. 332 411 ///
Note: See TracChangeset
for help on using the changeset viewer.