[Graph] suggestion: rename distance_zero() to distance_identity()
Many of the graph algorithms, e.g., dag_shortest_paths(), combine edge weights to form distances along a path through the graph. Although the default combine functor is based on addition, quite general ones may be used. The naming of the distance_zero() named argument is apparently based on the fact that zero (0) is the identity for addition. However, for more general combine methods, zero (0) may not be an identity. Indeed, the latter, i.e., identity, not the former, i.e., zero (0), is in fact the relevant property for this argument with respect to the algorithms. Consequently, it seems that this argument is misnamed. As part of the revision of the graph library, I suggest that this named parameter be relabeled to distance_identity(). That would capture its general meaning, regardless of the nature of the combine method. Cheers, Brook
As part of the revision of the graph library, I suggest that this named parameter be relabeled to distance_identity(). That would capture its general meaning, regardless of the nature of the combine method.
Brook, I mostly agree, but I think we can do better too. One of the reasons that it probably took the name distance_zero() is that there haven't been many motivating examples of non-additive combinations of distance (and hence identities). I'm wondering if it might not be worthwhile to build simple structures that provide the function types and constants for these algorithms rather than specifying them as distinct parameters. For the common case, these would simply default to the basic additive operations and identities but could be easily overridden. I'm sure there are some nice mathematical terms and properties that could describe these (monoids, semigroups, group, etc.). I'm not a mathematician, so I don't know for sure. Andrew Sutton asutton@cs.kent.edu
Andrew Sutton writes:
I mostly agree, but I think we can do better too. One of the reasons that it probably took the name distance_zero() is that there haven't been many motivating examples of non-additive combinations of distance (and hence identities).
I suspect that you are right in that regard as most mathematical algorithms are specified in terms of summations. However, I ran into the more general case when I tried to develop generic graph-based algorithms for probability models, which require products. There is one example included in the probability library I have developed, which is described at: http://biology.nmsu.edu/software/probability/
I'm wondering if it might not be worthwhile to build simple structures that provide the function types and constants for these algorithms rather than specifying them as distinct parameters. For the common case, these would simply default to the basic additive operations and identities but could be easily overridden.
By this I take it that you mean something along the lines of std:limits<> that defines various properties of the type? That would certainly better integrate the concepts and simplify the graph algorithm interfaces. Cheers, Brook
participants (2)
-
Andrew Sutton -
Brook Milligan