The majority of visitors to the Algorithms Repository come seeking implementations of algorithms which solve the problem they are interested in. To help guide the user among the relevant implementations for each problem, I have rated each implementation from 1 (lowest) to 10 (highest), with my rating reflecting my opinion of the chances that an applied user will find that this implementation solves their problem.
My ratings are completely subjective, and in many cases were based on a perusal of the documentation instead of first-hand experience with the codes. Therefore, I cannot defend the correctness of my ratings on any strong objective basis. Still, I believe that they have proven useful in pointing people to the most relevant implementation. Of the two linear programming packages, lpsolve and linprog, the higher rated code received over five times as many hits (1859 to 340) than the lower rated one. 3
Table 7 records the number of hits received for each implementation,
along with the problem for which it received the highest rating, as well its average rating
across all problems.
LEDA [#!MN-95!#] received almost as many hits (8806) as the two following implementations,
both associated with popular books [#!Sedgewick-92!#] (5339) and [#!GY-91!#] (4360).
The fourth most popular implementation was (surprisingly) Ranger [#!MS-93!#] (3514), an implementation of kd-trees.
This reflects the enormous popularity of nearest-neighbor searching in higher dimensions, as well as
the fact that I had not updated the list of implementations since the publication of the book
in November 1997.
Arya and Mount's recently released ANN (http://www.cs.umd.edu/
mount/ANN/)
would be a better choice.
Such maintanence on the site is now underway.
Note that these counts record the number of people who looked at the information page
associated with each implementation.
The actual number of ftps is unknown but presumably much lower.
Despite their shortcomings, I believe that these ratings provide a useful insight into the state of the art of combinatorial computing today. Hits per problem page measures the level of interest in a particular algorithmic problem. Program mass, the sum of the rankings of all implementations for a given problem, provides a measure of how much effort has been expended by the algorithm engineering community on the given problem. By comparing the ranks of each problem by program mass and the popularity, we can assess which problems are most (and least) in need of additional implementations.
Table 4 presents the results of such an analysis, showing the 20 most under (and over) implemented algorithmic problems. Kd-trees (rank 1) and suffix trees (rank 2) are the most needed data structure implementations, while the closely related problems of bin packing (rank 3) and knapsack (rank 4) are in the most need of algorithm implementations. There seems to be greater interest than activity in routing problems like Eulerian cycle/Chinese postman (rank 9) and traveling salesman (rank 14). On the other hand, traditional algorithm engineering topics like matching (rank 59) and network flow (rank 56) have resulted in a relative abundance of codes for these problems.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
