Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
History for modules/struct/graphops.tcl
2023-09-30
| ||
01:10 | Bumped package version for all modules [a-z]*. file: [9eb40c88db] check-in: [5be206c63f] user: rolf branch: tcl9-testarea-rde, size: 109495 | |
2023-08-11
| ||
23:52 | More adaption to the package require Tcl commands, following what was discussed at the montly meeting 2023/08. More work and changes to come. file: [7836aec178] check-in: [46ab6ea7c8] user: rolf branch: tcl9-testarea-rde, size: 109495 | |
2023-06-23
| ||
10:22 | Pointsman testbed. file: [232a8025df] check-in: [a5532890a4] user: rolf branch: tcl9-testarea-rde, size: 109494 | |
2018-11-22
| ||
05:22 | Small fixes in the disjoint code (removed references to pairs, slight typos). Added references to data structure overview, and papers with time/complexity proofs. Fixed up dependent packages (now requiring 8.6 as well). Fixed package index of the module. file: [082c15f668] check-in: [4cabcb175c] user: aku branch: kbk-refactor-disjointset, size: 109493 | |
2009-09-24
| ||
19:30 | * graphops.tcl (::struct::graph::op::WeightedKCenter): Fixed * graphops.man: object leak. Added the missing release of the * pkgIndex.tcl: Gi(SQ) in error case (no solution). Bumped * graphops.test: version to 0.11.3. Tweaked comment in testsuite regarding repetition. * graph/tests/XOpsControl: Added testsuite for weighted k-center. * graph/tests/ops/weightedkcenter.test: Testsuite for weighted k-center. Changes compared to GSoC result: - Test names extended with 'treeimpl'. - Indentation, line-endings - Several tests demonstrates how the result is influenced by node/arc ordering. Extended to accept the variations. This passes the testsuite for both tcl and critcl implementations of struct::graph. * graph/tests/ops/kcenter.test: Moved the custom matcher/verifier for * graph/tests/XOpsSupport: max-independent-set to shared file. * graph/tests/XOpsSetup: Simplified some setup procedures a bit. file: [26d244211a] check-in: [fe19798dab] user: andreas_kupries branch: trunk, size: 109477 | |
18:03 | * graphops.tcl (::struct::graph::op::MaximumFlowByDinic): Fixed * graphops.man: object leak. Added the missing release of the * pkgIndex.tcl: residual graph generated in each iteration. Bumped version to 0.11.2. * graph/tests/XOpsControl: Added testsuite for Dinic Maximum Flow. * graph/tests/ops/dinicmaximumflow.test: Testsuite for Dinic Maximum Flow. Changes compared to GSoC result: - Test names extended with 'treeimpl'. - Indentation, line-endings - Added dictsort to force a canonical ordering on the results. - Results updated to be in the canonical ordering. This passes the testsuite for both tcl and critcl implementations of struct::graph. file: [ef0945d14e] check-in: [5d5a841846] user: andreas_kupries branch: trunk, size: 109384 | |
2009-09-23
| ||
20:56 | * graphops.tcl (::struct::graph::op::MinimumDegreeSpanningTree): Stop search+insertion loop after it has added the candidate arc. (::struct::graph::op::MinimumDiameterSpanningTree): Fix two object leaks. * graph/tests/XOpsControl: Added testsuite for Min D Spanning Trees. * graph/tests/ops/mdst.test: Testsuite for MDST. Blocking Flow. Changes compared to GSoC result: - Test names extended with 'treeimpl'. - Indentation, line-endings - Added undirected to force a canonical ordering on the results. - Results updated to be in the canonical ordering. - Several tests demonstrates how the result is influenced by node ordering. Extended to accept the variations. This passes the testsuite for both tcl and critcl implementations of struct::graph. file: [9058397653] check-in: [d670eccdc6] user: andreas_kupries branch: trunk, size: 109364 | |
18:36 | * graphops.tcl (::struct::graph::op::BlockingFlowByMKM): Fixed * graphops.man: object leak. Added the missing release of the * pkgIndex.tcl: LevelGraph on exceptional return (No path between nodes s and t). Bumped version to 0.11.1. * graph/tests/XOpsControl: Added testsuite for MKM Blocking Flow. * graph/tests/ops/mkmblockingflow.test: Testsuite for MKM Blocking Flow. Changes compared to GSoC result: - Test names extended with 'treeimpl'. - Indentation, line-endings - Added dictsort to force a canonical ordering on the results. - Results updated to be in the canonical ordering. This passes the testsuite for both tcl and critcl implementations of struct::graph. file: [91f7ea713a] check-in: [1e90dd21e0] user: andreas_kupries branch: trunk, size: 109206 | |
2009-09-21
| ||
23:48 | * graph/tests/XOpsControl: Added the testsuites for metrictsp, christofides and tspheuristics. * graph/tests/ops/metrictsp.test: Testsuite for metrictsp. * graph/tests/ops/christofides.test: Testsuite for christofides. * graph/tests/ops/tspheuristics.test: Testsuite for tspheuristics. Changes compared to GSoC result: - Test names extended with 'treeimpl'. - Indentation, line-endings - Conversion to v2 syntax, and cleanup of resource handling. - Updated results for different implementations, sorting. * graph/tests/XOpsSetup (SETUP_TSPHEURISTIC_1): Fixed growing cycle list throwing of repeated execution of the same test. * graph/tests/Xsupport: Added helper commands for the test cases of the various metric tsp commands (canonical tours, ...). * graph/tests/Xsetup (tmSE): Added result selection based on implementation of struct::set. * graphops.tcl (::struct::graph::op::MetricTravellingSalesman): Fixed problem in algorithm for asymmetric TSP, selecting the tour in the wrong (higher-weight) direction. The Fleury underneath does not care about arc direction. (::struct::graph::op::Christofides): Dropped superfluous variable and fixed M+T operation. The matching does not care about arc direction, and we have insert anti-parallel arcs to avoid any existing. (::struct::graph::op::isEulerian?): Extended API to return tour start. Computable from the arcs, but not easy. Better to get it from the algorithm which knows by definition. (::struct::graph::op::findHamiltonCycle): Get tour start from isEulerian, and drop bogus computation from the tour arcs. (::struct::graph::op::createTGraph): Moved graph creation after error check to avoid a leak when the check fails. * graphops.man: Bumped version to 0.11 * pkgIndex.tcl: (isEulerian API extension, plus bugfixes). file: [5f587ba9bc] check-in: [78e60eeefe] user: andreas_kupries branch: trunk, size: 109179 | |
2009-09-16
| ||
18:51 | * graphops.tcl: Fixed indentation, and removed trailing whitespace. * graph/tests/XOpsControl: Added testsuite for BFS. * graph/tests/ops/bfs.test: Testsuite for breadth-first search. Changes compared to GSoC result: - Test names extended with 'treeimpl'. - Added dictsort and lsort to force a canonical ordering on results. Where sorting was not possible we provide the two valid results for Tcl and Critcl implementations. - Results updated to be in the canonical ordering. - Indentation, line-endings This passes the testsuite for both tcl and critcl implementations of struct::graph. file: [2b2e345a2c] check-in: [9b4fb2389a] user: andreas_kupries branch: trunk, size: 106999 | |
2009-09-15
| ||
19:24 | * graphops.tcl: Starting on the integration of Michal * graphops.man: Antoniewski's (<[email protected]>) work on * graphops.test: graph operations for GSoC 2009. Added all * graphops.man: operations, and their documentation. Version * graphops.tcl: bumped to 0.10. The graphops package now requires * graphops.test: Tcl 8.5. The testsuite requires tcltest v2. * pkgIndex.tcl: Extended setup commands for upcoming new tests. * graph/tests/XOpsSetup: The package and tests now require * graph/tests/ops/adjmatrix.test: struct::tree, another package * graph/tests/ops/bipartite.test: with acceleration via critcl. * graph/tests/ops/bridge.test: Testsuite updated to switch its * graph/tests/ops/componentof.test: implementations well. The * graph/tests/ops/components.test: testsuites for the new * graph/tests/ops/connected.test: commands will be added * graph/tests/ops/cutvertex.test: incrementally over the next * graph/tests/ops/diameter.test: days. * graph/tests/ops/dijkstra.test: * graph/tests/ops/distance.test: * graph/tests/ops/eccentricity.test: * graph/tests/ops/eulerpath.test: * graph/tests/ops/eulertour.test: * graph/tests/ops/kruskal.test: * graph/tests/ops/maxmatching.test: * graph/tests/ops/prim.test: * graph/tests/ops/radius.test: * graph/tests/ops/tarjan.test: file: [87d07c1db5] check-in: [42c21b6c75] user: andreas_kupries branch: trunk, size: 106779 | |
03:47 | * graphops.tcl: Destroy internal temporary object on internal * graphops.man: error. Bumped version to 0.9.2. * pkgIndex.tcl: * graph/tests/ops/eulerpath.test: Converted to tcltest v2 form. * graph/tests/XOpsControl: Added sourcing of the support code needed when the graphops testsuite is run standalone. file: [0375833ff5] check-in: [49146e2480] user: andreas_kupries branch: trunk, size: 33185 | |
2009-07-10
| ||
16:25 | * graphops.tcl (::struct::graph::op::TarjanSub): * graphops.tcl (::struct::graph::op::isCutVertex?): * graphops.tcl (::struct::graph::op::Fleury): * pkgIndex.tcl: Fixed [Bug 2815302]. Replaced a number of uses of * graphops.man: struct::set subtract' with the proper 'struct::set exclude', as these places remove a single element, not a set. Use of the wrong method then breaks the code if elements (node/arc names) with whitespace in them is used. Bumped version to 0.9.1. file: [98f7b97645] check-in: [746fd7f965] user: andreas_kupries branch: trunk, size: 33162 | |
2008-11-20
| ||
07:26 | * graph1.test: Cleanup to avoid interference with the accelerators * graphops.test: of graph v2. Bring in the accelerators for queues * graph/tests/ops/adjmatrix.test: and stacks. Fixed bug in tarjan * graph/tests/ops/bipartite.test: exposed by the accelerator (*). * graph/tests/ops/bridge.test: (*) Changed order of arc traversal. * graph/tests/ops/componentof.test: * graph/tests/ops/components.test: * graph/tests/ops/connected.test: * graph/tests/ops/cutvertex.test: * graph/tests/ops/diameter.test: * graph/tests/ops/dijkstra.test: * graph/tests/ops/distance.test: * graph/tests/ops/eccentricity.test: * graph/tests/ops/eulerpath.test: * graph/tests/ops/eulertour.test: * graph/tests/ops/kruskal.test: * graph/tests/ops/maxmatching.test: * graph/tests/ops/prim.test: * graph/tests/ops/radius.test: * graph/tests/ops/tarjan.test: * graphops.tcl: Near-completed integration of graph algorithms. * graphops.man: Node distances, eccentricity, radius, diameter. * graph/tests/ops/distance.test: Bumped package version to 0.9. * graph/tests/ops/radius.test: Disabled the placeholders for max- * graph/tests/ops/diameter.test: matching, the only algorithm we * graph/tests/ops/eccentricity.test: are missing. * graph/tests/XOpsControl: * pkgIndex.tcl: file: [4a0f4b3af7] check-in: [c003c44aec] user: andreas_kupries branch: trunk, size: 33163 | |
2008-11-19
| ||
07:39 | * graphops.tcl: Continued integration of graph algorithms. Node * graphops.man: distances, dijkstra's algorithm. Bumped the * graph/tests/ops/disjkstra.test: package version to 0.8. * graph/tests/XOpsControl: * graph/tests/XOpsSetup: * pkgIndex.tcl: file: [04c62b7e95] check-in: [cf986355de] user: andreas_kupries branch: trunk, size: 29300 | |
2008-11-18
| ||
03:49 | * graphops.tcl: Continued integration of graph algorithms. Euler * graphops.man: paths and tours. Bumped the package version * graph/tests/ops/eulertour.test: to 0.7. * graph/tests/ops/eulerpath.test: * graph/tests/XOpsControl: * graph/tests/XOpsSetup: * graph/tests/XOpsSupport: * pkgIndex.tcl: file: [ec1400fef6] check-in: [4a3caef0e5] user: andreas_kupries branch: trunk, size: 25724 | |
2008-11-15
| ||
05:48 | * graphops.tcl: Continued integration of graph algorithms. More * graphops.man: about connectivity. Bumped the package version * graph/tests/ops/connected.test: to 0.6. * graph/tests/ops/cutvertex.test: * graph/tests/ops/bridge.test: * graph/tests/XOpsControl: * pkgIndex.tcl: file: [5ac7e4a663] check-in: [68a7d1b0f4] user: andreas_kupries branch: trunk, size: 21723 | |
2008-11-14
| ||
04:13 | * graphops.tcl: Continued integration of graph algorithms. * graphops.man: Connected components. Bumped package version * graph/tests/ops/components.test: to 0.5. * graph/tests/ops/componentof.test: * graph/tests/XOpsControl: * graph/tests/XOpsSetup: * graph/tests/XOpsSupport: * pkgIndex.tcl: file: [dcf7bd49f9] check-in: [0c11b1a2f2] user: andreas_kupries branch: trunk, size: 18253 | |
2008-11-13
| ||
05:36 | * graphops.tcl: Continued integration of graph algorithms. * graphops.man: SCCs via Tarjan. Placeholder for max matching. * graph/tests/ops/tarjan.test: Bumped version to 0.4. * graph/tests/ops/maxmatching.test: * graph/tests/XOpsControl: * graph/tests/XOpsSetup: * graph/tests/XOpsSupport: * pkgIndex.tcl: file: [eae9448f4c] check-in: [03aaffa0d0] user: andreas_kupries branch: trunk, size: 16167 | |
2008-11-08
| ||
09:57 | * graphops.tcl: Continued integration of graph algorithms. * graphops.man: Test for bipartite graph. Bumped version * graph/tests/ops/bipartite.test: to 0.3 * graph/tests/XOpsControl: * graph/tests/XOpsSetup: * graph/tests/XOpsSupport: * pkgIndex.tcl: file: [f033fa9540] check-in: [9a564f2d2a] user: andreas_kupries branch: trunk, size: 12975 | |
06:43 | * graphops.tcl: Continued integration of graph algorithms. * graphops.man: Minimum spanning tree/forest as per Prim. * graph/tests/ops/prim.test: Bumped version to 0.2 * graph/tests/XOpsControl: * graph/tests/XOpsSetup: * pkgIndex.tcl: file: [f3da80df2d] check-in: [9b3638d3ae] user: andreas_kupries branch: trunk, size: 10089 | |
2008-11-07
| ||
03:47 | * graphops.tcl: Continued integration of graph algorithms. * graphops.man: Minimum spanning tree/forest as per Kruskal. * graph/tests/ops/kruskal.test: * graph/tests/XOpsControl: * graph/tests/XOpsSetup: file: [de692e1084] check-in: [1d5a42bc9d] user: andreas_kupries branch: trunk, size: 6048 | |
2008-11-05
| ||
07:28 | Added: * graphops.tcl: Starting on the integration of Alejandro Paz's * graphops.man: (<[email protected]>) work on graph operations * graphops.test: for GSoC 2008. First operation: Adjacency matrix. * pkgIndex.tcl: * graph/test/XOpsControl: * graph/test/XOpsSetup: * graph/test/XOpsSupport: * graph/test/ops/adjmatrix.test: file: [89742285a1] check-in: [a4f579c8ce] user: andreas_kupries branch: trunk, size: 3200 | |