ดาวน์โหลด graph - ดาวน์โหลดซอร์สโค้ด graph

graph

ซอร์สโค้ดอื่น ๆ

ดาวน์โหลด

กราฟ/กราฟ

GraPHP คือกราฟทางคณิตศาสตร์/ไลบรารีเครือข่ายที่เขียนด้วย PHP

เวอร์ชันการพัฒนา: สาขานี้มีโค้ดสำหรับการเปิดตัว 1.0 ที่กำลังจะมาถึง สำหรับโค้ดของเวอร์ชัน 0.9 ที่เสถียรในปัจจุบัน โปรดดูที่สาขา 0.9.x
การเปิดตัว 1.0 ที่กำลังจะมาถึงจะเป็นแนวทางสำหรับแพ็คเกจนี้ อย่างไรก็ตาม เรายังคงสนับสนุน 0.9.x สำหรับผู้ที่ยังไม่มีเวอร์ชันล่าสุดอยู่ ดูคำแนะนำในการติดตั้งสำหรับรายละเอียดเพิ่มเติม

สารบัญ

ตัวอย่างการเริ่มต้นอย่างรวดเร็ว
คุณสมบัติ
ส่วนประกอบ
- การวาดกราฟ
- อัลกอริธึมทั่วไป
ติดตั้ง
การทดสอบ
มีส่วนร่วม
ใบอนุญาต

ตัวอย่างการเริ่มต้นอย่างรวดเร็ว

เมื่อติดตั้งแล้ว ให้เริ่มต้นกราฟตัวอย่าง:

 <?php

require __DIR__ . ' /vendor/autoload.php ' ;

$ graph = new Graphp  Graph  Graph ();

// create some cities
$ rome = $ graph -> createVertex ( array ( ' name ' => ' Rome ' ));
$ madrid = $ graph -> createVertex ( array ( ' name ' => ' Madrid ' ));
$ cologne = $ graph -> createVertex ( array ( ' name ' => ' Cologne ' ));

// build some roads
$ graph -> createEdgeDirected ( $ cologne , $ madrid );
$ graph -> createEdgeDirected ( $ madrid , $ rome );
// create loop
$ graph -> createEdgeDirected ( $ rome , $ rome );

มาดูกันว่าเมืองใด (Vertex) มีถนน (เช่น ปลายแหลม) ไปยังกรุงโรม:

 foreach ( $ rome -> getVerticesEdgeFrom () as $ vertex ) {
    echo $ vertex -> getAttribute ( ' name ' ) . ' leads to Rome ' . PHP_EOL ;
    // result: Madrid and Rome itself lead to Rome
}

คุณสมบัติ

ห้องสมุดนี้สร้างขึ้นตามแนวคิดของทฤษฎีกราฟทางคณิตศาสตร์ (กล่าวคือ ไม่ใช่ ห้องสมุดแผนภูมิสำหรับการวาดกราฟของฟังก์ชัน) โดยพื้นฐานแล้ว กราฟคือชุดของ โหนด ที่มี การเชื่อมต่อ ระหว่างกันจำนวนเท่าใดก็ได้ ในทฤษฎีกราฟ จุดยอด (พหูพจน์ของจุดยอด) เป็นตัวแทนเชิงนามธรรมของ โหนด เหล่านี้ ในขณะที่ การเชื่อมต่อ จะแสดงเป็น ขอบ ขอบอาจเป็นได้ทั้งแบบไม่มีทิศทาง ("สองทาง") หรือแบบมีทิศทาง ("ทางเดียว" หรือที่รู้จักกันในชื่อ di-edges หรือส่วนโค้ง)

ขึ้นอยู่กับวิธีการสร้างขอบ กราฟทั้งหมดสามารถเป็นแบบไม่มีทิศทาง อาจเป็นกราฟแบบมีทิศทาง (หรือที่เรียกว่าไดกราฟ) หรือเป็นกราฟแบบผสมก็ได้ ขอบยังได้รับอนุญาตให้สร้างลูป (เช่น ขอบจากจุดยอด A ชี้ไปที่จุดยอด A อีกครั้ง) นอกจากนี้ยังรองรับหลายขอบจากจุดยอด A ถึงจุดยอด B เช่นกัน (หรือที่เรียกว่าขอบขนาน) ซึ่งสร้างกราฟหลายกราฟได้อย่างมีประสิทธิภาพ (หรือที่เรียกว่ากราฟเทียม) และแน่นอนว่าการผสมผสานใดๆ ก็ตามก็ได้รับการสนับสนุนเช่นกัน ในขณะที่ผู้เขียนหลายคนพยายามแยกความแตกต่างระหว่างแนวคิดหลักเหล่านี้ ห้องสมุดนี้พยายามอย่างหนักที่จะไม่กำหนดข้อจำกัดหรือสมมติฐานปลอมๆ บนกราฟของคุณ

ส่วนประกอบ

ไลบรารีนี้มีโครงสร้างข้อมูลหลักสำหรับการทำงานกับกราฟ จุดยอด ขอบ และคุณลักษณะ

มีส่วนประกอบอย่างเป็นทางการหลายอย่างที่สร้างขึ้นบนโครงสร้างเหล่านี้เพื่อให้มีฟังก์ชันการทำงานที่จำเป็นโดยทั่วไป สถาปัตยกรรมนี้ช่วยให้ส่วนประกอบเหล่านี้สามารถใช้งานได้อย่างอิสระและตามความต้องการเท่านั้น

ต่อไปนี้เป็นรายการส่วนประกอบที่เน้นบางส่วน รายชื่อส่วนประกอบอย่างเป็นทางการทั้งหมดสามารถพบได้ในโปรเจ็กต์กราฟป์

การวาดกราฟ

ไลบรารีนี้สร้างขึ้นเพื่อรองรับการแสดงภาพกราฟ รวมถึงภาพเหล่านั้นในหน้าเว็บ การเปิดภาพจากภายในแอปพลิเคชัน CLI และส่งออกเป็นรูปแบบไฟล์ PNG, JPEG หรือ SVG (รวมถึงรูปแบบอื่น ๆ อีกมากมาย) เนื่องจากการวาดกราฟเป็นพื้นที่ที่ซับซ้อนในตัวเอง การจัดวางจริงของกราฟจึงขึ้นอยู่กับ "ซอฟต์แวร์สร้างภาพกราฟ" ที่ยอดเยี่ยมของ GraphViz และเราเพียงจัดเตรียม API บางอย่างที่สะดวกเพื่อเชื่อมต่อกับ GraphViz เท่านั้น

ดูGraphp/Graphvizสำหรับรายละเอียดเพิ่มเติม

อัลกอริธึมทั่วไป

นอกจากการวาดกราฟแล้ว สิ่งที่พบได้บ่อยที่สุดอย่างหนึ่งเกี่ยวกับกราฟคือการเรียกใช้อัลกอริทึมเพื่อแก้ไขปัญหากราฟทั่วไป ดังนั้นไลบรารีนี้จึงถูกใช้เป็นพื้นฐานสำหรับการใช้งานสำหรับอัลกอริธึมกราฟที่ใช้กันทั่วไปจำนวนหนึ่ง:

ค้นหา
- ลึกก่อน (DFS)
- การค้นหาแบบกว้างก่อน (BFS)
เส้นทางที่สั้นที่สุด
- ไดจค์สตรา
- มัวร์-เบลล์แมน-ฟอร์ด (MBF)
- การนับจำนวนฮ็อพ (BFS แบบง่าย)
ต้นไม้ขยายขั้นต่ำ (MST)
- ครูสกาล
- พริม
ปัญหาพนักงานขายเดินทาง (TSP)
- อัลกอริธึมบรูตฟอร์ซ
- การวิเคราะห์พฤติกรรมต้นไม้แบบขยายขั้นต่ำ (TSP MST heuristic)
- การวิเคราะห์พฤติกรรมเพื่อนบ้านที่ใกล้ที่สุด (NN heuristic)
การไหลสูงสุด
- เอ็ดมันด์-คาร์ป
กระแสต้นทุนขั้นต่ำ (MCF)
- การยกเลิกวงจร
- เส้นทางที่สั้นที่สุดต่อเนื่อง
การจับคู่สูงสุด
- อัลกอริธึมการไหล

ดูกราฟ/อัลกอริทึมสำหรับรายละเอียดเพิ่มเติม

ติดตั้ง

วิธีที่แนะนำในการติดตั้งไลบรารีนี้คือผ่าน Composer ยังใหม่กับนักแต่งเพลงใช่ไหม?

เมื่อเปิดตัวแล้ว โปรเจ็กต์นี้จะติดตาม SemVer ในขณะนี้จะติดตั้งเวอร์ชันการพัฒนาล่าสุด:

composer require graphp/graph:^1@dev

ดูเพิ่มเติมที่ CHANGELOG สำหรับรายละเอียดเกี่ยวกับการอัปเกรดเวอร์ชัน

โปรเจ็กต์นี้มีจุดมุ่งหมายเพื่อทำงานบนแพลตฟอร์มใดๆ ดังนั้นจึงไม่จำเป็นต้องมีส่วนขยาย PHP ใดๆ และรองรับการทำงานบน PHP 5.3 รุ่นเก่าจนถึง PHP 8+ ปัจจุบัน ขอแนะนำอย่างยิ่งให้ใช้ PHP เวอร์ชันล่าสุดที่รองรับ สำหรับโปรเจ็กต์นี้

คุณอาจต้องการติดตั้งส่วนประกอบเพิ่มเติมบางอย่างด้วย รายชื่อส่วนประกอบอย่างเป็นทางการทั้งหมดสามารถพบได้ในโปรเจ็กต์กราฟป์

การทดสอบ

ไลบรารีนี้ใช้ PHPUnit สำหรับชุดทดสอบที่ครอบคลุม หากต้องการรันชุดทดสอบ คุณต้องโคลน repo นี้ก่อน จากนั้นจึงติดตั้งการขึ้นต่อกันทั้งหมดผ่าน Composer:

composer install

หากต้องการรันชุดทดสอบ ให้ไปที่รูทโปรเจ็กต์แล้วรัน:

vendor/bin/phpunit

มีส่วนร่วม

ไลบรารีนี้มาพร้อมกับชุดทดสอบที่ครอบคลุมและได้รับการทดสอบและใช้งานเป็นประจำใน โลกแห่งความเป็นจริง อย่างไรก็ตาม ไลบรารีนี้ยังถือเป็นซอฟต์แวร์เบต้า และ API อาจมีการเปลี่ยนแปลงได้ บันทึกการเปลี่ยนแปลงจะแสดงข้อมูลที่เกี่ยวข้องทั้งหมดสำหรับการอัปเดตระหว่างรุ่นต่างๆ

หากคุณพบปัญหาใด ๆ โปรดอย่าลังเลที่จะโทรหาเรา ยื่นรายงานข้อผิดพลาด หรือแม้แต่ส่งคำขอแก้ไข / ดึงข้อมูล และ/หรือการทดสอบหน่วยเพื่อทำให้ปัญหาของคุณเกิดขึ้นอีกครั้ง

นอกเหนือจากการทำงานกับโค้ดโดยตรงแล้ว เอกสารเพิ่มเติมใดๆ การเพิ่มเติมใน readme ของเรา หรือแม้แต่การแก้ไขการพิมพ์ผิดธรรมดาก็ได้รับการชื่นชมเช่นกัน

ข้อเสนอแนะและ/หรือการสนับสนุนใด ๆ ยินดีต้อนรับ!

ลองดู #graphp บน irc.freenode.net