Changes in / [779:c160bf9f18ef:778:a143f19f465b] in lemon-1.2
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/static_graph.h
r779 r778 198 198 node_first_out[node_num] = arc_num; 199 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()");239 node_first_out[node_num] = arc_num;240 }241 200 242 201 protected: … … 370 329 } 371 330 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 whole376 /// 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 be380 /// <tt>std::pair<int,int></tt>.381 /// Each arc must be specified by a pair of integer indices382 /// from the range <tt>[0..n-1]</tt>. <i>The pairs must be in a383 /// non-decreasing order with respect to their first values.</i>384 /// If the k-th pair in the list is <tt>(i,j)</tt>, then385 /// <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 /// \code393 /// 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 /// \endcode402 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 410 331 /// \brief Clear the digraph. 411 332 /// -
test/digraph_test.cc
r777 r776 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 476 444 checkNodeIds(G); 477 445 checkArcIds(G);
Note: See TracChangeset
for help on using the changeset viewer.