kahypar
v.1.3.5
ไฮเปอร์กราฟเป็นภาพรวมของกราฟโดยที่ขอบ (ไฮเปอร์) แต่ละอัน (เรียกอีกอย่างว่าเน็ต) สามารถเชื่อมต่อได้มากกว่าสองจุด ปัญหาการแบ่งพาร์ติชัน K -way hypergraph คือการวางนัยทั่วไปของปัญหาการแบ่ง กราฟ ที่รู้จักกันดี: พาร์ติชันจุดสุดยอดตั้งค่าเป็นบล็อก disjoint ของขนาดที่มีขอบเขต (มากที่สุด 1 + εเท่าที่ขนาดบล็อกเฉลี่ย)
ฟังก์ชั่นวัตถุประสงค์ที่โดดเด่นที่สุดสองฟังก์ชั่นคือการตัดและการเชื่อมต่อ (หรือλ-1) ตัวชี้วัด Cut-Net เป็นลักษณะทั่วไปที่ตรงไปตรงมาของวัตถุประสงค์ที่ตัดขอบในการแบ่งกราฟ (เช่นลดผลรวมของน้ำหนักของอวนเหล่านั้นที่เชื่อมต่อมากกว่าหนึ่งบล็อก) ตัวชี้วัดการเชื่อมต่อยังคำนึงถึงหมายเลขจริงλของบล็อกที่เชื่อมต่อด้วยเน็ต โดยการรวม (λ-1) -values ของอวนทั้งหมดหนึ่งแบบจำลองปริมาณการสื่อสารทั้งหมดอย่างแม่นยำของการคูณเมทริกซ์-เวกเตอร์-เวกเตอร์แบบขนานและอีกครั้งจะได้รับการวัดที่เปลี่ยนเป็นกราฟธรรมดา
Kahypar เป็นกรอบการแบ่งพาร์ติชันไฮเปอร์กราฟหลายระดับสำหรับการปรับการตัด- และ (λ- 1)- เมทริก รองรับทั้ง การแบ่งแยกแบบเรียกซ้ำ และการแบ่งพาร์ติชัน K-way โดยตรง ในฐานะอัลกอริทึมหลายระดับมันประกอบด้วยสามขั้นตอน: ใน ขั้นตอนที่มีความหยาบ ไฮเปอร์กราฟจะหยาบเพื่อให้ได้ลำดับชั้นของไฮเปอร์กราฟขนาดเล็ก หลังจากใช้อัลกอริทึม การแบ่งพาร์ติชันเริ่มต้น กับไฮเปอร์กราฟที่เล็กที่สุดในระยะที่สองการหยาบจะถูกยกเลิกและในแต่ละระดับวิธี การค้นหาในท้องถิ่น จะใช้เพื่อปรับปรุงพาร์ติชันที่เกิดจากระดับที่หยาบกว่า Kahypar สร้างสรรค์วิธีการหลายระดับในเวอร์ชันที่รุนแรงที่สุดโดยลบจุดสุดยอดเพียงครั้งเดียวในทุกระดับของลำดับชั้น ด้วยการใช้วิธี N -level ที่ละเอียดมากนี้รวมกับฮิวริสติกการค้นหาในท้องถิ่นที่แข็งแกร่งมันคำนวณโซลูชันที่มีคุณภาพสูงมาก อัลกอริทึมและผลการทดลองโดยละเอียดจะถูกนำเสนอในสิ่งพิมพ์การวิจัยหลายฉบับ
การแบ่งพาร์ติชันไฮเปอร์กราฟด้วยน้ำหนักบล็อกตัวแปร
Kahypar มีการรองรับน้ำหนักบล็อกผันแปร หากใช้ตัวเลือกบรรทัดคำสั่ง --use-individual-part-weights=true พาร์ทิชันพยายามที่จะแบ่งพาร์ติชันไฮเปอร์กราฟเพื่อให้แต่ละบล็อก VX มีน้ำหนักของ BX ส่วนใหญ่ที่ BX สามารถระบุได้สำหรับแต่ละบล็อกโดยใช้พารามิเตอร์บรรทัดคำสั่ง --part-weights= B1 B2 B3 ... Bk-1 เนื่องจากเฟรมเวิร์กยังไม่รองรับการแบ่งพาร์ติชันที่สมดุลอย่างสมบูรณ์แบบขอบเขตบนจำเป็นต้องมีขนาดใหญ่กว่าน้ำหนักรวมของจุดยอดทั้งหมดของไฮเปอร์กราฟเล็กน้อย โปรดทราบว่าคุณลักษณะนี้ยังคงทดลองอยู่
การแบ่งพาร์ติชันไฮเปอร์กราฟด้วยจุดยอดคงที่
การแบ่งพาร์ติชันไฮเปอร์กราฟด้วยจุดยอดคงที่เป็นการเปลี่ยนแปลงของการแบ่งพาร์ติชันไฮเปอร์กราฟมาตรฐาน ในปัญหานี้มีข้อ จำกัด เพิ่มเติมเกี่ยวกับการกำหนดบล็อกของจุดยอดบางอย่างเช่นจุดยอดบางส่วนจะได้รับการออกแบบให้กับบล็อกเฉพาะก่อนที่จะแบ่งพาร์ติชันด้วยเงื่อนไขที่หลังจากการแบ่งพาร์ติชันที่เหลือ "ฟรี" จุดยอดคงที่ยังคงอยู่ในบล็อกที่พวกเขาได้รับมอบหมาย พารามิเตอร์บรรทัดคำสั่ง --fixed / -f สามารถใช้เพื่อระบุไฟล์ fix ในรูปแบบไฟล์ HMETIS Fix สำหรับไฮเปอร์กราฟที่มี Vertices V ไฟล์ fix ประกอบด้วยบรรทัด V - หนึ่งสำหรับแต่ละจุดยอด บรรทัด i th มี -1 เพื่อระบุว่าจุดสุดยอดนั้นมีอิสระที่จะย้ายหรือ <part id> เพื่อระบุว่าจุดสุดยอดนี้ควรได้รับการออกแบบล่วงหน้าเพื่อบล็อก <part id> โปรดทราบว่า ID ส่วนเริ่มต้นจาก 0
ปัจจุบัน Kahypar สนับสนุนนโยบายการหดตัวที่แตกต่างกันสามประการสำหรับการแบ่งพาร์ติชันด้วยจุดยอดคงที่:
free_vertex_only อนุญาตให้มีการหดตัวทั้งหมดที่คู่ค้าการหดตัวเป็นจุดสุดยอด ฟรี เช่นจะช่วยให้การหดตัวของคู่จุดสุดยอดที่จุดยอดทั้งสองฟรีหรือจุดยอดหนึ่งได้รับการแก้ไขและจุดยอดอื่น ๆ ฟรีfixed_vertex_allowed เพิ่มเติมอนุญาตให้มีการหดตัวของจุดยอดคงที่สองจุดโดยมีเงื่อนไขว่าทั้งคู่จะได้รับการออกแบบล่วงหน้าไปยังบล็อก เดียวกัน จากการทดลองเบื้องต้นปัจจุบันเป็นนโยบายเริ่มต้นequivalent_vertices อนุญาตให้หดตัวของคู่จุดสุดยอดที่ประกอบด้วยจุดยอดฟรีสองจุดหรือจุดยอดคงที่สองจุดที่ออกแบบไว้กับบล็อกเดียวกันเฟรมเวิร์กวิวัฒนาการ (Kahypar-E)
Kahypar-E ช่วยเพิ่ม Kahypar ด้วยกรอบวิวัฒนาการตามที่อธิบายไว้ในสิ่งพิมพ์ Gecco'18 ของเรา ด้วยเวลาทำงานค่อนข้างมากอัลกอริทึมหลายระดับที่น่าจดจำนี้ทำงานได้ดีกว่าการประหารชีวิตซ้ำ ๆ ของการกำหนดค่า Kahypar ที่ไม่ใช่ปฏิวัติ, Hmetis และ Patoh พารามิเตอร์บรรทัดคำสั่ง --time-limit=xxx สามารถใช้เพื่อตั้งค่าเวลาทำงานสูงสุด (เป็นวินาที) พารามิเตอร์ --partition-evolutionary=true เปิดใช้งานการแบ่งพาร์ติชันวิวัฒนาการ
การปรับปรุงพาร์ติชันที่มีอยู่
Kahypar ใช้ K-Way V-cycles โดยตรงเพื่อพยายามปรับปรุงพาร์ติชันที่มีอยู่ที่ระบุผ่านพารามิเตอร์ --part-file=</path/to/file> จำนวนสูงสุดของ V-cycles สามารถควบคุมได้ผ่านพารามิเตอร์ --vcycles=
การแบ่งไฮเปอร์กราฟ
ในขณะที่รหัสยังไม่ได้รวมเข้ากับที่เก็บหลัก แต่ก็มีส้อมที่รองรับการแบ่งพาร์ติชันไฮเปอร์กราฟอะซิลิค รายละเอียดเพิ่มเติมสามารถพบได้ในสิ่งพิมพ์การประชุมที่เกี่ยวข้อง
เราใช้ โปรไฟล์ประสิทธิภาพ เพื่อเปรียบเทียบ Kahypar กับอัลกอริทึมการแบ่งพาร์ติชันอื่น ๆ ในแง่ของคุณภาพการแก้ปัญหา สำหรับชุดของ
อัลกอริทึมและชุดมาตรฐาน
การมีอยู่
อินสแตนซ์ อัตราส่วนประสิทธิภาพ
เกี่ยวข้องกับการตัดที่คำนวณโดย partitioner P เช่น ฉัน กับการตัดขั้นต่ำที่เล็กที่สุดของอัลกอริทึม ทั้งหมด เช่น
-
โปรไฟล์ประสิทธิภาพ
ของอัลกอริทึม P จะได้รับจากฟังก์ชัน
-
สำหรับการเพิ่มประสิทธิภาพการเชื่อมต่ออัตราส่วนประสิทธิภาพจะถูกคำนวณโดยใช้ค่าการเชื่อมต่อ
แทนที่จะเป็นค่าตัด ค่าของ
สอดคล้องกับสัดส่วนของอินสแตนซ์ที่ Partitioner P คำนวณทางออกที่ดีที่สุดในขณะที่ คือความน่าจะเป็นที่อัตราส่วนประสิทธิภาพ อยู่ในปัจจัย
อัตราส่วนที่ดีที่สุดเท่าที่จะเป็นไปได้ โปรดทราบว่าเนื่องจากโปรไฟล์ประสิทธิภาพอนุญาตให้ประเมินประสิทธิภาพของอัลกอริทึมแต่ละตัวที่สัมพันธ์กับอัลกอริทึม ที่ดีที่สุด เท่านั้น
ค่าไม่สามารถใช้ในการจัดอันดับอัลกอริทึม (เช่นเพื่อกำหนดอัลกอริทึมที่ดีที่สุดเป็นอันดับสอง ฯลฯ )
ในการวิเคราะห์การทดลองของเราพล็อตโปรไฟล์ประสิทธิภาพจะขึ้นอยู่กับโซลูชัน ที่ดีที่สุด (เช่นการเชื่อมต่อ ขั้นต่ำ /การตัด) แต่ละอัลกอริทึมที่พบสำหรับแต่ละอินสแตนซ์ นอกจากนี้เราเลือกพารามิเตอร์
สำหรับ P , I และ
เช่นนั้นอัตราส่วนประสิทธิภาพ
หากอัลกอริทึม P คำนวณวิธีแก้ปัญหาที่ไม่สามารถทำได้เช่น I และ
หากอัลกอริทึมไม่สามารถคำนวณวิธีแก้ปัญหาได้เช่น ฉัน ภายในระยะเวลาที่กำหนด ในพล็อตโปรไฟล์ประสิทธิภาพของเราอัตราส่วนประสิทธิภาพที่สอดคล้องกับโซลูชัน ที่ไม่สามารถทำได้ จะแสดงบน X -Tick บน X -axis ในขณะที่อินสแตนซ์ที่ไม่สามารถแบ่งพาร์ติชันภายในเวลา จำกัด จะแสดงโดยเส้นที่ออกจากพล็อตด้านล่างโดยปริยายที่ออกจากพล็อตด้านล่าง
- เนื่องจากอัตราส่วนประสิทธิภาพนั้นเบี่ยงเบนไปอย่างมากพล็อตโปรไฟล์ประสิทธิภาพจึงแบ่งออกเป็นสามส่วนด้วยช่วงที่แตกต่างกันสำหรับพารามิเตอร์ เพื่อสะท้อนพื้นที่ต่าง ๆ ที่น่าสนใจ ส่วนแรกเน้นค่าเล็ก ๆ (
) ในขณะที่เซ็กเมนต์ที่สองมีผลลัพธ์สำหรับทุกกรณีที่สูงถึงปัจจัย
แย่กว่าอัตราส่วนที่ดีที่สุดเท่าที่จะเป็นไปได้ ส่วนสุดท้ายมีอัตราส่วนที่เหลือทั้งหมดเช่นอินสแตนซ์ที่อัลกอริทึมบางอย่างดำเนินการแย่กว่าอัลกอริทึมที่ดีที่สุดอย่างมากอินสแตนซ์ที่อัลกอริทึมผลิตโซลูชันที่ไม่สามารถทำได้และอินสแตนซ์ที่ไม่สามารถแบ่งพาร์ติชันภายในเวลาที่กำหนด
ในตัวเลขเราเปรียบเทียบ kahypar กับ patoh ในคุณภาพ (patoh-q) และโหมดเริ่มต้น (patoh-d), k-way (hmetis-k) และตัวแปร biscedection แบบเรียกซ้ำ (HMETIS-R) ของ HMETIS 2.0 (P1) อัลกอริทึม hype
คุณภาพการแก้ปัญหา 
เวลาทำงาน 
เราให้บริการทรัพยากรเพิ่มเติมสำหรับสิ่งพิมพ์ที่เกี่ยวข้องกับ Kahypar ทั้งหมด:
| Kkahypar-Sea20 / rkahypar-sea20 | Sea'20 | กระดาษ | TR | สไลด์ | ผลการทดลอง |
|---|---|---|---|---|---|
| Kkahypar / Rkahypar | - | วิทยานิพนธ์ | - | สไลด์ | ผลการทดลอง |
| kahypar-mf / Kahypar-R-MF | Sea'18 / jea'19 | กระดาษทะเล / กระดาษ Jea | TR | สไลด์ | ผลการทดลอง: ทะเล / JEA |
| 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 เพื่อดาวน์โหลดแยกและสร้างการพึ่งพาที่จำเป็นโดยอัตโนมัติ โคลนพื้นที่เก็บข้อมูลรวมถึง submodules:
git clone --depth=1 --recursive [email protected]:SebastianSchlag/kahypar.git
สร้างไดเรกทอรีบิลด์: mkdir build && cd build
เรียกใช้ cmake: cmake .. -DCMAKE_BUILD_TYPE=RELEASE
Run Make: make
การทดสอบจะดำเนินการโดยอัตโนมัติในขณะที่สร้างโครงการ นอกจากนี้ยังมีเป้าหมาย test การทดสอบการรวมแบบ end-to-end สามารถเริ่มต้นได้ด้วย: make integration_tests การทำโปรไฟล์สามารถเปิดใช้งานผ่าน CMake Flag: -DENABLE_PROFILE=ON
สามารถสร้างโปรแกรมแบบสแตนด์อโลนผ่าน make KaHyPar ไบนารีจะอยู่ที่: build/kahypar/application/
Kahypar มีพารามิเตอร์การกำหนดค่าหลายอย่าง สำหรับรายการพารามิเตอร์ที่เป็นไปได้ทั้งหมดโปรดเรียกใช้: ./KaHyPar --help เราใช้รูปแบบ HMETIS สำหรับไฟล์อินพุตไฮเปอร์กราฟรวมถึงไฟล์เอาต์พุตพาร์ติชัน
พารามิเตอร์บรรทัดคำสั่ง --quiet=1 สามารถใช้เพื่อระงับเอาต์พุตการบันทึกทั้งหมด หากคุณใช้อินเทอร์เฟซไลบรารีการเพิ่ม quiet=1 ในไฟล์การกำหนดค่า .ini ที่สอดคล้องกันมีเอฟเฟกต์เดียวกัน
เราให้การกำหนดค่าเฟรมเวิร์กเริ่มต้นสองแบบ - หนึ่งสำหรับการเรียกซ้ำ bipartitioning ( 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 Release 1.1.0 เนื่องจากรหัสเก่าบางส่วนที่ถูกลบออกในรุ่นล่าสุด
ในการเริ่มต้น Kahypar-MF (โดยใช้ การปรับแต่งแบบไหล ) เพิ่มประสิทธิภาพ (การเชื่อมต่อ-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-way โดยตรง:
./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
ในการเริ่มต้น EvoHGP/Kahypar-E การเพิ่มประสิทธิภาพ (การเชื่อมต่อ-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_direct_kway_gecco18.ini
โปรดทราบว่าการกำหนดค่า km1_direct_kway_gecco18.ini ขึ้นอยู่กับ kahypar-ca อย่างไรก็ตาม Kahypar-E ยังทำงานร่วมกับการปรับปรุงในท้องถิ่นแบบไหล ในสิ่งพิมพ์ JEA ของเรา km1_kahypar_e_mf_jea19.ini การกำหนดค่าถูกนำมาใช้
ในการเริ่มต้น Kahypar-CA (โดยใช้ ความรู้ที่เป็นชุมชน ) การเพิ่มประสิทธิภาพ (การเชื่อมต่อ-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_direct_kway_sea17.ini
ในการเริ่มต้น Kahypar ในโหมด K-way โดยตรง (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
พารามิเตอร์ที่ตั้งไว้ล่วงหน้าทั้งหมดสามารถเขียนทับได้โดยใช้ตัวเลือกบรรทัดคำสั่งที่เกี่ยวข้อง
เมื่อสร้างไฮเปอร์กราฟ Kahypar ตรวจสอบว่าอินพุตนั้นเป็นไฮเปอร์กราฟที่ถูกต้องจริงมิฉะนั้นการพิมพ์ข้อผิดพลาดและการยกเลิก สิ่งนี้ใช้กับไฟล์อินพุต HGR, อินเตอร์เฟส C และอินเตอร์เฟส Python ค่าใช้จ่ายรันไทม์ของการตรวจสอบความถูกต้องควรเล็กน้อยในเกือบทุกกรณี อย่างไรก็ตามการตรวจสอบอินพุตสามารถปิดใช้งานได้โดยใช้ CMake Flag -DKAHYPAR_INPUT_VALIDATION=OFF
นอกจากนี้คำเตือนจะถูกพิมพ์สำหรับปัญหาที่ไม่ใช่เฟตอล (เช่น hyperedges ที่มีพินซ้ำ) ในการรักษาปัญหาที่ไม่ใช่อันตรายเป็นข้อผิดพลาดอย่างหนักแทนให้ใช้ CMake Flag -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 หมายเหตุ: หากไม่พบการเพิ่มในระหว่างการเชื่อมโยงคุณอาจต้องเพิ่ม -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 หากคุณไม่ได้ติดตั้ง Boost Run: 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 )สำหรับข้อมูลเพิ่มเติมเกี่ยวกับฟังก์ชั่น Library Python โปรดดู: module.cpp
นอกจากนี้เรายังมีเวอร์ชันที่รวบรวมไว้ล่วงหน้าซึ่งสามารถติดตั้งได้ผ่าน:
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 " ))Romain Wallon ได้สร้างอินเทอร์เฟซ Java สำหรับ Kahypar โปรดดู readMe สำหรับคำอธิบายโดยละเอียดเกี่ยวกับวิธีการสร้างและใช้อินเทอร์เฟซ
เราขอแนะนำให้คุณรายงานปัญหาใด ๆ กับ Kahypar ผ่านระบบติดตามปัญหา GitHub ของโครงการ
Kahypar เป็นซอฟต์แวร์ฟรีที่ให้ไว้ภายใต้ใบอนุญาตสาธารณะ GNU ทั่วไป (GPLV3) สำหรับข้อมูลเพิ่มเติมดูไฟล์คัดลอก เราแจกจ่ายเฟรมเวิร์กนี้อย่างอิสระเพื่อส่งเสริมการใช้และการพัฒนาเครื่องมือแบ่งพาร์ติชันไฮเปอร์กราฟ หากคุณใช้ 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 อย่าลังเลที่จะติดต่อฉันหรือสร้างปัญหาเกี่ยวกับระบบการติดตามปัญหา
