CXXGraph
v4.1.0
CXXGraph เป็นไลบรารี C++ ที่ครอบคลุมซึ่งจัดการอัลกอริทึมกราฟ ไลบรารีส่วนหัวเท่านั้นนี้ทำหน้าที่เป็นทางเลือกแทน Boost Graph Library (BGL)
เรากำลังมองหา:
หากคุณสนใจ โปรดติดต่อเราที่ [email protected] หรือมีส่วนร่วมในโครงการนี้ เรากำลังรอคุณอยู่!
| สมบูรณ์ | คำอธิบาย | วันที่แล้วเสร็จ |
|---|---|---|
| ปล่อย 0.4.0 | 7 ต.ค. 2022 | |
| ปล่อย 0.5.0 | 23 มี.ค. 2023 | |
| เปิดตัวเสถียรครั้งแรก 1.0.0 | 28 มี.ค. 2023 | |
| ปล่อย 1.0.1 | 7 พฤษภาคม 2023 | |
| ปล่อย 1.1.0 | 8 พฤษภาคม 2023 | |
| รุ่นเสถียร 2.0.0 | 1 มิถุนายน 2023 | |
| รุ่นเสถียร 3.0.0 | 3 พ.ย. 2566 | |
| รุ่น 3.1.0 | 9 มกราคม 2023 | |
| แนะนำไฮเปอร์กราฟ #122 | จะแจ้งภายหลัง | |
| รุ่นเสถียร 4.0.0 | จะแจ้งภายหลัง |
หากต้องการติดตั้งบนระบบ Unix/Linux ให้ดำเนินการต่อไปนี้จากบรรทัดคำสั่ง:
$ sudo tar xjf CXXGraph-{version}.tar.bz2
หากต้องการถอนการติดตั้ง:
$ sudo rm -f /usr/include/Graph.hpp /usr/include/CXXGraph*
หากต้องการติดตั้งบนระบบ Fedora/CentOS/RedHat ให้ดำเนินการต่อไปนี้จากบรรทัดคำสั่ง:
$ sudo rpm -ivh CXXGraph-{version}.noarch.rpm
หากต้องการถอนการติดตั้ง:
$ sudo rpm -e CXXGraph-{version}
หากต้องการติดตั้งบนระบบ Debian/Ubuntu ให้ดำเนินการต่อไปนี้จากบรรทัดคำสั่ง:
$ sudo dpkg -i CXXGraph_{version}.deb
หากต้องการถอนการติดตั้ง:
$ sudo apt-get remove CXXGraph
สำหรับการติดตั้งที่คอมไพล์เองโดยใช้ CMake ให้ดำเนินการต่อไปนี้จากบรรทัดคำสั่งเมื่อการคอมไพล์เสร็จสิ้น:
$ sudo make install
คำอธิบายชั้นเรียนสามารถพบได้ในส่วนชั้นเรียนของเอกสารประกอบ Doxygen
หากต้องการใช้ไลบรารี เพียงแค่วางไฟล์ส่วนหัวในตำแหน่งที่คุณต้องการ มันง่ายมาก!
งานอยู่ระหว่างดำเนินการ
Unit-Test ต้องใช้ CMake 3.9 ขึ้นไป และไลบรารี GoogleTest
GoogleTest
git clone https://github.com/google/googletest.git
cd googletest # Main directory of the cloned repository
mkdir -p build # Create a directory to hold the build output
cd build
cmake .. # Generate native build scripts for GoogleTest
make # Compile
sudo make install # Install in /usr/local/ by defaultจากไดเร็กทอรีฐาน:
mkdir -p build # Create a directory to hold the build output
cd build # Enter the build folder
cmake -DTEST=ON .. # Generate native build scripts for GoogleTest,
make # Compileหลังจากคอมไพล์บิลด์แล้ว ให้รันไฟล์ปฏิบัติการ "test_exe" ในไดเร็กทอรี "build" ด้วยคำสั่งต่อไปนี้:
./test_exe
เกณฑ์มาตรฐานต้องใช้ CMake 3.9 ขึ้นไป, ไลบรารี GoogleTest และไลบรารี Google Benchmark
เกณฑ์มาตรฐานของ Google
# Check out the library
$ git clone https://github.com/google/benchmark.git
# Google Benchmark requires GoogleTest as a dependency. Add the source tree as a subdirectory
$ git clone https://github.com/google/googletest.git benchmark/googletest
# Go to the library's root directory
$ cd benchmark
# Make a build directory to place the build output
$ cmake -E make_directory " build "
# Generate the build system files with CMake
$ cmake -E chdir " build " cmake -DCMAKE_BUILD_TYPE=Release ../
# If starting with CMake 3.13, you can use the following:
# cmake -DCMAKE_BUILD_TYPE=Release -S . -B "build"
# Build the library
$ cmake --build " build " --config Release
# Install the library
$ sudo cmake --build " build " --config Release --target installจากไดเร็กทอรีฐาน:
mkdir -p build # Create a directory to hold the build output
cd build # Enter the build folder
cmake -DBENCHMARK=ON .. # Generate native build scripts for Google Benchmark
make # Compileหลังจากคอมไพล์บิลด์แล้ว ให้รันไฟล์ปฏิบัติการ "benchmark" ในไดเร็กทอรี "build" ด้วยคำสั่งต่อไปนี้:
./benchmark
คุณสามารถตรวจสอบผลลัพธ์การวัดประสิทธิภาพโดยใช้ลิงก์นี้
หากต้องการสร้างแพ็คเกจ tarball ให้ดำเนินการต่อไปนี้จากบรรทัดคำสั่ง:
# Enter Packaging Directory
$ cd packaging
# Execute the script to generate tarballs
$ ./tarballs.shหากต้องการสร้างแพ็คเกจ RPM ให้ดำเนินการต่อไปนี้จากบรรทัดคำสั่ง:
# Enter Packaging Directory
$ cd packaging/rpm
# Execute the script to generate tarballs
$ ./make_rpm.shหากต้องการสร้างแพ็คเกจ deb ให้ดำเนินการต่อไปนี้จากบรรทัดคำสั่ง:
# Enter Packaging Directory
$ cd packaging/deb
# Execute the script to generate tarballs
$ ./make_deb.shGraph Dijkstras Shortest Path Algorithm(เส้นทางที่สั้นที่สุดของ Dijkstra) [อัลกอริทึมของ Dijkstra] (https://www.interviewbit.com/blog/find-shortest-path-dijkstras-algorithm/) ใช้เพื่อค้นหาเส้นทางที่สั้นที่สุดจากโหนดต้นทางไปยัง โหนดอื่นๆ ที่สามารถเข้าถึงได้ทั้งหมดในกราฟ ในตอนแรกอัลกอริทึมจะถือว่าโหนดทั้งหมดไม่สามารถเข้าถึงได้จากโหนดต้นทางที่กำหนด ดังนั้นเราจึงทำเครื่องหมายระยะทางของโหนดทั้งหมดเป็นอนันต์ (อนันต์) จากโหนดต้นทาง (INF / อนันต์หมายถึงไม่สามารถเข้าถึงได้)
ความเชี่ยวชาญพิเศษของอัลกอริธึมของ dijkstra
เมื่อน้ำหนักขอบเป็นจำนวนเต็มเล็ก (ล้อมรอบด้วยพารามิเตอร์ C ) คิวพิเศษที่ใช้ประโยชน์จากข้อเท็จจริงนี้สามารถใช้เพื่อเร่งความเร็วอัลกอริธึมของ Dijkstra อัลกอริธึมแรกของประเภทนี้คืออัลกอริธึมของ Dial (Dial 1969) สำหรับกราฟที่มีน้ำหนักขอบจำนวนเต็มบวก ซึ่งใช้คิวบัคเก็ตเพื่อรับเวลาทำงาน O(|E|+|V|C) (ที่มา วิกิพีเดีย)
ด้านล่างเป็นอัลกอริทึมที่สมบูรณ์:
ที่ลิงค์นี้คุณจะพบภาพประกอบทีละขั้นตอน
Prim's Algorithm Prim's Algorithm เป็นอัลกอริธึมที่มีความละโมบซึ่งจะค้นหาแผนผังการขยายขั้นต่ำสำหรับกราฟแบบถ่วงน้ำหนักแบบไม่มีทิศทาง ซึ่งหมายความว่าจะค้นหาชุดย่อยของขอบที่ก่อตัวเป็นต้นไม้ที่มีทุกจุดยอด โดยที่น้ำหนักรวมของขอบทั้งหมดในต้นไม้จะลดลง อัลกอริธึมดำเนินการโดยการสร้างทรีนี้ทีละจุด จากจุดเริ่มต้นที่กำหนดขึ้นเอง ในแต่ละขั้นตอนจะเพิ่มการเชื่อมต่อที่ถูกที่สุดที่เป็นไปได้จากทรีไปยังจุดยอดอื่น
ขั้นตอน:
(การค้นหาแบบกว้างก่อน) อัลกอริธึมการค้นหาแบบกว้างก่อน (การค้นหาแบบกว้างก่อน) Breadth First Search หรือที่อ้างถึงในชื่อ BFS คืออัลกอริทึมการแวะผ่านกราฟ ความซับซ้อนของเวลา O(|V| + |E|) โดยที่ V คือจำนวนจุดยอด และ E คือจำนวนขอบในกราฟ การใช้งานของ Broadth First Search คือ:
และยังมีอีกมากมาย...
(การค้นหาเชิงลึกก่อน) อัลกอริธึมการค้นหาเชิงลึกก่อน (การค้นหาเชิงลึกก่อน) การค้นหาเชิงลึกก่อน หรือที่อ้างถึงในชื่อ DFS คืออัลกอริทึมการแวะผ่านกราฟ ความซับซ้อนของเวลา O(|V| + |E|) โดยที่ V คือจำนวนจุดยอด และ E คือจำนวนขอบในกราฟ การประยุกต์ใช้การค้นหาเชิงลึกก่อนคือ:
และยังมีอีกมากมาย...
Best First Search Best First Search คือคลาสของอัลกอริธึมการค้นหาที่สำรวจกราฟโดยการสำรวจโหนดที่มีแนวโน้มมากที่สุดที่เลือกตามฟังก์ชันการประเมิน ความซับซ้อนของเวลาที่แย่ที่สุดคือ O(n * log n) โดยที่ n คือจำนวนโหนดในกราฟ
วงจร (ทฤษฎีกราฟ)
การมีอยู่ของวงจรในกราฟแบบกำหนดทิศทางและแบบไม่กำหนดทิศทางสามารถกำหนดได้โดยการค้นหาเชิงลึกก่อน (DFS) ค้นหาขอบที่ชี้ไปยังบรรพบุรุษของจุดยอดปัจจุบัน (ซึ่งมีขอบด้านหลัง) ขอบด้านหลังทั้งหมดที่ DFS ข้ามไปเป็นส่วนหนึ่งของวงจร ในกราฟที่ไม่มีทิศทาง ขอบไปยังพาเรนต์ของโหนดไม่ควรนับเป็นขอบด้านหลัง แต่การค้นหาจุดยอดอื่นๆ ที่เยี่ยมชมแล้วจะบ่งบอกถึงขอบด้านหลัง ในกรณีของกราฟที่ไม่มีทิศทาง ต้องใช้เวลา O(n) เท่านั้นในการค้นหาวงจรในกราฟ n-vertex เนื่องจากขอบส่วนใหญ่ n − 1 สามารถเป็นขอบต้นไม้ได้
อัลกอริธึมการเรียงลำดับทอพอโลยีจำนวนมากจะตรวจจับรอบด้วย เนื่องจากสิ่งเหล่านี้เป็นอุปสรรคต่อลำดับทอพอโลยีที่มีอยู่ นอกจากนี้ หากกราฟกำหนดทิศทางถูกแบ่งออกเป็นองค์ประกอบที่เชื่อมต่อกันอย่างแน่นหนา วงจรจะมีอยู่ภายในส่วนประกอบเท่านั้น และจะไม่อยู่ระหว่างส่วนประกอบเหล่านั้น เนื่องจากวงจรมีการเชื่อมต่อกันอย่างแน่นหนา
สำหรับกราฟกำกับ สามารถใช้อัลกอริธึมตามข้อความแบบกระจายได้ อัลกอริธึมเหล่านี้อาศัยแนวคิดที่ว่าข้อความที่ส่งโดยจุดยอดในรอบจะกลับมาที่ตัวมันเอง อัลกอริธึมการตรวจจับวงจรแบบกระจายมีประโยชน์สำหรับการประมวลผลกราฟขนาดใหญ่โดยใช้ระบบประมวลผลกราฟแบบกระจายบนคลัสเตอร์คอมพิวเตอร์ (หรือซูเปอร์คอมพิวเตอร์)
การประยุกต์ใช้การตรวจจับวงจรรวมถึงการใช้กราฟรอเพื่อตรวจจับการหยุดชะงักในระบบที่ทำงานพร้อมกัน
สามารถใช้อัลกอริธึม Bellman-Ford เพื่อค้นหาระยะห่างที่สั้นที่สุดระหว่างต้นทางและโหนดเป้าหมาย ความซับซ้อนของเวลา O(|V| . |E|) โดยที่ V คือจำนวนจุดยอดและ E คือจำนวนขอบในกราฟซึ่งสูงกว่าอัลกอริธึมเส้นทางที่สั้นที่สุดของ Dijkstra ความซับซ้อนของเวลาของอัลกอริทึมของ dijkstra คือ O(|E| + |V| log |v| ) ข้อดีของ bellman-ford เหนือ dijkstra คือ สามารถรองรับกราฟที่มีน้ำหนักขอบเป็นลบได้ นอกจากนี้ หากกราฟมีวงจรน้ำหนักเป็นลบ อัลกอริธึมจะสามารถตรวจจับและรายงานการมีอยู่ของวงจรลบได้
วิดีโอนี้ให้ภาพรวมที่ดีของการนำอัลกอริทึมไปใช้ การบรรยายของ MIT นี้เป็นข้อพิสูจน์ถึงความถูกต้องของ Bellman-Ford และความสามารถในการตรวจจับวงจรเชิงลบ การใช้งาน:
อัลกอริทึมของฟลอยด์ วอร์แชล
เราเริ่มต้นเมทริกซ์โซลูชันเหมือนกับเมทริกซ์กราฟอินพุตเป็นขั้นตอนแรก จากนั้นเราอัปเดตเมทริกซ์โซลูชันโดยพิจารณาจุดยอดทั้งหมดเป็นจุดยอดที่อยู่ตรงกลาง แนวคิดคือการเลือกจุดยอดทั้งหมดทีละจุดและอัปเดตเส้นทางที่สั้นที่สุดทั้งหมด ซึ่งรวมถึงจุดยอดที่เลือกเป็นจุดยอดกลางในเส้นทางที่สั้นที่สุด เมื่อเราเลือกจุดยอดหมายเลข k เป็นจุดยอดตรงกลาง เราได้ถือว่าจุดยอด {0, 1, 2, .. k-1} เป็นจุดยอดตรงกลางแล้ว สำหรับทุกคู่ (i, j) ของจุดยอดต้นทางและปลายทางตามลำดับ มีสองกรณีที่เป็นไปได้
การลดสกรรมกริยา
อัลกอริธึมนี้ใช้เพื่อสร้างกราฟกำกับที่มีความสามารถในการเข้าถึงเท่ากันและเป็นไปตามการปิดสกรรมกริยาโดยมีขอบน้อยที่สุด กล่าวอย่างเป็นรูปธรรมมากขึ้น คือ การสร้างกราฟที่เทียบเท่าขั้นต่ำโดยมีขอบน้อยที่สุดเท่าที่จะทำได้ โดยลบเส้นทาง "ลัดวงจร" ผ่านกราฟ
สิ่งนี้ทำได้โดยการวนซ้ำแต่ละคู่โหนด ตรวจสอบเพื่อดูว่ามีขอบสองอันที่นำออกจากโหนดแรกหรือออกจากโหนดสุดท้ายหรือไม่ โดยถอดขอบคู่โหนดออกหากมีอยู่
ในรหัสเทียม: foreach x ใน graph.vertices foreach y ใน graph.vertices foreach z ใน graph.vertices ลบ edge xz ถ้า edges xy และ yz มีอยู่
การใช้งานของเรามี if gate ที่ทำการตรวจสอบขอบล่วงหน้าในหลาย ๆ ที่ ซึ่งทำให้รันไทม์เร็วกว่าโค้ดเทียมแบบลูกบาศก์เล็กน้อยที่นี่
อัลกอริทึม Kruskal สามารถใช้ค้นหาฟอเรสต์ที่ขยายต่ำสุดของกราฟถ่วงน้ำหนักขอบที่ไม่ได้กำหนดทิศทาง ความซับซ้อนของเวลา O(E log E) = O(E log V) โดยที่ V คือจำนวนจุดยอด และ E คือจำนวนขอบในกราฟ ข้อจำกัดความเร็วหลักสำหรับอัลกอริธึมนี้คือการเรียงลำดับขอบ
เพื่อความเข้าใจอย่างรวดเร็วเกี่ยวกับขั้นตอนของอัลกอริทึม โปรดดูวิดีโอนี้ แอปพลิเคชันในชีวิตจริงบางส่วน ได้แก่:
อัลกอริธึมอื่นๆ ในการค้นหาฟอเรสต์ที่ขยายน้อยที่สุดคืออัลกอริธึมของ Prim หรืออัลกอริธึมของ Borůvka
อัลกอริทึมของ Borůvka เป็นอัลกอริทึมที่ละโมบซึ่งสามารถใช้ในการค้นหาต้นไม้ที่ขยายน้อยที่สุดในกราฟ หรือฟอเรสต์ที่ขยายน้อยที่สุด ในกรณีของกราฟที่ไม่ได้เชื่อมต่อกัน
อัลกอริธึมเริ่มต้นด้วยการค้นหาเหตุการณ์ขอบน้ำหนักต่ำสุดที่แต่ละจุดยอดของกราฟ และเพิ่มขอบเหล่านั้นทั้งหมดลงในฟอเรสต์ จากนั้น จะทำซ้ำขั้นตอนที่คล้ายกันในการค้นหาขอบน้ำหนักขั้นต่ำจากต้นไม้แต่ละต้นที่สร้างขึ้นจนถึงต้นไม้อื่น และเพิ่มขอบทั้งหมดเหล่านั้นลงในป่า การทำซ้ำของกระบวนการแต่ละครั้งจะลดจำนวนต้นไม้ภายในแต่ละองค์ประกอบที่เชื่อมต่อกันของกราฟ เหลือเพียงครึ่งหนึ่งของค่าเดิม ดังนั้นหลังจากการทำซ้ำหลายครั้งในลอการิทึม กระบวนการจะเสร็จสิ้น เมื่อเป็นเช่นนั้น ชุดของขอบที่ได้เพิ่มเข้าไปจะทำให้เกิดฟอเรสต์ที่ขยายน้อยที่สุด
อัลกอริธึมของ Borůvka สามารถแสดงให้ทำการวนซ้ำ O(log V) ของลูปด้านนอกจนกระทั่งสิ้นสุด และดังนั้นให้รันทันเวลา O(E log V) โดยที่ E คือจำนวนขอบ และ V คือจำนวนจุดยอดใน G (สมมติว่า E ≥ V)
คำจำกัดความทางคณิตศาสตร์ของปัญหา: ให้ G เป็นเซตของโหนดในกราฟ และ n เป็นโหนดที่กำหนดในชุดนั้น ให้ C เป็นเซตย่อยที่ไม่เข้มงวดของ G ที่มีทั้ง n และโหนดทั้งหมดที่สามารถเข้าถึงได้จาก n และให้ C' เป็นส่วนเสริมของมัน มีชุดที่สาม M ซึ่งเป็นชุดย่อยที่ไม่เข้มงวดของ C ซึ่งมีโหนดทั้งหมดที่สามารถเข้าถึงได้จากโหนดใดๆ ใน C' ปัญหาประกอบด้วยการค้นหาโหนดทั้งหมดที่เป็นของ C แต่ไม่ใช่ของ M
อัลกอริทึมที่นำไปใช้ในปัจจุบัน:
แอปพลิเคชัน:
อัลกอริธึมนี้ใช้ในระบบรวบรวมขยะเพื่อตัดสินใจว่าอ็อบเจ็กต์อื่นใดที่จำเป็นต้องถูกปล่อยออกมา โดยพิจารณาว่ามีหนึ่งอ็อบเจ็กต์ที่กำลังจะถูกปล่อยออกมา
อัลกอริทึมของ Ford-Fulkerson เป็นอัลกอริทึมที่โลภในการค้นหาการไหลสูงสุดในเครือข่ายการไหล แนวคิดเบื้องหลังอัลกอริธึมมีดังนี้ ตราบใดที่มีเส้นทางจากต้นทาง (โหนดเริ่มต้น) ไปยังซิงก์ (โหนดปลาย) ด้วยความจุที่พร้อมใช้งานบนขอบทั้งหมดในเส้นทาง เราก็จะส่งโฟลว์ไปตามเส้นทางใดเส้นทางหนึ่ง แล้วเราก็พบเส้นทางอื่นเป็นต้น เส้นทางที่มีความจุที่มีอยู่เรียกว่าเส้นทางเสริม
อัลกอริทึมของ Kosaraju เป็นอัลกอริทึมเวลาเชิงเส้นเพื่อค้นหาองค์ประกอบที่เชื่อมต่ออย่างแน่นหนาของกราฟกำหนดทิศทาง มีพื้นฐานมาจากแนวคิดที่ว่าหากใครสามารถไปถึงจุดยอด v โดยเริ่มจากจุดยอด u ได้ เราก็ควรจะสามารถไปถึงจุดยอด u โดยเริ่มจากจุดยอด v และหากเป็นเช่นนั้น เราสามารถพูดได้ว่าจุดยอด u และ v นั้น เชื่อมต่อกันอย่างแน่นหนา - พวกมันอยู่ในกราฟย่อยที่เชื่อมต่ออย่างแน่นหนา ต่อไปนี้เป็นตัวอย่าง:
1). สร้างสแต็กว่าง 'S' และทำการข้าม DFS ของกราฟ ในการแวะผ่าน DFS หลังจากการเรียก DFS แบบเรียกซ้ำสำหรับจุดยอดที่อยู่ติดกันของจุดยอด ให้ดันจุดยอดเพื่อสแต็ก 2). กลับทิศทางของส่วนโค้งทั้งหมดเพื่อให้ได้กราฟทรานสโพส 3). จุดยอดจาก S ปรากฏขึ้นทีละจุดในขณะที่ S ไม่ว่างเปล่า ให้จุดยอดที่โผล่ออกมาเป็น 'v' ใช้ v เป็นแหล่งที่มาและทำ DFS (เรียก DFSUtil(v)) DFS ที่เริ่มต้นจาก v จะพิมพ์ส่วนประกอบที่เชื่อมต่ออย่างแน่นหนาของ v
อัลกอริทึมของคาห์นค้นหาการเรียงลำดับทอพอโลยีโดยการลบโหนดในกราฟที่ไม่มีขอบเข้ามาซ้ำๆ เมื่อโหนดถูกลบออกจากกราฟ โหนดนั้นจะถูกเพิ่มในการเรียงลำดับทอพอโลยี และขอบทั้งหมดจะถูกลบออก เพื่อให้สามารถเลือกโหนดชุดถัดไปที่ไม่มีขอบขาเข้าได้
อัลกอริธึมการระบายสี Welsh Powell เป็นอัลกอริธึมการระบายสีจุดยอดโลภ อัลกอริธึมนี้ยังใช้เพื่อค้นหาหมายเลขสีของกราฟด้วย
อัลกอริทึม Welsh Powell ประกอบด้วยขั้นตอนต่อไปนี้:
อัลกอริทึมส่งคืนผลลัพธ์ std::map<Node, int> ที่กำหนดแต่ละโหนดให้กับสีที่เรียงลำดับตามจำนวนเต็ม ผู้ใช้ยังสามารถสืบค้นลำดับสีขั้นต่ำของกราฟได้โดยการสืบค้นค่าสูงสุดจากแผนที่ผลลัพธ์
std::map<Node, int > result = graph.welshPowellColoring();
auto chromatic_color = std::max_element(result.begin(), result.end(),
[]( const auto & lhs, const auto & rhs) {
return lhs. second < rhs. second ;
}การระบายสีขั้นต่ำเริ่มต้นจาก 1 แทนที่จะเป็น 0
อัลกอริทึมจะถือว่ากราฟไม่มีทิศทาง แหล่งที่มาและแรงบันดาลใจทั้งหมดเชื่อมโยงกันในการประกาศอัลกอริทึมและกรณีทดสอบ
การแบ่งพาร์ติชันแบบตัดจุดยอดจะแบ่งขอบของกราฟออกเป็นพาร์ติชันที่มีขนาดเท่ากัน จุดยอดที่เก็บจุดสิ้นสุดของขอบจะถูกวางไว้ในพาร์ติชันเดียวกันกับขอบด้วย อย่างไรก็ตาม จุดยอดจะไม่ซ้ำกันระหว่างพาร์ติชัน และอาจต้องมีการจำลอง (ตัด) เนื่องจากการกระจายขอบของจุดนั้นไปยังพาร์ติชันต่างๆ
ปัจจัยการจำลองจะวัดจำนวนจุดยอดที่ถูกจำลองบนคอมพิวเตอร์ เทียบกับจำนวนจุดยอดของกราฟอินพุตดั้งเดิม
อัลกอริทึมนี้เป็นการตัดจุดยอดอย่างง่ายในรูปแบบ Round-Robin ใช้ขอบกราฟต้นฉบับและกำหนดให้กับพาร์ติชัน โดยแบ่งเป็นขนาดเท่ากัน (หรือคล้ายกัน) อัลกอริธึมนี้ไม่ได้ดูแลการปรับให้เหมาะสมในการจำลองจุดยอด ( ปัจจัยการจำลอง) แต่เพียงปรับสมดุลขอบในพาร์ติชันเท่านั้น
อัลกอริธึมการแบ่งพาร์ติชันที่ละโมบใช้ประวัติทั้งหมดของการกำหนด Edge เพื่อตัดสินใจครั้งต่อไป อัลกอริธึมจะจัดเก็บชุดของพาร์ติชัน A(v) ซึ่งแต่ละจุดยอด v ที่สังเกตได้ถูกกำหนดไว้แล้วและขนาดพาร์ติชันปัจจุบัน เมื่อประมวลผลขอบ e ∈ E ที่เชื่อมต่อจุดยอด vi, vj ∈ V อัลกอริธึมโลภจะเป็นไปตามกฎง่ายๆ นี้:
อัลกอริธึมระดับสูง (เป็น) การจำลองแบบแรก (HDRF) เป็นอัลกอริธึมการตัดจุดยอดโลภตามที่อธิบายไว้ในบทความนี้ อัลกอริทึมนี้พยายามปรับปัจจัยการจำลองให้เหมาะสมโดยใช้ประวัติของการกำหนดขอบและระดับจุดยอดที่เพิ่มขึ้น ด้วยฟังก์ชันที่คำนึงถึงปัจจัยทั้งสองนี้จะคำนวณพาร์ติชันที่ดีที่สุดเพื่อกำหนดขอบที่วิเคราะห์ แบบจำลองที่สร้างขึ้นจะขึ้นอยู่กับระดับของจุดยอด และจุดยอดที่จำลองแบบอาจเรียกว่า "Hub-Node" ซึ่งเป็นจุดยอดที่มีระดับที่สูงกว่า
Vertex-cut (EBV) ที่มีประสิทธิภาพและสมดุลเป็นอัลกอริธึมการตัดจุดสุดยอดแบบออฟไลน์ตามที่อธิบายไว้ในบทความนี้ อัลกอริทึมนี้พยายามปรับสมดุลพาร์ติชันตามจำนวนขอบและจุดยอดของแต่ละพาร์ติชันและปัจจัยการจำลองแบบ ใช้สูตรในการประเมินพาร์ติชันโดยกำหนดขอบโดยคำนึงถึงจำนวนขอบและจุดยอดทั้งหมดของกราฟด้วย สูตรการประเมินมีดังนี้:
ค่าต่ำสุดจะถูกใช้เป็นรหัสพาร์ติชัน
Degree Matrix เป็นเมทริกซ์จตุรัสที่ให้ข้อมูลเชิงลึกเกี่ยวกับการเชื่อมต่อของโหนดในกราฟ สำหรับกราฟที่มีการกำหนดทิศทาง จะแสดงจำนวนของขอบขาเข้าและขาออกสำหรับแต่ละโหนด ในขณะที่สำหรับกราฟที่ไม่มีทิศทาง จะแสดงจำนวนขอบที่เกิดขึ้นกับแต่ละโหนด
Laplacian Matrix เป็นเมทริกซ์จตุรัสที่ได้มาจากเมทริกซ์ adjacency และเมทริกซ์ระดับของกราฟ เป็นเครื่องมือในการวิเคราะห์คุณสมบัติต่างๆ ของกราฟ เช่น ความเชื่อมโยง จำนวนต้นไม้ที่ทอดยาว และลักษณะสเปกตรัมอื่นๆ
Transition Matrix มักใช้ในการศึกษา Markov Chains และกระบวนการสุ่ม ภายในบริบทของกราฟ จะแสดงถึงความน่าจะเป็นของการเปลี่ยนจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง ซึ่งมักขึ้นอยู่กับน้ำหนักของขอบหรือเกณฑ์ที่กำหนดไว้ล่วงหน้า เมทริกซ์นี้จะค้นหาแอปพลิเคชันในด้านต่างๆ เช่น การวิเคราะห์เครือข่าย การเรียนรู้ของเครื่อง และการเพิ่มประสิทธิภาพ
หากคุณต้องการให้การสนับสนุน คุณสามารถสร้าง คำขอดึง หรือรายงาน ปัญหา ได้ หากคุณต้องการเปลี่ยนโค้ด แก้ไขปัญหา หรือใช้ฟีเจอร์ใหม่ โปรดอ่านคู่มือการมีส่วนร่วมของเรา
หากคุณต้องการหารือเกี่ยวกับคุณสมบัติใหม่หรือมีคำถามหรือข้อเสนอแนะเกี่ยวกับห้องสมุด โปรดเปิดการสนทนาหรือเพียงแค่แชท
เว็บไซต์ CXXGraph
อีเมล์ : [email protected]
โปรไฟล์ GitHub
เพื่อสนับสนุนฉัน เพิ่ม ดาว ในโครงการหรือ ติดตามฉัน
หากต้องการติดตามข่าวสาร โปรดดู โครงการ
เราได้รับการอ้างอิงโดย:
ขอขอบคุณชุมชน TheAlgorithms สำหรับแรงบันดาลใจเกี่ยวกับอัลกอริทึม
ขอบคุณ GeeksForGeeks สำหรับแรงบันดาลใจเกี่ยวกับอัลกอริทึม
ขอขอบคุณทุกคนที่มีส่วนร่วมใน CXXGraph แล้ว!
หากคุณใช้ซอฟต์แวร์นี้ โปรดปฏิบัติตามคำแนะนำการอ้างอิง ขอบคุณ!
เราเข้าร่วมในงาน Hacktoberfest 2021 ขอขอบคุณผู้ร่วมให้ข้อมูลทุกคน!
เราได้เข้าร่วมในงาน Hacktoberfest 2022 ขอขอบคุณผู้ร่วมให้ข้อมูลทุกคน!
เราได้เข้าร่วมในงาน Hacktoberfest 2023 ขอขอบคุณผู้ร่วมให้ข้อมูลทุกคน!
ดูมูลค่าโดยประมาณของโครงการ
@ZigRazor |
|---|
