العثور على أقصر مسار بكفاءة في الرسوم البيانية الكبيرة

Question

إنني أتطلع إلى إيجاد طريقة للعثور في الوقت الفعلي على أقصر مسار بين العقد في رسم بياني ضخم.لديها مئات الآلاف من القمم وملايين الحواف.أعلم أن هذا السؤال قد تم طرحه من قبل وأعتقد أن الإجابة هي استخدام البحث الموسع أولاً، لكنني مهتم أكثر بمعرفة البرنامج الذي يمكنك استخدامه لتنفيذه.على سبيل المثال، سيكون مثاليًا تمامًا إذا كانت هناك مكتبة موجودة بالفعل (مع روابط بايثون!) لتنفيذ bfs في الرسوم البيانية غير الموجهة.

Answer 1

بيثون الرسم

إضافة:

جعلتني التعليقات فضولية حول كيفية قيام أداء Pygraph بمشكلة بناء على ترتيب البروتوكول الاختياري ، لذلك قمت بإنشاء برنامج لعبة لمعرفة ذلك. إليك الإخراج للحصول على نسخة أصغر قليلاً من المشكلة:

$ python2.6 biggraph.py 4 6
biggraph generate 10000 nodes     00:00:00
biggraph generate 1000000 edges   00:00:00
biggraph add edges                00:00:05
biggraph Dijkstra                 00:01:32
biggraph shortest_path done       00:04:15
step: 1915 2
step: 0 1
biggraph walk done                00:04:15
path: [9999, 1915, 0]

ليس سيئا للغاية لعقد 10K وحواف 1M. من المهم أن نلاحظ أن الطريقة التي يتم بها حساب Dijkstra بواسطة Pygraph تعطي قاموسًا لجميع أشجار الامتداد لكل عقدة بالنسبة إلى هدف واحد (الذي تم تعسفي العقدة 0 ، ولا يحمل أي موضع متميز في الرسم البياني). لذلك ، فإن الحل الذي استغرق 3.75 دقيقة لحساب أسفر بالفعل عن الإجابة على "ما هو أقصر مسار من جميع العقد إلى الهدف؟". في الواقع مرة واحدة shortest_path تم القيام به ، والمشي الإجابة كان مجرد بحث القاموس ولم يستغرق وقتا في الأساس. تجدر الإشارة أيضًا إلى أن إضافة الحواف المحسوبة مسبقًا إلى الرسم البياني كانت مكلفة إلى حد ما عند 1.5 دقيقة تقريبًا. هذه التوقيتات متسقة عبر عدة أشواط.

أود أن أقول إن العملية تسير بشكل جيد ، لكنني ما زلت أنتظر biggraph 5 6 على جهاز كمبيوتر خالص (Athlon 64 ، 4800 Bogomips لكل معالج ، كل ذلك في جوهر) الذي تم تشغيله لأكثر من ربع ساعة. على الأقل استخدام الذاكرة مستقر عند حوالي 0.5 جيجابايت. والنتائج في:

biggraph generate 100000 nodes    00:00:00
biggraph generate 1000000 edges   00:00:00
biggraph add edges                00:00:07
biggraph Dijkstra                 00:01:27
biggraph shortest_path done       00:23:44
step: 48437 4
step: 66200 3
step: 83824 2
step: 0 1
biggraph walk done                00:23:44
path: [99999, 48437, 66200, 83824, 0]

هذا وقت طويل ، لكنه كان أيضًا حسابًا ثقيلًا (وأتمنى حقًا أن أخلص النتيجة). إليك رمز الفضوليين:

#!/usr/bin/python

import pygraph.classes.graph
import pygraph.algorithms
import pygraph.algorithms.minmax
import time
import random
import sys

if len(sys.argv) != 3:
    print ('usage %s: node_exponent edge_exponent' % sys.argv[0])
    sys.exit(1)

nnodes = 10**int(sys.argv[1])
nedges = 10**int(sys.argv[2])

start_time = time.clock()
def timestamp(s):
    t = time.gmtime(time.clock() - start_time)
    print 'biggraph', s.ljust(24), time.strftime('%H:%M:%S', t)

timestamp('generate %d nodes' % nnodes)
bg = pygraph.classes.graph.graph()
bg.add_nodes(xrange(nnodes))

timestamp('generate %d edges' % nedges)
edges = set()
while len(edges) < nedges:
    left, right = random.randrange(nnodes), random.randrange(nnodes)
    if left == right:
        continue
    elif left > right:
        left, right = right, left
    edges.add((left, right))

timestamp('add edges')
for edge in edges:
    bg.add_edge(edge)

timestamp("Dijkstra")
target = 0
span, dist = pygraph.algorithms.minmax.shortest_path(bg, target)
timestamp('shortest_path done')

# the paths from any node to target is in dict span, let's
# pick any arbitrary node (the last one) and walk to the
# target from there, the associated distance will decrease
# monotonically
lastnode = nnodes - 1
path = []
while lastnode != target:
    nextnode = span[lastnode]
    print 'step:', nextnode, dist[lastnode]
    assert nextnode in bg.neighbors(lastnode)
    path.append(lastnode)
    lastnode = nextnode
path.append(target)
timestamp('walk done')
print 'path:', path

Answer 2

بالنسبة للرسوم البيانية الكبيرة، جرب واجهة Python الخاصة بـ igraph.يتم تنفيذ جوهرها في لغة C، وبالتالي يمكنها التعامل مع الرسوم البيانية بملايين القمم والحواف بسهولة نسبيًا.يحتوي على تطبيق BFS (من بين خوارزميات أخرى) ويتضمن أيضًا خوارزمية Dijkstra وخوارزمية Bellman-Ford للرسوم البيانية الموزونة.

أما بالنسبة لـ "الواقعية"، فقد أجريت بعض الاختبارات السريعة أيضًا:

from igraph import *
from random import randint
import time

def test_shortest_path(graph, tries=1000):
    t1 = time.time()
    for _ in xrange(tries):
        v1 = randint(0, graph.vcount()-1)
        v2 = randint(0, graph.vcount()-1)
        sp = graph.get_shortest_paths(v1, v2)
    t2 = time.time()
    return (t2-t1)/tries

>>> print test_shortest_path(Graph.Barabasi(100000, 100))     
0.010035698396
>>> print test_shortest_path(Graph.GRG(1000000, 0.002))
0.413572219742

وفقًا لمقتطف الكود أعلاه، فإن العثور على أقصر مسار بين رأسين محددين في رسم بياني لعالم صغير يحتوي على رؤوس 100 ألف وحواف 10 مليون (10M = 100K * 100) يستغرق حوالي 0.01003 ثانية في المتوسط ​​(متوسطًا من 1000 محاولة).كانت هذه حالة الاختبار الأولى وهو تقدير معقول إذا كنت تعمل مع بيانات الشبكة الاجتماعية أو بعض الشبكات الأخرى التي من المعروف أن القطر فيها صغير مقارنة بحجم الشبكة.الاختبار الثاني عبارة عن رسم بياني عشوائي هندسي حيث يتم إسقاط مليون نقطة بشكل عشوائي على مستوى ثنائي الأبعاد ويتم توصيل نقطتين إذا كانت المسافة بينهما أقل من 0.002، مما يؤدي إلى رسم بياني بحوالي 1 مليون رأس و6.5 مليون حرف.في هذه الحالة، تستغرق عملية حساب أقصر مسار وقتًا أطول (حيث أن المسارات نفسها أطول)، لكنها لا تزال قريبة جدًا من الوقت الفعلي:0.41357 ثانية في المتوسط.

تنصل:أنا واحد من المؤلفين igraph.

Answer 3

للحصول على رسم بياني كبير (ومع قيود أدائك) ، ربما تريد تعزيز مكتبة الرسم البياني لأنه مكتوب في C ++. لديها روابط بيثون أنت تبحث عن.

Answer 4

حسنًا ، يعتمد ذلك على مقدار البيانات الوصفية التي تعلقها بعقدك وحوافك. إذا كان حجم الرسم البياني هذا قليلًا نسبيًا ، فإن هذا الحجم من الرسم البياني سوف يتناسب مع الذاكرة ، وبالتالي أوصي بحزمة NetworkX الممتازة (انظر بشكل خاص http://networkx.lanl.gov/reference/generated/networkx.shortest_path.html) ، وهو بيثون نقي.

للحصول على حل أكثر قوة يمكنه التعامل مع ملايين العقد ، والبيانات الوصفية الكبيرة ، مع المعاملات ، وتخزين القرص ، وما إلى ذلك ، كنت محظوظًا كبيرًا مع Neo4J (http://www.neo4j.org/). إنه مكتوب في Java ولكن لديه روابط Python أو يمكن تشغيلها كخادم REST. اجتياز معها خافطة بعض الشيء ولكنها ليست سيئة.

Answer 5

BFS في رسم بياني غير موجه هو حوالي 25 سطرًا من التعليمات البرمجية. أنت لا تحتاج إلى مكتبة. تحقق من رمز المثال في مقال ويكيبيديا.

Answer 6

اعتمادًا على نوع المعلومات الإضافية التي لديك ، قد تكون* فعالة للغاية. على وجه الخصوص ، إذا أعطيت عقدة ، يمكنك حساب تقدير التكلفة من تلك العقدة إلى الهدف ، A* فعال على النحو الأمثل.

Answer 7

خزن في neo4j

إنه يشمل Dijkstra ، A*، "أقصر مسار" خوارزميات.