การตามหาประเภทข้อมูลที่หายไป
(hillelwayne.com)- กราฟมีอยู่ทั่วซอฟต์แวร์ เช่น dependency, เว็บลิงก์, state space ของ model checker, และ foreign key ของฐานข้อมูลเชิงสัมพันธ์ แต่ในภาษาโปรแกรมกระแสหลักแทบไม่มีชนิดข้อมูลแบบ built-in หรือการรองรับใน standard library
- เหตุผลแรกที่ทำให้สร้างชนิดกราฟแบบ built-in ได้ยากคือมีชนิดของกราฟมากมาย เช่น มีทิศทาง/ไม่มีทิศทาง, simple/multi, และ hypergraph ซึ่งคุณสมบัติเฉพาะเหล่านี้ส่งผลอย่างมากต่อการเลือกอัลกอริทึมและประสิทธิภาพ
- รูปแบบการแทนข้อมูลแต่ละแบบ เช่น edge list, adjacency list, adjacency matrix, หรือโครงสร้างที่อ้างอิงกัน ให้ผลต่างกันทั้งด้านหน่วยความจำและประสิทธิภาพการค้นหา จึงยากที่จะมีตัวแทนแบบทั่วไปเพียงแบบเดียวที่ตอบโจทย์ทุกกรณี
- อัลกอริทึมกราฟนั้นเขียนยากและมักต้องรันกับอินพุตขนาดใหญ่ ทำให้การแทนข้อมูลและการ traversal ที่ออกแบบเฉพาะปัญหาอาจสำคัญกว่าการใช้ไลบรารีทั่วไป ดังที่เห็นจากกรณีของ Nosey Parker และ Gecode
- เหตุที่ standard library มักไม่ค่อยมีกราฟ เป็นเพราะ trade-off ด้านชนิดข้อมูล การแทนข้อมูล อัลกอริทึม และประสิทธิภาพ รวมถึงภาระการดูแลรักษาที่สูง ขณะที่ไลบรารีภายนอกก็อาจมีข้อจำกัดหรือช้าเกินไป
กราฟมีอยู่ทั่วไป แต่การรองรับในภาษาโปรแกรมยังขาดแคลน
- กราฟประกอบด้วยโหนดและเอดจ์ และทั้งโหนดกับเอดจ์สามารถเก็บข้อมูลได้
- ในงานวิศวกรรมซอฟต์แวร์ กราฟปรากฏในหลายรูปแบบ
- dependency ของแพ็กเกจและการ import โมดูลสร้างเป็นกราฟมีทิศทาง
- อินเทอร์เน็ตคือกราฟของลิงก์ระหว่างเว็บเพจ
- model checker สำรวจstate spaceของการตั้งค่าที่เป็นไปได้ทั้งหมด โดยโหนดคือสถานะและเอดจ์คือการเปลี่ยนสถานะที่ถูกต้อง
- ฐานข้อมูลเชิงสัมพันธ์สามารถมองได้ว่าเรคอร์ดคือโหนด และ foreign key คือเอดจ์
- กราฟอาจมองได้ว่าเป็นการทำให้ linked list, binary tree และ hash table เป็นแนวคิดทั่วไปขึ้น
- แม้แต่ใน business logic ก็ยังพบกราฟบ่อย เช่น ความสัมพันธ์การอ้างอิงงานวิจัย เส้นทางในเครือข่ายคมนาคม และการเชื่อมต่อในโซเชียลเน็ตเวิร์ก
- แม้กราฟจะเป็นสิ่งที่ต้องใช้บ่อย แต่ภาษาโปรแกรมกระแสหลักส่วนใหญ่ไม่ได้ให้กราฟเป็นชนิดข้อมูล built-in และก็มีน้อยมากที่รวมไว้ใน standard library
- ในหลาย ecosystem ยังขาดไลบรารีกราฟภายนอกที่แข็งแรงพอ ทำให้หลายครั้งต้องลงมือเขียนเอง
การออกแบบชนิดกราฟมีตัวเลือกมากเกินไป
- นอกจากกราฟมีทิศทางและไม่มีทิศทางแล้ว ยังมีกราฟแบบอื่นอีกหลายชนิด
- simple graph ที่มีเอดจ์ได้ไม่เกินหนึ่งเส้นระหว่างสองโหนด และ multigraph ที่อนุญาตหลายเอดจ์
- hypergraph ที่เอดจ์หนึ่งเส้นเชื่อมได้ตั้งแต่ 3 โหนดขึ้นไป
- ubergraph ที่เอดจ์สามารถชี้ไปยังเอดจ์อื่นได้
- ในแต่ละแบบก็ยังมีการตัดสินใจด้านการออกแบบเพิ่มเติม
- ต้องตัดสินใจว่าจะให้ ID กับเอดจ์ด้วยหรือให้เฉพาะโหนด
- ต้องกำหนดด้วยว่าจะเก็บข้อมูลแบบใดในโหนดและเอดจ์
- เราอาจให้กราฟทุกแบบอยู่ในชนิดข้อมูลทั่วไปอย่าง “directed hyper uber multigraph” แล้วให้ผู้ใช้จำกัดเงื่อนไขเองก็ได้ แต่จะเจอสองปัญหาทันที
- อินเทอร์เฟซเปลี่ยนไป เช่น ผลลัพธ์ของ operation ควรเป็นค่าเดี่ยวหรือเป็นลิสต์
- ถ้าไม่ใช้ประโยชน์จากคุณสมบัติเฉพาะของกราฟ อัลกอริทึมก็จะทำงานได้ช้าลง
- ตัวอย่างเช่น maximum weight matching ถ้ารู้ว่ากราฟเป็นกราฟสองฝั่ง ก็ใช้อัลกอริทึมที่เร็วกว่าได้ แต่ถ้าเป็นกราฟทั่วไปก็จำเป็นต้องใช้อัลกอริทึมที่ช้ากว่าและครอบคลุมกว่า
- เมื่อมีปัญหา P, กราฟ G, และอัลกอริทึม A·B·C ก็จะเกิดปัญหาเรื่องalgorithm dispatchว่าจะเลือกใช้อัลกอริทึมใด
- ไลบรารีกราฟที่สมบูรณ์แบบต้องรองรับกราฟหลายประเภท แต่ยิ่งทำเช่นนั้น เวลาที่จะใช้กับการลงมือเขียนอัลกอริทึมที่ผู้ใช้ต้องการจริงก็ยิ่งลดลง
- อัลกอริทึมกราฟมีความยากในการเขียนสูง
- อัลกอริทึม
find_shortest_pathที่ผู้สร้าง Python เขียนไว้ถูกแก้ไขในภายหลังถึงห้าครั้ง - Nicole บอกว่า implementation ของ PageRank ที่เธอเปรียบเทียบมานั้นผิดทั้งหมด
- NetworkX มีอัลกอริทึมกราฟประมาณ 500 รายการ และเฉพาะโค้ดอัลกอริทึมก็เกือบ 60,000 บรรทัด
- standard library ทั้งหมดของ Python มีราว 300 แพ็กเกจ และน้อยกว่า 600,000 บรรทัด
- อัลกอริทึม
- ผู้ดูแล standard library ต้องตัดสินใจว่าจะใส่ชนิดกราฟแบบใด การรองรับ topology เฉพาะทางแบบใด และอัลกอริทึมใดบ้าง จึงเป็นภาระการดูแลรักษาที่สูง
- แม้ Python จะขึ้นชื่อเรื่อง “batteries included” แต่ก็มีแนวโน้มลบโมดูล standard library ออก 20 ตัวผ่าน PEP 594
การแทนกราฟก็ยากจะกำหนดให้เหลือแบบเดียว
- ต่อให้คิดเฉพาะกราฟมีทิศทางแบบง่ายที่สุด ก็ยังมีตัวแทนภายในได้หลายแบบ
- edge list:
[[a, b], [b, c], [c, a], [c, b]] - adjacency list:
[[b], [c], [a, b]] - adjacency matrix:
[0 1 0; 0 0 1; 1 1 0] - ชุดของ struct ที่อ้างอิงถึงกัน
- edge list:
- ประสิทธิภาพของ operation เปลี่ยนไปตามรูปแบบการแทน
- หากแทนกราฟที่มี 100 โหนดและ 200 เอดจ์ด้วย adjacency matrix จะได้เมทริกซ์ 100×100 ที่มีค่า 1 อยู่ 200 ตำแหน่ง และ 0 อยู่ 9,800 ตำแหน่ง
- ถ้าแทนกราฟเดียวกันด้วย edge list ก็ต้องเก็บเพียงคู่ของโหนด 200 คู่
- ขึ้นอยู่กับภาษาและระดับการ optimization ความต่างด้านหน่วยความจำอาจมากกว่า 20 เท่า
- ในทางกลับกัน หากเป็นกราฟที่มี 100 โหนดและ 8,000 เอดจ์ แล้วต้องการหาเอดจ์ระหว่างโหนด 0 กับ 93 ผลก็จะต่างออกไป
- adjacency matrix ตรวจสอบได้แบบ O(1) ด้วย
graph[0][93] - edge list ต้องวนดูเอดจ์ทั้ง 8,000 เส้น จึงใช้เวลา O(|edge|)
- adjacency matrix ตรวจสอบได้แบบ O(1) ด้วย
- กราฟที่มีเอดจ์น้อยเรียกว่า sparse graph ส่วนกราฟที่มีเอดจ์เกือบครบทุกคู่เรียกว่า dense graph
- โปรแกรมที่สร้างกราฟจากข้อมูลภายนอกอาจเริ่มจาก sparse graph แล้วภายหลังกลายเป็น dense graph ได้ จึงไม่มี “ตัวเลือกที่ดีเสมอ” สำหรับการแทนข้อมูลภายใน
- หากรองรับข้อมูลบนโหนด ข้อมูลบนเอดจ์ รวมถึงหลายชนิดของโหนดและเอดจ์ ความซับซ้อนในการ implement ก็ยิ่งเพิ่มขึ้น
- ไลบรารีภายนอกมักเลือกเดินหนึ่งในสองทาง
- ให้ชนิดข้อมูลเดียวที่มีความสามารถหลากหลายครอบคลุมทุกกรณีใช้งาน แต่แลกกับประสิทธิภาพ
- หรือแยกชนิดกราฟตามรูปแบบการแทน และปล่อยให้ผู้ใช้จัดการข้อมูลของโหนดและเอดจ์เอง
Trade-off ที่เห็นได้จาก NetworkX และ Petgraph
- NetworkX เก็บกราฟเป็นโครงสร้าง dict of dict of dict เพื่อให้ผูกข้อมูลใดก็ได้กับโหนดและเอดจ์
- แม้จะมีฟังก์ชันแปลงไปเป็นตัวแทนแบบอื่น แต่ไม่ได้รองรับการทำงานโดยตรงบนตัวแทนเหล่านั้น
- Petgraph ซึ่งเป็นไลบรารีกราฟเด่นของ Rust มีชนิดข้อมูลแยกตามกรณีใช้งาน เช่น
graph,graphmap,matrix_graph - Bradford ใช้ Petgraph ใน Nosey Parker เครื่องมือความปลอดภัยสำหรับหา secret จากประวัติทั้งหมดของ git repository
- กราฟที่ใช้ benchmark คือ CPython ซึ่งมี 250,000 commit และ 1,300,000 object
- แต่ละ commit node มีเอดจ์เพียงไม่กี่เส้น จึงเลือกใช้ adjacency list
- การรองรับหลายรูปแบบการแทนทำให้ต้นทุนในการเพิ่มอัลกอริทึมสูงขึ้น
- หากเขียนอัลกอริทึมแยกตามแต่ละรูปแบบ ภาระการดูแลรักษาอาจเพิ่มขึ้น 3–4 เท่า
- หากเขียนบน abstraction ทั่วไปเหนือชนิดข้อมูลแบบ polymorphic ประสิทธิภาพก็จะลดลง
- ผู้ให้สัมภาษณ์คนหนึ่งคาดว่าอัลกอริทึมกราฟที่เขียนเองเฉพาะทางอาจเร็วกว่าอัลกอริทึมทั่วไปมากกว่า 20 เท่า
ข้อจำกัดด้านประสิทธิภาพคือปัญหาหลักของไลบรารีกราฟ
- ในอัลกอริทึมกราฟมีปัญหาแบบ NP-complete หรือยากกว่านั้นอยู่มาก
- ใน 21 canonical NP-complete problems ของ Karp มีถึง 14 ข้อที่เป็นปัญหากราฟ
- ปัญหากราฟอาจต้องรันกับอินพุตที่ใหญ่มาก ทำให้รูปแบบการแทนและรายละเอียดการ implement เป็นตัวชี้ขาดว่าจะรันได้จริงหรือไม่
- ใน Nosey Parker นั้น Bradford ต้อง traversal object graph เพื่อสร้าง snapshot ของระบบไฟล์ขึ้นใหม่สำหรับแต่ละ commit
- graph walker ทั้งสี่แบบของ Petgraph ไม่สามารถขยายให้เหมาะกับกรณีใช้งานนั้นได้
- เขาจึงออกแบบ graph traversal algorithm แบบ “semi-novel” ขึ้นเฉพาะหน้า และลดการใช้หน่วยความจำลงได้ถึง 1,000 เท่า
- Zayenz ยก 15 puzzle เป็นตัวอย่างของกรณีที่กราฟใหญ่เกินกว่าจะจัดการทั้งก้อนได้
- การหา solution คือการรัน A* search บน state space
- state space นี้มีมากกว่า 20 ล้านล้านสถานะ
- เพียงแค่สร้างทุกโหนดขึ้นมาก็ถือว่าล้มเหลวแล้ว
- ในโครงการวิจัยเพิ่มกราฟให้กับตัวแก้ปัญหาเชิง constraint อย่าง Gecode ที่ Zayenz มีส่วนร่วม ชนิดกราฟแบบทั่วไปก็ยังสู้การเลือกรูปแบบการแทนที่ออกแบบตามปัญหาไม่ได้
- แม้ graph database จะถูกออกแบบมาเพื่อรันอัลกอริทึมกราฟที่ซับซ้อน แต่ปัญหาด้านประสิทธิภาพก็ยังคงอยู่
- Nicole บอกว่าหาก traversal ไม่จำกัดความลึก สุดท้ายก็จะเยี่ยมชมทั้งกราฟ
- แม้แต่การค้นหาแบบ “ออกไป 3 ขั้นแล้วหาว่ามีเส้นทางหรือไม่” ก็ยังต้องแตะข้อมูลจำนวนมาก
- Nicole ทำงานให้คำปรึกษาด้านประสิทธิภาพของ graph query โดยส่วนใหญ่เป็นการย้ายออกจาก graph database
- ในโปรเจกต์หนึ่ง คงไว้เพียงการคำนวณอย่างเดียว แล้วเขียนส่วนที่เหลือใหม่เป็นกระบวนการ MapReduce
- แม้จะเข้าใจยากกว่า แต่ก็สามารถรันเสร็จจริงได้ภายในข้ามคืน
ทำไมกราฟจึงพบได้น้อยใน standard library
- สาเหตุที่การรองรับกราฟอย่างกว้างขวางพบได้น้อย มาจากหลายปัจจัยซ้อนกัน
- มีชนิดของกราฟจำนวนมาก
- ในแต่ละชนิดก็มีวิธีแทนข้อมูลหลายแบบ
- มีอัลกอริทึมกราฟหลายชนิด
- ประสิทธิภาพของอัลกอริทึมไวต่อรูปแบบการแทนและรายละเอียดการ implement
- ผู้คนรันอัลกอริทึมที่มีต้นทุนสูงมากบนกราฟขนาดใหญ่มาก
- standard library ของภาษาโปรแกรมจึงต้องแบกรับทั้งการตัดสินใจด้านการออกแบบจำนวนมาก trade-off จำนวนมาก และภาระการดูแลรักษาที่หนัก
- ยังมีเหตุผลที่โปรแกรมเมอร์หลีกเลี่ยงไลบรารีกราฟภายนอกด้วย
- ไลบรารีอาจจำกัดเกินไป
- ไลบรารีทั่วไปอาจไม่ตอบโจทย์ด้านประสิทธิภาพ
- กราฟมีประโยชน์มากต่อการวิเคราะห์ระบบ แต่ในขั้นลงมือ implement มักจำเป็นต้องควบคุมทั้งการแทนข้อมูลและการเลือกอัลกอริทึมด้วยตนเอง
ภาคผนวก: ภาษาและเครื่องมือที่มีชนิดกราฟหรือเกี่ยวข้องกับกราฟ
- ภาษา query สำหรับกราฟ (GQL) ทำหน้าที่คล้าย SQL ใน graph database
- GraphQL ไม่ใช่ภาษา query สำหรับกราฟ และชื่อนี้มาจากความเชื่อมโยงกับ Facebook Graph Search
- ความต่างสำคัญระหว่าง GQL กับ SQL คือความสัมพันธ์หรือ “join” เป็นเอนทิตีชั้นหนึ่ง
- ในชุดข้อมูลภาพยนตร์และบุคคล SQL จะ implement ความสัมพันธ์ “แสดง”, “กำกับ”, “อำนวยการสร้าง” เป็นตาราง many-to-many แยกกัน
- ใน SPARQL ความสัมพันธ์เป็นเอดจ์ จึง query ได้ง่ายว่า “คนที่มีบทบาทใดก็ได้ในภาพยนตร์ Y และบทบาทนั้นคืออะไร”
- GQL ยังอาจรองรับการจัดการเอดจ์ เช่น การกลับทิศเอดจ์ การประกอบ และ transitive closure
- SPARQL ไม่สามารถคำนวณระหว่างทางของเส้นทางหรือความยาวของเส้นทางได้ เช่น การรวบรวมสายภาพยนตร์ที่เชื่อมนักแสดงสองคน
- GQL ที่รองรับสิ่งนี้จะซับซ้อนกว่ามาก
- ภาษา formal specification อย่าง Alloy มี primitive สำหรับ traversal กราฟที่มีประโยชน์บนชนิดข้อมูล relation ทำให้จัดการการแทนกราฟได้ง่ายกว่าภาษาโปรแกรมทั่วไป
- อย่างไรก็ตาม primitive เหล่านี้อิงกับเอดจ์แบบมี label และอาจไม่เหมาะกับการแทนกราฟแบบอื่น
- Python เพิ่ม graphlib เข้ามาในปี 2020
- นอกเหนือจาก
TopologicalSorterก็ไม่มีเมธอดอื่น - กราฟรับเข้าได้เฉพาะ dict ของโหนด
- กราฟ
a -> bถูกแทนเป็น dict กลับทิศแบบ{b: [a]}
- นอกเหนือจาก
- ณ ปี 2023 ภายใน CPython เองก็ยังไม่ได้ใช้
graphlib- บน GitHub มีไฟล์ที่อ้างถึง
graphlibไม่ถึง 900 ไฟล์ - ขณะที่
zoneinfoซึ่งเพิ่มเข้ามาในปีเดียวกัน ปรากฏในมากกว่า 6,000 ไฟล์ - วลี
def topological_sort(ปรากฏใน 4,000 ไฟล์ - topological sort ที่เขียนขึ้นเองจำนวนมากใช้การแทนกราฟที่ต่างจาก graphlib จึงแปลงมาใช้ได้ยาก
- บน GitHub มีไฟล์ที่อ้างถึง
- ตัวอย่างอื่นของ standard library ที่มีชนิดกราฟ ได้แก่ Erlang และ SWI-Prolog
- ยังมีภาษาโปรแกรมที่ “ทุกอย่างคือกราฟ” ด้วย
- ภาษาซอฟต์แวร์คณิตศาสตร์อย่าง Mathematica, MATLAB และ Maple ก็มีไลบรารีกราฟในรูปแบบใดรูปแบบหนึ่งเช่นกัน
- อัปเดตเมื่อ 18 มีนาคม 2024: คอมเมนต์บางส่วนเกี่ยวกับบทความนี้ถูกรวบรวมไว้ในหน้าแยก
1 ความคิดเห็น
ความคิดเห็นบน Hacker News
Graphviz มี ไลบรารีกราฟพื้นฐาน ของตัวเองที่โปรเจกต์อื่นไม่ได้ใช้ ซึ่งมีทั้งข้อดีและข้อเสีย
จากประสบการณ์นั้น พวกเราก็เจอกับ second-system syndrome แบบคลาสสิกเช่นกัน เราอยากสร้างไลบรารีกราฟที่เป็นโมดูลาร์, type-safe และมีประสิทธิภาพ แต่ท้ายที่สุดก็น่าจะเป็นอีกเวอร์ชันของคำว่า “ดี เร็ว ถูก — เลือกได้แค่สองอย่าง”
คำว่าโมดูลาร์หมายถึงเราอยากให้ชุดไลบรารีอัลกอริทึมกราฟสามารถพัฒนาและคอมไพล์แยกกันได้ ส่วน type-safe หมายถึงเราอยากจับข้อผิดพลาดในการเขียนโปรแกรมได้ตั้งแต่ตอนคอมไพล์ หรืออย่างช้าที่สุดตอนลิงก์ แทนที่จะเป็น runtime error อย่าง “โหนดไม่มีพร็อพเพอร์ตี้ color”
คำว่ามีประสิทธิภาพหมายถึงต้นทุนการเข้าถึงพร็อพเพอร์ตี้ของกราฟควรถูกพอ ๆ กับการเข้าถึงฟิลด์ของ struct ใน C และเราไม่อยากใช้วิธีพก hash table ภายนอกไปมา หรือแปลงสตริงกันเยอะ ๆ
จะคุ้มค่ากับต้นทุนไหม หรือมีเหตุผลไหม เป้าหมายเหล่านี้ถกเถียงกันได้ แต่ตอนนั้นสิ่งที่เราต้องการคือแบบนั้น ในแล็บมีผู้สร้าง C++ ชื่อดังอยู่ และเราก็คิดจะให้โอกาส C++ อีกครั้ง
Gordon Woodhull ซึ่งเคยเป็นอินเทิร์นแล้วทำงานร่วมกันต่อ เป็นโปรแกรมเมอร์ที่ยอดเยี่ยม และเขาเขียน implementation ของไลบรารีกราฟแบบนี้ด้วย template C++ ซอร์สก็อยู่ที่ https://www.dynagraph.org/
คนที่เหลือไม่แน่ใจว่าจะเข้าใจได้ในที่สุดไหมว่าโค้ดนั้นทำงานอย่างไร เลยทำ code review กับนักประดิษฐ์ C++ ชื่อดัง และหลังจากหน้าจอโค้ดจำนวนมากกับความเงียบงัน สรุปกันว่า “น่าจะทำงานได้” ตอนนั้นเรารู้แล้วว่าเราอาจก้าวข้ามหน้าผาแห่งความซับซ้อนไปแล้ว
ข้อผิดพลาดของ template ตอนคอมไพล์หนึ่งครั้งกินเต็มทั้งหน้าจอ และพ่นรายละเอียดที่มีแต่ผู้ประดิษฐ์ C++ เท่านั้นที่จะรักได้ ความผิดอยู่ที่พวกเราเอง และ Gordon ก็ยังเดินหน้าต่อจนทำให้ dynamic graph layout ทำงานได้แม้แต่บน Microsoft OLE
มองย้อนกลับไป มันก็เป็น Project Xanadu ในแบบของเราเอง และระหว่างที่เราหลงทางอยู่ในนั้น สิ่งอย่าง Gephi(Java), NetworkX, NetworKit(Python) ก็เกิดขึ้นมา John Ellson วิศวกรซอฟต์แวร์ฝีมือเยี่ยมผู้เขียน Graphviz บางส่วน ได้กอบกู้งานสายหลักให้กลับมาเดินต่อ
ในฐานะคนที่ทำงานกับกราฟมามาก ผมถูกถามนับครั้งไม่ถ้วนว่า “ทำไมภาษาโปรแกรมถึงไม่มี ชนิดข้อมูลกราฟ ในตัว?”
ตอนนี้ดีใจที่ไม่ต้องบอกแค่ “มันทำให้ดีได้ยากจริง ๆ” แล้วขอให้เชื่อ แต่สามารถชี้ไปยังบทวิเคราะห์ที่ลึกกว่าแบบบทความนี้ได้
สิ่งที่ภาษาส่วนใหญ่ให้มาในฐานะ structural type ก็มีเพียง static array, dynamic array และ linked list เท่านั้น ส่วน binary search tree หรือ hash table เป็น abstraction เชิงความหมายที่ซ่อนความสามารถบางส่วนของโครงสร้างพื้นฐานไว้ ไม่ใช่การแทนโครงสร้างล้วน ๆ
ส่วนในบทความที่ว่า “มีตัวเลือกการ implement มากเกินไป” ก็พูดเรื่องเดียวกัน แล้วพอเห็น Petgraph [0] ผมจึงได้ลองสำรวจไลบรารีกราฟเอนกประสงค์อย่างจริงจังเป็นครั้งแรก และมันก็น่าสนใจทีเดียว แต่ผมก็ยังคง implement กราฟในระดับโดเมนมาโดยตลอด
[0] https://github.com/petgraph/petgraph
https://core.tcl-lang.org/tcllib/doc/trunk/embedded/md/tclli...
แทบทุกภาษามี hash map ให้ และแม้ในบางสถานการณ์การ implement เองอาจทำให้เร็วกว่า แต่ implementation พื้นฐานก็มักทำงานได้ดีโดยรวม กราฟทำแบบนั้นได้ยาก และถ้าจะทำได้ก็อาจต้องมีกราฟหลายชนิดให้ใช้
เสริมว่า HashMap ของ Java ค่อนข้างพิเศษเล็กน้อยตรงที่ปรับ load factor ได้ ต่างจากภาษาอื่นส่วนใหญ่
สิ่งที่ผู้คนต้องการไม่ใช่ตัวชนิดกราฟเอง แต่ใกล้เคียงกับเครื่องมือสำหรับ traversal กราฟมากกว่า
ผมคิดว่ากราฟเป็น abstraction มากกว่าจะเป็นโครงสร้างข้อมูลหรือชนิดข้อมูล
โดยพื้นฐานแล้ว สิ่งที่ต้องมีเพื่อกำหนดกราฟมีเพียงเซตของจุดยอด v \in V และฟังก์ชัน Neighbors(v) เท่านั้น และสำหรับอัลกอริทึมกราฟพื้นฐานส่วนใหญ่ เท่านี้ก็เพียงพอจริง ๆ
ที่เหลือเป็นข้อจำกัดรายกรณี เช่น A->B หมายถึง B->A ด้วยหรือไม่, ชุดโหนดสามารถแบ่งภายใต้ข้อจำกัดบางอย่างได้หรือไม่, มีสีหรือเลเบลหรือไม่
ถ้าทำให้ทั่วไปยิ่งขึ้น ก็ขยับไปถึง hypergraph ได้ และในกรณีนี้มีแค่เซตของจุดยอดกับเซตของเซตจุดยอดก็พอ สามารถแทนได้หลายวิธีมากตามสิ่งที่สนใจ และกราฟทั่วไปก็เป็นเพียงกรณีพิเศษของมัน
จากมุมมองฐานข้อมูล อาจมองเป็นปัญหา query optimization และ indexing ได้เช่นกัน วิธีแทนข้อมูลที่ตอบได้ดีกว่าจะต่างกันไปตามคำถามที่อยากถามกับกราฟ เช่นเดียวกับที่ abstraction อย่าง “table” ไม่ได้มีวิธีแทนเพียงแบบเดียว “graph” ก็ไม่ได้จบด้วยวิธีเดียวเช่นกัน
มันอยู่ในระดับ abstraction เดียวกับตัวเลขล้วน ๆ เราพูดได้ว่ามีไลบรารี “เชิงตัวเลข” ที่มีประโยชน์ฉันใด ก็มีไลบรารี “เชิงกราฟ” ที่มีประโยชน์ฉันนั้น แต่แทบไม่มีไลบรารี “ตัวเลข” หรือไลบรารี “กราฟ” แนวคิดแบบนั้นนามธรรมเกินไปสำหรับการทำ API
ไฟล์เป็นจุดยอด และไดเรกทอรีเป็นเซตของจุดยอดที่ซ้อนกันได้
อุปสรรคหลักมีอยู่สองข้อ
ปัญหากราฟที่เรียบง่ายและมีขนาดเล็กนั้น แค่เขียน adjacency list ด้วยเวกเตอร์ของเวกเตอร์เองก็ง่ายพอแล้ว ส่วนปัญหากราฟที่ซับซ้อนและมีขนาดใหญ่มาก จะได้ประสิทธิภาพก็ต่อเมื่อต้องปรับแต่งการใช้งานกราฟให้เข้ากับรายละเอียดของปัญหาที่ต้องการแก้
ดังนั้นจึงมองไม่ค่อยเห็นว่าการรองรับจากภาษารูปแบบใดจะช่วยได้ ยาก เว้นแต่จะมีคอมไพเลอร์อัจฉริยะสุด ๆ ที่วิเคราะห์โค้ดแล้วตัดสินได้ว่าอะไรเหมาะที่สุด ไม่ว่าจะเป็น adjacency list, matrix, อาร์เรย์ 3 มิติ ฯลฯ การปรับแต่งแบบนั้นคงยังเห็นได้ยากในคอมไพเลอร์ไปอีกพักใหญ่
นี่เป็นอีกตัวอย่างหนึ่งของปรากฏการณ์ที่ Stroustrup เห็น เราแชร์โค้ดของสิ่งเล็ก ๆ อย่างเวกเตอร์ และสิ่งใหญ่ ๆ อย่างระบบปฏิบัติการได้ดี แต่กลับแชร์ ปัญหาขนาดกลาง ได้ไม่ดี
ภายในอีโคซิสเต็มของภาษาเดียว API ของเวกเตอร์มีขนาดเล็ก จึงดูเหมือนแชร์ได้ง่าย ส่วนระบบปฏิบัติการมี API ที่ค่อนข้างเล็กเมื่อเทียบกับความซับซ้อนภายใน และไลบรารีคำนวณเชิงตัวเลขก็เช่นกัน จึงแชร์กันได้ดี
ในทางกลับกัน ยิ่งพยายามปรับแต่งให้มากขึ้นเหมือนโครงสร้างข้อมูลที่ซับซ้อน API ก็ยิ่งซับซ้อนและแชร์ได้ยากขึ้น ท้ายที่สุด ความเป็นไปได้ในการแชร์ดูเหมือนจะขึ้นอยู่กับ พื้นที่ผิว ของสิ่งที่จะแชร์ หรือก็คือขนาดสัมพัทธ์ของ API
Electric Clojure ใช้ s-expression ของ Clojure เองเป็น ไวยากรณ์สำหรับเขียนกราฟ และใช้แมโครทำให้ data flow ของระบบ client/server แบบ reactive เป็นรูปธรรม
ในที่นี้กรณีใช้งานคืออินเทอร์เฟซผู้ใช้แบบ full-stack แต่แนวคิดนี้สามารถทำให้เป็นทั่วไปได้ https://github.com/hyperfiddle/electric ผมเป็นผู้ก่อตั้ง
คำตอบต่อคำถาม “ชนิดกราฟหายไปไหนหมด?” ผมมองว่า DSL สำหรับเขียนกราฟต้องแสดง scope, control flow และ abstraction ได้ และเมื่อเป็นเช่นนั้นมันก็แทบจะเป็น isomorphic กับภาษาโปรแกรมมิงที่หลุดพ้นจาก evaluation model แล้ว ใน Python และ TypeScript การสอดภาษาโปรแกรมมิงเต็มรูปแบบเข้าไปนั้นค่อนข้างยาก
บล็อกโพสต์ “Four problems preventing visual flowchart programming from expressing web applications” ก็ควรค่าแก่การอ่าน
https://www.dustingetz.com/#/page/four%20problems%20preventi...
บทความนี้ตอบคำถามเป็นหลักว่า “ทำไมภาษาโปรแกรมมิงจึงไม่รองรับ อัลกอริทึมกราฟ ให้ดีกว่านี้” และดูเหมือนจะเน้นการประมวลผลกราฟแบบ “big data” มากกว่าการรองรับกราฟโดยทั่วไป
ถ้ามองการรองรับกราฟโดยรวม ยังมีคำถามที่กว้างกว่านั้นด้วย เช่น “ทำไม OGM(Object Graph Mapper) ถึงไม่ได้รับความนิยมเท่า ORM” หรือ “ทำไม JSON จึงถูกใช้อย่างแพร่หลาย แต่ RDF หรือการ serialize กราฟระดับต่ำแบบอื่น ๆ กลับไม่เป็นเช่นนั้น”
สุดท้ายผมมองว่าสาเหตุทางประวัติศาสตร์มีน้ำหนักมาก RDF ออกมาเร็วเกินไปเล็กน้อยและไม่ได้วิวัฒน์อย่างเหมาะสม แถมยังสร้างมาตรฐานเชิงวิชาการและอีโคซิสเต็มการใช้งานที่เลวร้ายไว้ด้วย นอกจากนี้ กราฟยังซับซ้อนกว่าเล็กน้อยโดยเนื้อแท้ทั้งในด้านการใช้งานและ learning curve จึงไม่ scale กับนักพัฒนาจำนวนมากได้ดี
ผมจะไม่ให้น้ำหนักกับส่วน “Graph Querying Language” ของบทความมากเกินไป บางส่วนอ่านเหมือนข้อความการตลาดที่ผู้ใช้ตัวยงของ Neo4J หรือ SPARQL เขียนขึ้นโดยไม่ได้ลองสร้างผลิตภัณฑ์จริง
มีการบอกว่า “ความแตกต่างหลักของ GQL ทั้งหมดกับ SQL คือ join หรือก็คือความสัมพันธ์เป็น entity ระดับ first-class” แต่ใน SQL เอง join ก็เป็น entity ระดับ first-class เช่นกัน ถึงขั้นมีคีย์เวิร์ดชื่อ JOIN ด้วย
หากลงไปยังชั้นที่ต่ำกว่าของภาษาคิวรีกราฟและดู query plan จะพบว่าแทบไม่มีความแตกต่างอย่างมีนัยสำคัญจากคิวรีที่อิง SQL การที่การทำมาตรฐาน GQL[0] ดำเนินไปในฐานะส่วนขยายของ SQL เป็นหลักฐานของเรื่องนี้
SPARQL นั้นง่ายเมื่อต้องการ traverse เส้นทางที่แน่นอน แต่ถ้าจะทำสิ่งที่ซับซ้อนขึ้นอีกเล็กน้อยแบบที่น่าจะทำใน backend ของเว็บแอป ก็จะชนกับกับดักอย่างการ join กับค่าที่ยังไม่ bound ซึ่งอาจทำให้ result set ทั้งหมดพังโดยไม่ตั้งใจได้อย่างรวดเร็ว
[0]: https://en.wikipedia.org/wiki/Graph_Query_Language
เช่น type class ของ Haskell ไม่ใช่ first-class และ control flow ในภาษาโปรแกรมมิงส่วนใหญ่ก็ไม่ใช่ first-class เช่นกัน
เพียงแต่ไม่มีทางลัดทางไวยากรณ์เท่านั้น และโดยเนื้อแท้แล้วภาษาคิวรีกราฟก็เน้นไปที่การเพิ่มทางลัดนั้น
เครื่องมือวาดกราฟก็น่าผิดหวังพอสมควร ใช้งานได้ดีเมื่อเป็นกราฟขนาดเล็ก แต่พอมีโหนดเกินราว 500 โหนด ผลลัพธ์ก็จะอ่านไม่เข้าใจโดยสิ้นเชิงหรือดูยากมาก
ยังขาดความสามารถในการจัดกราฟให้เป็นโครงสร้างแบบลำดับชั้นโดยอัตโนมัติ และให้อินเทอร์เฟซที่เหมาะต่อการสำรวจ เมื่อคิดว่าเราคุ้นเคยกับการมองทุกสิ่งรอบตัวในระดับหนึ่งว่าเป็น โครงสร้างแบบลำดับชั้น ก็ดูเหมือนว่าปัญหาประเภทเดียวกันนี้ควรถูกแก้ด้วยเมื่อสร้างชนิดข้อมูลกราฟเอนกประสงค์
งานแบบนี้อาจต้องถูกนำไปใช้ในระดับคอมไพเลอร์ เพื่อให้อัลกอริทึมกราฟเอนกประสงค์ปรับตัวเข้ากับลำดับชั้นของโครงสร้างที่ถูกสร้างขึ้นได้ หากเพิ่มตัวพิสูจน์ทฤษฎีบทเข้ามาเพื่อยืนยันได้ว่าซับกราฟบางส่วนมีโครงสร้างเฉพาะอยู่เสมอ ขั้นตอนส่วนนั้นก็สามารถสร้างแบบสแตติกได้ ส่วนกราฟระดับบนที่เหลือสามารถสร้างแบบไดนามิกในรันไทม์ได้
ดังนั้นผู้ที่แก้ปัญหา การวาดกราฟเอนกประสงค์ ได้ ก็น่าจะมีความสามารถหรือความเข้าใจเชิงลึกพอที่จะทำเรื่องนี้ได้ด้วย
ไลบรารีวาดกราฟเอนกประสงค์แนวเดียวกับ Graphviz แต่ให้ตัวเลือกและการควบคุมมากกว่า
https://eclipse.dev/elk/
การทดลองที่ทีมพัฒนา ELK แห่ง Kiel University ดำเนินการ
https://github.com/kieler/KLighD
วิกิโครงการ Kieler
https://rtsys.informatik.uni-kiel.de/confluence/display/KIEL...
ไลบรารีวาดกราฟแบบอิงข้อจำกัด
https://www.adaptagrams.org/
อิมพลีเมนต์ด้วย JavaScript
https://ialab.it.monash.edu/webcola/
แหล่งข้อมูลที่น่าสนใจ HOLA: Human-like Orthogonal Network Layout
https://ialab.it.monash.edu/~dwyer/papers/hola2015.pdf
เดโม Confluent Graphs ช่วยทำให้เส้นเชื่อมอ่านง่ายขึ้น
https://www.aviz.fr/~bbach/confluentgraphs/
Stress-Minimizing Orthogonal Layout of Data Flow Diagrams with Ports
https://arxiv.org/pdf/1408.4626.pdf
Improved Optimal and Approximate Power Graph Compression for Clearer Visualisation of Dense Graphs
https://arxiv.org/pdf/1311.6996v1.pdf
แม้เป็นกราฟที่มีโครงสร้างเดียวกัน คนสองคนก็อาจเรนเดอร์ต่างกันโดยสิ้นเชิงเพื่อเน้นคนละแง่มุมของข้อมูล เรื่องนี้คล้ายกับปัญหา “อัลกอริทึมกราฟเอนกประสงค์” และ “โครงสร้างข้อมูลกราฟเอนกประสงค์” ด้วย
กราฟคร่อมอยู่บนเส้นแบ่งระหว่างโค้ดกับข้อมูล เช่น โปรแกรมใด ๆ ก็มีกราฟการเรียกใช้ ดังนั้นในความหมายหนึ่ง “อัลกอริทึมกราฟเอนกประสงค์” ก็คือการคำนวณเอง
แค่เกินไม่กี่สิบโหนด การทำให้เป็นระนาบ หรือทำให้มีจุดตัดน้อยและจัดกลุ่มโหนดที่เกี่ยวข้องกันให้ดูเกือบเหมือนระนาบ ก็มักเป็นเรื่องยากแล้ว
ในความเป็นจริง สิ่งที่แทบไม่ได้เป็นลำดับชั้นต้องถูกการวาดกราฟประนีประนอมเข้าหากัน และยากที่จะขีดเส้นอย่างเคร่งครัดทางคณิตศาสตร์ว่าตรงไหนนับเป็นลำดับชั้น ยิ่งตั้งสมมติฐานเกี่ยวกับโครงสร้างกราฟพื้นฐาน เช่น การเชื่อมต่อ การมีวงรอบ หรือความเบาบาง น้อยลง ปัญหานี้ก็ยิ่งแย่ลง
ในงานจริง เมื่อสร้าง UI สำหรับโต้ตอบกับกราฟ โดยทั่วไปมักกำหนดหรือบังคับเมตา-ลำดับชั้นหนึ่งหรือสองชั้นเพื่อให้ทำคลัสเตอร์ได้ ซึ่งจะช่วยลดผลกระทบที่โหนดแบบ hairball ทำลายเลย์เอาต์ และลดจำนวนโหนดเพื่อปรับปรุงประสิทธิภาพการเรนเดอร์ได้ด้วย สำหรับเลย์เอาต์สามารถใช้ fCOSE ได้ และมีอิมพลีเมนต์ของ Cytoscape.js ด้วย
ผมคิดว่าข้อสังเกตหลักที่ว่า “มีทางเลือกในการ implement มากเกินไป” นั้นไม่ถูกต้องเสียทีเดียว
ในทางปฏิบัติ ไลบรารีสามารถ implement การแทนกราฟที่เหมาะสมทั้งหมดได้, จัดหาอัลกอริทึมที่มีประสิทธิภาพดีที่สุดสำหรับแต่ละการแทน, และจัดให้มีการแปลงระหว่างรูปแบบการแทนเหล่านั้นได้ การแปลงนี้มีจำนวนแปรผันตามจำนวนรูปแบบการแทน และทั้งการ implement กับการใช้งานก็เรียบง่าย จึงเป็นภาระที่ค่อนข้างสมเหตุสมผลทั้งต่อผู้ดูแลและผู้ใช้
แถมยังสามารถจัดให้มีการแปลงนำเข้า/ส่งออกจากชนิดข้อมูลและ idiom ของไลบรารีมาตรฐานได้ด้วย ต้นทุนด้านหน่วยความจำและการแปลงนั้นถูก และ 99% ของ use case น่าจะมองข้าม overhead จากการแปลงข้อมูลได้ ทั้งในแง่ RAM และ CPU
ทำให้นึกถึงคำพูดที่ว่า “ความจริงอันโหดร้ายของการทำงานที่ Google คือสุดท้ายแล้วคุณก็แค่ย้าย protobuf จากที่หนึ่งไปอีกที่หนึ่ง”
https://news.ycombinator.com/item?id=20132880
สุดท้ายก็ต้อง implement กราฟใหม่เองอยู่ดี ประสิทธิภาพสำคัญมาก และไลบรารีกราฟสำเร็จรูปที่ผมเคยเห็นไม่สามารถใช้ประโยชน์จากความเป็นระเบียบของ dataset ของเราได้ ตัวอย่างเช่น เราใช้ append-only DAG ซึ่งแทบทุกโหนดมี edge เพียงเส้นเดียวที่ชี้ไปยังรายการที่ถูกเพิ่มล่าสุด จึงสามารถทำ run-length encoding ภายในได้
ผมยังไม่เคยเห็นไลบรารีกราฟทั่วไปที่รองรับ query ที่เราต้องการด้วย โดยเฉพาะอย่างยิ่งฟังก์ชัน diff ของกราฟย่อย ซึ่งเป็นเรื่องใหญ่
อีกอย่าง การ implement แบบปรับแต่งเองก็ไม่ได้งานเยอะนัก กราฟ implement ใหม่ได้ง่ายกว่า B-tree มาก และ implementation แบบง่าย ๆ ก็ใช้แค่ไม่กี่สิบบรรทัด แม้แต่ไลบรารีของเราที่ optimize อย่างมากพร้อมอัลกอริทึมที่รองรับ ก็ยังอยู่แค่ระดับไม่กี่ร้อยบรรทัด
ถ้ามีวิธีส่งออกข้อมูลเป็นรูปแบบมาตรฐานก็คงสะดวก แต่ใน use case ของเรา การดึงไลบรารีเข้ามาน่าจะสร้างปัญหาเพิ่มมากกว่าช่วยแก้ปัญหา
แอปพลิเคชันที่หายไปซึ่งผมนึกถึงบ่อย ๆ คือ Excel สำหรับกราฟ
เป็นเครื่องมือที่จัดการข้อมูลขนาดที่พอจะใส่ใน RAM ได้สำหรับข้อมูลแบบตาราง เช่นเดียวกับ Excel กล่าวคือขนาดที่ต้องใช้คอมพิวเตอร์ แต่ยังไม่ถึงขั้นต้องใช้ data center, implement อัลกอริทึมและการแสดงผลภาพจำนวนมากในระดับ “ดีพอ”, และใช้ได้โดยไม่ต้องมีความรู้ด้านการเขียนโปรแกรม
อย่างที่บทความบอก ปัญหาในโลกจริงจำนวนมากคือปัญหากราฟ แล้วทำไมมีแค่โปรแกรมเมอร์เท่านั้นที่ควรมีเครื่องมือสำหรับแก้ปัญหาเหล่านั้น
ถึงอย่างนั้นก็ยังมีโครงสร้างข้อมูลและไลบรารีมาตรฐานที่เพียงพอสำหรับ use case ส่วนใหญ่ และถ้ามีข้อกำหนดที่เผ็ดร้อนเป็นพิเศษ ก็ค่อยสร้าง solution แบบปรับแต่งเอง
บทความบอกว่ากราฟมักมีขนาดใหญ่มาก แต่ถ้าไปถามคนที่ทำงานกับอัลกอริทึมกราฟจริง ๆ ก็ย่อมเจอประสบการณ์แบบนั้นได้ง่าย โปรแกรมเมอร์และผู้ใช้ส่วนใหญ่อาจจัดการแค่กราฟที่เล็กจริง ๆ เท่านั้น
ผมไม่คิดว่าผู้ใช้ทั่วไปจะมองเห็นกราฟในปัญหาโลกจริงแบบสุ่ม ๆ จากการทำงานในบริษัทใหญ่ สิ่งที่ผมได้เรียนรู้คือ ถ้าพยายามมากพอ ทุกอย่างก็สามารถกลายเป็นสเปรดชีต Excel ได้
https://strlen.com/treesheets/ ใกล้เคียงกับ Excel สำหรับข้อมูลแบบ tree
เช่น บอกว่าอินเทอร์เน็ตสามารถ model เป็นกราฟได้ ซึ่งถึงจะจริง แต่ก็ยังไม่ชัดว่ามันนำไปสู่อะไร อินเทอร์เน็ตสามารถแทนได้หลายวิธี และก็ไม่ชัดว่าการแทนเป็นกราฟมีนัยทางวิศวกรรมที่มีประโยชน์โดยทั่วไป
การแทนที่เหมาะที่สุดสำหรับดึงข้อมูลที่เป็นประโยชน์ อาจเป็นฟังก์ชัน encoding แบบเมทริกซ์กล่องดำที่ map input ใด ๆ ให้เป็น output ที่สม่ำเสมอ หรือก็คือ neural network ก็ยังฟังดูโน้มน้าวได้พอ ๆ กัน
สำหรับที่อย่าง Google อาจเป็นไอเดียมูลค่าหลายหมื่นล้านดอลลาร์ แต่ทั้งอินเทอร์เน็ตไม่ได้เป็นปัญหากราฟสำหรับคนจำนวนมาก และการแทนเป็นกราฟก็ไม่ได้ช่วยแก้ได้หลายสิ่งนัก
คนที่กำลังแก้ปัญหาโลกจริงบนกระดาษด้วยกราฟนั้นมีน้อย ตารางถูกใช้ตลอดเวลา กราฟพบได้ทั่วไป แต่ ปัญหากราฟ ไม่ได้พบได้ทั่วไป
คอมเมนต์อื่นก็บอกว่าการแสดงผลกราฟนั้นยาก แต่ interface แบบ 3D ให้พื้นที่มากกว่ามาก ตอนกระแส VR เริ่มขึ้น ผมคิดว่า “Excel ของ VR จะเป็นอะไร?” และคำตอบของ Microsoft คือ “สเปรดชีต 2D ที่ลอยอยู่ในพื้นที่ 3D” ซึ่งผมว่ามันไร้สาระ ผมคิดว่ามันคือกราฟ
ถ้ามีใครอยากสำรวจเรื่องนี้ด้วยกัน ส่งเมลมาที่ชื่อผู้ใช้ของผม at gmail.com ได้
ชนิดข้อมูลกราฟมีมานานพอสมควรแล้ว
Erlang มี https://www.erlang.org/doc/man/digraph.html และ https://www.erlang.org/doc/man/digraph_utils และถ้าต้องการทำงานเชิงทฤษฎีเซต ก็มี https://www.erlang.org/doc/man/sofs.html ด้วย
เนื้อหาคือ “ผมพบภาษาอีกสองภาษาที่มีชนิดข้อมูลกราฟคือ Erlang และ SWI-Prolog เพราะผมไม่ค่อยรู้จักทั้งสองภาษา จึงบอกไม่ได้ว่าเพิ่มเข้ามาเมื่อไหร่ แต่ Erlang มีอย่างน้อยก่อนปี 2008 ผมติดต่อคนในคณะกรรมการภาษาแกนของ Erlang แล้ว แต่ไม่ได้รับคำตอบ”
ผมเคยใช้มันสำหรับ dependency resolution เพื่อกำหนดลำดับงาน