From nobody Fri Jul 01 18:30:34 2022 X-Original-To: dev-commits-ports-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 6B98E8A4FA0; Fri, 1 Jul 2022 18:30:34 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4LZNzt2bwgz3QN6; Fri, 1 Jul 2022 18:30:34 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1656700234; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=l98p/8Tita7ITJLI3mYyfgFjqC8nYF4bARPI5jeH5Eg=; b=iHWGip5OgsdqevT+teg41qheL9/eFjeqdAe+2xhbXVUiT7Htxo4nVH4CHwn1NtYtXoPbaf dFeBxuPwMv34q1Fo9bbn3L40nzklNOa5+KIsY9+bMpCL0Ltfh/84Ag8I4EqHLMhWarRaZ8 /JAaUYourTUhTIkYlWyMAD64LKZPIBtFl7ByVklpZbqFfgsr3wDYeRcccG2wovBY894TOz E/S+hkySTcmlhl0S4gnG1JdiHf3qrYq/X6z1cF1QUDL9DKwrkb0nGdSz1IibfqfuUzUGPh vTV0w5yqyGE32MbuAzy0O0yOb6FjJaFGMJYJsjMxsHmRKAcVwkB3hefFK3vpMQ== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 336FF20984; Fri, 1 Jul 2022 18:30:34 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 261IUYRt051385; Fri, 1 Jul 2022 18:30:34 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 261IUYHu051384; Fri, 1 Jul 2022 18:30:34 GMT (envelope-from git) Date: Fri, 1 Jul 2022 18:30:34 GMT Message-Id: <202207011830.261IUYHu051384@gitrepo.freebsd.org> To: ports-committers@FreeBSD.org, dev-commits-ports-all@FreeBSD.org, dev-commits-ports-main@FreeBSD.org From: Yuri Victorovich Subject: git: 1c4c1f36f6b4 - main - math/kamis: New port: Maximum independent sets and vertex covers of large sparse graphs List-Id: Commit messages for all branches of the ports repository List-Archive: https://lists.freebsd.org/archives/dev-commits-ports-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-ports-all@freebsd.org X-BeenThere: dev-commits-ports-all@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: yuri X-Git-Repository: ports X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 1c4c1f36f6b4c8715744e94afc243ec96431f8c4 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1656700234; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=l98p/8Tita7ITJLI3mYyfgFjqC8nYF4bARPI5jeH5Eg=; b=kqeZ0/8/2x4+spN/IlnacU0opI72rNjklZ8tFNUI/Ts0U3ffkp61FOiEK7ghi7bkdPxxpf s8X4FMePMSNXCBwDe8DT+NTajeRxP1x4EJUbU29a2uDchYsy5HwcXq2RWPVv7sOqF4lat1 yaZKn+DdemKsj/UrsXGQkc7Z0QuCVPnRjr1iEc3aGwY/NGUGL4bxKu10lhggbIjat7S/vE j1j5l528H2SIjWDQIuZieMJ1AuxYc310lY2T/1SgvgO3Amq5XKwq9pJxcyVQPWfuwBptOh BUfolIhgx1THy50QYuh8cxx4uleujYhgfpoFqUCHha5CCLAX4mqzl4Dv1Z3pQQ== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1656700234; a=rsa-sha256; cv=none; b=XeuwWewPdvWr2thNoI98GwJKteWWHWJ6JSMz2120LPprXjdnd602Z0kUT8PUzpAz9ruAL8 cUIt8uoDQu1gUOUE9cqltNDAfI80YcccC01H+ZTRKnP2ry5Lx+cSubZHKq4mCi6Cp5ipWT JmWoCmgNE4Va7DLDZP4kwXAHi7TZdVjE0snVjWyFqdi26T0SdAjzxBzEfn4Xg1FLZXj2gA z4mXct+/EDoSURutkMNuTMDaIYqbEJg6m4inB3//5nNdljtpdjl4L7wdSGAPGH4GHms7Rj 6Jlbas9nRmEwCr/6+/0QxAqcaHGTx3kFT2Av2vu7zY17jsaeuXHhsfgsq8V4Bw== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch main has been updated by yuri: URL: https://cgit.FreeBSD.org/ports/commit/?id=1c4c1f36f6b4c8715744e94afc243ec96431f8c4 commit 1c4c1f36f6b4c8715744e94afc243ec96431f8c4 Author: Yuri Victorovich AuthorDate: 2022-07-01 18:28:53 +0000 Commit: Yuri Victorovich 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 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::m_instances = NULL; ++std::vector* 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(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 ++#include + #include "MaximumMatching.h" + #include + ++#include ++ + 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::vectorn), (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::vectornrows] = 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/