maximum-weight-matching

joris

Fork 0

36be21800b Fix random graph generation master v3 Joris van Rantwijk 2024-12-07 01:50:27 +0100
8ed1d42710 Fix C++ unit test module names Joris van Rantwijk 2024-11-28 23:08:21 +0100
8eb6b77523 Update README, section repository structure Joris van Rantwijk 2024-11-26 20:07:23 +0100
43502512ee Update README wrt C++ run time Joris van Rantwijk 2024-11-26 18:50:44 +0100
d4e86e9dcc make clean at start of C++ test script Joris van Rantwijk 2024-11-26 18:48:26 +0100
53e5ec618e gitignore compiled C++ code Joris van Rantwijk 2024-11-26 11:18:14 +0100
3914ea15a7 Add Python 3.13 in tox config Joris van Rantwijk 2024-11-26 11:17:37 +0100
d539e5cfbb Add C++ testcases from Python Joris van Rantwijk 2024-11-24 14:59:58 +0100
f652a08d43 Rename mwmatching.h to mwmatching.hpp Joris van Rantwijk 2024-11-24 14:25:43 +0100
0f18b7b05a Split datastruct.h Joris van Rantwijk 2024-11-24 14:22:26 +0100
087799cdca Minor comment cleanup Joris van Rantwijk 2024-11-24 13:59:28 +0100
02917b2caf Minor code and comment cleanups Joris van Rantwijk 2024-11-23 22:59:40 +0100
f0773eb84b Clean up code formatting Joris van Rantwijk 2024-11-22 23:29:10 +0100
1e6f2a11c4 Simplify expand_t_blossom() Joris van Rantwijk 2024-11-22 20:12:25 +0100
b5ccbdeda4 Remove expand_unlabeled_blossom() Joris van Rantwijk 2024-11-21 21:46:39 +0100
3815335a9f Keep alternating trees between stages in C++ Joris van Rantwijk 2024-11-20 21:10:14 +0100
082397ef80 Minor cleanup Joris van Rantwijk 2024-11-19 21:25:05 +0100
ab691813b3 The C++ code should now run in O(n*m*log(n)) Joris van Rantwijk 2024-11-17 21:19:15 +0100
105679c986 Use iterator to delete expanded blossom Joris van Rantwijk 2024-11-17 20:40:35 +0100
7683f891d5 Use priority queues for delta2 Joris van Rantwijk 2024-11-17 19:18:57 +0100
22251e64e8 Maintain concatenable queue for each blossom Joris van Rantwijk 2024-11-17 00:50:07 +0100
5b5c107a5c Initialize ConcatenableQueue name in constructor Joris van Rantwijk 2024-11-16 23:18:09 +0100
e8020f3e58 Use priority queue for delta4 Joris van Rantwijk 2024-11-16 20:23:51 +0100
2271df1897 Lazy updates of blossom duals Joris van Rantwijk 2024-11-16 14:23:13 +0100
228da75495 Lazy updates of vertex duals Joris van Rantwijk 2024-11-16 10:32:35 +0100
5500750c13 Reorganize code that handles labeling Joris van Rantwijk 2024-11-14 23:31:11 +0100
39eaea451e Minor code rearrangement Joris van Rantwijk 2024-11-10 00:10:26 +0100
7ea1562cc7 Use tight edges only during delta steps Joris van Rantwijk 2024-11-09 21:23:38 +0100
55a98238aa Implement heap-based tracking for delta3 Joris van Rantwijk 2024-11-09 00:11:07 +0100
b17ca1a364 Require signed type for edge weight Joris van Rantwijk 2024-11-08 20:30:53 +0100
67ca294840 Rework data structures Joris van Rantwijk 2024-11-08 18:38:20 +0100
efb238ff8e C++ datastructures for O(n*m*log(n)) Joris van Rantwijk 2023-06-16 19:55:43 +0200
e103a493fc Update Algorithm.md 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 v2 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

Commit Graph Select branches Hide Pull Requests master v2 v3 Mono Color

Commit Graph

Select branches

Hide Pull Requests

master

v2

v3