Debian Codegraph @

ChangeLog

raw
1 5.8.3.0
2 -------
3
4 * Data.Graph.Inductive.NodeMap now has functions mkLookupNode,
5 insMapLookupNode, memberNode, and lookupNode for detecting whether a
6 graph already contains a node (issue #72, PR #77).
7
8 5.8.2.0
9 -------
10
11 * Data.Graph.Inductive.Graph now only requires Graph, not DynGraph
12 (issue #100).
13
14 * Documented that some functions are partial (issue #98).
15
16 * Add `insert` function as synonym for `&` (issue #90).
17
18 5.8.1.1
19 -------
20
21 * Data.Graph.Inductive.Query.Dominators.{dom,iDom} could fail for some
22 graphs (issue #109, regression in 5.8.1.0).
23
24 5.8.1.0
25 -------
26
27 * Data.Graph.Inductive.PatriciaTree.Gr and
28 Data.Graph.Inductive.Tree.Gr now have Functor instances.
29
30 * 'Gr a' is now an instance of Functor.
31
32 5.8.0.0
33 -------
34
35 * Breaking change: MonadFail is no longer a superclass of GraphM.
36 This is to support GHC 9.4. This has no effect on the IO and ST
37 instances of GraphM, but may affect users.
38
39 5.7.0.3
40 -------
41
42 * Bump QuickCheck dependency
43
44 5.7.0.2
45 -------
46
47 * Bump dependencies.
48
49 5.7.0.1
50 -------
51
52 * Accidentally released the wrong version.
53
54 5.7.0.0
55 -------
56
57 * Updating the GraphM class to be compatible with the MonadFail proposal and GHC's
58 MonadFailDesugaring language extension which is enabled by default by GHC-8.6.1.
59
60 5.6.0.0
61 -------
62
63 * The previous version should have been a major version bump due to
64 the API change.
65
66 5.5.4.0
67 -------
68
69 * Improved type safety of shortest-path functions (in
70 `Data.Graph.Inductive.Query.SP`) thanks to Nathan Collins.
71
72 - `getDistance`, `spLength` and `sp` now return `Maybe` values.
73
74 * Fixed building on GHC < 7.4; previously uncaught due to
75 cabal-install doing the wrong thing on Travis-CI.
76
77
78 5.5.3.1
79 -------
80
81 * Hopefully clearer documentation for `&`, `Context` and the
82 `ufold`-based functions.
83
84 * Thanks to David Feuer, the existing benchmark suite is now runnable
85 with `cabal bench`.
86
87 * Some performance improvements for `PatriciaTree`, thanks to David
88 Feuer.
89
90 5.5.3.0
91 -------
92
93 * Additional closure functions by Matthew Danish.
94
95 * `Bifunctor` instances for base >= 4.8.0.0.
96
97 * An `ST`-based `GraphM` instance.
98
99 * Addition of `order` and `size` functions for finding the number of
100 nodes and edges respectively in a graph (the former is an alias for
101 the existing `noNodes` function).
102
103 * The rules for faster implementations of `insNode` and `insEdge` for
104 `PatriciaTree` should fire more often now.
105
106 5.5.2.3
107 -------
108
109 * Earlier fix for `NFData` wasn't quite complete/correct.
110
111 5.5.2.2
112 -------
113
114 * Ensure firing of specialised rules for `PatriciaTree`.
115
116 * Better way of only creating `NFData` instances when possible.
117
118 5.5.2.1
119 -------
120
121 * Only create `NFData` instances for GHC >= 7.4.1.
122
123 5.5.2.0
124 -------
125
126 * Documentation, clean-up and refactoring of various parts of the
127 library.
128
129 - As part of this, various types now have instances for classes
130 like `Show`, `Eq`, `Ord`, `NFData`, etc. where applicable.
131
132 - In particular, the various options for use with depth-first
133 search and shortest path queries was documented by David
134 Luposchainsky.
135
136 * Addition of a proper test-suite. So far it covers the
137 `Data.Graph.Inductive.Graph` module and all
138 `Data.Graph.Inductive.Query.*` modules except for `Monad`.
139
140 - The tests are also automatically run for every (set of) commits
141 thanks to Travis-CI.
142
143 * Arbitrary instances for the two graph types are now available in the
144 new `fgl-arbitrary` sub-package.
145
146 * Now depends solely on the `transformers` library rather than `mtl`.
147
148 * Potentially breaking changes:
149
150 These changes are those where the behaviour was un-specified or
151 didn't match the documentation.
152
153 - `nodeRange` and `nodeRangeM` for the various graph data
154 structures erroneously returned `(0,0)` for empty graphs (making
155 them indistinguishable from graphs containing the single node
156 `0`). They now match the default implementation of throwing an
157 error.
158
159 - The behaviour of `delLEdge` when dealing with multiple edges was
160 unspecified; it now deletes only a single edge and the new
161 function `delAllLEdge` deletes all edges matching the one
162 provided.
163
164 * Additional functions thanks to Sergiu Ivanov:
165
166 - Creating sub-graphs by `Node`- and `Context`-filtering as well
167 as induced by a set of `Node`s.
168
169 - Graph condensation (i.e. graph of
170 strongly-connected-components).
171
172 - Various edge- and neighbor-based helper functions.
173
174 * The graph types now have `Generic` instances thanks to Piotr
175 Mlodawski.
176
177 * The `OrdGr` wrapper by Trevor Cook allows performing `Ord`-based
178 comparisons on graphs.
179
180 5.5.1.0
181 -------
182
183 * Support added for GHC 7.10 by Herbert Valerio Riedel.
184
185 * Additional DFS query functions added by Conrad Parker.
186
187 * Repository location changed to GitHub.
188
189 * Code cleanup:
190
191 - Replaced usage of internal FiniteMap copy with Data.Map and
192 Data.Set from the containers library.
193
194 - Remove usage of data type contexts.
195
196 - Use newtypes where applicable.
197
198 5.5.0.1
199 -------
200
201 * Fix up Eq instances for Tree and PatriciaTree so that they work with
202 multiple edges.
203
204 5.5.0.0
205 -------
206
207 * Add proper Show, Read and Eq instances to Data.Graph.Inductive.Tree
208 and Data.Graph.Inductive.PatriciaTree.
209
210 * Add pretty-printing functions to Data.Graph.Inductive.Graph. These
211 are based upon the old Show implementation for
212 Data.Graph.Inductive.Tree.
213
214 * Now use PatriciaTree by default rather than Tree (and recommend as
215 such). IntMap has been receiving a lot of optimisation work on it,
216 whereas the internal FiniteMap implementation hasn't received any
217 attention.
218
219 * The `version :: IO ()` action now uses the actual Cabal version.
220
221 * Remove Data.Graph.Inductive.Graphviz; use the graphviz package
222 instead.
223
224 5.4.2.4
225 -------
226
227 * Update to work with GHC-7.2 and Cabal-1.6.
228
229 5.4.2.3
230 -------
231
232 * Maintainership taken over by Ivan Miljenovic.
233
234 * Allow Data.Graph.Inductive.PatriciaTree to deal with multiple edges
235 between nodes.
236
237 5.4.2.2 (November 2008)
238 -----------------------
239
240 * Bugfix in Graphviz.sq
241
242 5.4.2.1 (June 2008)
243 -------------------
244
245 * bug fix in bcc by Reid Barton
246
247 * added new dynamic graph implementation:
248 Data.Graph.Inductive.PatriciaTree (thanks to Pho)
249
250 * added test/benchmark.hs: a benchmark to compare Tree and PatriciaTree
251 implementations (thanks to Pho)
252
253 5.4.2 (May 2008)
254 ----------------
255
256 * added Setup.hs to tar file
257
258 * reimplementation of Data.Graph.Inductive.Query.Dominators
259 by Bertram Felgenhauer:
260
261 It was buggy and very slow for large graphs. See
262 http://www.haskell.org/pipermail/haskell-cafe/2008-April/041739.html
263
264 This patch also adds a new function, iDom, that returns the
265 immediate dominators of the graph nodes.
266
267 * Exported xdf*With functions from DFS.hs
268
269 * many little cleanups thanks to many people
270 (use 'darcs changes' to see the details)
271
272 5.4 (April 2007)
273 ----------------
274
275 * changed the implementation for inspection functions (suc, pred, ...)
276 to correct the behavior in the presence of loops (thanks to Ralf
277 Juengling for pointing out the inconsistency)
278
279 5.3 (June 2006)
280 ---------------
281
282 * fixed a bug in findP (thanks to [email protected])
283
284 * added function delLEdge in Graph.hs (thanks to Jose Labra)
285
286 * changed implementation of updFM and mkGraph (thanks to Don Stewart)
287
288 February 2005
289 -------------
290
291 * fixed an import error in Basic.hs
292
293 * removed Eq instance of gr because it caused overlapping instance
294 problems. Instead the function equal defined in Graph.hs can be
295 used
296
297 * added some more functions to the export list of DFS.hs
298
299 * changed the definition of LPath into a newtype to avoid overlapping
300 instances with lists
301
302 * fixed the Makefile (for GHC and GHCi)
303
304
305 January 2004
306 ------------
307
308 * bug fix for nearestNode (src/Data/Graph/Inductive/Query/GVD.hs)
309 Update contributed by Aetion Technologies LLC (www.aetion.com)
310
311 * Refactor into hierarchical namespace
312
313 * Build changes:
314 - build a standard haskell library (libHSfgl.a, HSfgl.o)
315 - install as ghc package (fgl), uses Auto so no -package is needed
316
317 * Automatic Node generation for labels: Data.Graph.Inductive.NodeMap
318
319 * Graphviz output: Data.Graph.Inductive.Graphviz
320
321 September 2002
322 --------------
323
324 * Introduction of graph classes
325
326 * Monadic graphs and graph computation monad
327
328 * Graph implementation based on balanced (AVL) trees
329
330 * Fast graph implementation based on IO arrays
331
332 * New algorithms:
333 - Maximum flow
334 - Articulation points
335 - biconnected components
336 - dominators
337 - transitive closure
338
339 * minor changes in utility functions
340 - changed signatures (swapped order of arguments) of
341 functions context and lab to be consistent with other graph functions
342 - changed function first in RootPath: not existing path is now reported
343 as an empty list and will not produce an error
344 - esp version that returns a list of labeled edges
345 (to find minimum label in maxflow algorithm)
346 - BFS uses amortized O(1) queue
347 - Heap stores key and value separately
348 - ...
349
350 March 2001
351 ----------
352 * Changes to User Guide
353
354 * a couple of new functions
355
356 * some internal changes
357
358 April 2000
359 ----------
360
361 * User Guide
362
363 * Systematic structure for all depth-first search functions
364
365 * Graph Voronoi diagram
366
367 * Several small changes and additions in utility functions
368
369 February 2000
370 -------------
371
372 * Representation for inward-directed trees
373
374 * Breadth-first search
375
376 * Dijkstra's algorithm
377
378 * Minimum-spanning-tree algorithm
379
380
381 August 1999
382 -----------
383
384 * First Haskell version