2006-05-27 Jarkko Hietaniemi * Still one bug hiding in articulation points: if the (randomly chosen) first vertex was a self-loop, an empty list was returned for articulation points. t/u_bo_ap.t now tests the test case from Brian Osborne 20 times to stress test more cases, and extra five tests testing self-loops and articulation points. * Release as 0.73. 2006-05-27 Jarkko Hietaniemi * Brian Osborne found a graph where articulation_points() ended up in an infinite loop. Resolved and the graph test case added as t/u_bo_ap.t. * Release as 0.72. 2006-05-22 Jarkko Hietaniemi * Tweak the pod-coverage.t so that it looks more like Test::Pod::Coverage documentation suggests in this case. * Fix the u_bo.t not to have a test class with a broken stringification method to avoid spurious warnings and failure (also do away with the use of Math::Complex to avoid problems because of different Math::Complex releases), and more even importantly fix the "next_root" logic in connected components not to advance to the next component if there is nothing to advance to. This seems to be prone to failure in 5.6.2, for some reason 5.8.8 works fine. * Test under Perl 5.6.2. * Force has_cycle() to return true/false, not the list of edges, reported by Casey Bergman. * Release as 0.71. 2006-05-21 Jarkko Hietaniemi * delete_vertex() from a refvertexed graph left an unnecessary reference to the referenced vertex hanging around in the graph, reported by Christoph Lamprecht. * Implement new 'super_component' option for connected_graph(), biconnected_graph(), and strongly_connected_graph(), to allow more complex ways of forming 'supercomponents' (and more customized ways of naming them). * Address rt.cpan.org #17159: "Nodes appear to unblessed after using articulation_points() - 2" (elaboration of rt.cpan.org #17108: "Nodes appear to unblessed after using articulation_points())" * Address rt.cpan.org #17160: "Nodes appear to unblessed after using connected_components()" * Address rt.cpan.org #17161: "Nodes appear to unblessed after using bridges()" * Address rt.cpan.org #17162: "Nodes appear to unblessed after using connected_graph()" * Address rt.cpan.org #17163, "SP_Dijkstra() is complaining" * Address rt.cpan.org #17164, "SP_Bellman_Ford() is complaining" * Address rt.cpan.org #17165, documentation error in SP_Bellman_Ford(). * Address rt.cpan.org #17405: "has_cycle with empty args should return FALSE" * Address rt.cpan.org: #17592: "articulation_points doesn't find all vertices" (didn't find all the vertices of non-connected graphs, only the vertices of the first (randomly chosen) connected subgraph) The rt.cpan.org cases 17159-17592 reported by Brian Obsorne. * Add Test::Pod and Test::Pod::Coverage tests. * Release as 0.70. 2005-12-06 Jarkko Hietaniemi * Add SP_Dijkstra() and SP_Bellman_Ford() to find the shortest path between any two vertices, the result is returned as the list of the vertices in the path. * In addition to the SPT per vertex result weight, also add a predecessor ('p') vertex attribute (the SP_Dijkstra() and SP_Bellman_Ford() unsurprisingly use this.) * Cache the SPT results for better speed. * Document that the SPT also allow a single argument as the starting (root) vertex. * Fix a bug in SPT_Dijkstra() which would ignore an "untrue" vertex (such as '0') if it was any other vertex than the root vertex (boolean context is dangerous, when you really mean "exists"). * For "components" (strongly, biconnected, and connected) graphs store the list of the original vertices as a vertex attribute 'subvertices' (so there is no need to do split(/\+/, ...) tricks), the list is stored as a array reference. * Release as 0.69. 2005-11-23 Jarkko Hietaniemi * SPT_Dijkstra() wasn't setting the vertex attributes of the result graph, noticed by Susan Tang, only the edge attributes were being set. SPT_Bellman_Ford() was doing neither! * There was an actual typo in the SPT test case from Sedgewick, a weight of 0.32 was mistyped as 0.22, this luckily didn't affect the result graph but it of course affected the resulting vertex 'weight' attributes. * Add tests to t/70_spt.t for the vertex and egde attributes of the SPT_Dijkstra() and SPT_Bellman_Ford() results. * Minor documentation tweaks, most importantly clarify the return value of the SPT_Dijkstra() and SPT_Bellman_Ford(). * Document that Perl 5.6.0 is the minimum (because of weak references) and also make Graph.pm require that (Makefile.PL was already doing the probing using Scalar::Util qw(weaken)). * Add an early test (02_trap.t) for catching the development-time-only setting of __DIE__ and __WARN__ handlers (as a result of this almost all the numbered tests were renumbered, so the diff is falsely gigantic). (If the handlers were mistakenly left turned on, a lot of later tests that checked the $@ got confusing failures.) * Release as 0.68. 2005-08-03 Jarkko Hietaniemi * The 0.66 add_edge_get_id() fix was not yet quite right, Tels found another problem with it. Now with another fix, and another test case (t/u_te_ae.t) * Documentation fixes from John P. Linderman. * Release as 0.67. 2005-07-20 Jarkko Hietaniemi * Fix [rt.cpan.org #13193] "Documentation error in set_edge_attributes" and [rt.cpan.org #13194] "Documentation error in set_edge_attributes" (duplicate report) * Fixes for problems listed in [rt.cpan.org #13195] "add_vertex_get_id/add_edge_get_id() return wrong result on first call" - add_edge_get_id() was returning an array reference instead of the id with the first call (the array reference was the ids of the vertices of the edge) - add_vertex_get_id() was even more broken (a multivertexed graph was using Graph::AdjacencyMap::Vertex for the vertex map, not Graph::AdjacencyMap::Heavy) - Added test t/u_te_me.t for the two above issues. - document in which order multiedge ids are returned (random) - require Data::Dumper only for deep_copy() and _dump() (not changes for two listed items, "check directly multiedged via a flag" and "remove returns for speed" because I have issues with speed hacks without actual measurements, and even if so would fear reduced maintainability) * Fix [rt.cpan.org #13352] "Dijkstra heap logic" Dijkstra was fine, the SPTHealElem cmp() routine was wrong in having no tie breakers in case the weights compared equal. Added test t/u_re_sd.t. * Release as 0.66. 2005-05-15 Jarkko Hietaniemi * Tests added to 64_ref.t to verify that using different kinds of blessed references as vertices works okay. Few bugs found by these tests squashed. * Release as 0.65. 2005-05-14 Jarkko Hietaniemi * Fix for [rt.cpan.org #12509] "Errors using objects as nodes", patch from the reporter of the bug, add t/u/bb_rv.t. * Fix for refvertexed isolated vertices not having overloaded cmp and graph string presentation failing because of that. * The s needed to be Bs. * Release as 0.64. 2005-04-16 Jarkko Hietaniemi * After setting a vertex attribute one could not delete non-attributed vertices, reported by Joseph Hamilton. * Inlining to speed up path_vertices() slightly. * Release as 0.63. 2005-04-10 Jarkko Hietaniemi * The documentation of add_weighted_vertices was wrong: the arguments are (v1, w1, v2, w2, ...) instead of (v1, v2, ..., w). * Made calling interfaces with an "options hash" like new() and random_graph() more robust, now bails out earlier instead of dieing mysteriously later with an "odd number of arguments" * Allow running under -d:DProf even when using random shuffling: workaround for List::Util::shuffle and -d:DProf not working together ([perl #32383]) by falling back to Fisher-Yates shuffle if (any use of) the -d: is detected. * Allow calling random_graph() also as a class method: Graph::random_graph(...) (the resulting graph will be a 'Graph'). * in_degree() and out_degree() (and therefore vertex_degree()) were one too low for self-loop vertices in undirected graphs (the self-loop edge was not counted). * Release as 0.62. 2005-03-27 Jarkko Hietaniemi * [rt.cpan.org #12023] from Macha Nikolski: deleting an attributed vertex left the graph in a state where has_vertex() returned correctly false but vertices() still wrongly returned the freshly deleted vertex. * A few missing "See":s added to the pod. * Release as 0.61. 2005-03-25 Jarkko Hietaniemi * Bug reported by Richard Ball: connected_component_by_index() and connected_component_by_vertex() were starting their indexing from one, not zero. * t/27_hyperedged.t was really testing for turning on hypervertexedness (the actual functionality was being tested correctly in t/32_hyperedge.t). * Release as 0.60. 2005-03-03 Jarkko Hietaniemi * deep_copy_graph() could not handle code references since Data::Dumper by default doesn't handle those. Now uses the Deparse option for 5.8.x and later. * The removed interfaces add_graph() and delete_graph() still had their documentation hanging around. * Release as 0.59. 2005-02-19 Jarkko Hietaniemi * Document that using attributes does have a slowing down effect on other graph operations [rt.cpan.org #11498] "Performance problem: edge attributes slow source_vertices" This is unlikely to get fixed any time soon, I am afraid, this is one of those working-as-designed-and-correctly-but- unfortunately-slow things. * Document that Graph 0.2xxx edges($v) is now edges_at($v) [rt.cpan.org #11494] * [rt.cpan.org #11543]: self-edges reported twice by edges_at(). * Declare/document that any attributes beginning with an underscore are reserved for the internal use of Graph. * Various inlining optimizations: should run 5-10% faster than the 0.57. * Release as 0.58. 2005-02-12 Jarkko Hietaniemi * Further 10% speedup on 'make test' on top of 0.56 by inlining various code paths related to finding edges, now 'make test' is cumulatively about 15% faster than the 0.55 release. The test case of [rt.cpan.org #11465] is about 10 times faster. * Release as 0.57. 2005-02-12 Jarkko Hietaniemi * Rewrite edges finding code (like edges_at()) to avoid a quadratic algorithm. Shame on me. Luckily this extremely slow path was not touched that often, but [rt.cpan.org #11465] shows one known bad case, source_vertices() for compat02 graphs. The removal of the slow path sped up 'make test' by about 5-10%. * Remove a voodoo keys() from vertices_at(). * Document stubs for Graph::Directed and Graph::Undirected. * Tiny documentation tweaks. * Release as 0.56. 2005-01-22 Jarkko Hietaniemi * Add unset_row(), get_row(), set_row(), and unset_row(), methods to Graph::BitMatrix and make it public (remove the "internal use only" warning from it). Add t/82_bitmatrix.t. * Add vertex_degree() as an alias for degree(). * One more alternative solution for spt.t from Koen. * I seem to have this drive to misspell people's names. Sorry, Koen. * Release as 0.55. 2005-01-16 Jarkko Hietaniemi * More bugs found in set_vertex_attribute(), fixed and tests added. (Basically the same failure pattern as with the [rt.cpan.org #9461]: after setting vertex attributes many of the 'structural' methods such as predecessors() often returned wrong results.) * More alternative solutions to spt.t, diameter.t, and dump.t, found by the PRNG of Koen van der Drift in Mac OS X 10.3.7, Perl 5.8.1. * Release as 0.54. 2005-01-14 Jarkko Hietaniemi * The #9461 was still there. But now we have a simple test case from Sebastian Nagel. The real culprit seemed to be a misapplied optimisation. * Release as 0.53. 2005-01-12 Jarkko Hietaniemi * Fix set_graph_attribute() documentation not to talk about $u, $v (noticed by Kurt Jaeger). * A mysterious failure fixed by a mysterious fix: under some circumstances it seems that an each() doesn't walk through all the key-value pairs, the workaround is to reset the each() iterator by a keys() call. Not simple test code, sadly, since the existing test code (see the case) is 13 kB and non-trivial. [rt.cpan.org #9461] * Add a safety guard against a missing Scalar::Util::weaken [rt.cpan.org #9481] * Release as 0.52. 2005-01-09 Jarkko Hietaniemi * Allow calling Makefile.PL with arguments other than --renum (which is for internal use only, and therefore undocumented). [rt.cpan.org #9481] * Remove the add_graph() and delete_graph() interfaces, sorry if you were already using them, but the current interface was very poor and the concept ill-planned. If you want to merge or remove edges and vertices between your graph, you can probably yourself implement the exactly right things to do. [rt.cpan.org #9493] * Document that one cannot assume Graphs are blessed hash references (and the likely error message one will get if one so assumes). [rt.cpan.org #9505] * Fix Andras' last name (sorry). * Merge duplicate documentation of find_a_cycle(). * Graph::AdjacencyMap::Base does not exist, fix Graph/AdjacencyMap.pm pod to comply. * Release as 0.51. 2005-01-01 Jarkko Hietaniemi * The 0.50. 2004-10-30 Jarkko Hietaniemi * Start wrapping up for the 0.50 release. * Start bothering beta testers.