Changes between Version 1 and Version 2 of soc/2007/UserFriendlyGraphs/Indexing

Timestamp:

Jun 25, 2007, 11:45:59 AM (15 years ago)

Author:

Andrew Sutton

Comment:

--

soc/2007/UserFriendlyGraphs/Indexing

@@ -55 +55 @@
 
 `renumber_vertex_indices(g)`
-  Renumber the indices in the vertex index map of ''g'' such that the index of each vertex is in the range [0, `num_vertices(g)`). Also, after calling this function, `max_vertex_index(g)` == `num_vertices(g`).
+  Renumber the indices in the vertex index map of ''g'' such that the index of each vertex is in the range [0, `num_vertices(g)`). Also, after calling this function, `max_vertex_index(g)` == `num_vertices(g)`.
 
 Implementing these three functions will allow more flexible algorithms for mutable graphs. Specifically, this model relaxes many of the constraints that vertices have indices in the range [0, num_vertices(g)). Instead, algorithms can require indices in the range \[0, max_vertex_index(g)).
@@ -70 +70 @@
 
 This proposal is implemented in this form for the `undirected_graph` and `directed_graph` classes. Comments are welcome.
+
+=== Additional Functionality ===
+One possible criticism of this approach is the absence of automated index management, which only needs to be implemented for the `remove_vertex(g)` method. One solution, might be to simply have that function call `renumber_vertex_indices(g)`, but that's probably overkill since it renumbers ''all'' vertices. If we think about it long enough, we'll eventually realize that we only need to renumber vertices that are ''after'' the removed vertex. So we could implement the `remove_vertex(g)` method to do that, effectively cutting the average cost of removal in half (assuming that on average removals tend toward the middle of the list). Clearly, worst case is removing the first vertex which runs in ''theta''(n) time. Best case is removal of the back vertex which is simply constant.
+
+The obvious downside of the previous solution is that it hamstrings programs that performa a number of sequential vertex removals without needing to renumber indices - which is a pretty bad side-effect, but is still a useful function. As such, we could introduce an additional function:
+
+`remove_vertex_and_renumber_indices(v, g)`
+  Removes the target vertex and renumbers all indices that follow it, in the order in which vertices were added.
+
+The `remove_vertex_and_renumber_indices(g)` method will run in ''theta''(n) time for `setS`, `multisetS`, and `hashS` selected vertex storage (if implemented). Unlike lists and vectors, the order of insertion is lost with these corresponding data sets, meaning that we can't cut the time in half as with above.
+
+=== Other Side-Effects of Indexing ===
+It should be probably be noted that any solution - even a fully automated index management suite - will still invalidate all exterior properties defined before the removal of a vertex. Once an index has been invalidated, so too are properties stored at those indices in exterior vectors. Exterior properties will need to be regenerated, which is probably a non-trivial task.
+