Changeset 826:c160bf9f18ef in lemon for lemon/static_graph.h
 Timestamp:
 11/05/09 10:01:02 (11 years ago)
 Branch:
 default
 Parents:
 825:a143f19f465b (diff), 824:5764dd9b6e18 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/static_graph.h
r824 r826 93 93 void nextIn(Arc& e) const { e.id = arc_next_in[e.id]; } 94 94 95 int id(const Node& n) const{ return n.id; }96 Node nodeFromId(int id) const{ return Node(id); }95 static int id(const Node& n) { return n.id; } 96 static Node nodeFromId(int id) { return Node(id); } 97 97 int maxNodeId() const { return node_num  1; } 98 98 99 int id(const Arc& e) const{ return e.id; }100 Arc arcFromId(int id) const{ return Arc(id); }99 static int id(const Arc& e) { return e.id; } 100 static Arc arcFromId(int id) { return Arc(id); } 101 101 int maxArcId() const { return arc_num  1; } 102 102 … … 310 310 /// This function returns the node with the given index. 311 311 /// \sa index() 312 Node node(int ix) const{ return Parent::nodeFromId(ix); }312 static Node node(int ix) { return Parent::nodeFromId(ix); } 313 313 314 314 /// \brief The arc with the given index. … … 316 316 /// This function returns the arc with the given index. 317 317 /// \sa index() 318 Arc arc(int ix) const{ return Parent::arcFromId(ix); }318 static Arc arc(int ix) { return Parent::arcFromId(ix); } 319 319 320 320 /// \brief The index of the given node. … … 322 322 /// This function returns the index of the the given node. 323 323 /// \sa node() 324 int index(Node node) const{ return Parent::id(node); }324 static int index(Node node) { return Parent::id(node); } 325 325 326 326 /// \brief The index of the given arc. … … 328 328 /// This function returns the index of the the given arc. 329 329 /// \sa arc() 330 int index(Arc arc) const{ return Parent::id(arc); }330 static int index(Arc arc) { return Parent::id(arc); } 331 331 332 332 /// \brief Number of nodes. 
lemon/static_graph.h
r825 r826 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.