Changeset 824:5764dd9b6e18 in lemon
- Timestamp:
- 09/29/09 12:03:02 (15 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 2 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..n-1]</tt>. <i>The pairs must be in a 383 /// non-decreasing order with respect to their first values.</i> 384 /// If the k-th pair in the list is <tt>(i,j)</tt>, then 385 /// <tt>arc(k-1)</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 /// -
test/digraph_test.cc
r823 r824 442 442 checkGraphConArcList(G, 4); 443 443 444 std::vector<std::pair<int,int> > arcs; 445 arcs.push_back(std::make_pair(0,1)); 446 arcs.push_back(std::make_pair(0,2)); 447 arcs.push_back(std::make_pair(1,3)); 448 arcs.push_back(std::make_pair(1,2)); 449 arcs.push_back(std::make_pair(3,0)); 450 arcs.push_back(std::make_pair(3,3)); 451 arcs.push_back(std::make_pair(4,2)); 452 arcs.push_back(std::make_pair(4,3)); 453 arcs.push_back(std::make_pair(4,1)); 454 455 G.build(6, arcs.begin(), arcs.end()); 456 457 checkGraphNodeList(G, 6); 458 checkGraphArcList(G, 9); 459 460 checkGraphOutArcList(G, G.node(0), 2); 461 checkGraphOutArcList(G, G.node(1), 2); 462 checkGraphOutArcList(G, G.node(2), 0); 463 checkGraphOutArcList(G, G.node(3), 2); 464 checkGraphOutArcList(G, G.node(4), 3); 465 checkGraphOutArcList(G, G.node(5), 0); 466 467 checkGraphInArcList(G, G.node(0), 1); 468 checkGraphInArcList(G, G.node(1), 2); 469 checkGraphInArcList(G, G.node(2), 3); 470 checkGraphInArcList(G, G.node(3), 3); 471 checkGraphInArcList(G, G.node(4), 0); 472 checkGraphInArcList(G, G.node(5), 0); 473 474 checkGraphConArcList(G, 9); 475 444 476 checkNodeIds(G); 445 477 checkArcIds(G);
Note: See TracChangeset
for help on using the changeset viewer.