12006-05-27 Jarkko Hietaniemi <jhi@iki.fi> 2 3 * Still one bug hiding in articulation points: if the 4 (randomly chosen) first vertex was a self-loop, an 5 empty list was returned for articulation points. 6 t/u_bo_ap.t now tests the test case from Brian 7 Osborne 20 times to stress test more cases, 8 and extra five tests testing self-loops and 9 articulation points. 10 * Release as 0.73. 11 122006-05-27 Jarkko Hietaniemi <jhi@iki.fi> 13 14 * Brian Osborne found a graph where articulation_points() 15 ended up in an infinite loop. Resolved and the graph 16 test case added as t/u_bo_ap.t. 17 * Release as 0.72. 18 192006-05-22 Jarkko Hietaniemi <jhi@iki.fi> 20 21 * Tweak the pod-coverage.t so that it looks more like 22 Test::Pod::Coverage documentation suggests in this case. 23 * Fix the u_bo.t not to have a test class with a broken 24 stringification method to avoid spurious warnings and 25 failure (also do away with the use of Math::Complex to 26 avoid problems because of different Math::Complex releases), 27 and more even importantly fix the "next_root" logic in 28 connected components not to advance to the next component 29 if there is nothing to advance to. This seems to be prone 30 to failure in 5.6.2, for some reason 5.8.8 works fine. 31 * Test under Perl 5.6.2. 32 * Force has_cycle() to return true/false, not the list of edges, 33 reported by Casey Bergman. 34 * Release as 0.71. 35 362006-05-21 Jarkko Hietaniemi <jhi@iki.fi> 37 38 * delete_vertex() from a refvertexed graph left an unnecessary 39 reference to the referenced vertex hanging around in the graph, 40 reported by Christoph Lamprecht. 41 * Implement new 'super_component' option for connected_graph(), 42 biconnected_graph(), and strongly_connected_graph(), to allow 43 more complex ways of forming 'supercomponents' (and more 44 customized ways of naming them). 45 * Address rt.cpan.org #17159: "Nodes appear to unblessed after 46 using articulation_points() - 2" (elaboration of rt.cpan.org 47 #17108: "Nodes appear to unblessed after using 48 articulation_points())" 49 * Address rt.cpan.org #17160: "Nodes appear to unblessed after 50 using connected_components()" 51 * Address rt.cpan.org #17161: "Nodes appear to unblessed after 52 using bridges()" 53 * Address rt.cpan.org #17162: "Nodes appear to unblessed after 54 using connected_graph()" 55 * Address rt.cpan.org #17163, "SP_Dijkstra() is complaining" 56 * Address rt.cpan.org #17164, "SP_Bellman_Ford() is complaining" 57 * Address rt.cpan.org #17165, documentation error in 58 SP_Bellman_Ford(). 59 * Address rt.cpan.org #17405: "has_cycle with empty args 60 should return FALSE" 61 * Address rt.cpan.org: #17592: "articulation_points doesn't 62 find all vertices" (didn't find all the vertices of non-connected 63 graphs, only the vertices of the first (randomly chosen) connected 64 subgraph) 65 The rt.cpan.org cases 17159-17592 reported by Brian Obsorne. 66 * Add Test::Pod and Test::Pod::Coverage tests. 67 * Release as 0.70. 68 692005-12-06 Jarkko Hietaniemi <jhi@iki.fi> 70 71 * Add SP_Dijkstra() and SP_Bellman_Ford() to find the shortest 72 path between any two vertices, the result is returned as 73 the list of the vertices in the path. 74 * In addition to the SPT per vertex result weight, also add 75 a predecessor ('p') vertex attribute (the SP_Dijkstra() and 76 SP_Bellman_Ford() unsurprisingly use this.) 77 * Cache the SPT results for better speed. 78 * Document that the SPT also allow a single argument 79 as the starting (root) vertex. 80 * Fix a bug in SPT_Dijkstra() which would ignore an "untrue" vertex 81 (such as '0') if it was any other vertex than the root vertex 82 (boolean context is dangerous, when you really mean "exists"). 83 * For "components" (strongly, biconnected, and connected) graphs 84 store the list of the original vertices as a vertex attribute 85 'subvertices' (so there is no need to do split(/\+/, ...) tricks), 86 the list is stored as a array reference. 87 * Release as 0.69. 88 892005-11-23 Jarkko Hietaniemi <jhi@iki.fi> 90 91 * SPT_Dijkstra() wasn't setting the vertex attributes of 92 the result graph, noticed by Susan Tang, only the edge 93 attributes were being set. SPT_Bellman_Ford() was doing neither! 94 * There was an actual typo in the SPT test case from Sedgewick, 95 a weight of 0.32 was mistyped as 0.22, this luckily didn't 96 affect the result graph but it of course affected the 97 resulting vertex 'weight' attributes. 98 * Add tests to t/70_spt.t for the vertex and egde attributes 99 of the SPT_Dijkstra() and SPT_Bellman_Ford() results. 100 * Minor documentation tweaks, most importantly clarify the 101 return value of the SPT_Dijkstra() and SPT_Bellman_Ford(). 102 * Document that Perl 5.6.0 is the minimum (because of weak references) 103 and also make Graph.pm require that (Makefile.PL was already doing 104 the probing using Scalar::Util qw(weaken)). 105 * Add an early test (02_trap.t) for catching the development-time-only 106 setting of __DIE__ and __WARN__ handlers (as a result of this almost 107 all the numbered tests were renumbered, so the diff is falsely 108 gigantic). (If the handlers were mistakenly left turned on, 109 a lot of later tests that checked the $@ got confusing failures.) 110 * Release as 0.68. 111 1122005-08-03 Jarkko Hietaniemi <jhi@iki.fi> 113 114 * The 0.66 add_edge_get_id() fix was not yet quite right, Tels 115 found another problem with it. Now with another fix, and 116 another test case (t/u_te_ae.t) 117 118 * Documentation fixes from John P. Linderman. 119 120 * Release as 0.67. 121 1222005-07-20 Jarkko Hietaniemi <jhi@iki.fi> 123 124 * Fix [rt.cpan.org #13193] "Documentation error in set_edge_attributes" 125 and [rt.cpan.org #13194] "Documentation error in set_edge_attributes" 126 (duplicate report) 127 128 * Fixes for problems listed in [rt.cpan.org #13195] 129 "add_vertex_get_id/add_edge_get_id() return wrong result on first call" 130 - add_edge_get_id() was returning an array reference instead 131 of the id with the first call (the array reference was the 132 ids of the vertices of the edge) 133 - add_vertex_get_id() was even more broken (a multivertexed 134 graph was using Graph::AdjacencyMap::Vertex for the vertex 135 map, not Graph::AdjacencyMap::Heavy) 136 - Added test t/u_te_me.t for the two above issues. 137 - document in which order multiedge ids are returned (random) 138 - require Data::Dumper only for deep_copy() and _dump() 139 (not changes for two listed items, "check directly multiedged 140 via a flag" and "remove returns for speed" because I have 141 issues with speed hacks without actual measurements, and even 142 if so would fear reduced maintainability) 143 144 * Fix [rt.cpan.org #13352] "Dijkstra heap logic" 145 Dijkstra was fine, the SPTHealElem cmp() routine was wrong 146 in having no tie breakers in case the weights compared equal. 147 Added test t/u_re_sd.t. 148 149 * Release as 0.66. 150 1512005-05-15 Jarkko Hietaniemi <jhi@iki.fi> 152 153 * Tests added to 64_ref.t to verify that using different kinds 154 of blessed references as vertices works okay. Few bugs found 155 by these tests squashed. 156 157 * Release as 0.65. 158 1592005-05-14 Jarkko Hietaniemi <jhi@iki.fi> 160 161 * Fix for [rt.cpan.org #12509] "Errors using objects as nodes", 162 patch from the reporter of the bug, add t/u/bb_rv.t. 163 164 * Fix for refvertexed isolated vertices not having overloaded cmp 165 and graph string presentation failing because of that. 166 167 * The <NOTE>s needed to be B<NOTE>s. 168 169 * Release as 0.64. 170 1712005-04-16 Jarkko Hietaniemi <jhi@iki.fi> 172 173 * After setting a vertex attribute one could not delete 174 non-attributed vertices, reported by Joseph Hamilton. 175 176 * Inlining to speed up path_vertices() slightly. 177 178 * Release as 0.63. 179 1802005-04-10 Jarkko Hietaniemi <jhi@iki.fi> 181 182 * The documentation of add_weighted_vertices was wrong: 183 the arguments are (v1, w1, v2, w2, ...) instead of (v1, v2, ..., w). 184 185 * Made calling interfaces with an "options hash" like new() 186 and random_graph() more robust, now bails out earlier instead 187 of dieing mysteriously later with an "odd number of arguments" 188 189 * Allow running under -d:DProf even when using random shuffling: 190 workaround for List::Util::shuffle and -d:DProf not working 191 together ([perl #32383]) by falling back to Fisher-Yates shuffle 192 if (any use of) the -d: is detected. 193 194 * Allow calling random_graph() also as a class method: 195 Graph::random_graph(...) (the resulting graph will be a 'Graph'). 196 197 * in_degree() and out_degree() (and therefore vertex_degree()) 198 were one too low for self-loop vertices in undirected graphs 199 (the self-loop edge was not counted). 200 201 * Release as 0.62. 202 2032005-03-27 Jarkko Hietaniemi <jhi@iki.fi> 204 205 * [rt.cpan.org #12023] from Macha Nikolski: 206 deleting an attributed vertex left the graph in a state 207 where has_vertex() returned correctly false but vertices() 208 still wrongly returned the freshly deleted vertex. 209 210 * A few missing "See":s added to the pod. 211 212 * Release as 0.61. 213 2142005-03-25 Jarkko Hietaniemi <jhi@iki.fi> 215 216 * Bug reported by Richard Ball: connected_component_by_index() 217 and connected_component_by_vertex() were starting their indexing 218 from one, not zero. 219 220 * t/27_hyperedged.t was really testing for turning on 221 hypervertexedness (the actual functionality was being 222 tested correctly in t/32_hyperedge.t). 223 224 * Release as 0.60. 225 2262005-03-03 Jarkko Hietaniemi <jhi@iki.fi> 227 228 * deep_copy_graph() could not handle code references since 229 Data::Dumper by default doesn't handle those. Now uses 230 the Deparse option for 5.8.x and later. 231 232 * The removed interfaces add_graph() and delete_graph() still 233 had their documentation hanging around. 234 235 * Release as 0.59. 236 2372005-02-19 Jarkko Hietaniemi <jhi@iki.fi> 238 239 * Document that using attributes does have a slowing down 240 effect on other graph operations 241 [rt.cpan.org #11498] 242 "Performance problem: edge attributes slow source_vertices" 243 This is unlikely to get fixed any time soon, I am afraid, 244 this is one of those working-as-designed-and-correctly-but- 245 unfortunately-slow things. 246 247 * Document that Graph 0.2xxx edges($v) is now edges_at($v) 248 [rt.cpan.org #11494] 249 250 * [rt.cpan.org #11543]: self-edges reported twice by edges_at(). 251 252 * Declare/document that any attributes beginning with an underscore 253 are reserved for the internal use of Graph. 254 255 * Various inlining optimizations: should run 5-10% faster 256 than the 0.57. 257 258 * Release as 0.58. 259 2602005-02-12 Jarkko Hietaniemi <jhi@iki.fi> 261 262 * Further 10% speedup on 'make test' on top of 0.56 by inlining 263 various code paths related to finding edges, now 'make test' 264 is cumulatively about 15% faster than the 0.55 release. 265 The test case of [rt.cpan.org #11465] is about 10 times faster. 266 267 * Release as 0.57. 268 2692005-02-12 Jarkko Hietaniemi <jhi@iki.fi> 270 271 * Rewrite edges finding code (like edges_at()) to avoid a 272 quadratic algorithm. Shame on me. Luckily this extremely 273 slow path was not touched that often, but [rt.cpan.org #11465] 274 shows one known bad case, source_vertices() for compat02 275 graphs. The removal of the slow path sped up 'make test' 276 by about 5-10%. 277 278 * Remove a voodoo keys() from vertices_at(). 279 280 * Document stubs for Graph::Directed and Graph::Undirected. 281 282 * Tiny documentation tweaks. 283 284 * Release as 0.56. 285 2862005-01-22 Jarkko Hietaniemi <jhi@iki.fi> 287 288 * Add unset_row(), get_row(), set_row(), and unset_row(), methods 289 to Graph::BitMatrix and make it public (remove the "internal use 290 only" warning from it). Add t/82_bitmatrix.t. 291 292 * Add vertex_degree() as an alias for degree(). 293 294 * One more alternative solution for spt.t from Koen. 295 296 * I seem to have this drive to misspell people's names. 297 Sorry, Koen. 298 299 * Release as 0.55. 300 3012005-01-16 Jarkko Hietaniemi <jhi@iki.fi> 302 303 * More bugs found in set_vertex_attribute(), fixed and tests 304 added. (Basically the same failure pattern as with the 305 [rt.cpan.org #9461]: after setting vertex attributes many of 306 the 'structural' methods such as predecessors() often returned 307 wrong results.) 308 309 * More alternative solutions to spt.t, diameter.t, and dump.t, 310 found by the PRNG of Koen van der Drift in Mac OS X 10.3.7, 311 Perl 5.8.1. 312 313 * Release as 0.54. 314 3152005-01-14 Jarkko Hietaniemi <jhi@iki.fi> 316 317 * The #9461 was still there. 318 But now we have a simple test case from Sebastian Nagel. 319 The real culprit seemed to be a misapplied optimisation. 320 321 * Release as 0.53. 322 3232005-01-12 Jarkko Hietaniemi <jhi@iki.fi> 324 325 * Fix set_graph_attribute() documentation not to talk about $u, $v 326 (noticed by Kurt Jaeger). 327 328 * A mysterious failure fixed by a mysterious fix: under some 329 circumstances it seems that an each() doesn't walk through 330 all the key-value pairs, the workaround is to reset the 331 each() iterator by a keys() call. Not simple test code, 332 sadly, since the existing test code (see the case) is 13 kB 333 and non-trivial. 334 [rt.cpan.org #9461] 335 336 * Add a safety guard against a missing Scalar::Util::weaken 337 [rt.cpan.org #9481] 338 339 * Release as 0.52. 340 3412005-01-09 Jarkko Hietaniemi <jhi@iki.fi> 342 343 * Allow calling Makefile.PL with arguments other than --renum 344 (which is for internal use only, and therefore undocumented). 345 [rt.cpan.org #9481] 346 347 * Remove the add_graph() and delete_graph() interfaces, sorry 348 if you were already using them, but the current interface was 349 very poor and the concept ill-planned. If you want to merge or 350 remove edges and vertices between your graph, you can probably 351 yourself implement the exactly right things to do. 352 [rt.cpan.org #9493] 353 354 * Document that one cannot assume Graphs are blessed hash references 355 (and the likely error message one will get if one so assumes). 356 [rt.cpan.org #9505] 357 358 * Fix Andras' last name (sorry). 359 360 * Merge duplicate documentation of find_a_cycle(). 361 362 * Graph::AdjacencyMap::Base does not exist, fix Graph/AdjacencyMap.pm 363 pod to comply. 364 365 * Release as 0.51. 366 3672005-01-01 Jarkko Hietaniemi <jhi@iki.fi> 368 369 * The 0.50. 370 3712004-10-30 Jarkko Hietaniemi <jhi@iki.fi> 372 373 * Start wrapping up for the 0.50 release. 374 375 * Start bothering beta testers. 376