git: 1c4c1f36f6b4 - main - math/kamis: New port: Maximum independent sets and vertex covers of large sparse graphs
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Fri, 01 Jul 2022 18:30:34 UTC
The branch main has been updated by yuri:
URL: https://cgit.FreeBSD.org/ports/commit/?id=1c4c1f36f6b4c8715744e94afc243ec96431f8c4
commit 1c4c1f36f6b4c8715744e94afc243ec96431f8c4
Author: Yuri Victorovich <yuri@FreeBSD.org>
AuthorDate: 2022-07-01 18:28:53 +0000
Commit: Yuri Victorovich <yuri@FreeBSD.org>
CommitDate: 2022-07-01 18:30:31 +0000
math/kamis: New port: Maximum independent sets and vertex covers of large sparse graphs
---
math/Makefile | 1 +
math/kamis/Makefile | 25 ++++++++++++++++
math/kamis/distinfo | 3 ++
...refinement_kway__graph__refinement__commons.cpp | 28 ++++++++++++++++++
...2way__fm__refinement_vertex__moved__hashtable.h | 11 +++++++
..._quotient__graph__refinement_boundary__lookup.h | 11 +++++++
...ib_mis_evolutionary_combine_multiway__combine.h | 11 +++++++
...astKer_fast__reductions_src_MaximumMatching.cpp | 34 ++++++++++++++++++++++
math/kamis/pkg-descr | 11 +++++++
9 files changed, 135 insertions(+)
diff --git a/math/Makefile b/math/Makefile
index 2e50bf157323..4cb265f73493 100644
--- a/math/Makefile
+++ b/math/Makefile
@@ -402,6 +402,7 @@
SUBDIR += kahip
SUBDIR += kalgebra
SUBDIR += kalker
+ SUBDIR += kamis
SUBDIR += kbruch
SUBDIR += kcalc
SUBDIR += kfr
diff --git a/math/kamis/Makefile b/math/kamis/Makefile
new file mode 100644
index 000000000000..2794cab7f0bc
--- /dev/null
+++ b/math/kamis/Makefile
@@ -0,0 +1,25 @@
+PORTNAME= kamis
+DISTVERSIONPREFIX= v
+DISTVERSION= 2.0-19
+DISTVERSIONSUFFIX= -g254fd16
+CATEGORIES= math
+
+MAINTAINER= yuri@FreeBSD.org
+COMMENT= Maximum independent sets and vertex covers of large sparse graphs
+
+LICENSE= MIT
+LICENSE_FILE= ${WRKSRC}/LICENSE
+
+USES= cmake
+USE_LDCONFIG= yes
+
+USE_GITHUB= yes
+GH_ACCOUNT= KarlsruheMIS
+GH_PROJECT= KaMIS
+
+PLIST_FILES= bin/graphchecker \
+ bin/online_mis \
+ bin/redumis \
+ bin/sort_adjacencies
+
+.include <bsd.port.mk>
diff --git a/math/kamis/distinfo b/math/kamis/distinfo
new file mode 100644
index 000000000000..a91804a269d6
--- /dev/null
+++ b/math/kamis/distinfo
@@ -0,0 +1,3 @@
+TIMESTAMP = 1656665299
+SHA256 (KarlsruheMIS-KaMIS-v2.0-19-g254fd16_GH0.tar.gz) = 73d2b5c2808b2a15b9b8f3833a8d56f8e94fe1da8d6afed581f539f4533dcd70
+SIZE (KarlsruheMIS-KaMIS-v2.0-19-g254fd16_GH0.tar.gz) = 783177
diff --git a/math/kamis/files/patch-extern_KaHIP_lib_partition_uncoarsening_refinement_kway__graph__refinement_kway__graph__refinement__commons.cpp b/math/kamis/files/patch-extern_KaHIP_lib_partition_uncoarsening_refinement_kway__graph__refinement_kway__graph__refinement__commons.cpp
new file mode 100644
index 000000000000..2abbfd3bf645
--- /dev/null
+++ b/math/kamis/files/patch-extern_KaHIP_lib_partition_uncoarsening_refinement_kway__graph__refinement_kway__graph__refinement__commons.cpp
@@ -0,0 +1,28 @@
+--- extern/KaHIP/lib/partition/uncoarsening/refinement/kway_graph_refinement/kway_graph_refinement_commons.cpp.orig 2022-07-01 08:58:46 UTC
++++ extern/KaHIP/lib/partition/uncoarsening/refinement/kway_graph_refinement/kway_graph_refinement_commons.cpp
+@@ -9,7 +9,7 @@
+
+ #include "kway_graph_refinement_commons.h"
+
+-std::vector<kway_graph_refinement_commons*>* kway_graph_refinement_commons::m_instances = NULL;
++std::vector<kway_graph_refinement_commons*>* kway_graph_refinement_commons::m_instances = nullptr;
+
+ kway_graph_refinement_commons::kway_graph_refinement_commons() {
+
+@@ -24,13 +24,13 @@ kway_graph_refinement_commons* kway_graph_refinement_c
+ bool created = false;
+ #pragma omp critical
+ {
+- if( m_instances == NULL ) {
+- m_instances = new std::vector< kway_graph_refinement_commons*>(omp_get_max_threads(), reinterpret_cast<kway_graph_refinement_commons*>(NULL));
++ if( m_instances == nullptr ) {
++ m_instances = new std::vector< kway_graph_refinement_commons*>(omp_get_max_threads(), (kway_graph_refinement_commons*)nullptr);
+ }
+ }
+
+ int id = omp_get_thread_num();
+- if((*m_instances)[id] == NULL) {
++ if((*m_instances)[id] == nullptr) {
+ (*m_instances)[id] = new kway_graph_refinement_commons();
+ (*m_instances)[id]->init(config);
+ created = true;
diff --git a/math/kamis/files/patch-extern_KaHIP_lib_partition_uncoarsening_refinement_quotient__graph__refinement_2way__fm__refinement_vertex__moved__hashtable.h b/math/kamis/files/patch-extern_KaHIP_lib_partition_uncoarsening_refinement_quotient__graph__refinement_2way__fm__refinement_vertex__moved__hashtable.h
new file mode 100644
index 000000000000..e029e77ec89f
--- /dev/null
+++ b/math/kamis/files/patch-extern_KaHIP_lib_partition_uncoarsening_refinement_quotient__graph__refinement_2way__fm__refinement_vertex__moved__hashtable.h
@@ -0,0 +1,11 @@
+--- extern/KaHIP/lib/partition/uncoarsening/refinement/quotient_graph_refinement/2way_fm_refinement/vertex_moved_hashtable.h.orig 2022-07-01 08:56:00 UTC
++++ extern/KaHIP/lib/partition/uncoarsening/refinement/quotient_graph_refinement/2way_fm_refinement/vertex_moved_hashtable.h
+@@ -13,7 +13,7 @@
+ #include "definitions.h"
+ #include "limits.h"
+
+-using namespace __gnu_cxx;
++//using namespace __gnu_cxx;
+
+ struct compare_nodes {
+ bool operator()(const NodeID lhs, const NodeID rhs) const {
diff --git a/math/kamis/files/patch-extern_KaHIP_lib_partition_uncoarsening_refinement_quotient__graph__refinement_boundary__lookup.h b/math/kamis/files/patch-extern_KaHIP_lib_partition_uncoarsening_refinement_quotient__graph__refinement_boundary__lookup.h
new file mode 100644
index 000000000000..98911062c209
--- /dev/null
+++ b/math/kamis/files/patch-extern_KaHIP_lib_partition_uncoarsening_refinement_quotient__graph__refinement_boundary__lookup.h
@@ -0,0 +1,11 @@
+--- extern/KaHIP/lib/partition/uncoarsening/refinement/quotient_graph_refinement/boundary_lookup.h.orig 2022-07-01 08:53:36 UTC
++++ extern/KaHIP/lib/partition/uncoarsening/refinement/quotient_graph_refinement/boundary_lookup.h
+@@ -14,7 +14,7 @@
+ #include "limits.h"
+ #include "partial_boundary.h"
+
+-using namespace __gnu_cxx;
++//using namespace __gnu_cxx;
+
+ struct boundary_pair {
+ PartitionID k;
diff --git a/math/kamis/files/patch-lib_mis_evolutionary_combine_multiway__combine.h b/math/kamis/files/patch-lib_mis_evolutionary_combine_multiway__combine.h
new file mode 100644
index 000000000000..1e3bcab24927
--- /dev/null
+++ b/math/kamis/files/patch-lib_mis_evolutionary_combine_multiway__combine.h
@@ -0,0 +1,11 @@
+--- lib/mis/evolutionary/combine/multiway_combine.h.orig 2022-06-26 07:46:47 UTC
++++ lib/mis/evolutionary/combine/multiway_combine.h
+@@ -112,7 +112,7 @@ class multiway_combine : public combine {
+ * @param pool Pool of k-partitions.
+ * @param part The partition that was applied.
+ */
+- void apply_k_partition_kahip(MISConfig & config, graph_access & G, separator_pool *pool, partition & part);
++ void apply_k_partition_kahip(MISConfig & config, graph_access & G, separator_pool *pool, ::partition & part);
+
+ /**
+ * Get a random k-separator from the pool build with the KaHIP-interface.
diff --git a/math/kamis/files/patch-lib_mis_kernel_ParFastKer_fast__reductions_src_MaximumMatching.cpp b/math/kamis/files/patch-lib_mis_kernel_ParFastKer_fast__reductions_src_MaximumMatching.cpp
new file mode 100644
index 000000000000..28ed6411884e
--- /dev/null
+++ b/math/kamis/files/patch-lib_mis_kernel_ParFastKer_fast__reductions_src_MaximumMatching.cpp
@@ -0,0 +1,34 @@
+--- lib/mis/kernel/ParFastKer/fast_reductions/src/MaximumMatching.cpp.orig 2022-07-01 08:50:58 UTC
++++ lib/mis/kernel/ParFastKer/fast_reductions/src/MaximumMatching.cpp
+@@ -44,10 +44,12 @@
+ * */
+
+
+-#include <parallel/numeric>
++#include <numeric>
+ #include "MaximumMatching.h"
+ #include <sys/resource.h>
+
++#include <omp.h>
++
+ void increaseStackLimit(unsigned const size) {
+
+ const rlim_t kStackSize = size * 1024 * 1024; // size = min stack size in MB
+@@ -83,7 +85,7 @@ MaximumMatching::MaximumMatching(std::vector<std::vect
+ degree[i] = adjacencyArray[i].size();
+ degree[i + numVertices] = adjacencyArray[i].size();
+ }
+- auto end_ptr = __gnu_parallel::partial_sum(degree, degree + (G->n), (G->vtx_pointer) + 1);
++ auto end_ptr = std::partial_sum(degree, degree + (G->n), (G->vtx_pointer) + 1);
+ assert(end_ptr == &(G->vtx_pointer[2 * numVertices]) + 1);
+ G->vtx_pointer[0] = 0;
+ long numEdges = G->vtx_pointer[2 * numVertices];
+@@ -148,7 +150,7 @@ void MaximumMatching::LoadGraph(std::vector<SparseArra
+ degree[i] = deg;
+ degree[i + G->nrows] = deg;
+ }
+- auto end_ptr = __gnu_parallel::partial_sum(degree, degree + (G->n), (G->vtx_pointer) + 1);
++ auto end_ptr = std::partial_sum(degree, degree + (G->n), (G->vtx_pointer) + 1);
+ assert(end_ptr == &(G->vtx_pointer[G->n]) + 1);
+ G->vtx_pointer[0] = 0;
+ long numEdges = G->vtx_pointer[G->n];
diff --git a/math/kamis/pkg-descr b/math/kamis/pkg-descr
new file mode 100644
index 000000000000..4726a40fc3e3
--- /dev/null
+++ b/math/kamis/pkg-descr
@@ -0,0 +1,11 @@
+KaMIS (Karlsruhe Maximum Independent Sets) is an open source project
+finding maximum independent sets and vertex covers of large sparse
+graphs.
+
+Given a graph G=(V,E), the goal of the maximum independent set problem
+is to compute a maximum cardinality set of vertices I, such that no
+vertices in the set are adjacent to one another. Such a set is called
+a maximum independent set. The problem is NP-hard and particularly
+difficult to solve in large sparse graphs.
+
+WWW: https://karlsruhemis.github.io/