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