__group__ ticket summary component version type owner status modified _time _description _reporter Milestone: none 8 GraphToEps() doesn't show loop egdes core hg main enhancement Alpar Juttner assigned 2008-11-03T18:16:46+01:00 13:35:54+01:00 "Although it would be nice. This ticket is a copy of report !#27 of the old bug tracking system. It refers to svn trunk -!r2561." Alpar Juttner Milestone: none 139 Support short and long style parameters in ArgParser core hg main enhancement Alpar Juttner assigned 2008-11-03T18:17:01+01:00 18:19:35+02:00 "This is a follow-up of ticket:104. I would propose a member function like {{{void style(StyleEnum st)}}}, where the parameter {{{st}}} would choose from the following options: - '''Short style''', where the form of the parameters are {{{ -param value }}} - '''Long style''', where the form of the parameters are {{{ -param=value }}} - '''Mixed style''', where options starting with one dash use the short form while those starting with two use the long style. With this approach, one can implement POSIX compliant parameters." Alpar Juttner Milestone: none 76 New features for graphToEps() core hg main enhancement Alpar Juttner assigned 2008-11-03T18:22:10+01:00 17:23:46+02:00 "Some additional features for {{{graphToEps()}}} would be nice to have. For example: - The ability of setting linestyles, such az dotted, dashed etc. - The ability of the assignment of a second color to the edges along with a percentage value. Then the edges would be colored with to color according to the percentage. " Alpar Juttner Milestone: none 85 Use eps.h for drawing in graphToEps() core hg main task Alpar Juttner new 2008-11-03T18:22:54+01:00 18:31:52+02:00 "We should consider using eps.h for the actual drawing in graphToEps(). See also ticket:43." Alpar Juttner Milestone: none 77 Added functionality to nodePsTexts() named param. of graphToEps(). core hg main enhancement Alpar Juttner assigned 2008-11-21T16:00:25+01:00 17:33:20+02:00 When a pure postscript block is inserted as each node with nodePsTexts(), it would be nice to offer the choice not to move to the center but pass the coordinates to the Postscript block inserted. Alpar Juttner Milestone: none 78 Added functionality to graphToEps(). core hg main enhancement Alpar Juttner assigned 2008-11-21T16:00:35+01:00 17:36:35+02:00 It would be nice to enable multiline copyright notices in {{{GraphToEps::copyright()}}} Alpar Juttner Milestone: none 6 VGraph and VMap core svn trunk enhancement Alpar Juttner assigned 2008-11-23T09:28:10+01:00 13:29:31+01:00 "It would be nice to have maps and graph with virtual functions in their interface. They would be inherited from common base classes, and there would be factories to ""virtualize"" graphs and maps. All these would make it possible to avoid the use of templates when the speed is not an issue. This ticket is a copy of report !#24 of the old bug tracking system. It refers to release 0.5. " Alpar Juttner Milestone: none 70 Port VirtualMaps core task Alpar Juttner assigned 2008-11-23T09:28:59+01:00 16:22:47+01:00 "This affects - lemon/vmap.h but this tool is still in an early stage. " Alpar Juttner Milestone: none 152 Using processed map in Dijkstra::processed() core hg main enhancement Peter Kovacs new 2008-11-24T12:59:41+01:00 06:31:33+02:00 "This ticket is a follow-up of #149. Now [source:lemon/dijkstra.h@0310c8984732#L906 Dijkstra::processed()] uses the heap to determine the return value whether or not the current {{{ProcessedMap}}} type is {{{NullMap}}} or not and whether it uses local map or not. It would be nice that the given processed map ({{{_processed}}}) is used if it is not of type {{{NullMap}}} and the heap is used otherwise. I think it would need some template tricks to implement. Otherwise we could introduce a bool flag that shows whether {{{SetProcessedMap}}} or {{{SetStandardProcessedMap}}} named class parameters were used. But in the the later case extra codes in {{{DijkstraWizard}}} would also be needed, since it does not use the above named class parameters but defining a traits class explicitly. " Peter Kovacs Milestone: none 71 Port Steiner tree approximation algorithm core task Balazs Dezso assigned 2008-11-24T13:44:37+01:00 16:24:31+01:00 "Namely, the file - lemon/steiner.h " Alpar Juttner Milestone: none 64 Port constrained shortest path algorithm core task Alpar Juttner assigned 2008-12-15T17:05:21+01:00 14:06:02+01:00 "Namely, this file: - lemon/csp.h " Alpar Juttner Milestone: none 235 Push-relabel max flow (Preflow) for undirected graphs core hg main enhancement Alpar Juttner new 2009-02-25T13:45:02+01:00 13:45:02+01:00 "The current Preflow algorithm works well on undirected graphs, however a specialized version for undirected graphs could more efficient than the current solution. The flow map could be EdgeMap in this case and the edges do not need to be iterated twice (outgoing and incoming arcs). I think the overall improvement could be a small factor both in time and storage complexity. " Balazs Dezso Milestone: none 237 Line graph implementations core hg main enhancement Alpar Juttner new 2009-03-03T13:29:46+01:00 13:29:46+01:00 They can either be adaptors or just simple tools for creating the line graph of a given graph similarly to the graph copying tools. Alpar Juttner Milestone: none 220 Implement a Dual Network Simplex algorithm core hg main enhancement Alpar Juttner new 2009-03-23T23:27:17+01:00 07:29:16+01:00 The title says everything. Alpar Juttner Milestone: none 151 Possible improvement in the function-type implementation of BFS/DFS/Dijkstra core hg main enhancement Balazs Dezso new 2009-08-02T13:20:55+02:00 17:38:45+02:00 "This ticket is a follow-up of #96. Maybe it would be better if we could avoid using {{{NodeMap}}}s (instead of {{{NullMap}}}s) as {{{PredMap}}} and {{{DistMap}}} structures in the cases when they are not necessary. So the default type of these maps would be a {{{NullMap}}} in {{{Bfs/Dfs/DijkstraWizardDefaultTraits}}} classes, and it would be changed only if it is really needed (i.e. {{{path()}}} and/or {{{dist()}}} named parameter is used). Balazs suggested a solution for this, saying: ""iff at least one s-t path search is queried, real pred map should be defined, and iff at least one length of an s-t path queried, real dist map should be used. It could be done with the {{{ForkMap}}}s"". It is a benchmark question however, that this implementation would be more efficient or not in practice." Peter Kovacs Milestone: none 310 Bounding box for Bezier-curves core hg main enhancement Balazs Dezso new 2009-08-18T21:15:53+02:00 21:15:53+02:00 The patch [1121710e18c9] contains functions for bounding box computation of Bezier-curves. Balazs Dezso Milestone: none 313 Revise the implementation of PairingHeap and RadixHeap core hg main enhancement Alpar Juttner new 2009-09-01T21:58:47+02:00 21:43:45+02:00 "The implementation of `PairingHeap` and `RadixHeap` should be revised, since they could most likely be made more efficient. For example, in LEDA (according to their tests) pairing heap is always faster than Fibonacci heap, moreover it is usually faster than binary heap. Radix heap is also very fast, it is usually better than both pairing and binary heaps. However according to my tests, `PairingHeap` and `RadixHeap` are almost always slower than `BinHeap` in LEMON. LEDA results: http://www.cs.elte.hu/~kiraly/sanyag.adatstr/LEDAbook.heaps.ps Two hints for `PairingHeap`: 1. It does not contain the heuristic that the small heaps created by `push()` and `decrease()` operations are collected in a temporary storage and they are merged into the main heap only if it is necessary (e.g. in case of a `pop()` or `prio()`). 2. The underlying binary tree is currently stored using two indices (pointers) and a bool value at each node. This needs less space than storing three indices (for the parent and the two children), but it is not clear if it is faster or slower. The latter representation should also be implemented and tested. Apart from that, there could be other points in which the code could be made better." Peter Kovacs Milestone: none 73 Port the remaining miscellaneous tools core task Alpar Juttner assigned 2009-10-07T16:40:50+02:00 16:29:50+01:00 "The following files should be considered. - lemon/dist_log.h - lemon/refptr.h - ~~lemon/iterable_maps.h~~ - lemon/bits/debug_map.h - lemon/matrix_maps.h - lemon/polynomial.h - lemon/concepts/matrix_maps.h - lemon/map_iterator.h" Alpar Juttner Milestone: none 98 Read-Write LoggerBoolMap core hg main enhancement Peter Kovacs assigned 2009-10-12T15:44:06+02:00 19:40:18+02:00 "!LoggerBoolMap map is only writable, so e.g. it can be used for !ProcessedMap, but it cannot be used for !ReachedMap in Bfs, Dfs, Dijkstra. Now the simplest way for creating such a map is {{{ #!cpp typedef LoggerBoolMap<...> LoggerMap; BoolEdgeMap map; LoggerMap log; ForkMap m(map, log); }}} " Peter Kovacs Milestone: none 94 Easy erase in list graphs core enhancement Alpar Juttner new 2009-10-13T12:55:30+02:00 20:25:57+02:00 The arcs and nodes might be able to erase during an iteration very easy way in the list and smart graph implementations. If an iterator points to an arc or a node, and the item is deleted, then the increment should be valid operation until other change occurred on the graph. Of course, accessing such iterator should be avoided. Balazs Dezso Milestone: none 189 Add the functionality of ItemSetTraits to the graphs core hg main enhancement Balazs Dezso new 2009-11-04T19:28:10+01:00 22:25:17+01:00 "Maybe we could introduce the functionality of `ItemSetTraits` to the graph concepts and to the adaptors in order to have the followings for all graph types. - `Graph::Map` - `Graph::It` or `Graph::ItemIt` Where `T` can be `Node`, `Arc` or `Edge`." Peter Kovacs Milestone: none 300 Faster building of heaps core hg main enhancement Alpar Juttner new 2009-11-04T19:28:31+01:00 18:09:49+02:00 "For some heap structures it is possible to build them from an existing list of `n` items faster than calling `push()` `n` times. E.g. for binary heap calling `push()` for each item takes `O(n log n)` time, while a heap can be built in `O(n)` time. It would be nice to indroduce `build()` (or something like that) member functions into those heap structures, for which it could be done faster than calling `push()` `n` times. Or maybe such a function could be introduced to the heap concept itself and all the heap structures (it could be implemented by calling `push()`, if it is not slower). The main reason why we have heaps is to use them in algorithms like Dijkstra and Prim. These algorithms do not need such a function, but if one would like to use LEMON heaps for other purposes, it may be useful. " Peter Kovacs Milestone: none 284 LGF to EPS converter tool tools hg main enhancement Alpar Juttner new 2009-11-04T19:29:44+01:00 10:33:32+02:00 "It would be nice to have a well configurable command line tool for converting LGF files into EPS. Of course, it would be basically a command line wrapper around `graph_to_eps()`." Alpar Juttner Milestone: none 269 Function type interface for Circulation core hg main enhancement Alpar Juttner new 2009-11-04T19:30:25+01:00 16:49:56+02:00 "It would be nice to have a function type interface for Circulation. It should have almost the same named parameters as !NetworkSimplex (without costs), and it should be implemented without map copying to be as efficient as the class interface. This ticket is a folow-up of #266." Peter Kovacs Milestone: none 247 DegMap core hg main enhancement Peter Kovacs new 2009-11-04T19:31:01+01:00 16:45:57+01:00 There are `InDegMap` and `OutDegMap` classes for directed graphs. So it would be nice to have a `DegMap` class for undirected graphs. I see that both `InDegMap` and `OutDegMap` can be used for this purpose, but it would be better to have `DegMap` even if it is just an alias for one of these maps. Peter Kovacs Milestone: none 37 operator= for RangeMap and SparseMap core hg main enhancement Peter Kovacs assigned 2009-11-04T19:45:17+01:00 18:50:14+01:00 Now {{{operator=}}} function is private (without implementation) in {{{RangeMap}}} and {{{SparseMap}}} classes. Do we need public {{{operator=}}}? Peter Kovacs Milestone: none 123 dim2::Point default constructor core hg main enhancement Peter Kovacs assigned 2009-11-04T19:46:29+01:00 10:09:53+02:00 "I think the default constructor of {{{dim2::Point}}} should set the point (0,0). It is a natural request for any class that provides {{{operator+}}} to be able to sum it correctly with a template function. I also made benchmark tests. They showed that this variant is not slower than the current one." Peter Kovacs Milestone: none 178 Port dynamic tree based max flow algs. core hg main task Balazs Dezso new 2009-11-05T11:21:07+01:00 11:34:10+01:00 "This ticket is a follow-up of #47. Affected files are: - lemon/dynamic_tree.h - lemon/goldberg_tarjan.h - lemon/dinitz_sleator_tarjan.h " Alpar Juttner Milestone: none 338 Infinite capacities in Preflow core hg main enhancement Alpar Juttner new 2010-02-09T23:28:34+01:00 23:28:34+01:00 "Infinite (or very high) capacities typically cause problems in `Preflow`, since the algorithm usually saturate arcs. This problem could be overcome by finding a finite cut and replace the huge capacities on the outgoing arcs of the source node with the value of the found cut if such a cut exists. Otherwise the max. flow value is infinite. This solution could be implemented in the `Preflow` class itself or rather in a separate wrapper class (it should be used in the DIMACS solver utility, as well). This ticket is a follow-up of #319." Peter Kovacs Milestone: none 86 Virtualmap based graphToEps(). core enhancement Alpar Juttner assigned 2010-02-17T06:58:36+01:00 18:35:35+02:00 "A rewrite of graphToEps() using virtual-maps instead of named template parameters would result in a much faster compilation time, at a cost of a slower execution, which is not really an issue here. See also ticket:43." Alpar Juttner Milestone: none 344 Cairo based version of graphToEps() core hg main enhancement Alpar Juttner new 2010-02-17T07:05:45+01:00 07:05:45+01:00 "Currently graphToEps() directly generates its output .eps file. This is good because we do not depend on any third party library. However using the cairo rendering backend would have a couple of advantages, most importantly it could directly create graphics in other formats like PDF, PNG (pixel graphics format) or SVG (editable vector graphics format). It would also allow easy integration to a GUI. This enhancement could also be incorporated with #86." Alpar Juttner Milestone: none 343 Support arbitrary precision integers and rationals in LEMON core hg main enhancement Akos Ladanyi assigned 2010-02-18T06:17:23+01:00 06:19:02+01:00 Of course we should rely on a third party library, but it would still be nice if e.g. dimacs-solver could provide dead true results. Alpar Juttner Milestone: none 352 Tolerance in GomoryHu core hg main enhancement Balazs Dezso new 2010-03-02T10:08:31+01:00 10:07:56+01:00 "For `GomoryHu` class, `Tolerance` type/object cannot be set, but it could be useful. The tolerance could be passed to the Preflow instances used by the algorithm. This ticket is a follow-up of #306." Peter Kovacs Milestone: none 361 Tolerance support in BellmanFord core hg main enhancement Peter Kovacs assigned 2010-03-18T08:25:06+01:00 01:31:54+01:00 "!BellmanFord (and maybe Dijkstra as well) could construct and store an instance of the operation traits class and use the operation traits functionalities through this object. This makes it possible to have such op. traits objects that can hold an ''epsilon'' value or a tolerance instance. It would also be important to have set/get functions for this instance in the algorithm class(es). This ticket is a follow-up of #51 and #360." Peter Kovacs Milestone: none 367 Gurobi backend for the LP interface core hg main enhancement Alpar Juttner new 2010-04-16T10:12:41+02:00 10:12:41+02:00 [http://www.gurobi.com/ Gurobi Optimizer] focuses on parallel optimization and it is of increasing popularity. AFAK, it is freely available for academic purposes, thus it would be nice if LEMON supported it. Alpar Juttner Milestone: none 378 Transitive closure core hg main enhancement Alpar Juttner new 2010-07-02T23:09:37+02:00 23:09:37+02:00 "It would be nice to have a tool that generates the transitive closure of an input graph to another graph (similarly to `digraphCopy()`). There are efficient solution methods based on the computation of the strongly connected components and their topological order. For more details see:[[BR]] http://www.cs.hut.fi/~enu/thesis.html" Peter Kovacs Milestone: none 379 Find odd cycles core hg main enhancement Alpar Juttner new 2010-07-02T23:58:23+02:00 23:58:23+02:00 We could extend the functions `bipartite()` and `bipartitePartitions()` so that they could return an odd cycle if the given graph is not bipartite. Peter Kovacs Milestone: none 63 Port metaheuristics core task Akos Ladanyi assigned 2010-07-03T17:57:27+02:00 14:04:23+01:00 "The following files are affected. - lemon/tabu_search.h - lemon/simann.h - test/simann_test.cc " Alpar Juttner Milestone: none 105 "Consider using the ""ziggurat"" method in Random::gauss()." core hg main enhancement Alpar Juttner new 2010-11-16T10:02:28+01:00 13:55:05+02:00 Currently, [source:lemon/random.h@716b220697a0#L825 Random::gauss()] uses a Box-Muller transformation based method. Ziggurat method is reported to be a better way of generating normally distributed random numbers, though one should check if it is indeed noticeably better in practice. Alpar Juttner Milestone: none 222 Network Simplex alg. for a simplified problem core hg main enhancement Alpar Juttner new 2011-01-09T17:50:39+01:00 07:40:59+01:00 "A simpler (but in fact equivalent) form of the Network Flow Problems when we have no upper limit on the arcs. We can also assume that the lower limit is 0 everywhere. In this case Network Simplex algorithms becomes much easier: - A basis is just a tree, and it's trivial to obtaine both the primal and the dual solutions from it. - A starting dual feasible solution is just a feasible potential w.r.t. the cost, so it can be computed by a shortest path algorithm. " Alpar Juttner Milestone: none 358 Runtime complexity for every algorithm documentation hg main enhancement Alpar Juttner new 2011-01-09T18:00:27+01:00 23:39:55+01:00 Some algorithms such as `MaxWeightedPerfectMatching` include the complexity of the runtime. Others such as `MaxMatching` do not. It might be nice to add this information to the documentation of every algorithm object. Ben Strasser Milestone: none 249 Bidirectional Bfs and Dijkstra core hg main enhancement Peter Kovacs assigned 2011-12-09T17:15:47+01:00 17:19:17+01:00 "It would be nice to have bidirectional Bfs and Dijkstra implementation in LEMON for the s-t shortest path problem. Theoretically it is simple: the algorithm should be started ""in parallel"" from the source node s on the original graph and from the target node t on the reversed graph. As soon as we have a node u for which both direction have set the final ''dist'' and ''pred'' values, we can finish searching and construct the s->t path form the s->u path and the opposite of the t->u path. It could be faster by about a factor of two due to smaller search spaces. However it is not clear for me how difficult it would be to implement it." Peter Kovacs Milestone: none 376 A star (A*) algorithm core hg main enhancement Peter Kovacs assigned 2011-12-09T17:17:01+01:00 19:28:11+02:00 "It would be nice to have an A-star (A*) algorithm implementation in LEMON. Additionally, a bidirectional version could also be implemented (see also: #249). http://en.wikipedia.org/wiki/A*_search_algorithm" Peter Kovacs Milestone: none 412 Implement Dinitz algorithm for the max flow problem core hg main task Alpar Juttner new 2012-01-11T10:42:32+01:00 17:30:53+01:00 "It would be nice to implement the ""original"" Dinitz algorithm for the max flow problem. We have an implementation that uses dynamic trees, but it would be better to have a separate implementation without dynamic trees, as well." Peter Kovacs Milestone: none 413 Implement Young-Tarjan-Orlin algorithm for min mean cycle core hg main enhancement Alpar Juttner new 2012-01-11T10:43:26+01:00 17:37:01+01:00 "It would be nice to implement the Young-Tarjan-Orlin algorithm for the minimum mean cycle problem. According to several survey papers, it is one of the fastest solution methods for this problem (and its extension: the optimum cycle ratio problem). Another method that is highly efficient is Howard's algorithm, which is already implemented in LEMON." Peter Kovacs Milestone: LEMON 1.4 release 374 Functions for weakly connected components core hg main enhancement Alpar Juttner new 2013-03-02T18:07:15+01:00 16:17:46+02:00 "I suggest to have the following functions: {{{ #!cpp bool weaklyConnected (const Digraph &graph); int countWeaklyConnectedComponents (const Digraph &graph); int weaklyConnectedComponents (const Digraph &graph, NodeMap &compMap); }}} which would work the same way as `connected()`, `countConnectedComponents()` and `connectedComponents()` for the undirected version of the digraph. These proposed functions could be implemented easily using the `Undirector` adaptor and the undirected connectivity tools." Peter Kovacs Milestone: none 415 Custom cost types in NetworkSimplex core hg main enhancement Alpar Juttner new 2013-03-07T09:04:13+01:00 16:29:05+01:00 "Duraid Madina proposed an enhancement for `NetworkSimplex`: {{{ I have been using Lemon's network-simplex code for some time. Recently I wanted to use it with a custom Cost type and int Value type. In order to make this simpler, I have patched network_simplex.h so that the Cost class/type does not need/use operator*. At the moment, my patch requires that a custom Cost class must still implement operator* for (Cost, int) pairs. However, this is only for the initialization of ART_COST, and for totalCost(). It is also possible to eliminate these uses of operator*, but I have not needed to make these changes. The patch consists of three things: 1) the addition of a unitMul() function for multiplying Costs by ""unit values"" -1, 0 and 1 2) changing all occurences of Cost*unit value multipication to calls to unitMul() 3) a small change to totalCost() allowing exact total costs to be computed (requires the custom Cost class to provide Cost*Value multiplication, but not Cost*Cost multiplication.) There is one potential problem with the patch. On x86 machines and ""int"" Cost type, there is a speed penalty of about 15%. This can be eliminated through template specialization of the unitMul function for ""int"" Costs, but I have not done this for two reasons: 1) It would be great if you could do it in your preferred ""LEMON style"" 2) On some machines, such as ia64 (Itanium), the unitMul in the attached patch actually leads to a speed _gain_ of about 10%. The reason is that there does not seem to be any compiler which can detect that the ""*"" can be replaced by predicated/conditional clears and negations. So rather than constant tempate specialization, perhaps the choice of unitMul() implementation could be left to the user, with a simple ""*""-based implementation as default? Anyway, I hope this patch makes sense and you consider it for inclusion in your code. I would like to conclude by saying a big ""thank you!"" for the excellent LEMON library!! Yours sincerely, Duraid MADINA RIKEN }}}" Peter Kovacs Milestone: LEMON 1.4 release 252 Smaller iterator classes for some graph structures core hg main enhancement Peter Kovacs assigned 2013-03-07T09:51:08+01:00 17:58:58+01:00 "All the `NodeIt`, `ArcIt`, `EdgeIt` etc. iterator classes stores a pointer for the underlying (di)graph. However it wouldn't be necessary in some cases. E.g. `SmartDigraph::next(Node&)` and `SmartDigraph::next(Arc&)` are static functions. Thus `SmartDigraph::NodeIt` and `SmartDigraph::ArcIt` could be implemented without a pointer to the graph. The three `next()` functions of `SmartGraph` are not static, but they could/should be. The special graph structures (`FullGraph`, `HypercubeGraph`, `GridGraph`) also have static `next()` functions." Peter Kovacs Milestone: LEMON 1.4 release 318 Document MapIt, ConstMapIt and ItemIt classes of standard maps documentation hg main enhancement Peter Kovacs new 2013-03-07T10:44:01+01:00 08:09:40+02:00 "There are three iterator classes: `MapIt`, `ConstMapIt` and `ItemIt` for all standard graph maps, which seem to be useful. However they are neither documented nor tested in the concept classes. I think, they sohuld be. This ticket is a follow-up of #311." Peter Kovacs Milestone: none 183 Improve doc of Elevator core hg main enhancement Peter Kovacs assigned 2013-03-07T10:44:17+01:00 11:22:17+01:00 "The documentation should describe the differences between {{{Elevator}}} and {{{LinkedElevator}}} and give some hints about their performance on specific tasks. This is a follow-up of #174." Alpar Juttner Milestone: LEMON 1.4 release 431 Remember the lastly evaluated arcs in Circulation (and in Preflow) core hg main enhancement Alpar Juttner new 2013-03-09T11:07:35+01:00 07:53:37+01:00 "The [attachment:23a4fa3a7e62.patch attached patch] changes the behavior of `Circulation` class. For each node, we now store the lastly evaluated arc, so we can continue from this arc instead of starting from the beginning when the node is evaluated again. A test on a network of 32768 nodes and 262892 arcs (generated by `netgen`) shows a running time improvement of 24%. A much more comprehensive test would of course be necessary, but this number seems quite promising. The same idea can (should?) also be applied to the `Preflow` class." Alpar Juttner Milestone: LEMON 1.4 release 33 Benchmarking core task Alpar Juttner new 2013-08-02T14:33:35+02:00 11:51:41+01:00 "Lemon seriously needs a benchmarking environment to test - the effect of implementation changes on the running time - performance of different compilers ans optimization settings This environment should contain - scripts for automated testing. - carefully chosen set test files and graph generators. " Alpar Juttner Milestone: LEMON 1.4 release 3 ListGraph should store/update the number of edges and nodes core hg main enhancement Peter Kovacs assigned 2013-08-02T14:34:26+02:00 13:10:42+01:00 "Counting the number of edges and nodes is a frequent graph operation. Now, it takes linear time to get these values. Instead we might store these values and update them at every edge/node addition and deletion. Of course this change would slow down these operations a bit. This ticket is a copy of report !#8 of the old bug tracking system. It refers to svn trunk -!r2460." Alpar Juttner Milestone: LEMON 1.4 release 462 Extended run time checking in debug mode core hg main enhancement Alpar Juttner new 2013-10-26T20:47:31+02:00 10:17:23+02:00 "When using more graph instances of the same time (e.g. `ListDigraph`) in a code, it is a very common error that a `Node` or `Arc` is used with a different graph that they actually belong to. For example a `NodeMap` may be indexed by a node belonging to another graph. These kind of errors remain hidden during the compilation. I propose adding a pointer to the owner graph to each `Node` and `Arc` objects, and check their the validity of the relevant graph and map operations. This feature would be turned on ''in debug mode only''. Two things are worth checking: - The item should belong to the corresponding graph - The item should be valid (i.e. not `INVALID` and point to an existing item) Here is a --- maybe incomplete --- list where checking could be made: - `source()`, `target()`, `u()`, `v()`, `runningNode()`, `baseNode()` - `id()` - constructors of the iterators - `operator++()` of the iterators (validity check only) - `*Map<>::operator[]()'`, `*Map<>::set()'`, - `changeSource()`, `changeTarget()`, `reverse()`" Alpar Juttner Milestone: none 201 Delaunay triangulation core hg main enhancement Balazs Dezso new 2014-10-12T17:22:03+02:00 12:13:23+01:00 "Delunay triangulation is actually implemented in {{{tools/lgf-gen.cc}}}, but it would be nice to have it as a separate tool in the core library. " Alpar Juttner Milestone: LEMON 1.4 release 594 STL syle iterators - phase II. core hg main enhancement Alpar Juttner new 2015-10-08T10:31:25+02:00 20:46:57+02:00 STL style iterators could be also added to other places. These possibilities should be discussed here. Alpar Juttner Milestone: LEMON 1.5 release 146 Cheap copy of maps (reference counting) PHASE II. core enhancement Alpar Juttner assigned 2016-07-15T13:22:32+02:00 16:06:45+02:00 This is a follow-up of #137. Alpar Juttner Milestone: LEMON 1.5 release 216 Member in Circulation to transform the solution to a basic one core hg main enhancement Peter Kovacs assigned 2016-07-15T13:28:42+02:00 07:17:27+01:00 "Having a basic solution for the circulation problem is sometime quite useful, e.g. it can be used as a staring solution of the primal Network Simplex algorithm. The interface should also provide the tree (or forest) of the basis. " Alpar Juttner Milestone: LEMON 1.5 release 217 Subroutine in Preflow alg. to make the solution cycle-less core hg main enhancement Peter Kovacs assigned 2016-07-15T13:28:55+02:00 07:21:47+01:00 "The title says everything. See also #218." Alpar Juttner Milestone: LEMON 1.5 release 218 Path decomposition subroutine in Preflow. core hg main enhancement Peter Kovacs assigned 2016-07-15T13:29:07+02:00 07:22:08+01:00 "The title says everything. See also #217." Alpar Juttner Milestone: LEMON 1.5 release 221 Primal Network Simplex algorithm with given starting solution core hg main enhancement Peter Kovacs assigned 2016-07-15T13:29:23+02:00 07:32:24+01:00 If a primal solution is available, then we don't need the extension of the underlying graphs, which may speed up the algorithm sometimes. Alpar Juttner Milestone: LEMON 1.5 release 224 Static graph maps core hg main enhancement Balazs Dezso new 2016-07-15T13:29:50+02:00 21:02:38+01:00 "Sometimes it would be nice to have a map which is not registered in the alteration notifier of the graph. One reason might be running time efficiency, but the more important is multi-thread applications (see #223). Currently, it is not safe to run say two Dijkstra algorithms on the same graph in parallel, as they would allocate maps and register them into the alteration notifier simultaneously, which is not safe. Changing these map allocations to static one would solve this problem. My suggestion is to use the standard maps with a special constructor for this purpose, e.g. {{{ ListGraph::NodeMap map1(g,STATIC); ListGraph::NodeMap map1(g,15,STATIC); }}} or {{{ ListGraph::NodeMap map1(STATIC,g); ListGraph::NodeMap map1(STATIC,g,15); }}} See also #223. ''''" Alpar Juttner Milestone: LEMON 1.5 release 225 Binary graph file format core hg main enhancement Alpar Juttner new 2016-07-15T13:31:16+02:00 07:52:21+01:00 "The {{{.lgf}}} format is nice, but the files become extremely large for big graphs. In some cases it would be nice to have a version of {{{GraphReader}}}/{{{GraphWriter}}} using a much more condensed binary format while providing close to the same API and feature set." Alpar Juttner Milestone: LEMON 1.5 release 238 Min cut iterators in Preflow core hg main enhancement Alpar Juttner new 2016-07-15T13:32:03+02:00 23:02:45+01:00 It would be nice to have iterators for obtaining the min. cut in `Preflow` class. E.g. there could be `MinCutNodeIt` and `MinCutArcIt` similarly to the ones in `GomoryHu` class (but note that in `Preflow` we have directed cuts). Peter Kovacs Milestone: LEMON 1.5 release 244 Support min. cost max. flow in MCF classes core hg main enhancement Peter Kovacs assigned 2016-07-15T13:32:19+02:00 22:29:41+01:00 "The new concept of the min cost flow classes (see #234) makes it easy to provide interface for the min. cost maximum flow problem, too. For example, there could be a `maxFlow(Node s, Node t)` function, which could be used instead of `supplyMap()` and `stSupply()`. In this case `Preflow::runMinCut()` should be called to determine the max. flow value (instead of `Circualtion`), and the algorithm have to be initialized as if `stSupport()` was called with this flow value. However apart from that nothing have to be changed." Peter Kovacs Milestone: LEMON 1.5 release 246 s() and t() as an alias for source() and target() core hg main enhancement Alpar Juttner new 2016-07-15T13:32:58+02:00 16:11:03+01:00 "As we have `u()` and `v()` for undirected graphs, it seems to be a good idea to have shorter alias names for `source()` and `target()`, e.g. `s()` and `t()`, since they are among the most frequently used functions. What do you think about it?" Peter Kovacs Milestone: LEMON 1.5 release 227 Command line tool for executing various algorithms core hg main enhancement Alpar Juttner new 2016-07-15T13:34:29+02:00 08:38:13+01:00 "This tool would read a .lgf file and run an algorithm on it. Finally it would report about the result or write the solution into a file. It should provide a wide range of algorithms which could be selected with command line options. This is somewhat similar to that are proposed in #226, but I think they should be separate tools, as that one have a quite limited feature set, while this one will probably become a complex tool with tons of option with the time." Alpar Juttner Milestone: LEMON 1.5 release 251 More efficient graph copying core hg main enhancement Alpar Juttner new 2016-07-15T13:34:46+02:00 17:44:14+01:00 "Is there any way to make graph copying faster for graph types like `List(Di)Graph` and `Smart(Di)Graph`? Maybe we could have specialized versions of `(di)graphCopy()` for the cases when both types are the same, e.g. list or smart graph, which function would directly copy the vectors that represent the graph. I'm not sure about the implementation, but I think this method would have two advantages: - It could be faster. - It would keep the node, arc and/or edge ids and the order of the items. Now if you have a `SmartDigraph` and copies it to another `SmartDigraph` structure, then the iteration orders of the nodes and arcs are reversed." Peter Kovacs Milestone: LEMON 1.5 release 271 Provide output in dimacs-solver core hg main enhancement Alpar Juttner new 2016-07-15T13:36:19+02:00 00:05:42+02:00 "Currently dimacs-solver reports only the shortest path length (distance), the max flow value or the min flow cost. It would be better to provide the full solution in DIMACS format. For the max flow here is a relevant output format (from the webpage of A. V. Goldberg):[[BR]] http://www.avglab.com/andrew/CATS/maxflow_formats.htm This format can be used for min cost flow problems as well. I found an MCF solver that actually use this, see the attached sample file. However I didn't find such output format for shortest path problems. There are various formats for correctness checking and performance reporting, but they are very specific to the 9th DIMACS implementation challenge and follow a slightly different concept.[[BR]] http://www.dis.uniroma1.it/~challenge9/format.shtml Maybe we should invent a shortest path output format according to the other dimacs input/output formats, or only provide output for the flow problems." Peter Kovacs Milestone: LEMON 1.5 release 292 Checker functions for min cost flow core hg main enhancement Peter Kovacs assigned 2016-07-15T13:37:17+02:00 12:50:33+02:00 "Maybe we could have checker functions for the minimum cost flow algorithms according to the test file. E.g. `checkFeasibility()` and `checkOptimality()` or `checkFlow()` and `checkPotential()`. They would be similar to the checker functions of `Circulation`. However it is questionable whether these functions should be introduced to all MCF algorithms or we should have them separetly, since the implementation would be independent form the algorithms." Peter Kovacs Milestone: LEMON 1.5 release 297 Graph and map serializer core hg main enhancement Alpar Juttner new 2016-07-15T13:37:30+02:00 12:22:47+02:00 "For real distributed computing, it would be nice to have a ''serializer'' for the graphs and the map structures. By a ''serializer'' I mean a facility to represent a graph/map as a compact raw sequence of bytes that can be sent to another (local or remote) process and the graph/map can be reconstructed from it. The raw data format should be compact and easy to code and decode, however it cannot be independent from the underlying graph representation, as we must keep the node/arc IDs at the graph reconstruction. This proposal is somewhat related to #225." Alpar Juttner Milestone: LEMON 1.5 release 328 Heuristic MinCostFlow and MinCostMaxFlow core hg main enhancement Peter Kovacs assigned 2016-07-15T13:38:43+02:00 01:23:26+01:00 "It could be worthwhile to create a heuristic min cost flow solver class named `MinCostFlow`. It would have the same interface as the single algorithms, but it could try to select the best algorithm to run according to the parameters of the problem (size of the graph, density, max. capacity etc.). This class could be used in e.g. thew dimacs solver. Similarly, we could have a heuristic `MinCostMaxFlow` using `Preflow` and `MinCostFlow`. Or the interface of `MinCostFlow` could be extended to support min cost max flow. See also #244. This ticket is a follow-up of #180. " Peter Kovacs Milestone: LEMON 1.5 release 329 Sort outgoing arcs in the build() function of StaticDigraph core hg main enhancement Alpar Juttner new 2016-07-15T13:39:32+02:00 10:40:32+01:00 "In the `build()` function of `StaticDigraph` which takes another digraph as an argument, the outgoing arcs of each node are sorted with respect to their target nodes. It clearly makes the `build()` function (and copying a graph to `StaticDigraph`) somewhat slower. Preliminary tests showed a difference of about 15 percent. On the other hand, it could make the usage of the constructed graph more efficient due to better caching. However, the trade-off is not clear. I suggest to make this sorting optional (e.g. by adding a bool parameter to the `build()` function). However, the default option is of high importance here, since it will be used by `DigraphCopy`. This ticket is a follow-up of #68." Peter Kovacs Milestone: LEMON 1.5 release 346 Port the remaining shortest path algorithms core hg main task Alpar Juttner new 2016-07-15T13:41:08+02:00 14:10:36+01:00 "The following files are affected: - lemon/floyd_warshall.h - lemon/johnson.h - lemon/dag_shortest_path.h - test/all_pairs_shortest_path_test.cc This ticket is a follow-up of #51." Peter Kovacs Milestone: LEMON 1.5 release 351 Port the LP utilities core hg main task Balazs Dezso new 2016-07-15T13:41:21+02:00 00:07:03+01:00 "Revise and port the Lp utilities from SVN, namely - `lp_utils.h` - `lp_utils.cc`" Peter Kovacs Milestone: LEMON 1.5 release 373 Compile time assertion core hg main enhancement Alpar Juttner new 2016-07-15T13:43:33+02:00 16:06:30+02:00 "Compile time assertion would be useful in some cases (instead of LEMON_ASSERT). A possible solution is the following: {{{ #!cpp template struct STATIC_ASSERT_FAILURE; template <> struct STATIC_ASSERT_FAILURE {}; template struct static_assert_test{}; #define LEMON_COMPILE_ASSERT(x) \ typedef static_assert_test<\ sizeof(STATIC_ASSERT_FAILURE< (bool)( x ) >)>\ _static_assert_typedef_ }}} It could be used like that: {{{ LEMON_COMPILE_ASSERT(numeric_limits::is_integer); }}}" Peter Kovacs Milestone: LEMON 1.5 release 384 Adaptor class for complementary graph core hg main enhancement Balazs Dezso new 2016-07-15T13:50:18+02:00 23:12:35+02:00 It would be nice to have an adaptor class to obtain the complementary graph of a simple, undirected graph. Peter Kovacs Milestone: LEMON 1.5 release 385 QuadHeap instead of BinHeap in Dijkstra core hg main enhancement Alpar Juttner new 2016-07-15T13:50:56+02:00 23:33:32+02:00 "It is questionable whether `Dijkstra` should use `QuadHeap` instead of `BinHeap` by default. In theory, a fourary heap is at least as efficient as a binary heap independently of the actual use case. I made some benchmark tests in which `QuadHeap` turned out to be typically faster than `BinHeap`, especially when many `decrease()` operations are performed. See the benchmark results [attachment:ticket:313:heap_benchmark_results.txt here]. However, binary heap is the ""standard"" choice." Peter Kovacs Milestone: LEMON 1.5 release 394 Add supprt for lp_solve core hg main enhancement Alpar Juttner new 2016-07-15T13:52:55+02:00 07:21:21+02:00 "http://lpsolve.sourceforge.net/5.5/ http://sourceforge.net/projects/lpsolve/ " Alpar Juttner Milestone: LEMON 1.5 release 399 Missing getter and streaming operator for Node/Arc id core hg main enhancement Alpar Juttner new 2016-07-15T13:54:02+02:00 16:57:10+01:00 please implement a getter and streaming operator for the id field of the Node and Arc class. This would be very helpful. Always have to use the graph class is very inconvenient and sometimes not even possible. thx tobi_connect Milestone: LEMON 1.5 release 400 MPL LpSolver/MipSolver backend core hg main enhancement Alpar Juttner new 2016-07-15T13:54:13+02:00 06:33:02+01:00 "The idea is to write an LP/MIP interface that is able to build up the problem, but when solving, it first create an MPL file, call the external command line solver, then parse back the output of the solver. Of course it will be less efficient than using the C API of the same solver, but - it can be useful to have the LP program built up by our code in MPL format, so that we can play with the solver separately (e.g. for experimenting with the tuning options). - for some legal reason, it may simply be impossible to link the mip/lp solver to our code." Alpar Juttner Milestone: LEMON 1.5 release 407 Extend random_test.cc core hg main enhancement Balazs Dezso new 2016-07-15T13:55:36+02:00 17:00:54+01:00 This ticket is a follow-up of #101. Peter Kovacs Milestone: LEMON 1.5 release 409 Extend unionfind_test.cc core hg main enhancement Alpar Juttner new 2016-07-15T13:55:50+02:00 17:04:18+01:00 "The following classes should be tested: - `UnionFind` - `ExtendFindEnum` - `HeapUnionFind` This ticket is a follow-up of #101." Peter Kovacs Milestone: LEMON 1.5 release 425 API for giving back the state of Random core hg main enhancement Balazs Dezso new 2016-07-15T13:57:05+02:00 17:36:26+02:00 "In some cases, it would be nice if we could query the state (i.e. the current seed) of Random in a format that is savable to a text file and retrievable later. " Alpar Juttner Milestone: LEMON 1.5 release 451 Functionality to test graph data structure consistency core hg main enhancement Alpar Juttner new 2016-07-15T14:02:28+02:00 06:58:01+02:00 The graph implementations (and other complex data structures, too) could provide a `dsSelfCheck()` member function, which thoroughly tests the inner consistency of the underlying data structures. This could help testing the correctness of the graph operations, thus preventing us from bugs like #450. Alpar Juttner Milestone: LEMON 1.5 release 466 Extended std::vector<> core hg main enhancement Alpar Juttner new 2016-07-15T14:03:18+02:00 09:28:12+02:00 "Based upon the idea of #462. We could implement a wrapper around `std::vector<>` with the following two extra features. - A extra permanent iterator. It has the same functionality as `std::vector::iterator` but remains valid even when the vector is extended by new elements. Technically, it contains a pointer to the base vector plus an index. - An `index` type. In non-debug mode it is just a `size_t`, but in debug mode it also contains a pointer to the vector it indexes, thus `operator[]()` is able to check if the index indexes the right vector (and also if it is in the actual range). Both would be safer alternatives to referencing `std::vector<>`'s elements by integer indices." Alpar Juttner Milestone: none 357 Guidelines for run/init/start documentation hg main enhancement Alpar Juttner new 2016-09-12T14:42:15+02:00 23:36:53+01:00 "Please add a few guidelines to the documentation about what are the invariants, pre and post conditions guaranteed by all algorithm objects and about the intended usage pattern. This includes documenting whenever: * The graph object and/or map objects must be fully constructed when the constructor of the algorithm object is run. (This is relevant if the graph and the algorithms objects are member of the same class, as may happen with algorithm objects that use a graph transformation based reduction.) * At what point may the graph and the other algorithm parameters no longer be changed anymore without causing a crash or without invalidating the results. Calling start after changing the graph without rerunning init is allowed to crash. Changing the graph after start has completed should invalidate the results (or maybe not but in that case that behavior should be documented). * Must the destructor of the algorithm object run before running the destructor of the graph object?" Ben Strasser Milestone: LEMON 1.5 release 402 Maps don't initialize subseqnetly added graph elements to the map-constructor's initial value. core release branch 1.2 enhancement Alpar Juttner new 2016-09-12T14:49:13+02:00 00:30:42+01:00 "Greetings all. I'm experiencing a ( perceived ) problem with Maps. Maps ""know"" when new elements in a graph are added, and provide a default value. One of the two constructors for a map allows a user ( me ) to specify this default value. I expect that, all elements of a graph will receive that value upon map-construction, and I expect subsequent graph element additions to also take on that value. I observe that, all elements of a graph *do* receive the default value upon map-construction, but *do not* set my specified default-value when new elements are subsequently added to the graph. I have a test program, which I will attach. I also have a diff against lemon/bits/{array,vector}_map.h that attempt to remedy this situation, and hopefully reinforce my expected behaviour. Please advise on if this is in fact a bit, or if it is intentional by design and my understanding is incorrect." Charles Wilcox Milestone: LEMON 1.5 release 452 time_measure.h uses obsolete headears core hg main defect Alpar Juttner new 2016-09-12T14:49:38+02:00 15:20:07+02:00 "[source:lemon/time_measure.h@e344f0887c59 time_measure.h] includes obsolete (pre C++) headers, such as `unistd.h`, `sys/times.h` and `sys/time.h` which in turn define a couple of things in the global namespace. Using the C++ counterparts of these headers (I hope they exist) would be a better option. " Alpar Juttner Milestone: LEMON 1.4 release 261 Support floating-point data in min-cost flow algorithms core hg main enhancement Peter Kovacs reopened 2017-05-25T17:29:49+02:00 16:31:07+02:00 This is a follow-up of #254. Alpar Juttner Milestone: LEMON 1.4 release 597 VF2 (sub)graph isomoprism algorithm core hg main enhancement Alpar Juttner reopened 2018-10-18T18:07:24+02:00 12:09:18+02:00 "The changesets [a037254714b3], [2f479109a71d] and [f85ee41c84bc] implement a slightly modified version of the VF2 algorithm for finding isomorphic copy of a graph as subgraph of another. It can find either normal or induced subgraph, or an isomorphism between the two graphs. It is also capable of enumerating all possible embedding. Finally, nodes can be labeled in order to model different (i.e. unmatchable) node types. The function type interface can be considered final, the base class may be refined later. This development was sponsored by !QuantumBio Inc. " Alpar Juttner Milestone: LEMON 1.4 release 427 Create build() routine for StaticDigraph that allows # of arcs to be set explicitly core hg main enhancement Alpar Juttner new 2018-10-23T03:05:37+02:00 05:23:52+02:00 "Hello, I recently tried used StaticDigraph with an iterator that used a forward-only traversal concept, as it was a thin wrapper to some rather complicated underlying structures. The problem is that the std::distance() call cause the iterator to run through the entire set to get the number of arcs, even though this was something I knew beforehand. Rather than create some sort of clumsy workaround, I found it easy to add another version of build() that permitted one to pass in the number of arcs explicitly. It's possible that mine is a rare case, but in case people are interested, here is a patch that does this. It's complete with appropriate documentation changes." Hoyt Koepke Milestone: LEMON 1.5 release 59 Port the remaining spanning tree algorithms core task Alpar Juttner new 2018-10-26T13:12:57+02:00 13:49:48+01:00 "The following files are affected. - lemon/fredman_tarjan.h - lemon/prim.h " Alpar Juttner Milestone: LEMON 1.5 release 381 Simplified heaps without priority update core hg main enhancement Alpar Juttner new 2018-10-26T13:13:10+02:00 17:41:14+02:00 "The existing heap implementations in LEMON cointain an Item->int map to indicate the current location of each item. It is required to implement `increase()`, `decrease()`, `erase()`, etc. functions. However, simplified heaps could be implemented with a limited functionality (`push()`, `pop()`, `top()`, `prio()`, `size()`, `empty()`, `clear()`, etc.) without this cross reference map. For such heaps, the basic `push()` and `pop()` operations could be implemented more efficiently, but the duplications of items could not be avoided. A Dijkstra or Prim algorithm could be implemented with such heaps, but it would require slight modifications. A node should be pushed each time its distance label is updated (i.e. more than once in some cases), and the duplicate nodes should be skipped after each `pop()` operation. It would be nice to introduce such implementations in LEMON. I think, they would lead to better performance in many practical cases, because not too many duplications would be expected on typical graphs. However, there are some problems with this proposal. First, such heaps would not conform to the current heap concept. Second, using them would require different implementation of the algorithms." Peter Kovacs Milestone: LEMON 1.5 release 287 Specify argument order for ArgParser core hg main enhancement Alpar Juttner new 2018-10-26T13:13:22+02:00 13:04:08+02:00 "I think it would be nice if the order in which `ArgParser` prints out the arguments and their documentations would be able to be changed. A good example is lgf-gen, for which a lot of command line arguments are printed and the alphabetical order makes them more difficult to overview. I suggest two options: alphabetical order and the order in which the arguments were specified. The first one could be the default, but the second one could be selected as an alternative." Peter Kovacs Milestone: LEMON 1.5 release 345 Obtaining and storing the LP solution core hg main enhancement Alpar Juttner new 2018-10-26T13:13:33+02:00 12:48:59+01:00 "It would be nice if the LP and MIP solver interfaces provided functions for obtaining the LP solution at once. We could use a class that can store the solution efficiently, i.e. it should store variable-value pairs for the non-zero valued variables. This ticket is a follow-up of #326." Peter Kovacs Milestone: LEMON 1.5 release 426 Expose CBC/CPL original interface in CbcMip and ClpLp core hg main enhancement Alpar Juttner new 2018-10-26T13:13:47+02:00 06:54:27+02:00 Something like [http://lemon.cs.elte.hu/pub/doc/1.2.2/a00148.html GlpkBase::lpx*] would be a satisfactory solution. Alpar Juttner Milestone: LEMON 1.5 release 475 DigraphWriter<> always saves Arc label core hg main enhancement Alpar Juttner new 2018-10-26T13:14:00+02:00 10:32:55+02:00 The `DigraphWriter` class always saves an `label` map in the `@arcs` section, even if it is not given explicitly not Arcs are saved in the `@attributes` section. I think it is unnecessary to save an auto generated label map in this case. Alpar Juttner Milestone: LEMON 1.5 release 370 Edge coloring algorithms core hg main enhancement Alpar Juttner new 2018-10-26T13:37:30+02:00 06:33:16+02:00 "Hello, for a project I am working on I had to implement a couple of edge coloring algorithms. If there is any interest I could LEMON-ify them. A valid edge coloring is a coloring of the edges so that each node has no two incident edges colored in the same way. What is implemented is: * An edge map to store valid colorings and that supports the queries needed by the algorithms in a fast way. * An algorithm that colors bipartite graphs using at most as many colors as the maximum node degree. * Vizing's algorithm to color general simple graphs using at most as many colors as the maximum node degree + 1. * Test cases Both algorithms are in O(m*n) For general simple graphs it is not always possible to color them using only maximum node degree. An example is K_3. Determining if this is possible is NP-hard so Vizing's algorithm seems to be the best you can get within polynomial time. I've attached my code. Best regards, Ben Strasser " Ben Strasser Milestone: LEMON 1.5 release 375 Both lower and upper supply bounds in Network simplex core hg main enhancement Peter Kovacs assigned 2018-10-26T13:42:26+02:00 07:15:34+02:00 "The idea is to extend Network Simplex so that the form of the problems are fully compatible with the one used by the LP solvers i.e. {{{ m_l<=Ax<=m_u l<=x<=u }}}" Alpar Juttner Milestone: LEMON 1.5 release 363 Implementing a planar graph type core hg main enhancement Balazs Dezso new 2018-10-26T13:55:32+02:00 20:30:45+01:00 My goal is to implement classes for planar graphs. The !PlanarGraph class maintains a topology of nodes, edges and faces and provides algorithms that are characteristic to planar graphs. !PlaneGraph extends this functionality with geometric properties, such as node coordinates and arc shapes. gyorokp Milestone: LEMON 1.5 release 191 Benchmark questions related to Preflow core hg main enhancement Peter Kovacs new 2018-11-01T13:03:43+01:00 22:43:09+01:00 "There are some efficiency questions about the `Preflow` implementation, that require thorough benchmarking. - `Elevator` or `LinkedElevator` should be used by default? - The BFS implementation in the `init()` function could be made more efficient using only one vector and three indices (`first`, `last`, `new_level`). - We should try very large instances and check again whether the current heuristics and the constant 20 factor that is used for them are really optimal or not. - We should try Goldberg's new idea of partial augmentations. (However it should probably be a new class.)" Peter Kovacs 355 SCIP MipSolver backend core hg main enhancement Alpar Juttner new 2018-11-02T07:58:51+01:00 10:39:38+01:00 "The title says everything. Please find Ambros Gleixner's beta version implementation attached. His comments comes below. Sziasztok, attached is a beta version of the SCIP interface. There is one segfault bug which I somehow cannot figure out. I will have to solve this with my colleagues in Berlin. Do you have some more extensive test files for the MIP interfaces besides test/mip_test.cc? If so, I would be happy to run them. Üdv, ambros " Alpar Juttner Milestone: LEMON 1.4 release 616 Current version 1.3.1 Incompatible with SoPlex-4.0.0 core hg main defect Alpar Juttner new 2018-12-09T20:55:56+01:00 20:55:56+01:00 "First, it can't find the header because the header is in include/soplex/: {{{ /usr/ports/math/coin-or-lemon/work/lemon-1.3.1/lemon/soplex.cc:23:10: fatal error: 'spxout.h' file not found #include ^~~~~~~~~~ }}} Then it fails to compile: {{{ /usr/ports/math/coin-or-lemon/work/lemon-1.3.1/lemon/soplex.cc:44:7: error: static_cast from 'soplex::SoPlex *' to 'soplex::SPxLP *' (aka 'SPxLPBase *'), which are not related by inheritance, is not allowed (*static_cast(soplex)) = *(lp.soplex); ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /usr/ports/math/coin-or-lemon/work/lemon-1.3.1/lemon/soplex.cc:76:13: error: no member named 'addCol' in 'soplex::SoPlex' soplex->addCol(c); ~~~~~~ ^ /usr/ports/math/coin-or-lemon/work/lemon-1.3.1/lemon/soplex.cc:80:20: error: no member named 'nCols' in 'soplex::SoPlex' return soplex->nCols() - 1; ~~~~~~ ^ /usr/ports/math/coin-or-lemon/work/lemon-1.3.1/lemon/soplex.cc:87:13: error: no member named 'addRow' in 'soplex::SoPlex' soplex->addRow(r); ~~~~~~ ^ /usr/ports/math/coin-or-lemon/work/lemon-1.3.1/lemon/soplex.cc:91:20: error: no member named 'nRows' in 'soplex::SoPlex' return soplex->nRows() - 1; ~~~~~~ ^ }}} Please make a release that fixes the problem. FreeBSD 11.2 amd64 SoPlex-4.0.0 installed from the port. " yurivict Milestone: LEMON 1.4 release 168 Port bipartite matching algorithms core hg main task Alpar Juttner new 2019-01-26T14:46:41+01:00 13:02:18+01:00 "This ticket is a follow-up of #48. The following tools are affected: - lemon/bipartite_matching.h - lemon/pr_bipartite_matching.h (I really dislike this filename) - test/bipartite_matching_test.cc It also depends on #69 (the port of the bipartite graphs)." Alpar Juttner Milestone: LEMON 1.4 release 620 Infinite loop in Nagamochi-Ibaraki with floating-point capacities core hg main defect Alpar Juttner new 2019-02-08T13:20:39+01:00 21:22:22+01:00 Floating point errors can cause the current Nagamochi-Ibaraki-implementation to get stuck because no edges are contracted in the iteration. I fixed this by using `Tolerance` in the relevant place (see attached patch). I also added a test case for this issue. Malte Schürks Milestone: LEMON 1.4 release 618 Constrained time measure core hg main enhancement Alpar Juttner new 2019-05-15T22:11:35+02:00 10:53:32+01:00 "It is not simple to implement benchmarking tool in C++. One of the difficulties is that some algorithms can run for unacceptable long time on some inputs, so the benchmark running time can be impractical. There are workarounds for this problem. For example, we can blacklist some test cases for some algorithms, but this can be a tedious work, and it requires updates on algorithm changes. Other solution is to use a controller script which starts the benchmarking tool with different parameters, but this requires the separation of the controller tool and the benchmark tool. Instead of the previous solutions, I propose a time measure tool, which executes a function with a time constraint. Technically, this can be implemented with a forked subprocess in unix systems (WIN32 doesn't have proper tool for it). This solution is similar to using a controller script, but we don't need to split out the test cases to the script. My implementation is [7a1a282efbb4]." Balazs Dezso Milestone: LEMON 1.4 release 421 Better DAG test and topological ordering implementation core hg main enhancement Alpar Juttner new 2019-05-17T08:49:16+02:00 19:16:52+02:00 "Currently all these functions use Dfs with a custom visitor. I have a feeling that a direct algorithm might be faster and/or more memory efficient. The algorithm I propose is the following: - Compute the in-degree of all nodes and store them in a `NodeMap` `deg`. - Put all node `n` with `deg[n]==0` into a queue (or a stack) `q`. - While `q` is not empty: - Get a node `n` from `q`. This is the next node in the topological order. - For each out-arc `a` of `n`: - Decrease `deg[target(a)]` by 1 - If `deg[target(a)]==0` then put `target(a)` into `q` " Alpar Juttner Milestone: LEMON 1.4 release 621 Lemon and Boost: call of overloaded ‘ignore_unused_variable_warning(...)’ is ambiguous core hg main defect Alpar Juttner new 2019-05-23T11:43:16+02:00 11:46:46+01:00 "Hello dear team of LEMON. The error is as far as i can tell not new. I have seen back in 2013 there has been an attempt to address that issue here at LEMON in issue #294. As well as on the side of boost in the issue 9438 [https://svn.boost.org/trac10/ticket/9438#no1] and 514 [https://github.com/boostorg/geometry/pull/514] **But it happens still:** Because there are ambigous declarations for `ignore_unused_variable_warning(...)` in `boost` and `lemon` the RTree implementations of boost cannot be used with lemon nodes. Since on the side of boost/geometry the issue has not been tackled further, I would like to ask you if there is a chance of replacement or unambiguously calling ignore_unused_variable_warning() in LEMON. - OS: Ubuntu 18.04 Bionic Beaver - clang: 6.0 - lemon: 1.3.1 - boost: happened under 1.63 and was reproduced with boost 1.68 {{{ #include #include namespace bg = boost::geometry; namespace bgi = boost::geometry::index; using Point = boost::geometry::model::point; using Graph = lemon::ListDigraph; using Node = lemon::ListDigraph::Node; typedef std::pair Pair; using BoostRTree = bgi::rtree>; using BoostQueryResult = std::vector; int main() { Point one = Point(10, 51); Point two = Point(10, 51); BoostRTree rtreePair = BoostRTree(); Graph graph; Node dummy1 = graph.addNode(); Node dummy2 = graph.addNode(); rtreePair.insert(std::make_pair(one, dummy1)); return 0; } }}} Here is the first error instance of the compiler output. All output has ~200k characters... not sure you want to see it, since the error is raised in boost-code. {{{ In file included from /usr/include/boost/range/concepts.hpp:19:0, from /usr/include/boost/range/size_type.hpp:20, from /usr/include/boost/range/size.hpp:21, from /usr/include/boost/range/functions.hpp:20, from /usr/include/boost/range/iterator_range_core.hpp:38, from /usr/include/boost/lexical_cast.hpp:30, from /usr/include/boost/math/tools/convert_from_string.hpp:15, from /usr/include/boost/math/constants/constants.hpp:13, from /usr/include/boost/geometry/util/math.hpp:28, from /usr/include/boost/geometry/core/radian_access.hpp:33, from /usr/include/boost/geometry/geometry.hpp:43, from /usr/include/boost/geometry.hpp:17, from test.cpp:1: /usr/include/boost/concept_check.hpp: In instantiation of ‘boost::DefaultConstructible::~DefaultConstructible() [with TT = std::pair, lemon::ListDigraphBase::Node>*]’: /usr/include/boost/iterator/iterator_concepts.hpp:143:3: required from ‘static void boost::concepts::requirement::failed() [with Model = boost_concepts::ForwardTraversal, lemon::ListDigraphBase::Node>*>]’ /usr/include/boost/geometry/index/detail/varray.hpp:288:9: required from ‘boost::geometry::index::detail::varray::varray(Iterator, Iterator) [with Iterator = std::pair, lemon::ListDigraphBase::Node>*; Value = std::pair, lemon::ListDigraphBase::Node>; long unsigned int Capacity = 17]’ /usr/include/boost/geometry/index/detail/rtree/quadratic/redistribute_elements.hpp:116:24: required from ‘static void boost::geometry::index::detail::rtree::redistribute_elements::apply(Node&, Node&, Box&, Box&, const parameters_type&, const Translator&, Allocators&) [with Node = boost::geometry::index::detail::rtree::variant_leaf, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::allocators, lemon::ListDigraphBase::Node> >, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::node_variant_static_tag>, boost::geometry::index::detail::rtree::node_variant_static_tag>; Value = std::pair, lemon::ListDigraphBase::Node>; Options = boost::geometry::index::detail::rtree::options, boost::geometry::index::detail::rtree::insert_default_tag, boost::geometry::index::detail::rtree::choose_by_content_diff_tag, boost::geometry::index::detail::rtree::split_default_tag, boost::geometry::index::detail::rtree::quadratic_tag, boost::geometry::index::detail::rtree::node_variant_static_tag>; Translator = boost::geometry::index::detail::translator, lemon::ListDigraphBase::Node> >, boost::geometry::index::equal_to, lemon::ListDigraphBase::Node> > >; Box = boost::geometry::model::box >; Allocators = boost::geometry::index::detail::rtree::allocators, lemon::ListDigraphBase::Node> >, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::node_variant_static_tag>; boost::geometry::index::detail::rtree::redistribute_elements::parameters_type = boost::geometry::index::quadratic<16>]’ /usr/include/boost/geometry/index/detail/rtree/visitors/insert.hpp:164:17: required from ‘static void boost::geometry::index::detail::rtree::split::apply(boost::geometry::index::detail::rtree::split::nodes_container_type&, Node&, Box&, const parameters_type&, const Translator&, Allocators&) [with Node = boost::geometry::index::detail::rtree::variant_leaf, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::allocators, lemon::ListDigraphBase::Node> >, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::node_variant_static_tag>, boost::geometry::index::detail::rtree::node_variant_static_tag>; Value = std::pair, lemon::ListDigraphBase::Node>; Options = boost::geometry::index::detail::rtree::options, boost::geometry::index::detail::rtree::insert_default_tag, boost::geometry::index::detail::rtree::choose_by_content_diff_tag, boost::geometry::index::detail::rtree::split_default_tag, boost::geometry::index::detail::rtree::quadratic_tag, boost::geometry::index::detail::rtree::node_variant_static_tag>; Translator = boost::geometry::index::detail::translator, lemon::ListDigraphBase::Node> >, boost::geometry::index::equal_to, lemon::ListDigraphBase::Node> > >; Box = boost::geometry::model::box >; Allocators = boost::geometry::index::detail::rtree::allocators, lemon::ListDigraphBase::Node> >, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::node_variant_static_tag>; boost::geometry::index::detail::rtree::split::nodes_container_type = boost::geometry::index::detail::varray >, boost::variant, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::allocators, lemon::ListDigraphBase::Node> >, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::node_variant_static_tag>, boost::geometry::index::detail::rtree::node_variant_static_tag>, boost::geometry::index::detail::rtree::variant_internal_node, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16, 4>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::allocators, lemon::ListDigraphBase::Node> >, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16, 4>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::node_variant_static_tag>, boost::geometry::index::detail::rtree::node_variant_static_tag> >*>, 1>; typename boost::geometry::index::detail::rtree::elements_type::type>::type::value_type = boost::geometry::index::detail::rtree::ptr_pair >, boost::variant, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::allocators, lemon::ListDigraphBase::Node> >, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::node_variant_static_tag>, boost::geometry::index::detail::rtree::node_variant_static_tag>, boost::geometry::index::detail::rtree::variant_internal_node, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16, 4>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::allocators, lemon::ListDigraphBase::Node> >, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16, 4>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::node_variant_static_tag>, boost::geometry::index::detail::rtree::node_variant_static_tag> >*>; boost::geometry::index::detail::rtree::split::parameters_type = boost::geometry::index::quadratic<16>]’ /usr/include/boost/geometry/index/detail/rtree/visitors/insert.hpp:357:26: required from ‘void boost::geometry::index::detail::rtree::visitors::detail::insert::split(Node&) const [with Node = boost::geometry::index::detail::rtree::variant_leaf, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::allocators, lemon::ListDigraphBase::Node> >, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::node_variant_static_tag>, boost::geometry::index::detail::rtree::node_variant_static_tag>; Element = std::pair, lemon::ListDigraphBase::Node>; Value = std::pair, lemon::ListDigraphBase::Node>; Options = boost::geometry::index::detail::rtree::options, boost::geometry::index::detail::rtree::insert_default_tag, boost::geometry::index::detail::rtree::choose_by_content_diff_tag, boost::geometry::index::detail::rtree::split_default_tag, boost::geometry::index::detail::rtree::quadratic_tag, boost::geometry::index::detail::rtree::node_variant_static_tag>; Translator = boost::geometry::index::detail::translator, lemon::ListDigraphBase::Node> >, boost::geometry::index::equal_to, lemon::ListDigraphBase::Node> > >; Box = boost::geometry::model::box >; Allocators = boost::geometry::index::detail::rtree::allocators, lemon::ListDigraphBase::Node> >, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::node_variant_static_tag>]’ /usr/include/boost/geometry/index/detail/rtree/visitors/insert.hpp:326:18: [ skipping 8 instantiation contexts, use -ftemplate-backtrace-limit=0 to disable ] /usr/include/boost/variant/variant.hpp:2431:52: required from ‘typename Visitor::result_type boost::variant::apply_visitor(Visitor&) [with Visitor = boost::geometry::index::detail::rtree::visitors::insert, lemon::ListDigraphBase::Node>, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::detail::rtree::options, boost::geometry::index::detail::rtree::insert_default_tag, boost::geometry::index::detail::rtree::choose_by_content_diff_tag, boost::geometry::index::detail::rtree::split_default_tag, boost::geometry::index::detail::rtree::quadratic_tag, boost::geometry::index::detail::rtree::node_variant_static_tag>, boost::geometry::index::detail::translator, lemon::ListDigraphBase::Node> >, boost::geometry::index::equal_to, lemon::ListDigraphBase::Node> > >, boost::geometry::model::box >, boost::geometry::index::detail::rtree::allocators, lemon::ListDigraphBase::Node> >, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::node_variant_static_tag>, boost::geometry::index::detail::rtree::insert_default_tag>; T0_ = boost::geometry::index::detail::rtree::variant_leaf, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::allocators, lemon::ListDigraphBase::Node> >, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::node_variant_static_tag>, boost::geometry::index::detail::rtree::node_variant_static_tag>; TN = {boost::geometry::index::detail::rtree::variant_internal_node, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16, 4>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::allocators, lemon::ListDigraphBase::Node> >, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16, 4>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::node_variant_static_tag>, boost::geometry::index::detail::rtree::node_variant_static_tag>}; typename Visitor::result_type = void]’ /usr/include/boost/variant/detail/apply_visitor_unary.hpp:70:43: required from ‘typename Visitor::result_type boost::apply_visitor(Visitor&, Visitable&) [with Visitor = boost::geometry::index::detail::rtree::visitors::insert, lemon::ListDigraphBase::Node>, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::detail::rtree::options, boost::geometry::index::detail::rtree::insert_default_tag, boost::geometry::index::detail::rtree::choose_by_content_diff_tag, boost::geometry::index::detail::rtree::split_default_tag, boost::geometry::index::detail::rtree::quadratic_tag, boost::geometry::index::detail::rtree::node_variant_static_tag>, boost::geometry::index::detail::translator, lemon::ListDigraphBase::Node> >, boost::geometry::index::equal_to, lemon::ListDigraphBase::Node> > >, boost::geometry::model::box >, boost::geometry::index::detail::rtree::allocators, lemon::ListDigraphBase::Node> >, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::node_variant_static_tag>, boost::geometry::index::detail::rtree::insert_default_tag>; Visitable = boost::variant, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::allocators, lemon::ListDigraphBase::Node> >, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::node_variant_static_tag>, boost::geometry::index::detail::rtree::node_variant_static_tag>, boost::geometry::index::detail::rtree::variant_internal_node, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16, 4>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::allocators, lemon::ListDigraphBase::Node> >, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16, 4>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::node_variant_static_tag>, boost::geometry::index::detail::rtree::node_variant_static_tag> >; typename Visitor::result_type = void]’ /usr/include/boost/geometry/index/detail/rtree/node/variant_visitor.hpp:51:25: required from ‘void boost::geometry::index::detail::rtree::apply_visitor(Visitor&, boost::variant, boost::geometry::index::detail::rtree::variant_internal_node >&) [with Visitor = boost::geometry::index::detail::rtree::visitors::insert, lemon::ListDigraphBase::Node>, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::detail::rtree::options, boost::geometry::index::detail::rtree::insert_default_tag, boost::geometry::index::detail::rtree::choose_by_content_diff_tag, boost::geometry::index::detail::rtree::split_default_tag, boost::geometry::index::detail::rtree::quadratic_tag, boost::geometry::index::detail::rtree::node_variant_static_tag>, boost::geometry::index::detail::translator, lemon::ListDigraphBase::Node> >, boost::geometry::index::equal_to, lemon::ListDigraphBase::Node> > >, boost::geometry::model::box >, boost::geometry::index::detail::rtree::allocators, lemon::ListDigraphBase::Node> >, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::node_variant_static_tag>, boost::geometry::index::detail::rtree::insert_default_tag>; Value = std::pair, lemon::ListDigraphBase::Node>; Parameters = boost::geometry::index::quadratic<16>; Box = boost::geometry::model::box >; Allocators = boost::geometry::index::detail::rtree::allocators, lemon::ListDigraphBase::Node> >, std::pair, lemon::ListDigraphBase::Node>, boost::geometry::index::quadratic<16>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::node_variant_static_tag>; Tag = boost::geometry::index::detail::rtree::node_variant_static_tag]’ /usr/include/boost/geometry/index/rtree.hpp:1454:37: required from ‘void boost::geometry::index::rtree::raw_insert(const value_type&) [with Value = std::pair, lemon::ListDigraphBase::Node>; Parameters = boost::geometry::index::quadratic<16>; IndexableGetter = boost::geometry::index::indexable, lemon::ListDigraphBase::Node> >; EqualTo = boost::geometry::index::equal_to, lemon::ListDigraphBase::Node> >; Allocator = std::allocator, lemon::ListDigraphBase::Node> >; boost::geometry::index::rtree::value_type = std::pair, lemon::ListDigraphBase::Node>]’ /usr/include/boost/geometry/index/rtree.hpp:582:15: required from ‘void boost::geometry::index::rtree::insert(const value_type&) [with Value = std::pair, lemon::ListDigraphBase::Node>; Parameters = boost::geometry::index::quadratic<16>; IndexableGetter = boost::geometry::index::indexable, lemon::ListDigraphBase::Node> >; EqualTo = boost::geometry::index::equal_to, lemon::ListDigraphBase::Node> >; Allocator = std::allocator, lemon::ListDigraphBase::Node> >; boost::geometry::index::rtree::value_type = std::pair, lemon::ListDigraphBase::Node>]’ test.cpp:23:49: required from here /usr/include/boost/concept_check.hpp:139:37: error: call of overloaded ‘ignore_unused_variable_warning(std::pair, lemon::ListDigraphBase::Node>*&)’ is ambiguous ignore_unused_variable_warning(a); }}} " F.Meckel Milestone: none 200 Port sparse SubGraph adaptor from SVN core hg main task Balazs Dezso new 2019-07-10T14:04:36+02:00 11:45:53+01:00 "The {{{SubGraph}}} class in the 0.x series stores the unhidden edges/nodes as a double linked list (just as {{{ListGraph}}} does), therefore it provides better performance than the {{{SubGraphAdaptor}}} when the subgraph is sparse. {{{SubGraphAdaptor}}} has been renamed to {{{SubGraph}}} in the 1.x series, thus I suggest to call the linked list based implementation as {{{SparseSubGraph}}}." Alpar Juttner Milestone: LEMON 1.4 release 626 Bug in CBC ProblemType determination core hg main defect Alpar Juttner new 2019-07-29T07:45:30+02:00 07:45:30+02:00 "Péter Madarasi reports the following: Solving a MIP with CBC-vel, if the presolver determined the the problem is infeasible, then CbcMip::type() wrongly returns FEASIBLE. To fix it, [source:/lemon/lemon/cbc.cc#L391 line 391 of cbc.cc] should be changed to {{{ else if(_cbc_model->isProvenInfeasible() || _cbc_model->isInitialSolveProvenPrimalInfeasible()) return INFEASIBLE; }}}" Alpar Juttner Milestone: LEMON 1.4 release 622 unused variable in elevator.h core hg main enhancement Alpar Juttner new 2019-09-23T17:10:51+02:00 11:08:35+02:00 "There are some unused class private variables in elevator.h. For example, _items[i] for i > 0 (class Elevator); _item_num (class LinkedElevator). " zhaofeng-shu33 Milestone: LEMON 1.4 release 625 lemon preflow algorithm init with flowmap failed because of excess < 0 core hg main defect Alpar Juttner reopened 2019-09-23T18:22:32+02:00 13:39:48+02:00 "I use the returned flowMap of Preflow algorithm to initialize the next Preflow class. But it fails because of in the Preflow code, the excess check gives -1e-19 < 0. The test code can be seen at https://gitee.com/freewind201301/test_preflow/blob/master/test_preflow.cpp . Hope some tolerance can be added." zhaofeng-shu33 Milestone: LEMON 1.4 release 628 make find package failed core release branch 1.3 defect Alpar Juttner new 2020-01-09T09:06:31+01:00 09:06:31+01:00 "On Ubuntu >= 18.04, after installing `liblemon` by `make install` and use it in other packages, cmake throws error: By not providing ""Findlemon.cmake"" in CMAKE_MODULE_PATH this project has asked CMake to find a package configuration file provided by ""lemon"", but CMake did not find one. Could not find a package configuration file provided by ""lemon"" with any of the following names: lemonConfig.cmake lemon-config.cmake Add the installation prefix of ""lemon"" to CMAKE_PREFIX_PATH or set ""lemon_DIR"" to a directory containing one of the above files. If ""lemon"" provides a separate development package or SDK, be sure it has been installed. I use CMake Version >= 3.10 How to fix: `LEMONConfig.cmake` should be changed to `lemonConfig.cmake` in root `CMakeLists.txt`. ``` IF(UNIX) INSTALL( FILES ${PROJECT_BINARY_DIR}/cmake/LEMONConfig.cmake DESTINATION share/lemon/cmake ) ```" zhaofeng-shu33 Milestone: LEMON 1.4 release 633 Fixes fox gcc 9 core hg main defect Alpar Juttner new 2021-02-25T10:28:30+01:00 21:28:56+02:00 "The gcc 9.x report tons of warnings like {{{ /home/alpar/projects/LEMON/hg/comptest-main/lemon/concepts/graph_components.h:527:15: error: implicitly-declared ‘lemon::concepts::Digraph::Node& lemon::concepts::Digraph::Node::operator=(const lemon::concepts::Digraph::Node&)’ is deprecated [-Werror=deprecated-copy] 527 | node=INVALID; | ~~~~^~~~~~~~ In file included from /home/alpar/projects/LEMON/hg/comptest-main/test/max_flow_test.cc:25: /home/alpar/projects/LEMON/hg/comptest-main/lemon/concepts/digraph.h:78:9: note: because ‘lemon::concepts::Digraph::Node’ has user-provided ‘lemon::concepts::Digraph::Node::Node(const lemon::concepts::Digraph::Node&)’ 78 | Node(const Node&) { } | ^~~~ }}} The patch attached makes an attempt to fix it. Some of the changes, and event some of the related part of the current code is strange even for myself. So this patch definitely needs a thorough review." Alpar Juttner Milestone: LEMON 1.4 release 650 MaxWeightedPerfectMatching fails for some graphs core hg main defect Alpar Juttner new 2021-07-03T20:37:02+02:00 17:05:41+02:00 "`MaxWeightedPerfectMatching` fails to find a solution for some graphs (i.e. `MaxWeightedPerfectMatching.run()` returns `false`). I attach 4 graphs which fail (`failing_graph_i.lgf` for `i=1,2,3,4`), as well as one which succeeds (`working_graph.lgf`), drawn from the same distribution, for comparison. The attached file `main.cpp` attempts to solve the MWPM problem using `lemon::MaxWeightedPerfectMatching` for these graphs and output success/failure. All five graphs are drawn from the same distribution (from which >1% of graphs fail), however for `failing_graph_1.lgf` and `failing_graph_2.lgf` I changed all the edge weights to 1, and the MWPM problem still fails (i.e. the problem seems to be independent of the choice of edge weights). I have tested this using versions `lemon-main-a278d16bd2d0` and `lemon-1-3-e5af35e6c93f` (both fail)." Oscar Higgott Milestone: LEMON 1.4 release 660 Drop support for C++98 core hg main enhancement Alpar Juttner new 2021-11-26T15:10:21+01:00 15:10:21+01:00 The title explains everything. Alpar Juttner Milestone: LEMON 1.4 release 631 Lemon c++20 compatibility patch core hg main defect Alpar Juttner new 2021-12-13T17:25:37+01:00 13:52:10+02:00 "From Kevin Tew: This feature was remove in c++20. https://en.cppreference.com/w/cpp/memory/allocator/destroy replace with https://en.cppreference.com/w/cpp/memory/allocator_traits/destroy " Alpar Juttner Milestone: none 296 Multicommodity flow algorithms core hg main task Peter Kovacs assigned 2021-12-13T17:47:31+01:00 18:47:21+02:00 It would be important to implement various multicommodity flow algorithms in LEMON. Approximation (and maybe exact) solution methods for fractional, integral and unsplittable multicommodity flow problems. Peter Kovacs Milestone: LEMON 1.4 release 658 CMake Rework core hg main enhancement Alpar Juttner new 2022-07-13T18:18:58+02:00 16:31:57+02:00 "Major rework of CMake for easier consumption in other projects. Minimum CMake version now 3.15. The major benefit of this is that consumption of LEMON from other projects is now really easy using `FetchContent` as shown in the demo. Also: - Added copyright headers - Explicit building options and disabled `Maintainer` options by default " David Torres Sanchez Milestone: LEMON 1.4 release 668 Crash in lgf_reader_writer_test core hg main defect Alpar Juttner new 2022-07-14T11:25:29+02:00 11:25:29+02:00 "The lgf_reader_writer_test test crashes for my. I am using the latest development version. Here's a stack trace from AddressSanitizer: {{{ ==61012==ERROR: AddressSanitizer: stack-use-after-scope on address 0x7ffee35a9ce0 at pc 0x00010cb7d0fe bp 0x7ffee35a8e10 sp 0x7ffee35a8e08 READ of size 4 at 0x7ffee35a9ce0 thread T0 #0 0x10cb7d0fd in lemon::SmartGraphBase::Arc::operator lemon::SmartGraphBase::Edge() const smart_graph.h:455 #1 0x10cb7cb7d in lemon::_writer_bits::GraphArcLookUpConverter::operator()(lemon::SmartGraphBase::Arc const&) lgf_writer.h:252 #2 0x10cb7c897 in lemon::_writer_bits::ValueStorage >::get() lgf_writer.h:190 #3 0x10cb86481 in lemon::GraphWriter::writeAttributes() lgf_writer.h:1549 #4 0x10c6a0694 in lemon::GraphWriter::run() lgf_writer.h:1573 #5 0x10c696a0e in checkGraphReaderWriter() lgf_reader_writer_test.cc:394 #6 0x10c6c1600 in main lgf_reader_writer_test.cc:572 #7 0x7fff5e6013d4 in start (libdyld.dylib:x86_64+0x163d4) Address 0x7ffee35a9ce0 is located in stack of thread T0 at offset 2208 in frame #0 0x10c69422f in checkGraphReaderWriter() lgf_reader_writer_test.cc:352 This frame has 71 object(s): [32, 368) 'graph' (line 354) [432, 436) 'n1' (line 355) [448, 452) 'n2' (line 356) [464, 468) 'n3' (line 357) [480, 484) 'e1' (line 359) [496, 500) 'agg.tmp' [512, 516) 'agg.tmp9' [528, 532) 'e2' (line 360) [544, 548) 'agg.tmp16' [560, 564) 'agg.tmp17' [576, 624) 'node_map' (line 362) [656, 704) 'edge_map' (line 367) [736, 784) 'arc_map' (line 371) [816, 820) 'ref.tmp' (line 372) [832, 836) 'agg.tmp61' [848, 852) 'ref.tmp73' (line 373) [864, 868) 'agg.tmp74' [880, 884) 'ref.tmp86' (line 374) [896, 900) 'agg.tmp87' [912, 916) 'ref.tmp99' (line 375) [928, 932) 'agg.tmp100' [944, 948) 'attr' (line 377) [960, 1224) 'os' (line 379) [1296, 1520) 'writer' (line 380) [1584, 1608) 'ref.tmp114' (line 382) [1648, 1672) 'ref.tmp120' (line 383) [1712, 1713) 'ref.tmp123' (line 383) [1728, 1752) 'ref.tmp130' (line 384) [1792, 1816) 'ref.tmp138' (line 385) [1856, 1857) 'ref.tmp141' (line 385) [1872, 1896) 'ref.tmp148' (line 386) [1936, 1960) 'ref.tmp156' (line 387) [2000, 2001) 'ref.tmp159' (line 387) [2016, 2040) 'ref.tmp166' (line 388) [2080, 2104) 'ref.tmp174' (line 389) [2144, 2168) 'ref.tmp182' (line 390) [2208, 2212) 'ref.tmp185' (line 390) <== Memory access at offset 2208 is inside this variable [2224, 2228) 'agg.tmp186' [2240, 2264) 'ref.tmp197' (line 391) [2304, 2328) 'ref.tmp205' (line 392) [2368, 2369) 'ref.tmp208' (line 392) [2384, 2736) 'exp_graph' (line 397) [2800, 2848) 'exp_node_map1' (line 398) [2880, 2928) 'exp_node_map2' (line 399) [2960, 3008) 'exp_edge_map1' (line 400) [3040, 3088) 'exp_edge_map2' (line 401) [3120, 3168) 'exp_arc_map1' (line 402) [3200, 3248) 'exp_arc_map2' (line 403) [3280, 3284) 'exp_n2' (line 404) [3296, 3300) 'exp_e1' (line 405) [3312, 3316) 'exp_a1' (line 406) [3328, 3332) 'exp_attr1' (line 407) [3344, 3348) 'exp_attr2' (line 408) [3360, 3632) 'is' (line 410) [3696, 3720) 'ref.tmp237' (line 410) [3760, 4280) 'reader' (line 411) [4416, 4440) 'ref.tmp248' (line 413) [4480, 4504) 'ref.tmp256' (line 414) [4544, 4545) 'ref.tmp259' (line 414) [4560, 4584) 'ref.tmp266' (line 415) [4624, 4648) 'ref.tmp274' (line 416) [4688, 4689) 'ref.tmp277' (line 416) [4704, 4728) 'ref.tmp284' (line 417) [4768, 4792) 'ref.tmp292' (line 418) [4832, 4833) 'ref.tmp295' (line 418) [4848, 4872) 'ref.tmp302' (line 419) [4912, 4936) 'ref.tmp310' (line 420) [4976, 5000) 'ref.tmp318' (line 421) [5040, 5064) 'ref.tmp326' (line 422) [5104, 5128) 'ref.tmp334' (line 423) [5168, 5169) 'ref.tmp337' (line 423) HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork (longjmp and C++ exceptions *are* supported) SUMMARY: AddressSanitizer: stack-use-after-scope smart_graph.h:455 in lemon::SmartGraphBase::Arc::operator lemon::SmartGraphBase::Edge() const }}} Instructions to reproduce: {{{ mkdir build && cd build cmake .. -DCMAKE_BUILD_TYPE=Debug -DCMAKE_CXX_FLAGS='-fno-omit-frame-pointer -fsanitize=address' cmake --build . --target check }}} " Szabolcs Horvát Milestone: LEMON 1.4 release 669 Mailing lists no longer work core hg main defect Alpar Juttner new 2022-07-14T12:07:06+02:00 12:07:06+02:00 "Yesterday I sent an email to the LEMON User mailing list, but message sending failed with the following address: {{{ There was a temporary problem while delivering your message to lemon-user@lemon.cs.elte.hu. Gmail will retry for 47 more hours. You'll be notified if the delivery fails permanently. }}} I notice that the last message is from 2018, so it must have been non-functional since then. Please either restore functionality or clearly indicate on the website that the mailing list is no longer in use. ---- P.S. If you migrated to GitHub, as requested in #656, you could replace the mailing lists with GitHub Discussions. You would no longer need to maintain a list server. There are other free options for open source projects as well, such as [Discourse](https://blog.discourse.org/2018/11/free-hosting-for-open-source-v2/)" Szabolcs Horvát Milestone: LEMON 1.4 release 671 best yugioh booster boxes core hg main defect Alpar Juttner new 2022-10-03T08:10:27+02:00 08:10:27+02:00 This booster box is considered among the most expensive ones among all the boxes available on Yugioh cards. [best yugioh booster boxes] https://www.webtechmantra.com/yugioh-booster-boxes-to-earn-money/Of course, this is not among the top pick of booster boxes because the cards available are not so expensive, but their prices are still quite high. This was the first release of booster cards in 2019 that contained 100 cards vinod129 Milestone: LEMON 1.4 release 672 Bug in the Vf2 implementations core hg main defect Alpar Juttner new 2022-10-14T15:46:48+02:00 15:46:48+02:00 "In [https://lemon.cs.elte.hu/trac/lemon/browser/lemon/lemon/vf2.h#L181 vf2.h line 181] and in [https://lemon.cs.elte.hu/trac/lemon/browser/lemon/lemon/vf2pp.h#L226 vf2pp.h line 226], we may index a `NodeMap` with `INVALID` --- to which we set a reference and do not use it later. The code seems to work as it is, but these could cause segmentation fault. The attached patch fixes both issues. " Peter Madarasi Milestone: LEMON 1.4 release 646 Bug in binomial heap with ties core hg main defect Alpar Juttner new 2022-10-14T15:51:09+02:00 18:01:58+01:00 "In the current implementation, it may happen that the top-priority item (i.e. _min) is not a root of the heap. This happens because when we merge the minimum-priority item (_min) tree with an other tree whose root has the same priority, we do not make sure that the new root will be _min. This causes a lot of problems, because we may try to pop a non-root item. The following code snippet demonstrates the issue. {{{ ListDigraph g; ListDigraph::Node v0 = g.addNode(); ListDigraph::Node v1 = g.addNode(); ListDigraph::NodeMap ref(g,-1); lemon::BinomialHeap > h(ref); h.push(v0,0); h.push(v1,0); h.pop(); h.pop(); }}} Before the pops, the heap consists of a single tree with root v1 and its only child is v0. However, the top priority item in the current implementation is v0, which is not a root in the heap! This causes an infinite loop in BinomialHeap::unlace. One possible fix of this issue is to replace [https://lemon.cs.elte.hu/trac/lemon/browser/lemon/lemon/binomial_heap.h#L177 line 177 of binomial_heap.h] with {{{ _min=findMin(); }}} " Peter Madarasi Milestone: LEMON 1.4 release 673 aboutcb core hg main defect Alpar Juttner new 2022-10-17T11:13:51+02:00 11:13:51+02:00 با ارائه بروزترين مطالب، گام بلندي در راستاي ارتقاي سطح علمي مخاطبين خود برداشته ايم. [https://30ib.ir/ سيب] اميد است مطالعه اين مطالب مفيد واقع شود. aboutcb Milestone: LEMON 1.4 release 674 nsystem core hg main defect Alpar Juttner new 2022-11-01T12:00:43+01:00 12:00:43+01:00 "پد سلولزی چیست؟ پد سلولزی یکی از کارآمدترین تکنیک های مورد استفاده در سیستم های گرمایشی به ویژه سرمایشی مانند کولر آبی محسوب می شود. [https://nikasaan.com/category/175-cellulose-pad/ قیمت پد سلولزی] این پدها، از ورقه های کاغذی سلولزی ساخته می شوند. ورقه های سلولزی در این پد، بسیار منظم و یکپارچه در هم تنیده شده اند. و خاصیت ترشدگی زیادی به خود گرفته اند. همچنین این کاغذ های سلولزی، به دلیل جنس و نوع چینشان کنار یکدیگر؛ در برابر هرگونه مواد شیمیایی و فساد مقاوم هستند. جدا از مقاومت و داشتن خاصیت ترشدگی بالا، مزیت های دیگر را هم دارد که در ادامه به آن پرداخته شده است. معنای دقیق پد سلولزی پد سلولزی کولر محصولی است که مواد اولیه آن از سلولز (Cellulose) ماده ای که از دیواره ی سلولی گیاهان ساخته می شود ، که خاصیت جذب آب بالایی دارد. [https://nikasaan.com/category/176-greenhouse-cellulose-pad/ پد سلولزی گلخانه] و از لایه های متعدد و نازک (پد، Pad) ساخته می شود." nsystem Milestone: LEMON 1.4 release 656 migrate to github core hg main defect Alpar Juttner new 2022-11-14T16:15:47+01:00 09:42:51+02:00 it would be great, if lemon would be available on github andrei Milestone: LEMON 1.4 release 675 تنزيل متجر التطبيقات Google Play APK core hg main defect Alpar Juttner new 2022-12-30T07:06:01+01:00 07:06:01+01:00 "Play Store يتيح لك تنزيل تطبيقات Android وتثبيتها في Google play بشكل رسمي وآمن. إنه متجر Google الرسمي والبوابة الإلكترونية لتطبيقات Android والألعاب والمحتويات الأخرى لهاتفك أو جهازك اللوحي الذي يعمل بنظام Android. [https://www.filetodown.com متجر بلاي] Google Play هو قلب نظام التشغيل Android. بدونها ، لن يتمكن المستخدم العادي من جعل جهاز Android يعمل بشكل صحيح. لذلك في هذه المقالة ، سنخبرك بأحدث تحديثات متجر Google Play وأحدث إصدار قيد التشغيل. [https://www.googleplay-apk.com جوجل بلاي] تمامًا كما تمتلك Apple متجر التطبيقات الخاص بها ، تمتلك Google Google Play! إنه مكان ضخم ويقدم الكثير من المحتوى لمستخدميه. متجر Play غير متوفر في Google Play كتطبيق للتنزيل. [https://www.dadysoft.com جوجل بلاي] متجر Play يتعامل فقط مع تطبيقات android. يستخدمه العالم كله لتنزيل التطبيقات في هواتفهم الذكية أو أجهزة Android أو الأجهزة اللوحية. يمكن للمستخدمين البحث عن تطبيقاتهم وتثبيتها باستخدام هذا النظام الأساسي. متجر تطبيقات Appvn هو نظام أساسي مشابه لتنزيلات التطبيقات وتحديثاتها. يتم دفع بعض التطبيقات ولكن معظم التطبيقات مجانية هنا. [https://www.softaty.com/android/google-play/ جوجل بلاي] تحديث متجر Play إلى أحدث إصدار: يأتي متجر Play مثبتًا على جميع أجهزة Android نظرًا لأهميته في إدارة التطبيقات المثبتة وتثبيت تطبيقات جديدة. ولكن ، عادةً بالنسبة للمستخدمين الجدد على نظام التشغيل Android أو للأشخاص الذين لم يحدّثوا إصداراتهم المثبتة من متجر Play ، يمكنك التحديث إلى أحدث إصدار من Google Play من خلال ملف APK هذا. تحميل جوجل بلاي يمكنك البدء بالتنزيل من هذه الصفحة إذا كنت ترغب في الحصول على أحدث إصدار من إصدار Google Play Store 2019. يمكنك أيضًا البحث عن جميع أنواع التطبيقات مثل الموسيقى والألعاب والكتب ومقاطع الفيديو ومحرري الصور وغير ذلك الكثير. يؤدي البحث عن كلمة واحدة إلى عدد من أنواع التطبيقات المتشابهة ويمكنك تثبيت التطبيق الذي تريده على هاتف Android الخاص بك. علاوة على ذلك ، فإنه يعرض التصنيفات الحالية للتطبيق. حتى تتمكن من الحكم على التطبيق من خلال تقييم العرض ثم تثبيت التطبيق. قم بتحديث تطبيقاتك عبر متجر Play مباشرة: ستتم إدارة جميع التطبيقات التي تقوم بتثبيتها على جهاز Android الخاص بك عبر متجر Play. سيتأكد من وصول جميع الإصدارات الأحدث التي أصدرها مطورو التطبيقات إليك. من خلال تحديث تطبيقاتك باستمرار ، يمكنك تمكينها من العمل بشكل صحيح. تحتوي تحديثات التطبيق عادةً على إصلاحات للأخطاء وميزات جديدة ستجعل تجربة التطبيق أفضل بكثير. ملاحظة: لن يعمل متجر Google Play إلا بعد تثبيت خدمات Google Play في جهازك. " PlayStore Milestone: LEMON 1.5 release 676 تنزيل متجر Play - تنزيل متجر play للموبايل سامسونج 2023 - 2022 مجانا web page hg main defect Peter Kovacs new 2023-01-16T02:41:35+01:00 02:41:35+01:00 "**تنزيل متجر Play** للموبايل سامسونج 34.0.12 مجانا أخر إصدار. حيث يعد تحديث متجر Play بشكل مستمر ضروريا على أجهزة Samsung و على الأجهزة الأندرويد الأخرى. و يوفر لك هذا التحديث المزيد من الأمان مع جوجل Play بروتيكت و الميزات الرائعة على الموبايل لخاص بك. يمكنك عبر الرابط أسفل الموضوع أن تقوم بتحميل و تنزيل متجر بلاي Play لهاتف سامسونغ و مختلف أجهزة الأندرويد. تقوم جوجل بتطوير و تنزيل تحديث [https://www.tanzilmatjarplay.com/2022/01/tanzil-matjar-play-apk.html /متجر Play للموبيل سامسونج] إلى الإصدار الأخير بشكل مستمر وعلى مدار الأسبوع، حيث توفر لك أحدث التطبيقات على متجرها ، و ذلك لأن الأجهزة التي تعمل على نظام الأندرويد هي الأكثر إنتشارا في العالم. لماذا يجب علينا تنزيل متجر Play؟ لمن ضروري تنزيل متجر play لأخر إصدار سواء يدويا أو أوتوماتيكيا من تطبيق جوجل بلاي نفسه. و ذلك لتجنب تحميل بالخطأ الفيروسات الضارة أو البرمجيات الخبيثة على هاتفك الأندرويد. و لأن متجر جوجل Play لا يتم تحميل فيه سوى التطبيقات الموثوقة بها فمتجر جوجل يقوم بفحص جميع التطبيقات و البرامج قبل ان يتم تحميلها على منصة جوجل بلاي. حيث يعتمد أغلب مستخدمي هاتف الأندرويد على تنزيل متجر play لأنه من المتاجر الأمنة 100%. و هذا ما يميز متجر جوجل Play عن باقي متاجر التطبيقات الأخرى التي توفر نفس الخدمة لتحميل التطبيقات. يوفر متجر جوجل Play العديد من المميزات و من أبسطها أنه يسهل البحث عن التطبيقات التي تريد تحميلها على هاتفك. فبمجرد الدخول على تطبيق جوجل بلاي و في مربع البحث الخاص بالمتجر أكتب إسم التطبيق المراد تحميله سوف تظهر لك الصفحة الخاصة بالتطبيق. و يمكنك تنزيله فورا Install أو إن كان هناك تحديث جديد لتطبيق فيمكنك أن تضغط على زر التحديث أو Update. أو طريقة التحقق من إصدار متجر بلاي ستور و تحديثه في هذه المقالة تعرفنا على كيفية التحقق و معرفة إصدار متجر جوجل بلاي ستور الخاص بنا و أيضا كيفية تحديثه لأخر لإصدار متوفر من التطبيق، تابعنا على موقع تنزيل متجر بلاي 2022 لتتوصل بكل جديد الموقع. شارك المقالة مع أصدقائك لتعم الفائدة. تحديث متجر بلاي 2022 - Google Play Store 34.0.12 أخر إصدار، فقد وضحنا لكم خلال السطور السابقة مميزات [https://www.tanzilmatjarplay.com /تنزيل متجر بلاي 2023]- 2022 وكيفية تحميله على موبايل سامسونج الأندرويد، حيث يهمنا أن تشاركونا أرائكم به من خلال التعليق على المقال." TanzilMatjarPlay Milestone: LEMON 1.4 release 677 zoodka core hg main defect Alpar Juttner new 2023-01-21T12:08:16+01:00 12:08:16+01:00 "تشخیص ژوپینگ تقلبی در سال های اخیر به دلیل توجه و رغبت مشتریان به خرید زیورآلات ژوپینگ، جنس های تقلبی که از مارک ژوپینگ الگو برداری کرده است در بازار های ایران به وفور یافت می شود که متاسفانه کیفیت و زیبایی و درخشش زیورآلات ژوپینگ را ندارند و در تماس با آب و یا مدت کمی پس از استفاده رنگ خود را از دست می دهند.یکی از روش های شناخت زیورآلات اصلی ژوپینگ دقت به رنگ متمایز محصولات آن است. همانطور که اشاره شد زیورآلات طلایی رنگ ژوپینگ مقدار کمی به رنگ رزگلد متمایل هستند. می توانید از این روش برای تشخیص زیورآلات ژوپینگ اصلی استفاده کنید. از دیگر نشانه های زیورآلات ژوپینگ اصل نام و یا لوگوی حک شده ی ژوپینگ در پشت اکسسوری و یا بر روی قفل آن است. [https://zoodika.com/category/61-stitched-earrings/ گوشواره بخیه ای] پس تنها به نام ژوپینگ بر روی بسته بندی اکتفا نکنید، زیرا بسته بندی های تقلبی با نام ژوپینگ به وفور در بازار یافت می شوند. کمپانی بدلیجات ژوپینگ در کشور هایی همچون کره، هند، ویتنام، تایلند، برزیل، ایتالیا و آلمان سرمایه گذاری میکنند و محصولات خود را طراحی کرده و با همکاری شرکت های مختلف محصولات را روانه بازار میکنند. تنوع و گوناگونی این محصولات سالانه بیش از هزاران یا میلیون ها قطعه بدلیجات و تزئینات است. جنس بدلیجات ژوپینگ جنس بدلیجات ژوپینگ معمولا از فلز مس است و روکشی از رادیوم یا آب طلای 24 عیار یا 18 عیار یا 14 عیار برای آن در نظر گرفته می شود. [https://zoodika.com/ بدلیجات زودیکا] رنگ فلز و آلیاژهایی که در زیورآلات ژوپینگ مورد استفاده قرار میگیرد با دیگر زیورآلات کمی متفاوت است و به عنوان مثال زیورآلات و بدلیجات طلایی رنگ ژوپینگ کمی متفاوت از رنگ طلایی دیگر بدلیجات می باشد و کمی متمایل به رنگ رزگلد است. " zoodka Milestone: LEMON 1.4 release 678 بدلیجات core hg main defect Alpar Juttner new 2023-01-21T12:12:45+01:00 12:12:45+01:00 "ژوپینگ چیست ؟ ژوپینگ یک برند معروف در جواهرات و زیورآلات بدلی است، محصولات آن شامل انگشتر، آویز، گوشواره ، دستبند ، گردنبند ، پابند ، النگو، ست زیورآلات و غیره می باشد.جنس محصولات ژوپینگ از فلز مس با روکش طلا یا رادیوم می باشد و جنس نگین های آن از نوع زیرکن صنعتی با کیفیت بالا و دیگر سنگهای قیمتی از جمله کریستال های سواروسکی است. امروزه به دلیل کیفیت بالا و ممتاز بودن و قیمت بسیار مناسب، محصولات ژوپینگ در تمام دنیا محبوب هستند و طرفداران بسیاری به خود جذب کرده اند.نام برند ژوپینگ را شاید تا به حال شنیده باشید که با عنوان هایی مثل شوپینگ نیز شناخته شده است. برند ژوپینگ که با نام انگلیسی xuping در دنیای تجارت مد و زیورآلات فعالیت می کند، تا چند سال پیش شاید کسی حتی اسمش را نشنیده بود ولی با طراحی انواع انگشتر ژوپینگ و دستبند و گردنبند و گوشواره ژوپینگ و دیگر زیورآلات و فعالیت در بازار های ایران توانسته است اعتبار قابل توجهی را برای خود کسب کند.اگر شما هم جزو افرادی هستید که زیورآلات ژوپینگ را خریداری کرده اید بدون اغراق می توان گفت [https://zoodika.com/category/43-new-pendant-earrings/ گوشواره آویز جدید] به احتمال بسیار بالا یکی از مشتری های پر و پا قرص آن شده اید. دلیل این اتفاق را می توان در قیمت های بسیار مناسب و کیفیت بسیار بالای محصولات این شرکت چینی دانست.همانطور که اشاره شد نگین های به کار رفته در زیورآلات ژوپینگ از کیفیت بالایی برخوردار هستند و معمولا به صورت باگت در آن ها به کار می روند که باعث می شود شما هنگام خرید زیورآلات هیچ ترسی از بابت افتادن یا بی کیفیت بودن نگین ها و کریستال های آن نداشته باشید و محو زیبایی و درخشش کریستال ها شوید. اگر شما قصد خرید انگشتر با کریستال های رنگی را دارید ژوپینگ این امکان را برای شما فراهم آورده است و می توانید انواع رو مانتوی و گردنبند و سرویس ها با رنگ های مختلف را از مارک شوپینگ تهیه کنید. ژوپینگ در سال 1991 میلادی در چین تأسیس شد. یکی از استراتژی های اصلی ژوپینگ استفاده از استراتژی های برند همتای خود، سواروسکی بود که این برند جزء 10 برند برتر جهان شناخته شده بود. [https://zoodika.com/category/47-synthetic-ring-girls/ انگشتر دخترانه] خریدارانی که خواهان بدلیجات و زیورآلات با کریستال های زیرکن (یا همان زیرکنیا که به الماس شرقی معروف است) هستند، عمده ترین گروه مشتریان برند ژوپینگ می باشند." zoodka Milestone: LEMON 1.4 release 679 mersansh core hg main defect Alpar Juttner new 2023-01-29T17:02:46+01:00 17:02:46+01:00 "انواع تیغه در ماشین اصلاح صورت و سر استفاده از ماشین‌های اصلاح که جزو لوازم اصلاح صورت مردانه است امروزه طرفداران بسیاری پیدا کرده و بسیاری از مردان به دنبال خرید این دستگاه هستند. [https://mersanshop.ir/shaving-machine-representative-kemei/ نمایندگی ماشین اصلاح کیمی] اما پیشنهاد می‌کنیم قبل از اینکه برای خرید اقدام کنید سعی کنید اطلاعات خود را در مورد ماشین اصلاح بالا ببرید. بالا بردن اطلاعات به شما کمک می‌کند تا گزینه بهتری را نسبت به سلیقه و نیاز خود انتخاب کنید. اولین چیزی که می‌خواهیم درباره این ماشین‌ها برایتان توضیح دهیم انواع تیغه در ماشین اصلاح است. به طور کلی ماشین‌های ریش تراش دو نوع تیغه دارند: ماشین ریش تراش با تیغه چرخشی ماشین ریش تراش با تیغه فویلی ماشین ریش تراش با تیغه چرخشی اگر می‌خواهید یک اصلاح خیلی تمیز و فوق العاده داشته باشید، ریش تراش با تیغه چرخشی بهترین گزینه برای شماست. تیغه‌های این مدل بیضی شکل بوده و استفاده از آن بسیار راحت است. این مدل ریش تراش صدای کمی دارند و موهای خیلی بلند را هم می‌تواند به خوبی اصلاح کند. تیغه‌های چرخشی معمولا دسترسی راحت‌تری به همه نواحی صورت دارند.ماشین اصلاح فویلی تیغه‌های ریش تراش فویلی زیر یک فویل محافظ قرار گرفته و به جای اینکه چرخش داشته باشند، دارای حرکت رفت و برگشتی هستند. در ریش تراش‌های فویلی چند تیغه وجود دارد. به طور مثال ریش تراش‌های با چهار تیغ، سریع تر از سه تیغه‌ها صورت را اصلاح می‌کنند. دقت کنید زمانی که با ریش تراش فویلی [https://mersanshop.ir/product/%D9%85%D8%A7%D8%B4%DB%8C%D9%86-%D8%A7%D8%B5%D9%84%D8%A7%D8%AD-%D8%AE%D8%B7%D8%B2%D9%86-%DA%A9%DB%8C%D9%85%DB%8C-%D9%85%D8%AF%D9%84-km-5017/ ریش تراش کیمی 5017] کار می‌کنید، دست شما باید حرکت رفت و برگشتی داشته باشد نه حرکت چرخشی.تفاوت تیغه سرامیک و فولادی همه ماشین‌های اصلاح تیغه ثابت (تیغه زیری) دارند که جنس آن از فولاد است. برخی ماشین‌ها تیغه متحرک هم دارند که از جنس سرامیک است. این دو جنس تیغه تفاوت‌هایی با هم دارند که می‌توان گفت تیغه سرامیکی تیزتر از فولادی بوده و کند نخواهد شد. اما در در کنار این نکته مثبت، تیغه سرامیکی در صورت ضربه خوردن امکان شکستگی دارد. پس تیغه‌های سرامیکی نسبت به فولادی تیزتر و شکننده‌تر هستند. این انتخاب بستگی به توقع شما از ماشین اصلاح سر و صورت دارد. انواع باتری‌های ماشین اصلاح سر ماشین‌های اصلاح به طور کلی دو نوع باتری دارند که عبارتند از: باتری لیتیومی باتری نیکلی این دو نوع باتری علاوه بر تفاوت در کارکرد، در قیمتشان هم با یکدیگر اختلاف دارند. دلیل این اختلاف قیمت هم این است که باتری‌های لیتیومی ماشین‌های اصلاح، برای شارژ به مدارهای پیشرفته‌ای نیاز دارند و همین مسئله باعث ایجاد اختلاف در قیمت‌ها می‌شود. در ادامه ویژگی‌های این دو نوع باتری را برایتان بیشتر توضیح می‌دهیم: باتری لیتیومی همان طور که گفتیم باتری لیتیومی یکی از انواع باتری‌های ماشین اصلاح سر است. از ویژگی‌های این نوع باتری می‌توان به موارد زیر اشاره کرد:این نوع باتری طول عمر بسیار بالایی دارد.قابلیت شارژ سریع داشته و در کمتر از ۲ ساعت شارژ می‌شود.باتری نیکلی یک نوع دیگر از باتری‌های ماشین اصلاح سر باتری نیکلی است که از ویژگی‌های این باتری می‌توان موارد زیر را نام برد:باتری نیکلی از جنس نیکل ساخته شده است.شارژ شدن این باتری طولانی مدت بوده و شارژ کامل آن تا ۸ ساعت طول می‌کشد. نکات مهم و کاربردی هنگام تهیه ماشین اصلاح صورت و سر اگر به دنبال راهنمای خرید ماشین اصلاح صورت و سر هستید و می‌خواهید اطلاعات کافی در این زمینه را داشته باشید ما سعی کرده‌ایم تمامی نکاتی که در زمان خرید ماشین اصلاح باید به آن دقت شود را برایتان جمع آوری کنیم. پس با ما همراه باشید تا نکات مهم و کاربردی هنگام تهیه ماشین اصلاح صورت و سر را بدانید. قیمت قیمت یکی از موارد مهم در زمان خرید هر وسیله است. ابتدا مشخص کنید که قصد دارید در چه رنج قیمتی ماشین اصلاح خریداری کنید چون با توجه به بودجه‌ای که در نظر گرفته‌اید باید ببینید می‌توانید یک ماشین ریش تراش گران قیمت با کیفیت فوق العاده عالی بخرید یا یک ماشین اصلاح ارزان با کیفیت متوسط. پس بودجه خود را مشخص کنید تا بدانید سراغ کدام دسته بروید.برق یا باتری قبل از این که اقدام به خرید ماشین اصلاح صورت و سر کنید، مشخص کنید که می‌خواهید ریش تراش باتری دار بخرید یا یک ریش تراش که با قدرت برق کار می‌کند؟ نکته‌ای که در مورد ماشین‌های اصلاح باتری دار وجود دارد این است که این ابزار قابل حمل بوده و شما می‌توانید به راحتی آن را با خودتان حمل کنید. علاوه بر این اغلب این ماشین‌ها ضدآب بوده و برای اصلاح زیر دوش هم کاربرد دارند. اما از لحاظ قدرت اگر بخواهیم مقایسه کنیم باید بگوییم که قدرت ریش تراش‌های باتری دار خیلی کمتر از ریش تراش‌های سیمی است و برای اصلاح موهای بسیار بلند کارایی ندارند. [https://mersanshop.ir/product/%D9%85%D8%A7%D8%B4%DB%8C%D9%86-%D8%A7%D8%B5%D9%84%D8%A7%D8%AD-%D9%85%D9%88%DB%8C-%D8%B3%D8%B1-%D9%88-%D8%B5%D9%88%D8%B1%D8%AA-%D9%88%DB%8C-%D8%AC%DB%8C-%D8%A7%D8%B1-%D9%85%D8%AF%D9%84-v-092/ وی جی ار 092] در کل این ریش تراش‌های باتری دار و شارژی عمرشان نسبت به ریش تراش‌های سیمی که با برق مستقیم کار می‌کنند، کمتر است." mersansh Milestone: LEMON 1.4 release 680 Fix C++17 compilation warnings regarding the use of the deprecated std::iterator. core hg main defect Alpar Juttner new 2023-02-02T13:59:36+01:00 13:59:36+01:00 "Compilations with C++17 or newer raise these warnings: In file included from /home/rturrado/.conan/data/coin-lemon/1.3.1/_/_/build/647d242d497da836490a4de0e700615d1d33a7d5/src/lemon/color.h:24, from /home/rturrado/.conan/data/coin-lemon/1.3.1/_/_/build/647d242d497da836490a4de0e700615d1d33a7d5/src/lemon/color.cc:22: /home/rturrado/.conan/data/coin-lemon/1.3.1/_/_/build/647d242d497da836490a4de0e700615d1d33a7d5/src/lemon/maps.h:1973:21: warning: ‘template struct std::iterator’ is deprecated [-Wdeprecated-declarations] 1973 | : public std::iterator { | ^~~~~~~~ In file included from /usr/include/c++/12.2.0/bits/stl_algobase.h:65, from /usr/include/c++/12.2.0/vector:60, from /home/rturrado/.conan/data/coin-lemon/1.3.1/_/_/build/647d242d497da836490a4de0e700615d1d33a7d5/src/lemon/color.h:22: /usr/include/c++/12.2.0/bits/stl_iterator_base_types.h:127:34: note: declared here 127 | struct _GLIBCXX17_DEPRECATED iterator | ^~~~~~~~ /home/rturrado/.conan/data/coin-lemon/1.3.1/_/_/build/647d242d497da836490a4de0e700615d1d33a7d5/src/lemon/maps.h:3135:21: warning: ‘template struct std::iterator’ is deprecated [-Wdeprecated-declarations] 3135 | : public std::iterator { | ^~~~~~~~ /usr/include/c++/12.2.0/bits/stl_iterator_base_types.h:127:34: note: declared here 127 | struct _GLIBCXX17_DEPRECATED iterator | ^~~~~~~~ This patch intends to remove those warnings." Roberto Turrado Camblor Milestone: LEMON 1.4 release 681 Bug in radix heap core hg main defect Alpar Juttner new 2023-07-27T13:39:37+02:00 13:39:37+02:00 "Levente Birszki reports that the implementation of radix heap does not work correctly in certain cases. It seems to mess up the sizes of the buckets, and it may pop an item with non-minimal key. For example, {{{ const int n = 10; // max num items const int c = 10; // max key lemon::RangeMap map(n, -1); lemon::RadixHeap> heap(map, 0, c); heap.push(0, 2); // (index, priority) heap.push(1, 3); heap.push(2, 4); heap.pop(); // ok, pops (0, 2) heap.increase(1, 5); heap.pop(); // oops, pops (1, 5) instead of (2,4) }}} Attached is a possible fix of the issue. The patch also extends [[source:test/heap_test.cc|heap_test.cc]] with the problematic example given above. The solution is based on a proposal of Levente." Peter Madarasi