Changes between Version 2 and Version 3 of soc/2007/UserFriendlyGraphNewAlgorithms

Timestamp:

Jun 7, 2007, 12:03:46 AM (15 years ago)

Author:

Andrew Sutton

Comment:

--

soc/2007/UserFriendlyGraphNewAlgorithms

@@ -6 +6 @@
 
 (Andrew: True enough... I was just looking for a graph-as-matrix adpater for my rewrite of the Kevin Bacon example. Apparently, there's a little extra work to find an edge given a couple of vertices).
+
+'''Update (06/06/07)''' I committed some files that hosted the original implementations of several computed metrics - they aren't very pretty and pretty non-boost conformant. I spent a little time renovating the `degree_distribution` computation.
+
+== Degree Distributions ==
+This is actually a fairly trivial computation since we're just looking at the degree of each vertex and then building a histogram from it. As of right now, the signature basically looks like this:
+
+{{{
+template <class BidirectionalGraph, class RandomAccessContainer>
+void degree_distribution(BidirectionalGraph&, RandomAccessContainer&);
+}}}
+
+That should give some ideas about the concept requirements for the parameters. Specifically, the `BidirectionalGraph` is required since this method calls the `degree()` function to compute the distribution. We also required a `RandomAccessContainer` since the distribution is a histogram indexed by the degree of a vertex. Incidentally, the container is required to be `Resizable` (preferably effeciently).
+
+It might be worth noting that both `[un]directed_graph`s satisfy the requirements of this function. Only an `adjacency_list` templated over `directedS` may not be type compatible with the property.
+
+Interestingly, we can extend this relatively simple method to a set of 3 - `in_degree_distribution()` and `out_degree_distribution()` using a similar approach.
+
+On a side note... I lied just a little bit. The method actually returns the maximum degree in the distribution, but I've been considering changing it to return a pair containing both the minimum and the maximum. I figure, we're doing a little data gathering, lets grab some more information at essentially no cost.
 
 == Various Concept Notes ==