maximum-weight-matching

joris

Fork 0

e103a493fc Update Algorithm.md dev Joris van Rantwijk 2024-07-20 15:13:06 +0200
4670cf1dca Add testcases to force big values for dual/slack Joris van Rantwijk 2024-07-26 19:41:57 +0200
c731c32473 Separate function top_level_blossom() Joris van Rantwijk 2024-07-21 14:25:49 +0200
e8490010d6 Implement ConcatenableQueue as 2-3 tree Joris van Rantwijk 2024-07-20 21:47:13 +0200
dc8cdae225 Minor simplification in UnionFindQueue Joris van Rantwijk 2024-07-20 15:13:36 +0200
e2f5b63a01 Fix README Joris van Rantwijk 2024-07-11 21:28:41 +0200
6bf04df77b Update README Joris van Rantwijk 2024-07-11 21:19:00 +0200
99f8a2d822 Add benchmark script Joris van Rantwijk 2024-07-10 21:00:53 +0200
ed70402310 Separate C++ test script Joris van Rantwijk 2024-07-10 20:52:59 +0200
54f59db753 Add tox.ini for Python testing Joris van Rantwijk 2024-07-10 20:18:41 +0200
c58374e6fb Remove debug checks of alternating tree Joris van Rantwijk 2024-07-09 21:18:53 +0200
658a393bb8 Test script for Python code Joris van Rantwijk 2024-07-08 21:25:35 +0200
c19fa9a76c Add pyproject.toml Joris van Rantwijk 2024-07-07 15:16:50 +0200
d3475834ab Add from __future__ import annotations Joris van Rantwijk 2024-07-09 19:25:55 +0200
147640329f Restructure Python code as package Joris van Rantwijk 2024-07-07 10:30:21 +0200
f2e8ca1357 Remove redundant type annotations "int|float" Joris van Rantwijk 2024-07-07 10:36:08 +0200
b2d4de41f9 Add __slots__ in datastruct.py Joris van Rantwijk 2024-07-06 22:53:41 +0200
d2debb6d6f Minor changes to docstrings Joris van Rantwijk 2024-07-06 22:32:19 +0200
bbe19a6798 Run all unittests in run_checks.sh Joris van Rantwijk 2024-07-06 20:22:18 +0200
50ef772271 Improve test coverage Joris van Rantwijk 2024-07-06 20:21:33 +0200
6a75ffaf63 Avoid leaking reference cycles Joris van Rantwijk 2024-07-06 16:13:34 +0200
4c6115fb2f Improve comments and docstrings Joris van Rantwijk 2024-06-30 21:38:12 +0200
0e76e6472b Minor cleanup in scanning and delta steps Joris van Rantwijk 2024-06-30 16:13:40 +0200
f35a640e43 Clean up management of the alternating tree Joris van Rantwijk 2024-06-30 13:48:11 +0200
b960a85b6c Clean up magagement of blossom labels Joris van Rantwijk 2024-06-30 09:11:58 +0200
f8c6b99842 Clean up least-slack edge tracking Joris van Rantwijk 2024-06-29 22:06:28 +0200
1a98624f2b Solve slow maintanance of blossom list Joris van Rantwijk 2024-06-25 21:01:52 +0200
61524990d7 Keep alternating trees between stages Joris van Rantwijk 2024-06-23 19:50:27 +0200
73641d7b70 Add method PriorityQueue.increase_prio Joris van Rantwijk 2024-06-23 19:46:50 +0200
0675230692 Code style cleanups Joris van Rantwijk 2024-06-22 20:04:49 +0200
de30ac3c5e Track blossoms in each alternating tree Joris van Rantwijk 2024-06-22 17:57:42 +0200
aab2acd78e Remove redundant clearing of scan queue Joris van Rantwijk 2024-06-22 14:28:24 +0200
e9baa88c70 Fix bug in delta2 tracking Joris van Rantwijk 2024-06-09 19:49:02 +0200
73479532ac Implement scan queue as a list instead of deque Joris van Rantwijk 2024-06-09 18:01:06 +0200
04b6908449 Do not check edge slack during scan Joris van Rantwijk 2024-06-02 00:31:40 +0200
3a77749425 Simplify slack handling in delta2 tracking Joris van Rantwijk 2024-05-31 00:24:22 +0200
9ee26584ab Use UnionFind to find top-level blossom of vertex Joris van Rantwijk 2024-05-29 22:01:26 +0200
225311dae0 Implement heap-based tracking for delta2 Joris van Rantwijk 2024-05-28 21:29:57 +0200
7cc1666cf2 Lazy delta updates of T-vertex duals Joris van Rantwijk 2024-05-26 20:55:54 +0200
6318de3b1f Lazy delta updates of T-blossom duals Joris van Rantwijk 2024-05-26 11:32:02 +0200
b2e055b357 Lazy delta updates of S-blossom duals Joris van Rantwijk 2024-05-26 00:07:16 +0200
de03796d99 Lazy delta updates of S-vertex duals Joris van Rantwijk 2024-05-25 23:18:15 +0200
a23c38eb70 Implement heap-based tracking for delta4 Joris van Rantwijk 2024-05-25 21:25:00 +0200
13b6b76d47 Implement heap-based edge tracking for delta3 Joris van Rantwijk 2024-05-25 17:51:23 +0200
91d4afb271 Clean up redundant type annotations "int|float" Joris van Rantwijk 2024-05-25 18:00:37 +0200
c8a3f7f684 Datastructures for O(n*m*log(n)) algorithm Joris van Rantwijk 2024-05-25 11:50:07 +0200
77dac28056 Moved repository to Gitea master Joris van Rantwijk 2024-03-08 12:09:30 +0100
9cabdce600 Test C++ code in Github Actions workflow Joris van Rantwijk 2023-07-07 23:15:32 +0200
327e83e701 Update README to mention C++ code Joris van Rantwijk 2023-07-07 22:41:27 +0200
d8d44f6171 Add corner cases to C++ unit test Joris van Rantwijk 2023-07-07 22:25:36 +0200
4b7fab3f43 Add struct Graph to represent input graph Joris van Rantwijk 2023-05-27 23:29:05 +0200
9b064de4d8 Add C++ testcases for verification Joris van Rantwijk 2023-05-18 20:59:12 +0200
9c669f2d03 Remove dependence on Boost.Hash Joris van Rantwijk 2023-05-18 09:55:55 +0200
731b202af3 Clean up verification code Joris van Rantwijk 2023-05-16 22:19:55 +0200
250fd4ea94 Minor cleanup of code layout Joris van Rantwijk 2023-05-13 20:35:08 +0200
a9010855a5 Avoid dynamic_cast<..> Joris van Rantwijk 2023-05-13 15:22:21 +0200
dd452f73da Superficial clean up of comments Joris van Rantwijk 2023-05-12 21:50:07 +0200
3aa2b20a74 Remove clutter from C++ unit tests Joris van Rantwijk 2023-05-12 21:49:37 +0200
ee14d45aa6 Minor clean up of shadowed variable Joris van Rantwijk 2023-05-12 20:59:11 +0200
da0040ba27 C++ command line tool to run matching Joris van Rantwijk 2023-05-12 20:51:49 +0200
8d7d1a537a Add C++ tests for maximum cardinality matching Joris van Rantwijk 2023-05-12 18:11:02 +0200
d08e3e1c58 Fix bug in C++ maximum cardinality adjustment Joris van Rantwijk 2023-05-12 18:09:32 +0200
a4da35d3aa Fix bug in C++ matching code Joris van Rantwijk 2023-05-12 00:43:57 +0200
61cb309082 Implement algorithm in C++ Joris van Rantwijk 2023-05-10 20:56:30 +0200
082a2d8f03 Simplify --solver syntax of run_test.py Joris van Rantwijk 2023-06-16 20:09:18 +0200
76de35471f Simplify find_path_through_blossom Joris van Rantwijk 2023-05-12 18:12:25 +0200
be2b474873 Minor clarifications in comments Joris van Rantwijk 2023-05-10 20:54:29 +0200
91a392a0dc Update README Joris van Rantwijk 2023-04-15 16:02:29 +0200
f9bd7aecf6 Move Algorithm.md to doc folder Joris van Rantwijk 2023-04-15 12:03:39 +0200
e16f502bcf Add script to run tests Joris van Rantwijk 2023-04-14 15:45:26 +0200
6ad3638142 Run test graphs in workflow Joris van Rantwijk 2023-04-14 12:49:49 +0200
536529c36c Check Python unittest coverage Joris van Rantwijk 2023-04-14 11:23:32 +0200
a3f29f0988 Run Python unittests in workflow Joris van Rantwijk 2023-04-14 11:06:29 +0200
94db975cf0 Add Github Actions workflow Joris van Rantwijk 2023-04-14 10:29:22 +0200
3b80109cff Add implementation notes to algorithm description Joris van Rantwijk 2023-04-13 21:51:24 +0200
b53e58902a Start writing algorithm description Joris van Rantwijk 2023-03-24 09:55:19 +0100
d4b8cf2067 Fix mistaken comments about run times Joris van Rantwijk 2023-04-09 21:18:56 +0200
0e79e1d2f6 Use FIFO queue for S-vertices Joris van Rantwijk 2023-04-06 20:50:06 +0200
caac6825a6 Expand zero-dual blossom before assigning label T Joris van Rantwijk 2023-04-05 20:56:13 +0200
8d69a3316c Minor fix language in docstring Joris van Rantwijk 2023-03-13 21:56:46 +0100
b144fd7cdd Update graph generation script (skip huge graphs) Joris van Rantwijk 2023-03-12 12:28:08 +0100
bf7437b7ad Add .gitignore Joris van Rantwijk 2023-03-12 12:17:38 +0100
b8391ea319 Pylint cleanups Joris van Rantwijk 2023-03-11 23:21:10 +0100
dd24776149 Add missing import statements Joris van Rantwijk 2023-03-11 22:00:38 +0100
ba28bbf7ca Add missing type annotation Joris van Rantwijk 2023-03-11 17:32:49 +0100
5048bbaf99 Input has type Sequence[...] instead of list Joris van Rantwijk 2023-03-11 17:31:41 +0100
ce5ff2d581 Add test graphs Joris van Rantwijk 2023-02-25 16:50:36 +0100
80dd53c736 Add program for matching with LEMON Joris van Rantwijk 2023-02-19 13:36:07 +0100
1e81129476 Tool for testing and benchmarking Joris van Rantwijk 2023-02-19 21:59:03 +0100
37aa0c605b Read from stdin when no input file specified Joris van Rantwijk 2023-02-19 19:44:06 +0100
83d9e37db6 Rename to test_mwmatching.py Joris van Rantwijk 2023-02-19 19:14:58 +0100
64851c98c5 Test that edge/vertex order is irrelevant Joris van Rantwijk 2023-02-14 21:08:15 +0100
71a7dfc9a3 Add generators: chain, hardcard.f, t.f, tt.f Joris van Rantwijk 2023-02-17 14:18:15 +0100
3f5d61d0e7 Rename Python module to "mwmatching" Joris van Rantwijk 2023-02-14 20:49:24 +0100
f0624fa2a5 Slightly rephrase docstring Joris van Rantwijk 2023-02-13 22:38:40 +0100
118007e953 Add testcases that are sensitive to specific bugs Joris van Rantwijk 2023-02-13 21:58:55 +0100
8f81154169 Test coverage of verification routine Joris van Rantwijk 2023-02-12 22:56:04 +0100
4dc7befd9d Check that unmatched vertices have zero dual Joris van Rantwijk 2023-02-12 22:55:08 +0100
be0f5c3881 Raise MatchingFailed when verify fails Joris van Rantwijk 2023-02-12 21:18:57 +0100
f1a60febe7 Improve test coverage to 100% Joris van Rantwijk 2023-02-12 17:29:24 +0100

Commit Graph Select branches Hide Pull Requests dev master Mono Color

Commit Graph

Select branches

Hide Pull Requests

dev

master