kahypar
v.1.3.5
Hypergraphs هي تعميم للرسوم البيانية ، حيث يمكن لكل حافة (Hyper) (التي تسمى أيضًا Net) توصيل أكثر من قمة. مشكلة تقسيم Hypergraph Hy -Way هي تعميم مشكلة تقسيم الرسوم البيانية المعروفة: التقسيم الذي تم تعيين قمة الرأس في كتل K مفككة من الحجم المحدد (على الأكثر 1 + intives متوسط حجم الكتلة) ، مع تقليل وظيفة موضوعية محددة على الشبكات.
أبرز وظيفتين موضوعيتين هما الشبكة المقطوعة والاتصال (أو λ-1). Cut-Net هو تعميم مباشر للهدف المقطوع الحافة في تقسيم الرسم البياني (أي ، يقلل من مجموع أوزان تلك الشبكات التي تربط أكثر من كتلة واحدة). بالإضافة إلى ذلك ، يأخذ مقياس الاتصال في الاعتبار الرقم الفعلي للكتل المتصلة بواسطة شبكة. من خلال تجميع القيم (λ-1) لجميع الشبكات ، يقوم أحدهم بصياغة حجم الاتصال الإجمالي لضرب المصفوفة المتفرق المتفرق ومرة أخرى يحصل على مقياس يعود إلى حافة الرسوم البيانية.
Kahypar هو إطار تقسيم فرط الرسم الفائق متعدد المستويات لتحسين القطع و (λ- 1). وهو يدعم كلاً من التشريح المتكرر وتقسيم K-Way المباشر . كخوارزمية متعددة المستويات ، تتكون من ثلاث مراحل: في مرحلة الغزو ، يتم تعقيد فرط الخرف للحصول على تسلسل هرمي من أشكال فرطات أصغر. بعد تطبيق خوارزمية التقسيم الأولية على أصغر فرط الخرف في المرحلة الثانية ، يتم التراجع عن التداخل ، وفي كل مستوى ، يتم استخدام طريقة بحث محلية لتحسين القسم الناجم عن المستوى الخشن. تقوم Kahypar بتثبيت النهج متعدد المستويات في نسخته الأكثر تطرفًا ، مما يزيل قمة واحدة فقط في كل مستوى من مستوى التسلسل الهرمي. من خلال استخدام هذا النهج الناعم جدًا في N -velize مع الاستدلال القوي للبحث المحلي ، فإنه يحسب حلول ذات جودة عالية للغاية. يتم تقديم خوارزمياتها والنتائج التجريبية التفصيلية في العديد من المنشورات البحثية.
تقسيم فرط الرسم البياني مع أوزان كتلة متغيرة
Kahypar لديه دعم لأوزان كتلة متغيرة. إذا تم استخدام خيار سطر الأوامر --use-individual-part-weights=true ، يحاول Partitioner تقسيم Hypergraph بحيث يكون لكل كتلة VX وزن في معظم BX ، حيث يمكن تحديد BX لكل كتلة على حدة باستخدام معلمة سطر الأوامر --part-weights= B1 B2 B3 ... Bk-1 . نظرًا لأن الإطار لا يدعم بعد التقسيم المتوازن تمامًا ، يجب أن تكون الحدود العليا أكبر قليلاً من الوزن الإجمالي لجميع رؤوس الرسم. لاحظ أن هذه الميزة لا تزال تجريبية.
تقسيم فرط الرسم البياني مع رؤوس ثابتة
تقسيم Hypergraph مع الرؤوس الثابتة هو تباين في تقسيم فرط الخريطة القياسية. في هذه المشكلة ، هناك قيود إضافية على تخصيص كتلة بعض القمم ، أي بعض القمم مُصممة على كتل محددة قبل التقسيم بشرط ، بعد تقسيم القمم "الحرة" المتبقية ، لا تزال القمم الثابتة في الكتلة التي تم تكليفها بها. يمكن استخدام معلمة سطر الأوامر --fixed / -f لتحديد ملف إصلاح بتنسيق ملف إصلاح HMETIS. بالنسبة لفرط الرسم البياني مع Veltices V ، يتكون ملف الإصلاح من خطوط V - واحدة لكل قمة. يحتوي السطر I th إما -1 للإشارة إلى أن قمة الرأس مجانية في التحرك أو <part id> للإشارة إلى أن هذه الرأس يجب أن يتم تصميمها قبل أن تمنع <part id> . لاحظ أن معرفات الجزء تبدأ من 0.
يدعم Kahypar حاليًا ثلاث سياسات تقلص مختلفة لتقسيمها مع القمم الثابتة:
free_vertex_only جميع الانقباضات التي يكون فيها شريك الانكماش قمة قمة مجانية ، أي أنه يتيح تقلصات من أزواج قمة الرأس حيث يكون كلتا الرئمين مجانيين ، أو يتم إصلاح قمة واحدة ويكون الرأس الآخر مجانيًا.fixed_vertex_allowed تقلصات من قمة ثابتة شريطة أن يتم تصميم كلاهما إلى نفس الكتلة. استنادًا إلى التجارب الأولية ، هذه هي السياسة الافتراضية حاليًا.equivalent_vertices سوى تقلصات من أزواج قمة الرأس التي تتكون من قمة مجانية أو اثنين من القمة الثابتة التي تم تصميمها على نفس الكتلة.الإطار التطوري (kahypar-e)
يعزز Kahypar-E Kahypar مع إطار تطوري كما هو موضح في منشور GECCO'18. بالنظر إلى كمية كبيرة من وقت التشغيل ، تعمل هذه الخوارزمية متعددة المستويات Memetic أفضل من عمليات الإعدام المتكررة لتكوينات Kahypar غير الثورية ، Hmetis ، و Patoh. يمكن استخدام معلمة سطر الأوامر --time-limit=xxx لتعيين الحد الأقصى لوقت التشغيل (بالثواني). المعلمة --partition-evolutionary=true تمكين التقسيم التطوري.
تحسين الأقسام الحالية
يستخدم Kahypar دورات V المباشرة K-Way لمحاولة تحسين قسم موجود محدد عبر المعلمة-- --part-file=</path/to/file> . يمكن التحكم في الحد الأقصى لعدد الدورات V عبر المعلمة- --vcycles= .
التقسيم الموجه Hypergraphs
على الرغم من أنه لم يتم دمج الكود في المستودع الرئيسي حتى الآن ، إلا أن هناك شوكة تدعم تقسيم Hypergraph Acyclic. يمكن العثور على مزيد من التفاصيل في منشور المؤتمر المقابل.
نستخدم ملفات تعريف الأداء لمقارنة Kahypar مع خوارزميات التقسيم الأخرى من حيث جودة الحل. لمجموعة من
الخوارزميات ومجموعة مؤشرات
تحتوي على
الحالات ، نسبة الأداء
يرتبط القطع المحسوبة بواسطة Partitioner P على سبيل المثال I إلى أصغر الحد الأدنى لجميع الخوارزميات ، أي ،
.
ملف تعريف الأداء
ثم يتم إعطاء الخوارزمية P بواسطة الوظيفة
.
لتحسين الاتصال ، يتم حساب نسب الأداء باستخدام قيم الاتصال
بدلا من قيم قطع. قيمة
يتوافق مع جزء الحالات التي قام فيها Partitioner P بحساب أفضل حل هو احتمال أن نسبة الأداء هو ضمن عامل
من أفضل نسبة ممكنة. لاحظ أنه نظرًا لأن ملفات تعريف الأداء تسمح فقط بتقييم أداء كل خوارزمية بالنسبة لأفضل خوارزمية ،
لا يمكن استخدام القيم لتصنيف الخوارزميات (أي ، لتحديد الخوارزمية هي ثاني الأفضل وما إلى ذلك).
في تحليلنا التجريبي ، تعتمد مخططات ملف تعريف الأداء على أفضل الحلول (أي الحد الأدنى للاتصال/قطع) كل خوارزمية موجودة لكل حالة. علاوة على ذلك ، نختار المعلمات
لجميع p ، أنا ، و
مثل نسبة الأداء
إذا وفقط إذا قامت الخوارزمية P بحساب حل غير ممكن على سبيل المثال ، و
إذا وفقط إذا لم تتمكن الخوارزمية من حساب حل على سبيل المثال ، فأنا ضمن الحد الزمني المحدد. في مخططات ملف تعريف الأداء لدينا ، سيتم عرض نسب الأداء المقابلة للحلول غير الممكنة على X -Tick على المحور X ، في حين أن الحالات التي لا يمكن تقسيمها خلال الوقت الزمني تظهر ضمنيًا بواسطة خط يخرج من المؤامرة أدناه
. نظرًا لأن نسب الأداء تتدفق بشكل كبير ، يتم تقسيم مخططات ملف تعريف الأداء إلى ثلاثة قطاعات ذات نطاقات مختلفة للمعلمة لتعكس مجالات الاهتمام المختلفة. يسلط الجزء الأول الضوء على القيم الصغيرة (
) ، في حين أن الجزء الثاني يحتوي على نتائج لجميع الحالات التي تصل إلى عامل
أسوأ من أفضل نسبة ممكنة. يحتوي الجزء الأخير على جميع النسب المتبقية ، على سبيل المثال ، الحالات التي أدت إليها بعض الخوارزميات أسوأ بكثير من أفضل الخوارزمية ، والحالات التي أنتجت الخوارزميات حلولًا غير قابلة للتطبيق ، والحالات التي لا يمكن تقسيمها خلال الحد الزمني المحدد.
في الأرقام ، قارنا kahypar مع patoh في الجودة (patoh-q) والوضع الافتراضي (patoh-d) ، و k-way (hmetis-k) ومتغير bisection العودية (hmetis-r) من hmetis 2.0 (p1) ، zoltan باستخدام coarsening الجبرية (zoltan-algd) خوارزمية.
جودة الحل 
وقت التشغيل 
نحن نقدم موارد إضافية لجميع المنشورات المتعلقة بـ Kahypar:
| kkahypar-se20 / rkahypar-se20 | Sea'20 | ورق | tr | الشرائح | النتائج التجريبية |
|---|---|---|---|---|---|
| kkahypar / rkahypar | - | أطروحة | - | الشرائح | النتائج التجريبية |
| kahypar-mf / kahypar-r-mf | Sea'18 / jea'19 | ورق البحر / ورقة جيا | tr | الشرائح | النتائج التجريبية: البحر / جيا |
| kahypar-e (evohgp) | GECCO'18 | ورق | tr | الشرائح | النتائج التجريبية |
| Kahypar-ca | Sea'17 | ورق | - | الشرائح | النتائج التجريبية |
| kahypar-k | Alenex'17 | ورق | - | الشرائح | النتائج التجريبية |
| kahypar-r | alenex'16 | ورق | tr | الشرائح | النتائج التجريبية |
يتطلب إطار تقسيم Karlsruhe Hypergraph:
g++ الإصدار 9 أو أعلى أو clang الإصدار 11.0.3 أو أعلى.-DKAHYPAR_USE_MINIMAL_BOOST=ON العلامة إلى أمر cmake لتنزيل التبعيات اللازمة واستخراجها وإنشائها تلقائيًا. استنساخ المستودع بما في ذلك العارض الفرعي:
git clone --depth=1 --recursive [email protected]:SebastianSchlag/kahypar.git
إنشاء دليل بناء: mkdir build && cd build
تشغيل cmake: cmake .. -DCMAKE_BUILD_TYPE=RELEASE
تشغيل جعل: make
يتم تنفيذ الاختبارات تلقائيًا أثناء بناء المشروع. بالإضافة إلى ذلك يتم توفير هدف test . يمكن بدء اختبارات التكامل من طرف إلى طرف: make integration_tests . يمكن تمكين التنميط عبر علامة cmake: -DENABLE_PROFILE=ON .
يمكن بناء البرنامج المستقل عبر make KaHyPar . سيكون الثنائي موجودًا على: build/kahypar/application/ .
Kahypar لديه العديد من معلمات التكوين. للحصول على قائمة بجميع المعلمات الممكنة ، يرجى تشغيل: ./KaHyPar --help . نستخدم تنسيق HMETIS لملف الإدخال Hypergraph بالإضافة إلى ملف إخراج القسم.
يمكن استخدام معلمة سطر الأوامر --quiet=1 لقمع جميع إخراج التسجيل. إذا كنت تستخدم واجهات المكتبة ، فإن إضافة quiet=1 إلى ملف تكوين .ini المقابل له نفس التأثير.
نحن نقدم تكوينين إطارين افتراضيين - واحد لتكييف الحزبين العودية ( R Kahypar) وواحد لتقسيم K -Way ( K Kahypar).
بشكل عام ، نوصي باستخدام K kahypar لأنه يعمل بشكل أفضل من R kahypar من حيث وقت التشغيل وجودة الحل.
لبدء K kahypar تحسين (الاتصال - 1) التشغيل الهدف:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/km1_kKaHyPar_sea20.ini
لبدء K kahypar تحسين تشغيل الهدف الصافي المقطوع :
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m direct -p ../../../config/cut_kKaHyPar_sea20.ini
لبدء R kahypar تحسين (الاتصال - 1) التشغيل الهدف:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m recursive -p ../../../config/km1_rKaHyPar_sea20.ini
لبدء R kahypar تحسين تشغيل الهدف الصافي المقطوع :
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m recursive -p ../../../config/cut_rKaHyPar_sea20.ini
لبدء خوارزمية memetic k kahypar -e تحسين (التوصيل - 1) التشغيل الهدف:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/km1_kKaHyPar-E_sea20.ini
بالإضافة إلى ذلك ، فإننا نقدم إعدادات مسبقة مختلفة تتوافق مع التكوينات المستخدمة في المنشورات في Alenex'16 و Alenex'17 و Sea'17 و Sea'18 و Gecco'18 ، وكذلك في ورقة Jea Journal وفي أطروحة Sebastian Schlag. توجد هذه التكوينات في مجلد config/old_reference_configs. من أجل استخدام هذه التكوينات ، يجب عليك الخروج من إصدار Kahypar 1.1.0 ، نظرًا لأن بعض التعليمات البرمجية القديمة تمت إزالتها في أحدث إصدار.
لبدء kahypar-mf (باستخدام التحسين القائم على التدفق ) تحسين الهدف (connectivity-1) باستخدام وضع K-way المباشر:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/old_reference_configs/km1_kahypar_mf_jea19.ini
لبدء kahypar-mf (باستخدام التحسين المستند إلى التدفق ) ، قم بتحسين هدف الشبكة المقطوعة باستخدام وضع k-wway المباشر:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m direct -p ../../../config/old_reference_configs/cut_kahypar_mf_jea19.ini
للبدء
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/old_reference_configs/km1_direct_kway_gecco18.ini
لاحظ أن التكوين km1_direct_kway_gecco18.ini يعتمد على kahypar-ca. ومع ذلك ، يعمل Kahypar-E أيضًا مع تحسينات محلية قائمة على التدفق. في منشور JEA الخاص بنا ، تم استخدام تكوين km1_kahypar_e_mf_jea19.ini .
لبدء kahypar-ca (باستخدام توخيل المجتمع ) تحسين الهدف (التوصيل-1) باستخدام وضع K-wway المباشر:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/old_reference_configs/km1_direct_kway_sea17.ini
لبدء Kahypar في وضع K-way Direct (Kahypar-K) تحسين (الاتصال-1) التشغيل الهدف:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/old_reference_configs/km1_direct_kway_alenex17.ini
لبدء kahypar في وضع التحسينات العودية (kahypar-r) تحسين تشغيل الهدف المقطوع:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m recursive -p ../../../config/old_reference_configs/cut_rb_alenex16.ini
يمكن الكتابة على جميع المعلمات المسبقة باستخدام خيارات سطر الأوامر المقابلة.
عند إنشاء Hypergraph Kahypar يتحقق من صحة أن الإدخال هو في الواقع فرط الخرف الصحي الصحيح ، وإلا طباعة خطأ وإجهاض. ينطبق هذا على ملفات إدخال HGR وواجهة C وواجهة Python. يجب أن تكون تكلفة وقت التشغيل للتحقق ضئيلة في جميع الحالات تقريبًا. ومع ذلك ، يمكن أيضًا تعطيل التحقق من صحة الإدخال باستخدام علامة cmake -DKAHYPAR_INPUT_VALIDATION=OFF .
بالإضافة إلى ذلك ، تتم طباعة التحذيرات للقضايا غير المميتة (مثل التضخم مع دبابيس مكررة). لعلاج المشكلات غير المميتة كأخطاء صلبة بدلاً من ذلك ، استخدم علامة cmake -DKAHYPAR_INPUT_VALIDATION_PROMOTE_WARNINGS_TO_ERRORS=ON .
نحن نقدم واجهة بسيطة على غرار C لاستخدام Kahypar كمكتبة. لاحظ أن هذه الواجهة ليست آمنة مؤشرات الترابط بعد. ومع ذلك ، هناك بعض الحلول الموجودة. يمكن بناء وتثبيت المكتبة عبر
make install.libraryويمكن استخدامها مثل هذا:
# include < memory >
# include < vector >
# include < iostream >
# include < libkahypar.h >
int main ( int argc, char * argv[]) {
kahypar_context_t * context = kahypar_context_new ();
kahypar_configure_context_from_file (context, " /path/to/config.ini " );
kahypar_set_seed (context, 42 );
const kahypar_hypernode_id_t num_vertices = 7 ;
const kahypar_hyperedge_id_t num_hyperedges = 4 ;
std::unique_ptr< kahypar_hyperedge_weight_t []> hyperedge_weights = std::make_unique< kahypar_hyperedge_weight_t []>( 4 );
// force the cut to contain hyperedge 0 and 2
hyperedge_weights[ 0 ] = 1 ; hyperedge_weights[ 1 ] = 1000 ;
hyperedge_weights[ 2 ] = 1 ; hyperedge_weights[ 3 ] = 1000 ;
std::unique_ptr< size_t []> hyperedge_indices = std::make_unique< size_t []>( 5 );
hyperedge_indices[ 0 ] = 0 ; hyperedge_indices[ 1 ] = 2 ;
hyperedge_indices[ 2 ] = 6 ; hyperedge_indices[ 3 ] = 9 ;
hyperedge_indices[ 4 ] = 12 ;
std::unique_ptr< kahypar_hyperedge_id_t []> hyperedges = std::make_unique< kahypar_hyperedge_id_t []>( 12 );
// hypergraph from hMetis manual page 14
hyperedges[ 0 ] = 0 ; hyperedges[ 1 ] = 2 ;
hyperedges[ 2 ] = 0 ; hyperedges[ 3 ] = 1 ;
hyperedges[ 4 ] = 3 ; hyperedges[ 5 ] = 4 ;
hyperedges[ 6 ] = 3 ; hyperedges[ 7 ] = 4 ;
hyperedges[ 8 ] = 6 ; hyperedges[ 9 ] = 2 ;
hyperedges[ 10 ] = 5 ; hyperedges[ 11 ] = 6 ;
const double imbalance = 0.03 ;
const kahypar_partition_id_t k = 2 ;
kahypar_hyperedge_weight_t objective = 0 ;
std::vector< kahypar_partition_id_t > partition (num_vertices, - 1 );
kahypar_partition (num_vertices, num_hyperedges,
imbalance, k,
/* vertex_weights */ nullptr , hyperedge_weights. get (),
hyperedge_indices. get (), hyperedges. get (),
&objective, context, partition. data ());
for ( int i = 0 ; i != num_vertices; ++i) {
std::cout << i << " : " << partition[i] << std::endl;
}
kahypar_context_free (context);
} لتجميع البرنامج باستخدام g++ Run:
g++ -std=c++14 -DNDEBUG -O3 -I/usr/local/include -L/usr/local/lib program.cc -o program -lkahypar ملاحظة: إذا لم يتم العثور على Boost أثناء الارتباط ، فقد تحتاج إلى إضافة -L/path/to/boost/lib -I/path/to/boost/include -lboost_program_options إلى الأمر.
لإزالة المكتبة من نظامك ، استخدم هدف إلغاء التثبيت المقدم:
make uninstall-kahyparلتجميع واجهة Python ، افعل ما يلي:
mkdir build && cd buildcmake .. -DCMAKE_BUILD_TYPE=RELEASE -DKAHYPAR_PYTHON_INTERFACE=1 . إذا لم يكن لديك دفعة مثبتة ، قم بتشغيل: cmake .. -DCMAKE_BUILD_TYPE=RELEASE -DKAHYPAR_PYTHON_INTERFACE=1 -DKAHYPAR_USE_MINIMAL_BOOST=ON بدلاً من ذلك. سيؤدي ذلك إلى تنزيل واستخراج وبناء التبعيات اللازمة تلقائيًا.cd pythonmakecp kahypar.so <path-to-site-packages>بعد ذلك يمكنك استخدام kahypar libary مثل هذا:
import os
import kahypar as kahypar
num_nodes = 7
num_nets = 4
hyperedge_indices = [ 0 , 2 , 6 , 9 , 12 ]
hyperedges = [ 0 , 2 , 0 , 1 , 3 , 4 , 3 , 4 , 6 , 2 , 5 , 6 ]
node_weights = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ]
edge_weights = [ 11 , 22 , 33 , 44 ]
k = 2
hypergraph = kahypar . Hypergraph ( num_nodes , num_nets , hyperedge_indices , hyperedges , k , edge_weights , node_weights )
context = kahypar . Context ()
context . loadINIconfiguration ( "<path/to/config>/km1_kKaHyPar_sea20.ini" )
context . setK ( k )
context . setEpsilon ( 0.03 )
kahypar . partition ( hypergraph , context )لمزيد من المعلومات حول وظيفة مكتبة Python ، يرجى الاطلاع على: module.cpp
نحن نقدم أيضًا نسخة مسبقة الجهد كـ A ، والتي يمكن تثبيتها عبر:
python3 -m pip install --index-url https://pypi.org/simple/ --no-deps kahypar
بفضل Jordan Jalving (@Jalving) تقدم Kahypar الآن واجهة Julia ، والتي يمكن العثور عليها حاليًا هنا: Kahypar/Kahypar.jl.
يمكن تثبيت التبعية المقابلة عبر:
using Pkg
Pkg . add ( PackageSpec (url = " https://github.com/jalving/KaHyPar.jl.git " ))
Pkg . test ( " KaHyPar " )بعد ذلك ، يمكنك استخدام kahypar لتقسيم عمليات الرسم المفرطة مثل هذا:
using KaHyPar
using SparseArrays
I = [ 1 , 3 , 1 , 2 , 4 , 5 , 4 , 5 , 7 , 3 , 6 , 7 ]
J = [ 1 , 1 , 2 , 2 , 2 , 2 , 3 , 3 , 3 , 4 , 4 , 4 ]
V = Int .( ones ( length (I)))
A = sparse (I,J,V)
h = KaHyPar . hypergraph (A)
KaHyPar . partition (h, 2 ,configuration = :edge_cut )
KaHyPar . partition (h, 2 ,configuration = :connectivity )
KaHyPar . partition (h, 2 ,configuration = joinpath ( @__DIR__ , " ../src/config/km1_kKaHyPar_sea20.ini " ))قام رومان والون بإنشاء واجهة Java لـ Kahypar. يرجى الرجوع إلى README للحصول على وصف مفصل حول كيفية إنشاء الواجهة واستخدامها.
نشجعك على الإبلاغ عن أي مشاكل مع Kahypar عبر نظام تتبع قضية Github للمشروع.
Kahypar هو برنامج مجاني متوفر تحت رخصة GNU العامة العامة (GPLV3). لمزيد من المعلومات ، راجع ملف النسخ. نقوم بتوزيع هذا الإطار بحرية لتعزيز استخدام وتطوير أدوات تقسيم Hypergraph. إذا كنت تستخدم Kahypar في إعداد أكاديمي ، فيرجى الاستشهاد بالأوراق المناسبة. إذا كنت مهتمًا برخصة تجارية ، فيرجى الاتصال بي.
// Overall KaHyPar framework
@phdthesis{DBLP:phd/dnb/Schlag20,
author = {Sebastian Schlag},
title = {High-Quality Hypergraph Partitioning},
school = {Karlsruhe Institute of Technology, Germany},
year = {2020}
}
@article{10.1145/3529090,
author = {Schlag, Sebastian and
Heuer, Tobias and
Gottesb"{u}ren, Lars and
Akhremtsev, Yaroslav and
Schulz, Christian and
Sanders, Peter},
title = {High-Quality Hypergraph Partitioning},
url = {https://doi.org/10.1145/3529090},
doi = {10.1145/3529090},
journal = {ACM J. Exp. Algorithmics},
year = {2022},
month = {mar}
}
// KaHyPar-R
@inproceedings{shhmss2016alenex,
author = {Sebastian Schlag and
Vitali Henne and
Tobias Heuer and
Henning Meyerhenke and
Peter Sanders and
Christian Schulz},
title = {k-way Hypergraph Partitioning via emph{n}-Level Recursive
Bisection},
booktitle = {18th Workshop on Algorithm Engineering and Experiments, (ALENEX 2016)},
pages = {53--67},
year = {2016},
}
// KaHyPar-K
@inproceedings{ahss2017alenex,
author = {Yaroslav Akhremtsev and
Tobias Heuer and
Peter Sanders and
Sebastian Schlag},
title = {Engineering a direct emph{k}-way Hypergraph Partitioning Algorithm},
booktitle = {19th Workshop on Algorithm Engineering and Experiments, (ALENEX 2017)},
pages = {28--42},
year = {2017},
}
// KaHyPar-CA
@inproceedings{hs2017sea,
author = {Tobias Heuer and
Sebastian Schlag},
title = {Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure},
booktitle = {16th International Symposium on Experimental Algorithms, (SEA 2017)},
pages = {21:1--21:19},
year = {2017},
}
// KaHyPar-MF
@inproceedings{heuer_et_al:LIPIcs:2018:8936,
author ={Tobias Heuer and Peter Sanders and Sebastian Schlag},
title ={{Network Flow-Based Refinement for Multilevel Hypergraph Partitioning}},
booktitle ={17th International Symposium on Experimental Algorithms (SEA 2018)},
pages ={1:1--1:19},
year ={2018}
}
@article{KaHyPar-MF-JEA,
author = {Heuer, T. and Sanders, P. and Schlag, S.},
title = {Network Flow-Based Refinement for Multilevel Hypergraph Partitioning},
journal = {ACM Journal of Experimental Algorithmics (JEA)}},
volume = {24},
number = {1},
month = {09},
year = {2019},
pages = {2.3:1--2.3:36},
publisher = {ACM}
}
// KaHyPar-E (EvoHGP)
@inproceedings{Andre:2018:MMH:3205455.3205475,
author = {Robin Andre and Sebastian Schlag and Christian Schulz},
title = {Memetic Multilevel Hypergraph Partitioning},
booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference},
series = {GECCO '18},
year = {2018},
pages = {347--354},
numpages = {8}
}
// KaHyPar-SEA20 (KaHyPar-HFC)
@InProceedings{gottesbren_et_al:LIPIcs:2020:12085,
author = {Lars Gottesb{"u}ren and Michael Hamann and Sebastian Schlag and Dorothea Wagner},
title = {{Advanced Flow-Based Multilevel Hypergraph Partitioning}},
booktitle = {18th International Symposium on Experimental Algorithms (SEA)},
pages = {11:1--11:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
year = {2020}
}
إذا كنت مهتمًا بالمساهمة في إطار Kahypar ، فلا تتردد في الاتصال بي أو إنشاء مشكلة في نظام تتبع المشكلات.
