Contraction hierarchies
کمپیوٹر سائنس میں، سنکچن ہائیرارکیز کا طریقہ گراف میں مختصر ترین راستہ تلاش کرنے کے لیے ایک اسپیڈ اپ تکنیک ہے۔ سب سے زیادہ بدیہی ایپلی کیشنز کار نیویگیشن سسٹم ہیں: ایک صارف تیز ترین ممکنہ راستے سے گاڑی چلانا چاہتا ہے۔ یہاں جو میٹرک بہتر بنایا گیا ہے وہ سفر کا وقت ہے۔ چوراہوں کی نمائندگی عمودی طور پر کی جاتی ہے، سڑک کے حصے جو انہیں کناروں سے جوڑتے ہیں۔ کنارے کے وزن سڑک کے اس حصے کے ساتھ گاڑی چلانے میں لگنے والے وقت کی نمائندگی کرتے ہیں۔ سے جانے والا راستہ کناروں کا ایک سلسلہ ہے (سڑک کے حصے) ؛ سب سے چھوٹا راستہ وہ ہے جس میں تمام ممکنہ راستوں میں کنارے کے وزن کا کم سے کم مجموعہ ہو۔ گراف میں مختصر ترین راستے کا حساب ڈیجسٹرا کے الگورتھم کا استعمال کرتے ہوئے کیا جا سکتا ہے لیکن، یہ دیکھتے ہوئے کہ روڈ نیٹ ورک دسیوں لاکھوں عمودی حصوں پر مشتمل ہے، یہ ناقابل عمل ہے۔ کنٹریکشن ہائیرارکیز ایک اسپیڈ اپ طریقہ ہے جو روڈ نیٹ ورک کی نمائندگی کرنے والے گراف کی خصوصیات سے فائدہ اٹھانے کے لیے بہتر بنایا گیا ہے۔ اسپیڈ اپ کو پری پروسیسنگ مرحلے میں شارٹ کٹ بنا کر حاصل کیا جاتا ہے جسے پھر "غیر اہم" عمودی حصوں کو چھوڑنے کے لیے مختصر ترین راستے کے استفسار کے دوران استعمال کیا جاتا ہے۔ یہ اس مشاہدے پر مبنی ہے کہ روڈ نیٹ ورک انتہائی درجہ بندی پر مبنی ہیں۔ کچھ چوراہے، مثال کے طور پر ہائی وے جنکشن، "زیادہ اہم" ہوتے ہیں اور درجہ بندی میں اونچے ہوتے ہیں، مثال کے طور پر ایک جنکشن جو ڈیڈ اینڈ کی طرف جاتا ہے۔ شارٹ کٹ کو دو اہم جنکشنوں کے درمیان پہلے سے مرتب کردہ فاصلے کو بچانے کے لیے استعمال کیا جا سکتا ہے تاکہ الگورتھم کو استفسار کے وقت ان جنکشنوں کے درمیان مکمل راستے پر غور نہ کرنا پڑے۔ سنکچن کی درجہ بندی نہیں جانتی کہ انسان کون سی سڑکوں کو "اہم" سمجھتے ہیں (مثال کے طور پر۔ ہائی ویز)، لیکن انہیں ان پٹ کے طور پر گراف فراہم کیا جاتا ہے اور وہ ہیورسٹکس کا استعمال کرتے ہوئے عمودی حصوں کو اہمیت تفویض کرنے کے قابل ہوتے ہیں۔ کنٹریکشن کی درجہ بندی کا اطلاق نہ صرف کار نیویگیشن سسٹم میں اسپیڈ اپ الگورتھم پر ہوتا ہے بلکہ ویب پر مبنی روٹ پلانرز، ٹریفک سیمولیشن، اور لاجسٹک آپٹیمائزیشن میں بھی ہوتا ہے۔ الگورتھم کے نفاذ عوامی طور پر اوپن سورس سافٹ ویئر کے طور پر دستیاب ہیں۔ سنکچن ہائیرارکیز (سی ایچ) الگورتھم مختصر ترین راستے کے مسئلے کے لیے دو مراحل کا نقطہ نظر ہے جس میں پری پروسیسنگ مرحلہ اور استفسار مرحلہ شامل ہے۔ جیسا کہ سڑک کے نیٹ ورک کبھی کبھار تبدیل ہوتے ہیں، سوالات کے جوابات دینے سے پہلے کچھ حسابات کو پہلے سے مرتب کرنے کے لیے زیادہ وقت (سیکنڈ سے گھنٹے) استعمال کیا جا سکتا ہے۔ اس پہلے سے مرتب کردہ ڈیٹا کا استعمال کرتے ہوئے، بہت سے سوالات کا جواب بہت کم وقت (مائیکرو سیکنڈ) میں دیا جا سکتا ہے۔ سی ایچ ایس اس رفتار کو حاصل کرنے کے لیے شارٹ کٹ پر انحصار کرتے ہیں۔ ایک شارٹ کٹ دو عمودی حصوں کو جوڑتا ہے اور اصل گراف میں ملحقہ نہیں ہے۔ اس کے کنارے کا وزن مختصر ترین راستے پر کنارے کے وزن کا مجموعہ ہے۔ ہائی وے سے جڑے دو بڑے شہروں پر غور کریں۔ ان دونوں شہروں کے درمیان، چھوٹے دیہاتوں اور مضافات کی طرف جانے والے بہت سے جنکشن ہیں۔ زیادہ تر ڈرائیور ایک شہر سے دوسرے شہر جانا چاہتے ہیں-شاید کسی بڑے راستے کے حصے کے طور پر-اور راستے میں کسی ایک راستے سے باہر نہیں نکلنا چاہتے۔ اس سڑک کی ترتیب کی نمائندگی کرنے والے گراف میں، ہر چوراہے کی نمائندگی نوڈ کے ذریعے کی جاتی ہے اور پڑوسی چوراہوں کے درمیان کنارے بنائے جاتے ہیں۔ ان دونوں شہروں کے درمیان فاصلے کا حساب لگانے کے لیے، الگورتھم کو راستے کے تمام کناروں کو عبور کرنا پڑتا ہے، جس سے ان کی لمبائی بڑھ جاتی ہے۔ اس فاصلے کو ایک بار پہلے سے گننے اور اسے دو بڑے شہروں کے درمیان بنائے گئے اضافی کنارے میں ذخیرہ کرنے سے ہر بار جب اس شاہراہ کا استفسار میں جائزہ لینا پڑے گا تو حساب کی بچت ہوگی۔ اس اضافی کنارے کو "شارٹ کٹ" کہا جاتا ہے اور حقیقی دنیا میں اس کا کوئی ہم منصب نہیں ہے۔ سنکچن ہائیرارکیز الگورتھم کو سڑک کی اقسام کے بارے میں کوئی علم نہیں ہے لیکن وہ اس بات کا تعین کرنے کے قابل ہے کہ ان پٹ کے طور پر صرف گراف کا استعمال کرتے ہوئے کون سے شارٹ کٹ بنائے جائیں گے۔ پری پروسیسنگ مرحلہ سی ایچ الگورتھم سرچ اسپیس کو کم کرنے کے لیے پری پروسیسنگ مرحلے میں بنائے گئے شارٹ کٹ پر انحصار کرتا ہے-یعنی سوال کے وقت سی ایچ کو دیکھنے والے عمودی حصوں کی تعداد۔ اس کو حاصل کرنے کے لیے، تکراری ورٹیکس سنکچن کیے جاتے ہیں۔ کسی سرے کو سکڑتے وقت اسے عارضی طور پر گراف سے ہٹا دیا جاتا ہے، اور پڑوسی سرے کے ہر جوڑے کے درمیان ایک شارٹ کٹ بنایا جاتا ہے اگر سب سے مختصر راستہ شامل ہو۔ اس بات کا تعین کرنے کا عمل کہ آیا اس کے درمیان اور اس میں شامل مختصر ترین راستہ گواہوں کی تلاش کہلاتا ہے۔ یہ مثال کے طور پر صرف ابھی تک معاہدہ شدہ نوڈس کا استعمال کرتے ہوئے فارورڈ سرچ کا استعمال کرنے کے راستے کا حساب لگا کر انجام دیا جا سکتا ہے۔ نوڈ آرڈر ان پٹ گراف کے عمودی حصوں کو اس طرح سے سکڑنا پڑتا ہے جو سکڑنے سے گراف میں شامل کناروں کی تعداد کو کم سے کم کرتا ہے۔ چونکہ زیادہ سے زیادہ نوڈ آرڈر این پی مکمل ہے، اس لیے ہیورسٹکس کا استعمال کیا جاتا ہے۔ باٹم اپ اور ٹاپ ڈاؤن ہیورسٹکس موجود ہیں۔ ایک طرف، کمپیوٹیشنل طور پر سستا باٹم اپ ہیورسٹکس اس ترتیب کا فیصلہ کرتا ہے جس میں عمودی حصوں کو لالچی انداز میں سکڑنا ہے۔ اس کا مطلب ہے کہ ترتیب پہلے سے معلوم نہیں ہے بلکہ پچھلے سکڑنے کے مکمل ہونے کے بعد سکڑنے کے لیے اگلے نوڈ کا انتخاب کیا جاتا ہے۔ دوسری طرف ٹاپ ڈاؤن ہیورسٹکس پہلے نوڈ کے سکڑنے سے پہلے پورے نوڈ کی ترتیب کا پہلے سے حساب لگائیں۔ اس سے بہتر نتائج ملتے ہیں لیکن پری پروسیسنگ میں مزید وقت درکار ہوتا ہے۔ باٹم اپ ہیورسٹکس میں، سکڑنے کے لیے اگلے سرے کو منتخب کرنے کے لیے عوامل کا ایک مجموعہ استعمال کیا جاتا ہے۔ چونکہ شارٹ کٹ کی تعداد بنیادی عنصر ہے جو پری پروسیسنگ اور استفسار کے رن ٹائم کا تعین کرتی ہے، ہم اسے ہر ممکن حد تک چھوٹا رکھنا چاہتے ہیں۔ سب سے اہم اصطلاح جس کے ذریعے سکڑنے کے لیے اگلے نوڈ کا انتخاب کرنا ہے اس لیے نوڈ کو سکڑتے وقت جوڑے گئے کناروں کی خالص تعداد ہے۔ اس کی تعریف اس طرح کی گئی ہے کہ شارٹ کٹ کی تعداد کہاں ہے جو اگر معاہدہ کیا جائے تو بنائی جائے گی اور کناروں کی تعداد کہاں ہے۔ صرف اس معیار کا استعمال کرتے ہوئے، ایک لکیری راستے کے نتیجے میں لکیری درجہ بندی (بہت سی سطحیں) ہوگی اور کوئی شارٹ کٹ نہیں بنایا جائے گا۔ قریبی عمودی حصوں کی تعداد پر غور کرنے سے جو پہلے ہی سکڑ چکے ہیں، ایک یکساں سنکچن اور ایک ہموار درجہ بندی (کم سطح) حاصل کی جاتی ہے۔ یہ، مثال کے طور پر، ہر نوڈ کے لیے ایک کاؤنٹر کو برقرار رکھ کر کیا جا سکتا ہے جسے ہر بار پڑوسی ورٹیکس کے سکڑنے پر بڑھایا جاتا ہے۔ پھر نچلے کاؤنٹرز والے نوڈس کو اعلی کاؤنٹرز والے نوڈس کے مقابلے ترجیح دی جاتی ہے۔ دوسری طرف ٹاپ ڈاؤن ہیورسٹکس بہتر نتائج دیتا ہے لیکن اس کے لیے زیادہ پری پروسیسنگ وقت درکار ہوتا ہے۔ وہ ان چوٹیوں کی درجہ بندی کرتے ہیں جو بہت سے مختصر ترین راستوں کا حصہ ہیں ان سے زیادہ اہم ہیں جو صرف چند مختصر ترین راستوں کے لیے درکار ہیں۔ نیسٹڈ ڈسیکشنز کا استعمال کرتے ہوئے اس کا تخمینہ لگایا جا سکتا ہے۔ نیسٹڈ ڈسیکشن کا حساب لگانے کے لیے، ایک بار بار گراف کو دو حصوں میں الگ کرتا ہے، جو خود دو حصوں میں تقسیم ہوتے ہیں اور اسی طرح۔ یعنی نوڈس کا ایک ذیلی سیٹ تلاش کریں جو گراف سے ہٹائے جانے پر تقریبا برابر سائز کے دو جداگانہ ٹکڑوں میں الگ ہو جاتے ہیں۔ تمام نوڈس کو نوڈ آرڈرنگ میں آخری مقام پر رکھیں اور پھر بار بار نیسٹڈ ڈسیکشن کا حساب لگائیں اور، وجدان یہ ہے کہ گراف کے ایک نصف سے لے کر گراف کے دوسرے نصف تک کے تمام سوالات کو چھوٹے جداکار سے گزرنے کی ضرورت ہے اور اس لیے اس جداکار میں نوڈس بہت اہمیت کے حامل ہیں۔ نیسٹڈ ڈسیکشنز کا حساب سڑک کے نیٹ ورک پر ان کے چھوٹے جداکار کی وجہ سے مؤثر طریقے سے لگایا جا سکتا ہے۔ استفسار کا مرحلہ استفسار کے مرحلے میں، ابتدائی نوڈ سے شروع ہونے والی دو طرفہ تلاش کی جاتی ہے اور اصل گراف پر ٹارگٹ نوڈ کو پری پروسیسنگ مرحلے میں بنائے گئے شارٹ کٹ کے ذریعے بڑھایا جاتا ہے۔ اور کے درمیان مختصر ترین راستے پر سب سے اہم ورٹیکس یا تو خود یا دونوں سے زیادہ اہم ہوگا۔ لہذا، کم سے کم کرنے والا ورٹیکس اصل گراف اور ہولڈز میں مختصر ترین راستے پر ہے۔ یہ، شارٹ کٹ بنانے کے طریقے کے ساتھ مل کر، اس کا مطلب ہے کہ آگے اور پیچھے کی تلاش دونوں کو صرف کناروں کو آرام کرنے کی ضرورت ہے جو درجہ بندی میں زیادہ اہم نوڈس (اوپر کی طرف) کی طرف جاتا ہے جو تلاش کی جگہ کو چھوٹا رکھتا ہے۔ تمام اپ-(ڈاؤن-اپ)-ڈاؤن راستوں میں، اندرونی (ڈاؤن-اپ) کو چھوڑا جا سکتا ہے، کیونکہ پری پروسیسنگ مرحلے میں ایک شارٹ کٹ بنایا گیا ہے۔ راستہ بازیافت ایک سی ایچ استفسار، جیسا کہ اوپر بیان کیا گیا ہے، وقت یا فاصلہ حاصل کرتا ہے لیکن اصل راستہ نہیں۔ مختصر ترین راستے پر کناروں (سڑکوں) کی فہرست حاصل کرنے کے لیے لیے گئے شارٹ کٹ کو کھولنا پڑتا ہے۔ ہر شارٹ کٹ دو کناروں کا امتزاج ہے: یا تو اصل گراف کے دو کنارے، یا دو شارٹ کٹ، یا ایک اصل کنارے اور ایک شارٹ کٹ۔ سنکچن کے دوران ہر شارٹ کٹ کے درمیانی سرے کو ذخیرہ کرنے سے مختصر ترین راستے کی لکیری ٹائم ریکرسو ان پیکنگ ممکن ہوتی ہے۔ حسب ضرورت سنکچن کی درجہ بندی اگر کنارے کے وزن کو نیٹ ورک ٹوپولوجی سے زیادہ بار تبدیل کیا جاتا ہے، تو سی ایچ کو پری پروسیسنگ اور استفسار مرحلے کے درمیان حسب ضرورت مرحلے کو شامل کرکے تین مراحل کے نقطہ نظر تک بڑھایا جا سکتا ہے۔ اسے مثال کے طور پر کم سے کم فاصلے اور کم سے کم وقت کے درمیان تبدیل کرنے کے لیے استعمال کیا جا سکتا ہے یا موجودہ ٹریفک کی معلومات کے ساتھ ساتھ صارف کی ترجیحات جیسے بعض قسم کی سڑکوں (فیری، ہائی ویز) سے گریز کرنا شامل کیا جا سکتا ہے۔ پری پروسیسنگ مرحلے میں، زیادہ تر رن ٹائم اس ترتیب کی کمپیوٹنگ پر خرچ ہوتا ہے جس میں نوڈس کو معاہدہ کیا جاتا ہے۔ پری پروسیسنگ مرحلے میں سنکچن آپریشنز کے اس سلسلے کو اس وقت کے لیے محفوظ کیا جا سکتا ہے جب بعد میں حسب ضرورت مرحلے میں ان کی ضرورت ہو۔ ہر بار جب میٹرک کو حسب ضرورت بنایا جاتا ہے، تب سنکچن کو حسب ضرورت میٹرک کا استعمال کرتے ہوئے ذخیرہ شدہ ترتیب میں مؤثر طریقے سے لاگو کیا جا سکتا ہے۔ مزید برآں، نئے کنارے کے وزن کے لحاظ سے کچھ شارٹ کٹ دوبارہ گننا ضروری ہو سکتا ہے۔ اس کے کام کرنے کے لیے، سنکچن آرڈر کا حساب میٹرک آزاد نیسٹڈ ڈسیکشنز کا استعمال کرتے ہوئے لگانا پڑتا ہے۔ ایکسٹینشنز اور ایپلی کیشنز CHs جیسا کہ اوپر بیان کیا گیا ہے ایک ابتدائی نوڈ سے ایک ٹارگٹ نوڈ تک مختصر ترین راستے کی تلاش کریں۔ اسے ون ٹو ون مختصر ترین راستہ کہا جاتا ہے اور مثال کے طور پر کار نیویگیشن سسٹم میں استعمال ہوتا ہے۔ دیگر ایپلی کیشنز میں سڑک کے حصوں میں جی پی ایس کے نشانات کا ملاپ اور ٹریفک سمیلیٹرز کو تیز کرنا شامل ہے جن کو نیٹ ورک میں موجود تمام ڈرائیوروں کے ممکنہ راستوں پر غور کرنا ہوتا ہے۔ روٹ پیشن گوئی میں یہ اندازہ لگانے کی کوشش کی جاتی ہے کہ گاڑی ممکنہ طور پر کہاں جا رہی ہے، یہ حساب لگا کر کہ اس کی موجودہ اور ماضی کی پوزیشنیں اس کے ابتدائی مقام سے کسی ممکنہ ہدف تک کے مختصر ترین راستے سے کتنی اچھی طرح متفق ہیں۔ یہ سی ایچ ایس کا استعمال کرتے ہوئے مؤثر طریقے سے کیا جا سکتا ہے۔ ایک سے کئی منظرناموں میں، ایک ابتدائی نوڈ اور ٹارگٹ نوڈس کا ایک سیٹ دیا جاتا ہے اور سب کے لیے فاصلے کا حساب لگانا پڑتا ہے۔ ایک سے کئی سوالات کے لیے سب سے نمایاں ایپلی کیشن پوائنٹ آف انٹرسٹ سرچز ہیں۔ عام مثالوں میں قریب ترین گیس اسٹیشن، ریستوراں یا پوسٹ آفس کو تلاش کرنا شامل ہے جس میں جغرافیائی فاصلے کے بجائے حقیقی سفر کے وقت کو میٹرک کے طور پر استعمال کیا جاتا ہے۔ بہت سے سے بہت سے مختصر ترین راستے کے منظر نامے میں، ابتدائی نوڈس کا ایک سیٹ اور ٹارگٹ نوڈس کا ایک سیٹ دیا جاتا ہے اور سب کے لیے فاصلے کا حساب لگانا پڑتا ہے۔ یہ مثال کے طور پر لاجسٹک ایپلی کیشنز میں استعمال ہوتا ہے۔ سی ایچ ایس کو درج ذیل طریقے سے بہت سے سوالات تک بڑھایا جا سکتا ہے۔ سب سے پہلے، ہر ایک سے اوپر کی طرف پیچھے کی طرف تلاش کریں۔ اس تلاش کے دوران اسکین کیے گئے ہر سرے کے لیے، ایک بالٹی میں اسٹور کریں۔ پھر، ہر ایک سے آگے کی طرف اوپر کی طرف تلاش کی جاتی ہے، ہر خالی بالٹی کی جانچ پڑتال کی جاتی ہے، کہ آیا متعلقہ سرے پر جانے والا راستہ کسی بھی بہترین فاصلے کو بہتر بناتا ہے۔ یعنی، اگر کسی کے لیے۔ کچھ ایپلی کیشنز کو ایک سے دوسرے کے حسابات کی بھی ضرورت ہوتی ہے، یعنی، گراف میں ماخذ کے سرے سے دوسرے تمام عمودی حصوں تک کے فاصلے تلاش کرنا۔ چونکہ ڈیجسٹرا کا الگورتھم ہر کنارے کا بالکل ایک بار دورہ کرتا ہے اور اس لیے لکیری وقت میں چلتا ہے اس لیے یہ نظریاتی طور پر بہترین ہے۔ تاہم، ڈیجسٹرا کے الگورتھم کو متوازی بنانا مشکل ہے اور اس کے خراب مقام کی وجہ سے کیش-آپٹیمل نہیں ہے۔ سی ایچ ایس کو زیادہ کیش-بہترین نفاذ کے لیے استعمال کیا جا سکتا ہے۔ اس کے لیے، شارٹ کٹ سے بھرپور گراف میں تمام نوڈس پر نیچے کی طرف اسکین کے بعد آگے کی طرف اوپر کی طرف تلاش کی جاتی ہے۔ بعد کا آپریشن میموری کے ذریعے لکیری انداز میں اسکین کرتا ہے، کیونکہ نوڈس کو اہمیت کی کم ہوتی ہوئی ترتیب میں پروسیس کیا جاتا ہے اور اس لیے اسی کے مطابق میموری میں رکھا جا سکتا ہے۔ نوٹ کریں، کہ یہ ممکن ہے کیونکہ جس ترتیب میں نوڈس کو دوسرے مرحلے میں پروسیس کیا جاتا ہے وہ سورس نوڈ سے آزاد ہوتا ہے۔ پیداوار میں، کار نیویگیشن سسٹم کو پیش گوئی شدہ ٹریفک کی معلومات کا استعمال کرتے ہوئے تیز ترین سفری راستوں کا حساب لگانے اور متبادل راستوں کو ظاہر کرنے کے قابل ہونا چاہیے۔ دونوں سی ایچ ایس کا استعمال کرتے ہوئے کیے جا سکتے ہیں۔ سابقہ کو وقت پر منحصر نیٹ ورکس کے ساتھ روٹنگ کہا جاتا ہے جہاں کسی دیئے گئے کنارے کا سفر کا وقت اب مستقل نہیں ہوتا ہے بلکہ کنارے میں داخل ہوتے وقت دن کے وقت کا ایک کام ہوتا ہے۔ متبادل راستوں کو ہموار نظر آنے کی ضرورت ہے، جو مختصر ترین راستے سے نمایاں طور پر مختلف ہوں لیکن نمایاں طور پر طویل نہ ہوں۔ سی ایچ ایس کو ایک ہی وقت میں متعدد میٹرکس کو بہتر بنانے کے لیے بڑھایا جا سکتا ہے ؛ اسے ملٹی کرائٹیریا روٹ پلاننگ کہا جاتا ہے۔ مثال کے طور پر، کوئی بھی سفر کی لاگت اور وقت دونوں کو کم کر سکتا ہے۔ ایک اور مثال برقی گاڑیاں ہیں جن کے لیے دستیاب بیٹری چارج درست راستوں کو روکتا ہے کیونکہ بیٹری خالی نہیں چل سکتی ہے۔ تھیوری سنکچن کی درجہ بندی کی پری پروسیسنگ اور استفسار کی کارکردگی پر متعدد حدود قائم کی گئی ہیں۔ مندرجہ ذیل میں گراف میں عمودی حصوں کی تعداد، کناروں کی تعداد، شاہراہ کا طول و عرض، گراف کا قطر، درخت کی گہرائی ہے اور درخت کی چوڑائی ہے۔ سنکچن ہیرارکی کارکردگی کا پہلا تجزیہ جزوی طور پر اس مقدار پر منحصر ہے جسے ہائی وے طول و عرض کہا جاتا ہے۔ اگرچہ اس مقدار کی تعریف تکنیکی ہے، بدیہی طور پر گراف کا ایک چھوٹا سا ہائی وے طول و عرض ہوتا ہے اگر ہر ایک کے لیے عمودی کا ایک چھوٹا سا مجموعہ ہوتا ہے جس میں لمبائی کا ہر مختصر ترین راستہ شامل ہوتا ہے۔ شاہراہ کے طول و عرض کی صحیح قیمت کا حساب لگانا این پی-ہارڈ اور ڈبلیو [1]-ہارڈ ہے، لیکن گرڈ کے لیے یہ معلوم ہے کہ شاہراہ کا طول و عرض۔ حسب ضرورت کنٹریکشن ہائیرارکی لائن آف ورک میں ایک متبادل تجزیہ پیش کیا گیا۔ سوال کے چلنے کے اوقات کو اس سے محدود کیا جا سکتا ہے۔ چونکہ درخت کی گہرائی کو درخت کی چوڑائی کے لحاظ سے محدود کیا جا سکتا ہے، اس لیے یہ بھی ایک درست اوپری حد ہے۔ اہم ذریعہ یہ ہے کہ لیکن بدترین صورت حال کے چلنے کے اوقات کے نتائج بہتر طور پر تفصیل سے بیان کیے گئے ہیں۔ پری پروسیسنگ کارکردگی سوال کارکردگی حوالہ جات بیرونی لنکس اوپن سورس نفاذ https://www.graphhopper.com https://github.com/ifsttar/Tempus https://github.com/RoutingKit/RoutingKit http://project-osrm.org http://www.opentripplanner.org گراف الگورتھم تلاش الگورتھم روٹنگ الگورتھم