joris
/
maximum-weight-matching
1
0
Fork 0
Code Pull Requests Activity
129 Commits 2 Branches 0 Tags 1.1 MiB
Commit Graph

84 Commits

Author SHA1 Message Date
Joris van Rantwijk e103a493fc Update Algorithm.md 2024-07-28 11:38:05 +02:00
Joris van Rantwijk 4670cf1dca Add testcases to force big values for dual/slack 2024-07-28 11:38:05 +02:00
Joris van Rantwijk c731c32473 Separate function top_level_blossom() 2024-07-21 15:32:41 +02:00
Joris van Rantwijk e8490010d6 Implement ConcatenableQueue as 2-3 tree 2024-07-21 15:32:41 +02:00
Joris van Rantwijk dc8cdae225 Minor simplification in UnionFindQueue 2024-07-21 15:32:41 +02:00
Joris van Rantwijk c58374e6fb Remove debug checks of alternating tree 2024-07-09 21:18:53 +02:00
Joris van Rantwijk c19fa9a76c Add pyproject.toml 2024-07-09 21:10:38 +02:00
Joris van Rantwijk d3475834ab Add from __future__ import annotations 
This makes the code work on Python versions 3.7 and 3.8.
 2024-07-09 21:10:38 +02:00
Joris van Rantwijk 147640329f Restructure Python code as package 2024-07-09 21:10:38 +02:00
Joris van Rantwijk f2e8ca1357 Remove redundant type annotations "int|float" 2024-07-09 21:10:38 +02:00
Joris van Rantwijk b2d4de41f9 Add __slots__ in datastruct.py 
It does not make a clear difference for performance.
But it should at least reduce memory usage a bit.
 2024-07-09 21:10:38 +02:00
Joris van Rantwijk d2debb6d6f Minor changes to docstrings 2024-07-09 21:10:38 +02:00
Joris van Rantwijk 50ef772271 Improve test coverage 2024-07-09 21:10:38 +02:00
Joris van Rantwijk 6a75ffaf63 Avoid leaking reference cycles 2024-07-09 21:10:38 +02:00
Joris van Rantwijk 4c6115fb2f Improve comments and docstrings 2024-07-09 21:10:38 +02:00
Joris van Rantwijk 0e76e6472b Minor cleanup in scanning and delta steps 2024-07-09 21:10:38 +02:00
Joris van Rantwijk f35a640e43 Clean up management of the alternating tree 2024-07-09 21:10:38 +02:00
Joris van Rantwijk b960a85b6c Clean up magagement of blossom labels 2024-07-09 21:10:38 +02:00
Joris van Rantwijk f8c6b99842 Clean up least-slack edge tracking 2024-07-09 21:10:38 +02:00
Joris van Rantwijk 1a98624f2b Solve slow maintanance of blossom list 2024-07-09 21:10:38 +02:00
Joris van Rantwijk 61524990d7 Keep alternating trees between stages 
Delete only the trees that are involved in an augmenting path.
Keep the other trees and reuse them in the next stage.

This gives a big speedup on many cases such as random graphs.
The code is a mess, needs to be cleaned up.
 2024-07-09 21:10:38 +02:00
Joris van Rantwijk 73641d7b70 Add method PriorityQueue.increase_prio 2024-07-09 21:10:38 +02:00
Joris van Rantwijk 0675230692 Code style cleanups 2024-07-09 21:10:38 +02:00
Joris van Rantwijk de30ac3c5e Track blossoms in each alternating tree 2024-07-09 21:10:38 +02:00
Joris van Rantwijk aab2acd78e Remove redundant clearing of scan queue 2024-07-09 21:10:38 +02:00
Joris van Rantwijk e9baa88c70 Fix bug in delta2 tracking 2024-07-09 21:10:38 +02:00
Joris van Rantwijk 73479532ac Implement scan queue as a list instead of deque 2024-07-09 21:10:38 +02:00
Joris van Rantwijk 04b6908449 Do not check edge slack during scan 
Tight edges are not used immediately during the scan.
Just like other edges, tight edges are tracked in priority queues
and are used later through a zero-delta step.

This simplifies slack calculations.
 2024-07-09 21:10:38 +02:00
Joris van Rantwijk 3a77749425 Simplify slack handling in delta2 tracking 2024-07-09 21:10:38 +02:00
Joris van Rantwijk 9ee26584ab Use UnionFind to find top-level blossom of vertex 
The run time should now be O(n*m*log(n))
 2024-07-09 21:10:38 +02:00
Joris van Rantwijk 225311dae0 Implement heap-based tracking for delta2 2024-07-09 21:10:38 +02:00
Joris van Rantwijk 7cc1666cf2 Lazy delta updates of T-vertex duals 2024-07-09 21:10:38 +02:00
Joris van Rantwijk 6318de3b1f Lazy delta updates of T-blossom duals 2024-07-09 21:10:38 +02:00
Joris van Rantwijk b2e055b357 Lazy delta updates of S-blossom duals 2024-07-09 21:10:38 +02:00
Joris van Rantwijk de03796d99 Lazy delta updates of S-vertex duals 2024-07-09 21:10:38 +02:00
Joris van Rantwijk a23c38eb70 Implement heap-based tracking for delta4 2024-07-09 21:10:38 +02:00
Joris van Rantwijk 13b6b76d47 Implement heap-based edge tracking for delta3 2024-07-09 21:10:38 +02:00
Joris van Rantwijk 91d4afb271 Clean up redundant type annotations "int|float" 2024-07-09 21:10:00 +02:00
Joris van Rantwijk c8a3f7f684 Datastructures for O(n*m*log(n)) algorithm 2024-05-25 11:50:07 +02:00
Joris van Rantwijk a4da35d3aa Fix bug in C++ matching code 2023-07-07 22:33:33 +02:00
Joris van Rantwijk 76de35471f Simplify find_path_through_blossom 2023-05-12 18:12:25 +02:00
Joris van Rantwijk be2b474873 Minor clarifications in comments 2023-05-10 20:54:29 +02:00
Joris van Rantwijk d4b8cf2067 Fix mistaken comments about run times 2023-04-10 12:56:56 +02:00
Joris van Rantwijk 0e79e1d2f6 Use FIFO queue for S-vertices 2023-04-09 21:19:41 +02:00
Joris van Rantwijk caac6825a6 Expand zero-dual blossom before assigning label T 2023-04-09 21:19:41 +02:00
Joris van Rantwijk b8391ea319 Pylint cleanups 2023-03-12 12:16:29 +01:00
Joris van Rantwijk 5048bbaf99 Input has type Sequence[...] instead of list 2023-03-11 17:31:41 +01:00
Joris van Rantwijk 37aa0c605b Read from stdin when no input file specified 2023-02-22 23:20:43 +01:00
Joris van Rantwijk 83d9e37db6 Rename to test_mwmatching.py 2023-02-22 23:20:43 +01:00
Joris van Rantwijk 64851c98c5 Test that edge/vertex order is irrelevant 2023-02-22 23:20:17 +01:00