Graph
view release on metacpan or search on metacpan
- 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.
0.69 2005-12-06 Jarkko Hietaniemi <jhi@iki.fi>
- 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.
0.68 2005-11-23 Jarkko Hietaniemi <jhi@iki.fi>
- 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 edge 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.)
0.67 2005-08-03 Jarkko Hietaniemi <jhi@iki.fi>
- 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.
0.66 2005-07-20 Jarkko Hietaniemi <jhi@iki.fi>
- 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.
0.65 2005-05-15 Jarkko Hietaniemi <jhi@iki.fi>
- 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.
0.64 2005-05-14 Jarkko Hietaniemi <jhi@iki.fi>
- 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.
0.56 2005-02-12 Jarkko Hietaniemi <jhi@iki.fi>
- 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.
0.55 2005-01-22 Jarkko Hietaniemi <jhi@iki.fi>
- 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.
0.54 2005-01-16 Jarkko Hietaniemi <jhi@iki.fi>
- 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.
0.53 2005-01-14 Jarkko Hietaniemi <jhi@iki.fi>
- 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.
0.52 2005-01-12 Jarkko Hietaniemi <jhi@iki.fi>
- 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]
0.51 2005-01-09 Jarkko Hietaniemi <jhi@iki.fi>
- 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.
0.50 2005-01-01 Jarkko Hietaniemi <jhi@iki.fi>
- Unknown contents
0.001 1998-05-04
- First release to CPAN
( run in 0.971 second using v1.01-cache-2.11-cpan-39bf76dae61 )