DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH PRINT BOOK
 
The C++ Graph Classes: A Tutorial - Graph(C++) and Graph_alg(C++)

Performance

Graphs have been optimized so that the member functions insert, remove, and contains perform in O(1) time. The remaining member functions, which iterate over Graph data, perform in O(n) time, where n is the number of objects in the iteration. Iteration is slower than iteration over a list or an array, but by a constant factor.

Extensive performance tests have been performed on the Graph Algorithms package. Most results are O(v + e), where v represents the number of Vertices and e represents the number of Edges in the Graph. The cycle results are worst case O(v+e) but in practice are much better than this, approximating constant time.


Next topic: Source Code for the Widget Manufacturing Example (Complete Listing)
Previous topic: Cycles

© 2005 The SCO Group, Inc. All rights reserved.
SCO OpenServer Release 6.0.0 -- 02 June 2005