| 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 |
|