stefiosif/reachability-algorithms
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity

Commit Graph

  • 6044d20c60 Include .vscode settings master stefiosif 2024-08-03 13:54:29 +03:00
  • 467edb4019 Fix issues with std::range::views using clang and C++20 stefiosif 2024-08-03 13:54:11 +03:00
  • 3951db7ff9 Use clang-format stefiosif 2024-08-03 13:14:42 +03:00
  • d216a9611f Add CMakeLists.txt and build script stefiosif 2024-08-03 13:14:07 +03:00
  • f5b48bbafd Update README Stefanos Iordanis Iosifidis 2023-03-08 22:40:25 +02:00
  • 80f8a00a24 Only update the reachability tree of the vertex that is the center of insertions stefiosif 2023-02-10 18:28:09 +02:00
  • 3591c58f6d Improve readability stefiosif 2023-02-10 18:26:48 +02:00
  • 2175ac0ca9 Add contains method for single vertex and hash function for SCCs stefiosif 2023-02-10 18:20:00 +02:00
  • 54eee41f7d Reconstruct only the deconstructed SCC stefiosif 2023-01-28 21:32:25 +02:00
  • c2a4a32c6d Add benchmark stefiosif 2022-12-05 23:45:10 +02:00
  • 55efd8b816 Update tests stefiosif 2022-12-05 23:44:55 +02:00
  • 7c78bbd7ca Remove "using namespace" from headers and make single param constructors explicit stefiosif 2022-12-03 15:43:00 +02:00
  • d7e87e0956 Update README, missing benchmarks stefiosif 2022-10-15 18:10:43 +03:00
  • c8c4afc64b Add dynamic reachability benchmark for dags and general graphs stefiosif 2022-10-15 18:10:27 +03:00
  • 38641ac6f4 Update README stefiosif 2022-10-15 11:55:42 +03:00
  • e7fd88f82c Refactor: Change reachability interfaces to handle multiple removals/insertions stefiosif 2022-10-15 10:40:08 +03:00
  • 04ab33888e Add random example stefiosif 2022-10-14 18:38:40 +03:00
  • 92cf8950c2 Move headers into include folder and add single header to include all reachability algorithms stefiosif 2022-10-14 18:38:01 +03:00
  • dc7fa93a6a Refactor: Replace std::map and std::set with unordered versions stefiosif 2022-10-12 17:26:11 +03:00
  • c525aeaa43 Refactor: Rename adjMatrix to adjList stefiosif 2022-10-12 16:57:48 +03:00
  • 8b6d341d18 Move Graph::vertices to Digraph stefiosif 2022-10-12 09:32:40 +03:00
  • 3d9651c474 Fix HK::query for vertices in set S and tests stefiosif 2022-10-12 09:31:58 +03:00
  • 0847851536 Add HenzingerKing tests stefiosif 2022-10-11 15:50:55 +03:00
  • 285109277b Upload README draft stefiosif 2022-10-11 15:50:22 +03:00
  • 70c7e2998c Add Eext removal in frigioni and tests stefiosif 2022-10-11 15:25:17 +03:00
  • b8f12e334a Refactor: Remove unused method setGraph stefiosif 2022-09-29 23:48:00 +03:00
  • a1f955ebb9 Refactor: Split remove into remove/repairTrees stefiosif 2022-09-29 23:47:36 +03:00
  • 371104a337 Complete RZ dynamic algorithm inspired by henzinger and king, TODO: finish frigioni stefiosif 2022-09-29 23:34:42 +03:00
  • fee5b8d0ab Add edge removal method and tree repair, TODO: handle Eext stefiosif 2022-09-29 23:33:54 +03:00
  • 9fd41bd85b Create getter method for the SCC collection stefiosif 2022-09-29 23:32:25 +03:00
  • f4acf57c88 Check if edge to be removed is part of the graph stefiosif 2022-09-26 12:33:13 +03:00
  • cbaf50d401 Fix TC to update correctly, and move all to-hook children on the stack stefiosif 2022-09-26 12:23:49 +03:00
  • 14a61c92e9 Update decremental algorithms according to project structure changes stefiosif 2022-09-25 17:42:00 +03:00
  • d63411672d Add dynamic RZ algorithms inspired by King and Henzinger stefiosif 2022-09-25 17:41:17 +03:00
  • fa65e54376 Rename decrementalscc to rodittyzwick as it is the core algorithm stefiosif 2022-09-25 17:33:47 +03:00
  • 95e7d56c1e Refactor file names to better understand inheritance of the skeleton of RZ algorithms stefiosif 2022-09-25 17:27:21 +03:00
  • ffc3ae4ec3 Complete Frigioni::query and Frigioni::init and tests stefiosif 2022-09-21 19:35:23 +03:00
  • 813c63a4ea Add unit test for SCC::normalize stefiosif 2022-09-21 19:32:57 +03:00
  • 5f9b225609 Add method that identifies if a vertex is part of this component stefiosif 2022-09-21 19:32:00 +03:00
  • 7345a28945 Fix bug that would make ids connect to a different component stefiosif 2022-09-21 19:30:26 +03:00
  • 7d2d9fd82c Finish italiano and tests stefiosif 2022-09-20 13:41:15 +03:00
  • 40f23c5bf8 Add method to access adjMatrix keys and add adjMatrix on seaching method stefiosif 2022-09-19 22:04:45 +03:00
  • 0b16ebc677 Update italiano::remove stefiosif 2022-09-16 15:17:50 +03:00
  • 037560949d Update misc stefiosif 2022-09-16 15:17:32 +03:00
  • ae193d5f69 Update italiano's query and remove methods stefiosif 2022-09-14 19:41:33 +03:00
  • 0ffc20496d Add vertices without arcs into the BFTree stefiosif 2022-09-14 19:41:08 +03:00
  • 42f824a249 Update decremental scc algorithm stefiosif 2022-09-12 00:08:45 +03:00
  • 5c1b13b400 Add default param constructors, create bool query for bfs and tests stefiosif 2022-09-09 18:12:38 +03:00
  • a4ddc3fbe7 Add operator<< for graph types, add contains query for digraph types and normalize scc stefiosif 2022-09-09 17:50:28 +03:00
  • 4d189f269c Fix graph volume V() stefiosif 2022-08-09 00:22:21 +03:00
  • 3f3c58b0b8 Add italiano edge removal algorithm sketch stefiosif 2022-08-09 00:21:03 +03:00
  • 1a416794fc Revert "Fix volume V()" stefiosif 2022-08-09 00:15:47 +03:00
  • a40e42b964 Fix volume V() stefiosif 2022-08-09 00:15:26 +03:00
  • 433955e2cf Minor project updates and add 2 example datasets stefiosif 2022-08-08 22:22:52 +03:00
  • 484d90482f Add incomplete benchmark files stefiosif 2022-08-08 22:21:58 +03:00
  • d459fe9df6 Split frigioni and italiano algorithms and add query function stefiosif 2022-08-08 22:20:32 +03:00
  • dd71ab75b6 Add custom equality comparison for SCCs stefiosif 2022-08-08 22:18:52 +03:00
  • 5f5bd889d7 Change test file name to split fully dynamic and decremental algorithms stefiosif 2022-07-29 17:14:40 +03:00
  • 8e8cf23399 Add required data structures for DecrementalTC::init stefiosif 2022-07-26 20:42:38 +03:00
  • 48de05174a Add tests for DecrementalSCC::query and DecrementalSCC::remove stefiosif 2022-07-26 20:42:02 +03:00
  • 46cdadc758 Add tests for Digraph::V and Digraph::E stefiosif 2022-07-26 20:39:57 +03:00
  • 41e5bead43 Add new tests, remove duplicate tests (scc creation ~ tarjan's algorithm) stefiosif 2022-07-20 23:46:50 +03:00
  • fe3bb68c18 Add single vertex contains method and replace vertices field with adjMatrix' keys stefiosif 2022-07-20 23:43:15 +03:00
  • 31567f9e57 Add BreadthFirstTree's to decremental maintenance algorithm and delete In/Out tree classes stefiosif 2022-07-20 23:04:06 +03:00
  • 227749b9e4 Make reverse() return type auto stefiosif 2022-07-13 23:04:59 +03:00
  • 31ba84dc2a Add remove and contain functions stefiosif 2022-07-13 23:02:54 +03:00
  • 0f857a6c9e Add new graph example stefiosif 2022-07-12 14:44:43 +03:00
  • 601f80c8d4 Fix includes and add some comments stefiosif 2022-07-12 14:42:29 +03:00
  • e7ad824116 Put root of BFS tree as constructor parameter stefiosif 2022-07-12 14:41:18 +03:00
  • 77dee72317 Add license stefiosif 2022-07-10 16:47:07 +03:00
  • b9cd1a1cbd Split graph folder into graph and tree stefiosif 2022-07-10 15:32:13 +03:00
  • 3fa6935b84 Add virtual class for the dynamic reachability algorithms stefiosif 2022-07-10 15:31:00 +03:00
  • 4a9cbe19f9 Make SCC inherit parent constructor to avoid duplicate code stefiosif 2022-07-10 13:23:27 +03:00
  • 6b1edfa164 Update final step of decremental scc algorithm stefiosif 2022-06-29 17:58:52 +03:00
  • d199b7de17 Add tests for same SCC O(1) query stefiosif 2022-06-29 17:33:27 +03:00
  • 8d8e6ef831 Change project structure stefiosif 2022-06-27 22:45:26 +03:00
  • e488b309c8 Update decremental maintenance of SCC algorithm stefiosif 2022-06-27 17:45:47 +03:00
  • de29435933 Add reverse a digraph function and test stefiosif 2022-06-13 17:04:43 +03:00
  • 1e16e671ea Make RodittyZwick class abstract stefiosif 2022-06-13 12:57:09 +03:00
  • cc79737ecc Add roditty and zwick class stefiosif 2022-06-12 20:33:11 +03:00
  • 4058c3f6fb Make bfs return a digraph since shortest-path in-out trees are directed graphs stefiosif 2022-06-12 20:32:15 +03:00
  • 2029900035 Update tarjan test cases and add BFS test case stefiosif 2022-06-12 17:34:52 +03:00
  • 72741a6a5b Make class Graph abstract and make derived classes Digraph and SCC stefiosif 2022-06-12 00:49:42 +03:00
  • b5b031db7f Add BFS tree stefiosif 2022-06-11 19:27:03 +03:00
  • dfa8e649ee Create variable instead of reference when accessing the stack stefiosif 2022-06-11 19:17:37 +03:00
  • 89a2a24f50 Add decremental maintenance of SCCs frame stefiosif 2022-05-17 21:25:47 +03:00
  • c2c278784b Delete unused methods stefiosif 2022-05-15 00:39:36 +03:00
  • 8a52c80bc8 Finish Tarjan algorithm and add tests stefiosif 2022-05-07 17:05:43 +03:00
  • 122d11b189 Add base paper and tarjan's SCC algorithm stefiosif 2022-05-06 12:25:04 +03:00
  • adb36adea7 Add core graph member functions stefiosif 2022-05-02 17:57:04 +03:00
  • 116d8831e2 Update gitignore and add relevant paper stefiosif 2022-04-25 20:31:06 +03:00
  • 0ab49de690 Add nanobench stefiosif 2022-04-21 20:29:36 +03:00
  • 550d83bb84 Add doctest stefiosif 2022-04-21 20:28:11 +03:00
  • abcaa2662d Add project files. stefiosif 2022-04-21 20:07:24 +03:00