
1 20100319 Version 1.2 released 

2 

3 This is major feature release 

4 

5 * New algorithms 

6 * BellmanFord algorithm (#51) 

7 * Minimum mean cycle algorithms (#179) 

8 * Karp, HartmanOrlin and Howard algorithms 

9 * New minimum cost flow algorithms (#180) 

10 * Cost Scaling algorithms 

11 * Capacity Scaling algorithm 

12 * CycleCanceling algorithms 

13 * Planarity related algorithms (#62) 

14 * Planarity checking algorithm 

15 * Planar embedding algorithm 

16 * Schnyder's planar drawing algorithm 

17 * Coloring planar graphs with five or six colors 

18 * Fractional matching algorithms (#314) 

19 * New data structures 

20 * StaticDigraph structure (#68) 

21 * Several new priority queue structures (#50, #301) 

22 * Fibonacci, Radix, Bucket, Pairing, Binomial 

23 Dary and fourary heaps (#301) 

24 * Iterable map structures (#73) 

25 * Other new tools and functionality 

26 * Map utility functions (#320) 

27 * Reserve functions are added to ListGraph and SmartGraph (#311) 

28 * A resize() function is added to HypercubeGraph (#311) 

29 * A count() function is added to CrossRefMap (#302) 

30 * Support for multiple targets in Suurballe using fullInit() (#181) 

31 * Traits class and named parameters for Suurballe (#323) 

32 * Separate reset() and resetParams() functions in NetworkSimplex 

33 to handle graph changes (#327) 

34 * tolerance() functions are added to HaoOrlin (#306) 

35 * Implementation improvements 

36 * Improvements in weighted matching algorithms (#314) 

37 * Jumpstart initialization 

38 * ArcIt iteration is based on outarc lists instead of inarc lists 

39 in ListDigraph (#311) 

40 * Faster add row operation in CbcMip (#203) 

41 * Better implementation for split() in ListDigraph (#311) 

42 * ArgParser can also throw exception instead of exit(1) (#332) 

43 * Miscellaneous 

44 * A simple interactive bootstrap script 

45 * Doc improvements (#62,#180,#299,#302,#303,#304,#307,#311,#331,#315, 

46 #316,#319) 

47 * BibTeX references in the doc (#184) 

48 * Optionally use valgrind when running tests 

49 * Also check ReferenceMapTag in concept checks (#312) 

50 * dimacssolver uses long long type by default. 

51 * Several bugfixes (compared to release 1.1): 

52 #295: Suppress MSVC warnings using pragmas 

53 : Various CMAKE related improvements 

54 * Remove duplications from doc/CMakeLists.txt 

55 * Rename documentation install folder from 'docs' to 'html' 

56 * Add tools/CMakeLists.txt to the tarball 

57 * Generate and install LEMONConfig.cmake 

58 * Change the label of the html project in Visual Studio 

59 * Fix the check for the 'long long' type 

60 * Put the version string into config.h 

61 * Minor CMake improvements 

62 * Set the version to 'hgtip' if everything fails 

63 #311: Add missing 'explicit' keywords 

64 #302: Fix the implementation and doc of CrossRefMap 

65 #308: Remove duplicate list_graph.h entry from source list 

66 #307: Bugfix in Preflow and Circulation 

67 #305: Bugfix and extension in the rename script 

68 #312: Also check ReferenceMapTag in concept checks 

69 #250: Bugfix in pathSource() and pathTarget() 

70 #321: Use pathCopy(from,to) instead of copyPath(to,from) 

71 #322: Distribure LEMONConfig.cmake.in 

72 #330: Bug fix in map_extender.h 

73 #336: Fix the date field comment of graphToEps() output 

74 #323: Bug fix in Suurballe 

75 #335: Fix clear() function in ExtendFindEnum 

76 #337: Use void* as the LPX object pointer 

77 #317: Fix (and improve) error message in mip_test.cc 

78 Remove unnecessary OsiCbc dependency 

79 #356: Allow multiple executions of weighted matching algorithms (#356) 

80 
1 20090513 Version 1.1 released 
81 20090513 Version 1.1 released 
2 
82 
3 This is the second stable release of the 1.x series. It 
83 This is the second stable release of the 1.x series. It 
4 features a better coverage of the tools available in the 0.x 
84 features a better coverage of the tools available in the 0.x 
5 series, a thoroughly reworked LP/MIP interface plus various 
85 series, a thoroughly reworked LP/MIP interface plus various 
70 : Set the proper version for CMAKE in the tarballs 
150 : Set the proper version for CMAKE in the tarballs 
71 (made by autotools) 
151 (made by autotools) 
72 : Minor clarification in the LICENSE file 
152 : Minor clarification in the LICENSE file 
73 : Add missing unistd.h include to time_measure.h 
153 : Add missing unistd.h include to time_measure.h 
74 #204: Compilation bug fixed in graph_to_eps.h with VS2005 
154 #204: Compilation bug fixed in graph_to_eps.h with VS2005 
75 #214,#215: windows.h should never be included by lemon headers 
155 #214,#215: windows.h should never be included by LEMON headers 
76 #230: Build systems check the availability of 'long long' type 
156 #230: Build systems check the availability of 'long long' type 
77 #229: Default implementation of Tolerance<> is used for integer types 
157 #229: Default implementation of Tolerance<> is used for integer types 
78 #211,#212: Various fixes for compiling on AIX 
158 #211,#212: Various fixes for compiling on AIX 
79 : Improvements in CMAKE config 
159 : Improvements in CMAKE config 
80  docs is installed in share/doc/ 
160  docs is installed in share/doc/ 
92 development of opensource software for the operations research 
172 development of opensource software for the operations research 
93 community. 
173 community. 
94 
174 
95 20081013 Version 1.0 released 
175 20081013 Version 1.0 released 
96 
176 
97 This is the first stable release of LEMON. Compared to the 0.x 
177 This is the first stable release of LEMON. Compared to the 0.x 
98 release series, it features a considerably smaller but more 
178 release series, it features a considerably smaller but more 
99 matured set of tools. The API has also completely revised and 
179 matured set of tools. The API has also completely revised and 
100 changed in several places. 
180 changed in several places. 
101 
181 
102 * The major name changes compared to the 0.x series (see the 
182 * The major name changes compared to the 0.x series (see the 
103 Migration Guide in the doc for more details) 
183 Migration Guide in the doc for more details) 
104 * Graph > Digraph, UGraph > Graph 
184 * Graph > Digraph, UGraph > Graph 
105 * Edge > Arc, UEdge > Edge 
185 * Edge > Arc, UEdge > Edge 
106 * source(UEdge)/target(UEdge) > u(Edge)/v(Edge) 
186 * source(UEdge)/target(UEdge) > u(Edge)/v(Edge) 
107 * Other improvements 
187 * Other improvements 
108 * Better documentation 
188 * Better documentation 
109 * Reviewed and cleaned up codebase 
189 * Reviewed and cleaned up codebase 
110 * CMake based build system (along with the autotools based one) 
190 * CMake based build system (along with the autotools based one) 
111 * Contents of the library (ported from 0.x) 
191 * Contents of the library (ported from 0.x) 
112 * Algorithms 
192 * Algorithms 
113 * breadthfirst search (bfs.h) 
193 * breadthfirst search (bfs.h) 
114 * depthfirst search (dfs.h) 
194 * depthfirst search (dfs.h) 
115 * Dijkstra's algorithm (dijkstra.h) 
195 * Dijkstra's algorithm (dijkstra.h) 
116 * Kruskal's algorithm (kruskal.h) 
196 * Kruskal's algorithm (kruskal.h) 
117 * Data structures 
197 * Data structures 
118 * graph data structures (list_graph.h, smart_graph.h) 
198 * graph data structures (list_graph.h, smart_graph.h) 
119 * path data structures (path.h) 
199 * path data structures (path.h) 
120 * binary heap data structure (bin_heap.h) 
200 * binary heap data structure (bin_heap.h) 
121 * unionfind data structures (unionfind.h) 
201 * unionfind data structures (unionfind.h) 
122 * miscellaneous property maps (maps.h) 
202 * miscellaneous property maps (maps.h) 
123 * two dimensional vector and bounding box (dim2.h) 
203 * two dimensional vector and bounding box (dim2.h) 
124 * Concepts 
204 * Concepts 
125 * graph structure concepts (concepts/digraph.h, concepts/graph.h, 
205 * graph structure concepts (concepts/digraph.h, concepts/graph.h, 
126 concepts/graph_components.h) 
206 concepts/graph_components.h) 
127 * concepts for other structures (concepts/heap.h, concepts/maps.h, 
207 * concepts for other structures (concepts/heap.h, concepts/maps.h, 
128 concepts/path.h) 
208 concepts/path.h) 
129 * Tools 
209 * Tools 
130 * Mersenne twister random number generator (random.h) 
210 * Mersenne twister random number generator (random.h) 
131 * tools for measuring cpu and wall clock time (time_measure.h) 
211 * tools for measuring cpu and wall clock time (time_measure.h) 
132 * tools for counting steps and events (counter.h) 
212 * tools for counting steps and events (counter.h) 
133 * tool for parsing command line arguments (arg_parser.h) 
213 * tool for parsing command line arguments (arg_parser.h) 
134 * tool for visualizing graphs (graph_to_eps.h) 
214 * tool for visualizing graphs (graph_to_eps.h) 
135 * tools for reading and writing data in LEMON Graph Format 
215 * tools for reading and writing data in LEMON Graph Format 
136 (lgf_reader.h, lgf_writer.h) 
216 (lgf_reader.h, lgf_writer.h) 
137 * tools to handle the anomalies of calculations with 
217 * tools to handle the anomalies of calculations with 
138 floating point numbers (tolerance.h) 
218 floating point numbers (tolerance.h) 
139 * tools to manage RGB colors (color.h) 
219 * tools to manage RGB colors (color.h) 
140 * Infrastructure 
220 * Infrastructure 
141 * extended assertion handling (assert.h) 
221 * extended assertion handling (assert.h) 
142 * exception classes and error handling (error.h) 
222 * exception classes and error handling (error.h) 
143 * concept checking (concept_check.h) 
223 * concept checking (concept_check.h) 
144 * commonly used mathematical constants (math.h) 
224 * commonly used mathematical constants (math.h) 