เริ่มต้นใช้งานเริ่มต้นใช้งานได้ฟรี

ค้นหา maximal clique ทั้งหมดที่มีขนาด "n"

หลังจากที่ได้สำรวจ triangle (และ open triangle) แล้ว มาทำความรู้จักกับ maximal clique กัน Maximal clique คือ clique ที่ไม่สามารถขยายได้ด้วยการเพิ่ม edge ที่ติดกัน และเป็นคุณสมบัติที่มีประโยชน์ของกราฟในการค้นหา community NetworkX มีฟังก์ชันที่ช่วยระบุโหนดที่อยู่ใน maximal clique แต่ละอันในกราฟ ได้แก่ nx.find_cliques(G) ลองใช้ฟังก์ชันนี้กับ T ใน IPython Shell เพื่อทดสอบดู แล้วจึงทำแบบฝึกหัด

แบบฝึกหัดนี้เป็นส่วนหนึ่งของหลักสูตร

การวิเคราะห์เครือข่ายเบื้องต้นด้วย Python

ดูคอร์ส

คำแนะนำการฝึกหัด

  • เขียนฟังก์ชัน maximal_cliques() ที่มีพารามิเตอร์สองตัว คือ G และ size เพื่อค้นหา maximal clique ทั้งหมดที่มีขนาด n
    • ใน for loop ให้วนซ้ำผ่าน clique ทั้งหมดใน G โดยใช้ฟังก์ชัน nx.find_cliques()
    • หาก clique ปัจจุบันมีขนาดเท่ากับ size ให้เพิ่มเข้าไปในลิสต์ mcs
  • ใช้คำสั่ง assert ร่วมกับฟังก์ชัน maximal_cliques() เพื่อตรวจสอบว่ากราฟ T มี maximal clique ขนาด 3 จำนวน 33 อัน

แบบฝึกหัดเชิงโต้ตอบแบบลงมือทำ

ลองทำแบบฝึกหัดนี้โดยเติมโค้ดตัวอย่างนี้ให้สมบูรณ์

# Define maximal_cliques()
def ____:
    """
    Finds all maximal cliques in graph `G` that are of size `size`.
    """
    mcs = []
    for clique in ____:
        if ____ == ____:
            ____
    return mcs

# Check that there are 33 maximal cliques of size 3 in the graph T
assert ____ == ____
แก้ไขและรันโค้ด