Debian Codegraph @

Changes

raw
1 0.9735 2025-03-27
2 - better connectedness docs (#36 #37) - thanks @gwselke
3
4 0.9734 2025-03-01
5 - add connected_subgraphs (#35) - thanks @merkys
6
7 0.9733 2025-01-12
8 - added max_cliques (#33,#34) - thanks @choroba
9 - restore 0.9716 behaviour of random_graph (#32) - thanks @kester-habermann for report
10
11 0.9732 2024-09-02
12 - delete_vertex_by_id now deletes edges if vertex multiness to 0
13 - add filter_{vertic,edg}es
14 - {un,}directed_copy no longer use caching mechanism so can mutate copies
15
16 0.9731 2024-08-24
17 - add add_{edges,path}_by_id
18 - fix calling "new" on Graph::Undirected object
19 - make {,{un,}directed_}copy preserve multi{edg,vertex}ed
20 - add {un,}directed_copy_attributes
21
22 0.9730 2024-08-22
23 - add get_edge_attribute_all
24 - make SP_Dijkstra and SP_Bellman_Ford work with multiedged
25
26 0.9729 2024-06-28
27 - add is_planar (#31) - thanks @merkys
28
29 0.9728 2024-06-25
30 - add is_bipartite (#30) - thanks @merkys
31
32 0.9727 2023-06-25
33 - fix biconnectivity to work with refvertexed (#29) - thanks @merkys for report
34
35 0.9726 2023-02-11
36 - fix subgraph of undirected (#28) - thanks @merkys for report
37
38 0.9725 2021-10-10
39 - fix refvertexed which was stringifying not using ref address - thanks @merkys for report
40
41 0.9724 2021-09-13
42 - make deep_copy not interfere with $. - thanks @merkys for report
43
44 0.9723 2021-09-01
45 - doc fixes - thanks @xsawyerx
46 - fix problem with deep_copy with vertices that are refs - thanks @merkys for report
47
48 0.9722 2021-07-04
49 - fix neighbours et al not returning count in scalar context - thanks @merkys for report
50
51 0.9721 2021-04-18
52 - fix BitMatrix and AdjacencyMatrix problems - thanks @dod38fr for report
53
54 0.9720 2021-03-25
55 - better fix - no mutate inputs
56
57 0.9719 2021-03-25
58 - fix all_paths infinite loop on cycle - thanks @tobez for report
59
60 0.9718 2021-03-13
61 - remove doc of deleted average_degree method - thanks @lindleyw for report
62
63 0.9717 2021-01-27
64 - bulk APIs for UnionFind
65 - add unionfind config option for util/grand.pl (benchmark-ish script)
66 - GRAPH_ALLOW_RECURSION env var to turn off recursion protection
67 - "Light" edge-map now uses bit-vectors -> smaller storage
68 - directed hypergraphs
69 - fix same_biconnected_components logic when given >2 vertices
70
71 0.9716 2021-01-01
72 - use Set::Object
73 - {neighbours,successors,predecessors,reachable}_by_radius
74
75 0.9715 2020-12-31
76 - fix AdjacencyMap::Light attributes so delete when path deleted
77 - fix as_hashes undirected edges: now both directions
78 - subgraph_by_radius take multiple vertices
79
80 0.9714 2020-12-25
81 - remove "omni*" - hypergraphs are simply directed or undirected
82 - as_hashes works with undirected hypergraphs
83 - add_edge with != 2 vertices only for undirected hypergraph
84 - any_edge
85 - delete_*_attributes_by_id (and deleting last attribute) now don't destroy that entity
86 - AdjacencyMap::Light can have attributes, so no slowdown if use (eg APSP)
87
88 0.9713 2020-12-19
89 - fix edges_at on self-edges in scalar context
90 - fix refvertexed_stringified predicate
91 - remove "hypervertices": a collection of n vertices is a hyperedge
92 - AdjacencyMap.get_paths_by_ids
93 - transitive_closure et al no longer re-bless objects to Graph
94 - AdjacencyMap.get_ids_by_paths
95 - no more uniqedged configurability
96 - BitMatrix transpose option
97 - Transitive closure records path successor, not predecessor. Method name and docs updated.
98
99 0.9712 2020-12-05
100 - bug-fix: set_edge_attribute_by_id add_edge_by_id if not exist
101 - connected_component_by_index behaves same with/without unionfind
102 - AdjacencyMatrix handle multiedged
103 - reduce redundant sorting for _UNORD, fix AdjacencyMap::Vertex with ID 0
104 - AdjacencyMap.stringify
105 - allow constructor args to override "prototype" object
106 - fix docs for TransitiveClosure to correctly say path_vertices default true
107 - AdjacencyMatrix now always creates adjacency matrix (clue in name)
108 - remove compat02 features
109 - drop untested scalar-context Traversal.postorder mutation behaviour
110 - much more lazy-loading of modules
111 - set_vertex_attribute_by_id now works on hypervertexed
112 - internal AdjacencyMap uses array not hash for mapping index to path
113 - successors/predecessors/rename_path work right with multivertex
114 - AdjacencyMap array -> stable vertices ordering, TCM performance benefit
115 - TransitiveClosure etc handle multiedged
116 - all_paths ignore self-loops
117
118 0.9711 2020-11-27
119 - ingest handle multivertexed, multiedged right
120
121 0.9710 2020-11-27
122 - all_paths method
123 - as_hashes handle multivertexed, multiedged right
124
125 0.9709 2020-11-22
126 - add path_count option to TransitiveClosure
127 - get_{edge,vertex}_attributes undef if no such entity, in list context
128 - as_hashes method
129 - ingest method
130
131 0.9708 2020-11-06
132 - update metadata for Test::More version dep
133 - stringify hypervertices right
134 - add rename_vertex, rename_vertices
135
136 0.9707 2020-10-31
137 - can't use Safe, ergo Storable, on 5.8
138
139 0.9706 2020-10-20
140 - metadata list test-deps as not runtime
141
142 0.9705 2020-10-20
143 - document clustering_coefficient return empty list on no vertices - RT#114094
144 - apply lazy-load patch from Stephen Loyd - RT#123236
145 - depend on Heap 0.80 instead of local fork. Heap::Elem is really an interface not superclass.
146 - fix uninitialised value warning in SP_Dijkstra - RT#118539
147 - fix complement losing vertices on unconnected graphs - RT#115366
148 - fix average_path_length when two vertices given - RT#120611
149 - switch to GitHub issues rather than RT
150 - fix all_successors with non-truthy names - fix #5
151 - add Graph::Matrix->stringify to help debug
152 - fix APSP_Floyd_Warshall logic error when subpaths totalled 0 - fix #3
153 - typo fix - thanks @jkeenan (#6)
154 - Added "use strict; use warnings;", etc - thanks @manwar (closes #2)
155
156 0.9704 2015-10-07 Jarkko Hietaniemi <[email protected]>
157 - rt.cpan.org 107567: edges() missing on undirected multiedged graph:
158 was broken in 0.96, had been fixed somewhere there and here,
159 added the test case
160 - rt.cpan.org 107600: no modify Storable $VERSION
161
162 0.9703 2015-09-29 Jarkko Hietaniemi <[email protected]>
163 - document (at user level) the openbsd random problem
164 - using the 5.22+ Inf was done the wrong way:
165 https://github.com/neilbowers/Graph/issues/1
166
167 0.9702 2015-09-28 Jarkko Hietaniemi <[email protected]>
168 - rt.cpan.org 107394 $Storable::VERSION may contain underscores
169 - follow-up to rt.cpan.org 104687: more docs, fixes, and tests for
170 diameter/radius/shortest_path/center_vertices/vertex_eccentricity
171 for corner cases like empty graph, single-vertex graphs, and
172 in general unconnected graphs
173 - for perl 5.22 or later one should be able to use Inf for Infinity
174 - openbsd before perl 5.20 had nondeterministic rand()
175
176 0.97 2015-09-22 Jarkko Hietaniemi <[email protected]>
177 - rt.cpan.org 104687 diameter and centre of a one vertex graph
178 - rt.cpan.org 107195 [PATCH] fix POD: add missing NAME header
179 - rt.cpan.org 107194 [PATCH] fix a spelling mistake
180 - rt.cpan.org #94046 Loading graph produces a warning with Perl 5.16.3
181 - rt.cpan.org 62626 Graph::TransitiveClosure::Matrix contradictory wrt reflexive
182 - rt.cpan.org 71793 Problem with APSP and default weight 1
183 - rt.cpan.org 79143 Graph scalar context override causes problems
184 - rt.cpan.org 92427 Graph::delete_vertex should not use _edges_at (in all cases)
185 - rt.cpan.org 85238 bug in edges() method?
186 - rt.cpan.org 93278 SPT_Dijkstra sometimes returns a wrong answer
187 - rt.cpan.org 78465 find_a_cycle and has_cycle are broken
188 - rt.cpan.org 92204 (longest path is not calculated correctly in this case)
189 - rt.cpan.org 65497 induced subgraph method
190 - plus various doc and code nits found while looking at the above
191
192 0.96_01 2014-03-09 @NEILB
193 - Taken over maintenance from JHI
194 - Specified min perl version 5.6.0
195 - Tweaked COPYRIGHT and LICENSE in pod to match usual form
196 - Added "use warnings", but that results in loads of warnings
197 about functions redefined. So added "no warnings 'redefine';".
198 Have to come back and work that one out!
199 - Set all VERSION's to 0.96_01. I suspect a switch to Dist::Zilla
200 might be coming soon...
201 - Updated README to acknowledge change in maintainer
202 - Reformatted as per CPAN::Changes::Spec
203
204 0.96 2013-05-24 Jarkko Hietaniemi <[email protected]>
205 - Mop-up release for 0.95. Still is and will be unsupported.
206
207 0.95 2013-05-23 Jarkko Hietaniemi <[email protected]>
208
209 - Address rt.cpan.org #85449:
210 "Graph-0.94 tests fail under perl 5.18.0"
211
212 - Address rt.cpan.org #82324:
213 "Test failures due to hash randomisation in perl 5.17.6"
214
215 The two above fixes were the same: the biconnectedness
216 code was rewritten from scratch. The new code behaves
217 differently (but I believe more correctly) on certain
218 edge cases, in general it will generate more biconnected
219 components and bridges, for example for "a=b=c" it will
220 now return the same two biconnected components and bridges
221 (cut edges), namely "a=b" and "b=c", the "b" of course being
222 the articulation point (cut vertex).
223
224 - Address rt.cpan.org #67213:
225 "[PATCH] pod fixes"
226
227 - Remove the t/u_bo.t and t/u_bo1.t since they die in 5.18 due
228 to some strange failure, looks unrelated to Graph as such,
229 probably some fix/change made by newer Perls.
230
231
232 0.94 2010-03-13 Jarkko Hietaniemi <[email protected]>
233
234 - Address rt.cpan.org #43580:
235 "Reversed logic on overload::StrVal() in AdjacencyMap::Vertex::__set_path"
236 Had to add a new option, refvertexed_stringified.
237
238 - Address rt.cpan.org #50210:
239 "Graph-0.91: bug in unionfind parameter"
240
241 One cannot delete from a unionfind graph: now enforcing that.
242
243 - Address rt.cpan.org #48090:
244 "all_reachable on directed $g->add_edges(['a','b'],['b','a'])"
245
246 Now if there are loops, all_reachable() will include
247 the initial vertices themselves. Also all_neighbors()
248 had some problems in certain cases, fixed those too.
249
250 - Address rt.cpan.org #50210:
251 "Graph-0.91: bug in unionfind parameter"
252
253 One cannot delete edges or vertices from a unionfind
254 graph: now enforce that in code.
255
256 - Address rt.pcan.org #42549: "stron"
257
258 Document that strongly connected components will include
259 isolated and sink and source vertices.
260
261
262 0.93 2010-03-07 Jarkko Hietaniemi <[email protected]>
263
264 - Revert the SPTHeapElem.pm change made in Graph 0.92,
265 installing Heap 0.80 broke Graph. Better be conservative.
266
267
268 0.92 2010-03-03 Jarkko Hietaniemi <[email protected]>
269
270 - Address rt.cpan.org #55912 "Broken links in the documentation"
271
272 - Address rt.cpan.org #55196 "Heap 0.80 compatibility fix"
273
274 - Add copyright and clearer license statement.
275
276
277 0.91 2009-01-16 Jarkko Hietaniemi <[email protected]>
278
279 - Minor documentation cleanups.
280
281 - Add 'use strict;' to lib/Graph/TransitiveClosure.pm.
282
283 - Modernize the META.yml.
284
285
286 0.90 2008-12-29 Jarkko Hietaniemi <[email protected]>
287
288 - Storable deparse of coderefs for deep_copy() does not
289 work at all with 5.6.2: if modern enough Storable
290 and B::Deparse are not available, fall back to
291 the previous version which used Data::Dumper.
292
293 0.89 2008-12-27 Jarkko Hietaniemi <[email protected]>
294
295 - Some PAUSE upload problem with 0.88, retrying.
296
297
298 0.88 2008-12-26 Jarkko Hietaniemi <[email protected]>
299
300 - The 0.87 forgot to specify the Storable (and Safe,
301 used in the deserialization step of deep_copy)
302 prerequirement(s) in Makefile.PL.
303
304
305 0.87 2008-12-26 Jarkko Hietaniemi <[email protected]>
306
307 - Addressed a performance problem in successors()
308 and predecessors(), reported by Jonathan Moore.
309
310 - Reimplement deep_copy() by using Storable
311 freeze() and thaw() instead of Data::Dumper,
312 inspired by Jonathan Moore. Probably now safer
313 and faster, but Storable is now a prerequirement.
314
315
316 0.86 2008-11-27 Jarkko Hietaniemi <[email protected]>
317
318 - Addressed a performance problem in connected_components()
319 for 1000+ vertex graphs, reported by David Grobe.
320 Should in general speed up graph traversal.
321
322
323 0.85 2008-11-27 Jarkko Hietaniemi <[email protected]>
324
325 - Address rt.cpan.org #31608 "Graph::Undirected, unionfind and
326 connected_component"
327
328 - Address rt.cpan.org #34377 "recursive successors and predecessors"
329 (added all_successors/all_predecessors/all_neighbours/all_reachable)
330
331 - Address rt.cpan.org #39444 "inconsistent return value"
332 (make add_edges and add_vertices to always return the graph)
333
334 - Address rt.cpan.org #39614 "copy should retain more attributes"
335 (now copies also refvertexed/hypervertexed/countvertexed/
336 multivertexed/hyperedged/countedged/multiedged/omniedged)
337
338 - Address rt.cpan.org #39805 "UnionFind: Repeated adds clobbers
339 graph component information"
340
341 - Address rt.cpan.org #41190 "add_edge_by_id on multigraph
342 malfunctioning"
343
344 - Added betweenness(), clustering_coefficient(), and
345 subgraph_by_radius(), contributed by Matt Spear.
346
347
348 0.84 2007-08-13 Jarkko Hietaniemi <[email protected]>
349
350 - Tels found one more attributed edge problem.
351
352
353 0.83 2007-08-12 Jarkko Hietaniemi <[email protected]>
354
355 - One test in 73_diameter.t had too many possible answers,
356 dependent on the hash ordering, removed the test.
357
358
359 0.82 2007-08-11 Jarkko Hietaniemi <[email protected]>
360
361 - Since Heap 0.80 broke Graph, as a stop-gap measure
362 I will include the Heap::Elem and Heap::Fibonacci
363 of Heap 0.71, renamed as 'Heap071', addresses rt.cpan.org
364 #26943: "Heap 0.80 breaks Graph", and numerous bug reports
365 by email
366
367 - Address rt.cpan.org #27840: "add-edge_attributes() on
368 undirected graph wrongly depends on node order", from Tels
369
370 - Address rt.cpan.org #27959: "radius method incorrect",
371 code and test case from ROSULEK.
372
373
374 0.81 2007-01-21 Jarkko Hietaniemi <[email protected]>
375
376 - Address rt.cpan.org #24417: "next_successor unavailable in
377 Traversal (PATCH)", from Ted Carnahan.
378
379 - Small pod tweaks.
380
381 - Minor internal cleanup for the caching code.
382
383
384 0.80 2006-09-10 Jarkko Hietaniemi <[email protected]>
385
386 - SP_Bellman_Ford() used actually SPT_Dijkstra(), not
387 SPT_Bellman_Ford(), noticed by "aramos". This changed
388 some regression test results a bit.
389
390 - The NAME line of Graph::Undirected said "directed graphs",
391 noticed by "Ruslan", the first one to notice this in two
392 years, including the author yours truly...
393
394 - Add Scalar::Util to the prereqs listed in Makefile.PL since
395 one of the tests uses refaddr, shouldn't be a problem because
396 List::Util already is a prereq.
397
398 - Fix few broken intra-pod links.
399
400
401 0.79 2006-08-06 Jarkko Hietaniemi <[email protected]>
402
403 - The u_bo_ap1.t wasn't really testing the same for 20 times,
404 which meant that one bug was waiting for Koen van der Drift.
405 (If one start vertex of biconnectivity search was a self-loop,
406 an empty list of articulation points was returned.)
407
408 - Add a new API family: $g->..._clear_cache(), which allows
409 one to forget a cached value such as biconnectivity().
410 Without clearing the cache once the result has been computed
411 it stays the same (until the graph is modified, of course).
412 If the cache is cleared, (pseudo)randomness is applied again,
413 and the algorithm results may become different.
414
415
416 0.78 2006-07-16 Jarkko Hietaniemi <[email protected]>
417
418 - Address rt.cpan.org #20476: "SPT_Bellman_Ford does not respect
419 refvertexed" - now fixed, and SPT_Dijkstra() had the same problem.
420
421
422 0.77 2006-07-08 Jarkko Hietaniemi <[email protected]>
423
424 - Address rt.cpan.org #20185: "problem with SPT_Bellman_Ford",
425 SPT_Bellman_Ford() was broken for undirected graphs
426 (they were handled as directed ones, therefore missing vertices).
427
428 - weakly_connected_component_by_vertex() usage example
429 was wrong, was using weakly_connected_component(),
430 noted by 'yanick' in annocpan.org.
431
432 - Implement and document the saving of the SPT_Dijkstra()
433 and SPT_Bellman_Ford() start vertices.
434
435 - Document add_edges() alternative API.
436
437 - Aerate the Changes by adding empty lines between the * items.
438
439
440 0.76 2006-06-28 Jarkko Hietaniemi <[email protected]>
441
442 - Problem found by Xiaoli Zheng in diameter(): adding vertices
443 did not change diameter, this was due to a deeper bug where
444 the transitive closure matrix was being cached wrong:
445 sometimes saved too long, sometimes recomputed too often.
446 Enhanced 73_diameter.t to detect this.
447
448 - Problem found by Andree Toonk and Ronald van der Pol:
449 SP_Dijkstra() tried too hard to find a path between
450 vertices even if there was none - and returned rubbish.
451 Added t/u_at3.t to detect this.
452
453 - Address rt.cpan.org #20021: "bridges() sometimes returns
454 empty list when isolated vertices present". biconnectivity()
455 did not work right if isolated vertices were picked as roots,
456 it either hung or returned empty. Added t/u_bill.t to detect this.
457
458 - Document that add_vertex() is often unnecessary.
459
460 - Directed.pm and Undirected.pm were missing "use strict".
461
462
463 0.75 2006-06-09 Jarkko Hietaniemi <[email protected]>
464
465 - Had accidentally removed Digest::MD5 from the Makefile.PL
466 prereq list, found by Anton Berezin (using Perl 5.6.2, which
467 doesn't include that), solved by removing the dependency
468 to Digest::MD5.
469
470 - Speeded up repeated longest/shortest paths computations
471 by using a cached (Floyd-Warshall) transitive closure.
472
473 - Implemented:
474 - graph radius
475 - graph center (vertices)
476 - vertex eccentricity
477
478
479 0.74 2006-05-31 Jarkko Hietaniemi <[email protected]>
480
481 - Bug in SP_Dijkstra() found by Andree Toonk and Ronald van der Pol.
482 The edge weights of the Dijkstra shortest paths graph were
483 not cumulative (if the whole graph is a-b = 1 and b-c = 2,
484 a-c should be 3), which caused the SP_Dijsktra() results
485 sometimes to be nonsense. Two test cases, one of them rather
486 large (about 5000 edges).
487
488 - Bugs when using references as vertices in bridges()
489 and (Traversal) seen() found by Brian Osborne.
490
491 - Added another articulation_points() test by Brian Obsorne.
492
493 - Explicitly disallow adding undef as a vertex.
494
495
496 0.73 2006-05-27 Jarkko Hietaniemi <[email protected]>
497
498 - Still one bug hiding in articulation points: if the
499 (randomly chosen) first vertex was a self-loop, an
500 empty list was returned for articulation points.
501 t/u_bo_ap.t now tests the test case from Brian
502 Osborne 20 times to stress test more cases,
503 and extra five tests testing self-loops and
504 articulation points.
505
506
507 0.72 2006-05-27 Jarkko Hietaniemi <[email protected]>
508
509 - Brian Osborne found a graph where articulation_points()
510 ended up in an infinite loop. Resolved and the graph
511 test case added as t/u_bo_ap.t.
512
513
514 0.71 2006-05-22 Jarkko Hietaniemi <[email protected]>
515
516 - Tweak the pod-coverage.t so that it looks more like
517 Test::Pod::Coverage documentation suggests in this case.
518
519 - Fix the u_bo.t not to have a test class with a broken
520 stringification method to avoid spurious warnings and
521 failure (also do away with the use of Math::Complex to
522 avoid problems because of different Math::Complex releases),
523 and more even importantly fix the "next_root" logic in
524 connected components not to advance to the next component
525 if there is nothing to advance to. This seems to be prone
526 to failure in 5.6.2, for some reason 5.8.8 works fine.
527
528 - Test under Perl 5.6.2.
529
530 - Force has_cycle() to return true/false, not the list of edges,
531 reported by Casey Bergman.
532
533
534 0.70 2006-05-21 Jarkko Hietaniemi <[email protected]>
535
536 - delete_vertex() from a refvertexed graph left an unnecessary
537 reference to the referenced vertex hanging around in the graph,
538 reported by Christoph Lamprecht.
539
540 - Implement new 'super_component' option for connected_graph(),
541 biconnected_graph(), and strongly_connected_graph(), to allow
542 more complex ways of forming 'supercomponents' (and more
543 customized ways of naming them).
544
545 - Address rt.cpan.org #17159: "Nodes appear to unblessed after
546 using articulation_points() - 2" (elaboration of rt.cpan.org
547 #17108: "Nodes appear to unblessed after using
548 articulation_points())"
549
550 - Address rt.cpan.org #17160: "Nodes appear to unblessed after
551 using connected_components()"
552
553 - Address rt.cpan.org #17161: "Nodes appear to unblessed after
554 using bridges()"
555
556 - Address rt.cpan.org #17162: "Nodes appear to unblessed after
557 using connected_graph()"
558
559 - Address rt.cpan.org #17163, "SP_Dijkstra() is complaining"
560
561 - Address rt.cpan.org #17164, "SP_Bellman_Ford() is complaining"
562
563 - Address rt.cpan.org #17165, documentation error in
564 SP_Bellman_Ford().
565
566 - Address rt.cpan.org #17405: "has_cycle with empty args
567 should return FALSE"
568
569 - Address rt.cpan.org: #17592: "articulation_points doesn't
570 find all vertices" (didn't find all the vertices of non-connected
571 graphs, only the vertices of the first (randomly chosen) connected
572 subgraph)
573
574 The rt.cpan.org cases 17159-17592 reported by Brian Obsorne.
575
576 - Add Test::Pod and Test::Pod::Coverage tests.
577
578
579 0.69 2005-12-06 Jarkko Hietaniemi <[email protected]>
580
581 - Add SP_Dijkstra() and SP_Bellman_Ford() to find the shortest
582 path between any two vertices, the result is returned as
583 the list of the vertices in the path.
584
585 - In addition to the SPT per vertex result weight, also add
586 a predecessor ('p') vertex attribute (the SP_Dijkstra() and
587 SP_Bellman_Ford() unsurprisingly use this.)
588
589 - Cache the SPT results for better speed.
590
591 - Document that the SPT also allow a single argument
592 as the starting (root) vertex.
593
594 - Fix a bug in SPT_Dijkstra() which would ignore an "untrue" vertex
595 (such as '0') if it was any other vertex than the root vertex
596 (boolean context is dangerous, when you really mean "exists").
597
598 - For "components" (strongly, biconnected, and connected) graphs
599 store the list of the original vertices as a vertex attribute
600 'subvertices' (so there is no need to do split(/\+/, ...) tricks),
601 the list is stored as a array reference.
602
603
604 0.68 2005-11-23 Jarkko Hietaniemi <[email protected]>
605
606 - SPT_Dijkstra() wasn't setting the vertex attributes of
607 the result graph, noticed by Susan Tang, only the edge
608 attributes were being set. SPT_Bellman_Ford() was doing neither!
609
610 - There was an actual typo in the SPT test case from Sedgewick,
611 a weight of 0.32 was mistyped as 0.22, this luckily didn't
612 affect the result graph but it of course affected the
613 resulting vertex 'weight' attributes.
614
615 - Add tests to t/70_spt.t for the vertex and edge attributes
616 of the SPT_Dijkstra() and SPT_Bellman_Ford() results.
617
618 - Minor documentation tweaks, most importantly clarify the
619 return value of the SPT_Dijkstra() and SPT_Bellman_Ford().
620
621 - Document that Perl 5.6.0 is the minimum (because of weak references)
622 and also make Graph.pm require that (Makefile.PL was already doing
623 the probing using Scalar::Util qw(weaken)).
624
625 - Add an early test (02_trap.t) for catching the development-time-only
626 setting of __DIE__ and __WARN__ handlers (as a result of this almost
627 all the numbered tests were renumbered, so the diff is falsely
628 gigantic). (If the handlers were mistakenly left turned on,
629 a lot of later tests that checked the $@ got confusing failures.)
630
631
632 0.67 2005-08-03 Jarkko Hietaniemi <[email protected]>
633
634 - The 0.66 add_edge_get_id() fix was not yet quite right, Tels
635 found another problem with it. Now with another fix, and
636 another test case (t/u_te_ae.t)
637
638 - Documentation fixes from John P. Linderman.
639
640
641 0.66 2005-07-20 Jarkko Hietaniemi <[email protected]>
642
643 - Fix [rt.cpan.org #13193] "Documentation error in set_edge_attributes"
644 and [rt.cpan.org #13194] "Documentation error in set_edge_attributes"
645 (duplicate report)
646
647 - Fixes for problems listed in [rt.cpan.org #13195]
648 "add_vertex_get_id/add_edge_get_id() return wrong result on first call"
649 - add_edge_get_id() was returning an array reference instead
650 of the id with the first call (the array reference was the
651 ids of the vertices of the edge)
652 - add_vertex_get_id() was even more broken (a multivertexed
653 graph was using Graph::AdjacencyMap::Vertex for the vertex
654 map, not Graph::AdjacencyMap::Heavy)
655 - Added test t/u_te_me.t for the two above issues.
656 - document in which order multiedge ids are returned (random)
657 - require Data::Dumper only for deep_copy() and _dump()
658 (not changes for two listed items, "check directly multiedged
659 via a flag" and "remove returns for speed" because I have
660 issues with speed hacks without actual measurements, and even
661 if so would fear reduced maintainability)
662
663 - Fix [rt.cpan.org #13352] "Dijkstra heap logic"
664 Dijkstra was fine, the SPTHealElem cmp() routine was wrong
665 in having no tie breakers in case the weights compared equal.
666 Added test t/u_re_sd.t.
667
668
669 0.65 2005-05-15 Jarkko Hietaniemi <[email protected]>
670
671 - Tests added to 64_ref.t to verify that using different kinds
672 of blessed references as vertices works okay. Few bugs found
673 by these tests squashed.
674
675
676 0.64 2005-05-14 Jarkko Hietaniemi <[email protected]>
677
678 - Fix for [rt.cpan.org #12509] "Errors using objects as nodes",
679 patch from the reporter of the bug, add t/u/bb_rv.t.
680
681 - Fix for refvertexed isolated vertices not having overloaded cmp
682 and graph string presentation failing because of that.
683
684 - The <NOTE>s needed to be B<NOTE>s.
685
686
687 0.63 2005-04-16 Jarkko Hietaniemi <[email protected]>
688
689 - After setting a vertex attribute one could not delete
690 non-attributed vertices, reported by Joseph Hamilton.
691
692 - Inlining to speed up path_vertices() slightly.
693
694
695 0.62 2005-04-10 Jarkko Hietaniemi <[email protected]>
696
697 - The documentation of add_weighted_vertices was wrong:
698 the arguments are (v1, w1, v2, w2, ...) instead of (v1, v2, ..., w).
699
700 - Made calling interfaces with an "options hash" like new()
701 and random_graph() more robust, now bails out earlier instead
702 of dieing mysteriously later with an "odd number of arguments"
703
704 - Allow running under -d:DProf even when using random shuffling:
705 workaround for List::Util::shuffle and -d:DProf not working
706 together ([perl #32383]) by falling back to Fisher-Yates shuffle
707 if (any use of) the -d: is detected.
708
709 - Allow calling random_graph() also as a class method:
710 Graph::random_graph(...) (the resulting graph will be a 'Graph').
711
712 - in_degree() and out_degree() (and therefore vertex_degree())
713 were one too low for self-loop vertices in undirected graphs
714 (the self-loop edge was not counted).
715
716
717 0.61 2005-03-27 Jarkko Hietaniemi <[email protected]>
718
719 - [rt.cpan.org #12023] from Macha Nikolski:
720 deleting an attributed vertex left the graph in a state
721 where has_vertex() returned correctly false but vertices()
722 still wrongly returned the freshly deleted vertex.
723
724 - A few missing "See":s added to the pod.
725
726
727 0.60 2005-03-25 Jarkko Hietaniemi <[email protected]>
728
729 - Bug reported by Richard Ball: connected_component_by_index()
730 and connected_component_by_vertex() were starting their indexing
731 from one, not zero.
732
733 - t/27_hyperedged.t was really testing for turning on
734 hypervertexedness (the actual functionality was being
735 tested correctly in t/32_hyperedge.t).
736
737
738 0.59 2005-03-03 Jarkko Hietaniemi <[email protected]>
739
740 - deep_copy_graph() could not handle code references since
741 Data::Dumper by default doesn't handle those. Now uses
742 the Deparse option for 5.8.x and later.
743
744 - The removed interfaces add_graph() and delete_graph() still
745 had their documentation hanging around.
746
747
748 0.58 2005-02-19 Jarkko Hietaniemi <[email protected]>
749
750 - Document that using attributes does have a slowing down
751 effect on other graph operations
752 [rt.cpan.org #11498]
753 "Performance problem: edge attributes slow source_vertices"
754 This is unlikely to get fixed any time soon, I am afraid,
755 this is one of those working-as-designed-and-correctly-but-
756 unfortunately-slow things.
757
758 - Document that Graph 0.2xxx edges($v) is now edges_at($v)
759 [rt.cpan.org #11494]
760
761 - [rt.cpan.org #11543]: self-edges reported twice by edges_at().
762
763 - Declare/document that any attributes beginning with an underscore
764 are reserved for the internal use of Graph.
765
766 - Various inlining optimizations: should run 5-10% faster
767 than the 0.57.
768
769
770 0.57 2005-02-12 Jarkko Hietaniemi <[email protected]>
771
772 - Further 10% speedup on 'make test' on top of 0.56 by inlining
773 various code paths related to finding edges, now 'make test'
774 is cumulatively about 15% faster than the 0.55 release.
775 The test case of [rt.cpan.org #11465] is about 10 times faster.
776
777
778 0.56 2005-02-12 Jarkko Hietaniemi <[email protected]>
779
780 - Rewrite edges finding code (like edges_at()) to avoid a
781 quadratic algorithm. Shame on me. Luckily this extremely
782 slow path was not touched that often, but [rt.cpan.org #11465]
783 shows one known bad case, source_vertices() for compat02
784 graphs. The removal of the slow path sped up 'make test'
785 by about 5-10%.
786
787 - Remove a voodoo keys() from vertices_at().
788
789 - Document stubs for Graph::Directed and Graph::Undirected.
790
791 - Tiny documentation tweaks.
792
793 0.55 2005-01-22 Jarkko Hietaniemi <[email protected]>
794
795 - Add unset_row(), get_row(), set_row(), and unset_row(), methods
796 to Graph::BitMatrix and make it public (remove the "internal use
797 only" warning from it). Add t/82_bitmatrix.t.
798
799 - Add vertex_degree() as an alias for degree().
800
801 - One more alternative solution for spt.t from Koen.
802
803 - I seem to have this drive to misspell people's names.
804 Sorry, Koen.
805
806 0.54 2005-01-16 Jarkko Hietaniemi <[email protected]>
807
808 - More bugs found in set_vertex_attribute(), fixed and tests
809 added. (Basically the same failure pattern as with the
810 [rt.cpan.org #9461]: after setting vertex attributes many of
811 the 'structural' methods such as predecessors() often returned
812 wrong results.)
813
814 - More alternative solutions to spt.t, diameter.t, and dump.t,
815 found by the PRNG of Koen van der Drift in Mac OS X 10.3.7,
816 Perl 5.8.1.
817
818 0.53 2005-01-14 Jarkko Hietaniemi <[email protected]>
819
820 - The #9461 was still there.
821 But now we have a simple test case from Sebastian Nagel.
822 The real culprit seemed to be a misapplied optimisation.
823
824 0.52 2005-01-12 Jarkko Hietaniemi <[email protected]>
825
826 - Fix set_graph_attribute() documentation not to talk about $u, $v
827 (noticed by Kurt Jaeger).
828
829 - A mysterious failure fixed by a mysterious fix: under some
830 circumstances it seems that an each() doesn't walk through
831 all the key-value pairs, the workaround is to reset the
832 each() iterator by a keys() call. Not simple test code,
833 sadly, since the existing test code (see the case) is 13 kB
834 and non-trivial.
835 [rt.cpan.org #9461]
836
837 - Add a safety guard against a missing Scalar::Util::weaken
838 [rt.cpan.org #9481]
839
840 0.51 2005-01-09 Jarkko Hietaniemi <[email protected]>
841
842 - Allow calling Makefile.PL with arguments other than --renum
843 (which is for internal use only, and therefore undocumented).
844 [rt.cpan.org #9481]
845
846 - Remove the add_graph() and delete_graph() interfaces, sorry
847 if you were already using them, but the current interface was
848 very poor and the concept ill-planned. If you want to merge or
849 remove edges and vertices between your graph, you can probably
850 yourself implement the exactly right things to do.
851 [rt.cpan.org #9493]
852
853 - Document that one cannot assume Graphs are blessed hash references
854 (and the likely error message one will get if one so assumes).
855 [rt.cpan.org #9505]
856
857 - Fix Andras' last name (sorry).
858
859 - Merge duplicate documentation of find_a_cycle().
860
861 - Graph::AdjacencyMap::Base does not exist, fix Graph/AdjacencyMap.pm
862 pod to comply.
863
864
865 0.50 2005-01-01 Jarkko Hietaniemi <[email protected]>
866 - Unknown contents
867
868 0.001 1998-05-04
869 - First release to CPAN
870