In [ ]:
%config InteractiveShell.ast_node_interactivity="none"
%pip install networkx
%pip install matplotlib
%pip install pygraphviz
import networkx as nx
import warnings
import base64
warnings.simplefilter(action='ignore', category=FutureWarning)
def f(globals, locals):
import base64
CODE = (
"ZGVmIG1ha2VfcHJpbnRfbG9jYWxzKCk6IAogICAgIyBJbiBhIGZ1bmN0aW9uIHRvIHByZXZlbnQgbG9jYWxzIGFuZCBpbXBvcnRzIGZyb20gbGVha2luZy4KICAgIGdsb2JhbCBtYWtlX3ByaW50X2xvY2FscwogICAgZGVsIG1ha2VfcHJpbnRfbG9jYWxzICAjIE9ubHkgcnVuIHRoaXMgZnVuY3Rpb24gb25jZS4KCiAgICBpbXBvcnQgSVB5dGhvbgogICAgaW1wb3J0IGFzdAogICAgaW1wb3J0IGluc3BlY3QKCiAgICBjbGFzcyBWaXNpdG9yKGFzdC5Ob2RlVmlzaXRvcik6CiAgICAgICAgZGVmIF9faW5pdF9fKHNlbGYpOgogICAgICAgICAgICBzZWxmLnZhcmlhYmxlcyA9IHNldCgpCiAgICAgICAgZGVmIHZpc2l0X05hbWUoc2VsZiwgbmFtZSk6CiAgICAgICAgICAgIHNlbGYudmFyaWFibGVzLmFkZChuYW1lLmlkKQogICAgICAgICMgVE9ETzogUG9zc2libHkgZGV0ZWN0IHdoZXRoZXIgdmFyaWFibGVzIGFyZSBhc3NpZ25lZCB0by4KCiAgICBBTExPV19UWVBFUyA9IFtpbnQsIGZsb2F0LCBzdHIsIGJvb2wsIGxpc3QsIGRpY3QsIHR1cGxlLCByYW5nZV0KICAgIGRlZiBmaWx0ZXJfdmFyaWFibGVzKHZhcmlhYmxlcywgbG9jYWxzKToKICAgICAgICBmb3IgdiBpbiB2YXJpYWJsZXM6CiAgICAgICAgICAgIGlmIHYgaW4gbG9jYWxzIGFuZCB0eXBlKGxvY2Fsc1t2XSkgaW4gQUxMT1dfVFlQRVM6CiAgICAgICAgICAgICAgICB5aWVsZCB2CiAgCiAgICAjIFVuZm9ydHVuYXRlbHksIHRoZXJlIGRvZXNuJ3Qgc2VlbSB0byBiZSBhIHN1cHBvcnRlZCB3YXkgb2YgZ2V0dGluZwogICAgIyB0aGUgY3VycmVudCBjZWxsJ3MgY29kZSB2aWEgdGhlIHB1YmxpYyBJUHl0aG9uIEFQSXMuIEhvd2V2ZXIsIGJlY2F1c2UKICAgICMgd2UgYXJlIGdldHRpbmcgY2FsbGVkIGZyb20gSVB5dGhvbiBpdHNlbGYgYW5kIHdlIGFyZSBhbHJlYWR5IGluc3BlY3RpbmcKICAgICMgdGhlIHN0YWNrdHJhY2UsIHdlIG1pZ2h0IGFzIHdlbGwganVzdCBwZWVrIGludG8gaXRzIGZyYW1lLi4uCiAgICBpZiBJUHl0aG9uLl9fdmVyc2lvbl9fID09ICI1LjUuMCI6CiAgICAgICAgIyBjb2xhYgogICAgICAgIGRlZiBnZXRfYXN0KGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGFzdC5Nb2R1bGUoZnJhbWUuZl9iYWNrLmZfYmFjay5mX2xvY2Fsc1sibm9kZWxpc3QiXSkKICAgICAgICBkZWYgZmluZF9sb2NhbHMoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4gZnJhbWUuZl9sb2NhbHMKICAgICAgICBkZWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfYmFjay5mX2NvZGUuY29fZmlsZW5hbWUuZW5kc3dpdGgoIklQeXRob24vY29yZS9pbnRlcmFjdGl2ZXNoZWxsLnB5IikKCiAgICBlbGlmIElQeXRob24uX192ZXJzaW9uX18gPT0gIjguNC4wIjoKICAgICAgICAjIGxhYiBjb21wdXRlcnMKICAgICAgICBkZWYgZ2V0X2FzdChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBhc3QuTW9kdWxlKGZyYW1lLmZfYmFjay5mX2JhY2suZl9sb2NhbHNbIm5vZGVsaXN0Il0pCiAgICAgICAgZGVmIGZpbmRfbG9jYWxzKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfbG9jYWxzCiAgICAgICAgZGVmIGF0X3RvcF9sZXZlbChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBmcmFtZS5mX2JhY2suZl9jb2RlLmNvX2ZpbGVuYW1lLmVuZHN3aXRoKCJJUHl0aG9uL2NvcmUvaW50ZXJhY3RpdmVzaGVsbC5weSIpCiAgICBlbHNlOgogICAgICAgIHByaW50KGYicHJpbnRfbG9jYWxzKCkgbm90IHN1cHBvcnRlZCBvbiBJUHl0aG9uIHZlcnNpb24ge0lQeXRob24uX192ZXJzaW9uX199IikKCiAgICBkZWYgZ2V0X2NlbGxfbmFtZXMoZnJhbWUpOgogICAgICAgIHRyZWUgPSBnZXRfYXN0KGZyYW1lKQogICAgICAgIHZpc2l0b3IgPSBWaXNpdG9yKCkKICAgICAgICB2aXNpdG9yLnZpc2l0KHRyZWUpCiAgICAgICAgcmV0dXJuIGZpbHRlcl92YXJpYWJsZXModmlzaXRvci52YXJpYWJsZXMsIGZyYW1lLmZfbG9jYWxzKQoKICAgIGRlZiBmaW5kX3doaWNoKGZyYW1lKToKICAgICAgICAjIEZyYW1lIGlzIHRoZSBmcmFtZSB3aG9zZSBsb2NhbHMgd2UgYXJlIGludGVyZXN0ZWQgaW4gcHJpbnRpbmcuCiAgICAgICAgaWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgIyBUaGUgcGFyZW50IGZyYW1lIG9mIHRoZSBpbnRlcmVzdGVkIGZyYW1lIGlzIGEgbW9kdWxlLCBtb3N0IGxpa2VseQogICAgICAgICAgICAjICJpbnRlcmFjdGl2ZXNoZWxsIi4gVGhpcyBtZWFucyB3ZSBhcmUgaW4gdGhlIGdsb2JhbCBzY29wZSwgc2luY2UKICAgICAgICAgICAgIyBvbmx5IHRoZSBnbG9iYWwgc2NvcGUgc2hvdWxkIGJlIGRpcmVjdGx5IHJ1biBieSB0aGUgaW50ZXJhY3RpdmUgc2hlbGwuCiAgICAgICAgICAgIHJldHVybiBzZXQoZ2V0X2NlbGxfbmFtZXMoZnJhbWUpKQogICAgICAgICMgVGhlIHBhcmVudCBmcmFtZSBpcyBub3QgYSBtb2R1bGUsIHNvIHdlIGFyZSBpbiBhIGxvY2FsIHNjb3BlLgogICAgICAgIHJldHVybiBzZXQoZnJhbWUuZl9sb2NhbHMpCgogICAgZGVmIHByaW50X2xvY2Fscygqd2hpY2gsIHR5cGVzPUZhbHNlKToKICAgICAgICAiIiJQcmludCB0aGUgbG9jYWwgdmFyaWFibGVzIGluIHRoZSBjYWxsZXIncyBmcmFtZS4iIiIKICAgICAgICBpbXBvcnQgaW5zcGVjdAogICAgICAgICMgY3VycmVudGZyYW1lKCkgZnJhbWUgaXMgcHJpbnRfbG9jYWxzLiBXZSB3YW50IHRoZSBjYWxsZXIncyBmcmFtZQogICAgICAgIGZyYW1lID0gaW5zcGVjdC5jdXJyZW50ZnJhbWUoKS5mX2JhY2sKICAgICAgICBsb2NhbHMgPSBmaW5kX2xvY2FscyhmcmFtZSkKICAgICAgICB3aGljaCA9IHNldCh3aGljaCkgaWYgd2hpY2ggZWxzZSBmaW5kX3doaWNoKGZyYW1lKQogICAgICAgIGxsID0ge2s6IHYgZm9yIGssIHYgaW4gbG9jYWxzLml0ZW1zKCkgaWYgayBpbiB3aGljaH0KICAgICAgICBpZiBub3QgbGw6CiAgICAgICAgICAgIHByaW50KCJwcmludF9sb2NhbHM6IG5vIGxvY2FscyIpCiAgICAgICAgICAgIHJldHVybgogICAgICAgIGlmIHR5cGVzOgogICAgICAgICAgICBwcmludCgiXG4iLmpvaW4oZiJ7a306IHt0eXBlKHYpLl9fbmFtZV9ffSDihpAge3Z9IiBmb3IgaywgdiBpbiBsbC5pdGVtcygpKSkKICAgICAgICBlbHNlOgogICAgICAgICAgICBwcmludCgiOyAiLmpvaW4oZiJ7a30g4oaQIHtyZXByKHYpfSIgZm9yIGssIHYgaW4gbGwuaXRlbXMoKSkpCgogICAgcmV0dXJuIHByaW50X2xvY2FscwoKcHJpbnRfbG9jYWxzID0gbWFrZV9wcmludF9sb2NhbHMoKQ==",
"ZGVmIG1ha2VfcHJldHR5X2Fzc2VydCgpOgogICAgaW1wb3J0IHN5cwogICAgaW1wb3J0IElQeXRob24KICAgIGltcG9ydCBhc3QKICAgIGltcG9ydCBpbnNwZWN0CiAgICBpbXBvcnQgaW8KICAgIGltcG9ydCBpdGVydG9vbHMKICAgIGltcG9ydCBmdW5jdG9vbHMKICAgIGltcG9ydCBjb3B5CiAgICAKICAgIGdsb2JhbCBtYWtlX3ByZXR0eV9hc3NlcnQKICAgIGRlbCBtYWtlX3ByZXR0eV9hc3NlcnQKCiAgICBpZiBJUHl0aG9uLl9fdmVyc2lvbl9fID09ICI1LjUuMCI6CiAgICAgICAgIyBjb2xhYiBUT0RPCiAgICAgICAgZGVmIGdldF9hc3NlcnRfbGluZShmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBmcmFtZS5mX2JhY2suZl9iYWNrLmZfbG9jYWxzWyJub2RlIl0KICAgICAgICBkZWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgY29kZSA9IGZyYW1lLmZfYmFjay5mX2JhY2suZl9jb2RlCiAgICAgICAgICAgIHJldHVybiBjb2RlLmNvX2ZpbGVuYW1lLmVuZHN3aXRoKCJJUHl0aG9uL2NvcmUvaW50ZXJhY3RpdmVzaGVsbC5weSIpCiAgICAgICAgZGVmIGNhbl9hbm5vdGF0ZShmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBGYWxzZQoKICAgIGVsaWYgSVB5dGhvbi5fX3ZlcnNpb25fXyA9PSAiOC40LjAiOgogICAgICAgICMgbGFiIGNvbXB1dGVycwogICAgICAgIGRlZiBnZXRfYXNzZXJ0X2xpbmUoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4gZnJhbWUuZl9iYWNrLmZfYmFjay5mX2xvY2Fsc1sibm9kZSJdCiAgICAgICAgZGVmIGF0X3RvcF9sZXZlbChmcmFtZSk6CiAgICAgICAgICAgIGNvZGUgPSBmcmFtZS5mX2JhY2suZl9iYWNrLmZfY29kZQogICAgICAgICAgICByZXR1cm4gY29kZS5jb19maWxlbmFtZS5lbmRzd2l0aCgiSVB5dGhvbi9jb3JlL2ludGVyYWN0aXZlc2hlbGwucHkiKSBhbmQgY29kZS5jb19uYW1lID09ICJydW5fYXN0X25vZGVzIgogICAgICAgIGRlZiBjYW5fYW5ub3RhdGUoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4gYXRfdG9wX2xldmVsKGZyYW1lKQoKICAgIGRlZiBpc19saXRlcmFsKGEpOgogICAgICAgIHRyeToKICAgICAgICAgICAgYXN0LmxpdGVyYWxfZXZhbChhKQogICAgICAgICAgICByZXR1cm4gVHJ1ZQogICAgICAgIGV4Y2VwdCBWYWx1ZUVycm9yOgogICAgICAgICAgICByZXR1cm4gRmFsc2UKICAgICAgICByZXR1cm4gRmFsc2UKCgogICAgZGVmIGFubm90YXRlX2NhbGwoZnJhbWUpOgogICAgICAgIGlmIG5vdCBjYW5fYW5ub3RhdGUoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4KICAgICAgICAKICAgICAgICBleHByOiBhc3QuRXhwciA9IGdldF9hc3NlcnRfbGluZShmcmFtZSkKICAgICAgICBmb3Iga3dhcmcgaW4gZXhwci52YWx1ZS5rZXl3b3JkczoKICAgICAgICAgICAgaWYga3dhcmcuYXJnID09ICJnb3QiOgogICAgICAgICAgICAgICAgZ290ID0ga3dhcmcudmFsdWUKCiAgICAgICAgaWYgaXNpbnN0YW5jZShnb3QsIGFzdC5DYWxsKToKICAgICAgICAgICAgaWYgbm90IGlzaW5zdGFuY2UoZ290LmZ1bmMsIGFzdC5OYW1lKToKICAgICAgICAgICAgICAgIHJldHVybgogICAgICAgICAgICBuYW1lID0gZ290LmZ1bmMuaWQKICAgICAgICAgICAgZnVuYyA9IGZyYW1lLmZfbG9jYWxzW25hbWVdCiAgICAgICAgICAgIGlmIG5vdCBoYXNhdHRyKGZ1bmMsIERFQlVHR0FCTEVfQVJHUyk6CiAgICAgICAgICAgICAgICByZXR1cm4KICAgICAgICAgICAgYXJncyA9IGdldGF0dHIoZnVuYywgREVCVUdHQUJMRV9BUkdTKQogICAgICAgICAgICBrd2FyZ3MgPSBnZXRhdHRyKGZ1bmMsIERFQlVHR0FCTEVfS1dBUkdTKQogICAgICAgICAgICBpZiBhcmdzIGlzIE5vbmUgb3Iga3dhcmdzIGlzIE5vbmU6CiAgICAgICAgICAgICAgICByZXR1cm4KICAgICAgICAgICAgYm91bmRhcmdzID0gaW5zcGVjdC5zaWduYXR1cmUoZnVuYykuYmluZCgqYXJncywgKiprd2FyZ3MpCgogICAgICAgICAgICByZXN1bHQgPSBpby5TdHJpbmdJTygpCiAgICAgICAgICAgIHBvcyA9IHJlc3VsdC53cml0ZShuYW1lKQogICAgICAgICAgICBwb3MgKz0gcmVzdWx0LndyaXRlKCIoIikKCiAgICAgICAgICAgIHNlcCA9ICcsICcKICAgICAgICAgICAgYXJnX3R1cGxlcyA9IFtdICAjIChhc3RfYXJnX3N0ciwgZXZhbHVhdGVkX2FyZywgc3RhcnQsIGxpbWl0KQoKICAgICAgICAgICAgIyBVc2UgYW4gaXRlcmF0b3IgaGVyZS4gSWYgYSBib3VuZGFyZyBpcyBub3QgY29uc3VtZWQgaGVyZSwKICAgICAgICAgICAgIyBpdCBtYXkgYmUgY29uc3VtZWQgbGF0ZXIgYnkgYSBwb3Mra3cgYXJnLgogICAgICAgICAgICBib3VuZGFyZ3NfaXRlciA9IGl0ZXIoYm91bmRhcmdzLmFyZ3MpCiAgICAgICAgICAgIGZvciBhc3RfYXJnLCBhcmcgaW4gemlwKGdvdC5hcmdzLCBib3VuZGFyZ3NfaXRlcik6CiAgICAgICAgICAgICAgICBhc3RfYXJnX3N0ciA9IGFzdC51bnBhcnNlKGFzdF9hcmcpCiAgICAgICAgICAgICAgICBhcmdfdHVwbGVzLmFwcGVuZCgoYXN0X2FyZ19zdHIsIGFyZywgcG9zLCBwb3MgKyBsZW4oYXN0X2FyZ19zdHIpKSkKICAgICAgICAgICAgICAgIHBvcyArPSBsZW4oYXN0X2FyZ19zdHIpICsgbGVuKHNlcCkKCiAgICAgICAgICAgIGZvciBhc3Rfa3dhcmcsIGt3YXJnIGluIGl0ZXJ0b29scy56aXBfbG9uZ2VzdChnb3Qua2V5d29yZHMsIGJvdW5kYXJnc19pdGVyKToKICAgICAgICAgICAgICAgIGFzdF9hcmdfc3RyID0gYXN0LnVucGFyc2UoYXN0X2t3YXJnKQogICAgICAgICAgICAgICAgYXJnX3R1cGxlcy5hcHBlbmQoKGFzdF9hcmdfc3RyLCBrd2FyZywgcG9zICsgbGVuKGFzdF9rd2FyZy5hcmcpICsgbGVuKCc9JyksIHBvcyArIGxlbihhc3RfYXJnX3N0cikpKQogICAgICAgICAgICAgICAgcG9zICs9IGxlbihhc3RfYXJnX3N0cikgKyBsZW4oc2VwKQoKICAgICAgICAgICAgcG9zIC09IGxlbihzZXApCiAgICAgICAgICAgIHJlc3VsdC53cml0ZShzZXAuam9pbih0WzBdIGZvciB0IGluIGFyZ190dXBsZXMpKQogICAgICAgICAgICByZXN1bHQud3JpdGUoJyknKQogICAgICAgICAgICByZXN1bHRfc3RyID0gcmVzdWx0LmdldHZhbHVlKCkKCiAgICAgICAgICAgIHlpZWxkIHJlc3VsdF9zdHIKCiAgICAgICAgICAgIG5vbmxpdGVyYWxzID0gW10gICMgKGV2YWx1YXRlZF9hcmcsIHJlc3VsdF9zdHIsIHN0YXJ0LCBsaW1pdCkKICAgICAgICAgICAgZm9yIF8sIGV2YWx1YXRlZF9hcmcsIHN0YXJ0LCBsaW1pdCBpbiBhcmdfdHVwbGVzOgogICAgICAgICAgICAgICAgaWYgbm90IGlzX2xpdGVyYWwocmVzdWx0X3N0cltzdGFydDpsaW1pdF0pOgogICAgICAgICAgICAgICAgICAgIG5vbmxpdGVyYWxzLmFwcGVuZCgoZXZhbHVhdGVkX2FyZywgcmVzdWx0X3N0cltzdGFydDpsaW1pdF0sIHN0YXJ0LCBsaW1pdCkpCgogICAgICAgICAgICB1bmRlcmxpbmVzID0gaW8uU3RyaW5nSU8oKQogICAgICAgICAgICBwb3MgPSAwCiAgICAgICAgICAgIGZvciBfLCBfLCBzdGFydCwgbGltaXQgaW4gbm9ubGl0ZXJhbHM6CiAgICAgICAgICAgICAgICBpZiAobGltaXQgLSBzdGFydCkgPCAzOgogICAgICAgICAgICAgICAgICAgIHBvcyArPSB1bmRlcmxpbmVzLndyaXRlKCcgJyAqIChzdGFydCAtIHBvcykpCiAgICAgICAgICAgICAgICAgICAgcG9zICs9IHVuZGVybGluZXMud3JpdGUoJ+KGkScpCiAgICAgICAgICAgICAgICAgICAgcG9zICs9IHVuZGVybGluZXMud3JpdGUoJ+KGkScgKiAobGltaXQgLSBwb3MpKQogICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlCiAgICAgICAgICAgICAgICBpZHggPSBzdGFydCArIChsaW1pdCAtIHN0YXJ0KSAvLyAyCiAgICAgICAgICAgICAgICBwb3MgKz0gdW5kZXJsaW5lcy53cml0ZSgnICcgKiAoc3RhcnQgLSBwb3MpKQogICAgICAgICAgICAgICAgI3BvcyArPSB1bmRlcmxpbmVzLndyaXRlKCfilZknKQogICAgICAgICAgICAgICAgcG9zICs9IHVuZGVybGluZXMud3JpdGUoJ+KGkScgKiAoaWR4IC0gcG9zKSkKICAgICAgICAgICAgICAgIHBvcyArPSB1bmRlcmxpbmVzLndyaXRlKCfihpEnKQogICAgICAgICAgICAgICAgcG9zICs9IHVuZGVybGluZXMud3JpdGUoJ+KGkScgKiAobGltaXQgLSBwb3MpKQogICAgICAgICAgICAgICAgI3BvcyArPSB1bmRlcmxpbmVzLndyaXRlKCfilZwnKQogICAgICAgICAgICB5aWVsZCB1bmRlcmxpbmVzLmdldHZhbHVlKCkKCiAgICAgICAgICAgIGRlZiBtYWtlX2JhcnNfYnVmKG5vbmxpdGVyYWxzLCBlbmQsIGV2YWxlZCk6CiAgICAgICAgICAgICAgICBidWYgPSBpby5TdHJpbmdJTygpCiAgICAgICAgICAgICAgICBwb3MgPSAwCiAgICAgICAgICAgICAgICBmb3IgaSBpbiByYW5nZShsZW4obm9ubGl0ZXJhbHMpIC0gMSk6CiAgICAgICAgICAgICAgICAgICAgXywgXywgc3RhcnQsIGxpbWl0ID0gbm9ubGl0ZXJhbHNbaV0KICAgICAgICAgICAgICAgICAgICBpZiAobGltaXQgLSBzdGFydCkgPCAzOgogICAgICAgICAgICAgICAgICAgICAgICBpZHggPSBzdGFydAogICAgICAgICAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICAgICAgICAgIGlkeCA9IHN0YXJ0ICsgKGxpbWl0IC0gc3RhcnQpIC8vIDIKICAgICAgICAgICAgICAgICAgICBwb3MgKz0gYnVmLndyaXRlKCcgJyAqIChpZHggLSBwb3MpKQogICAgICAgICAgICAgICAgICAgIHBvcyArPSBidWYud3JpdGUoJ+KUgicpCiAgICAgICAgICAgICAgICAgICAgcG9zICs9IGJ1Zi53cml0ZSgnICcgKiAobGltaXQgLSBwb3MpKQoKICAgICAgICAgICAgICAgIF8sIHJlc3VsdF9zdHIsIHN0YXJ0LCBsaW1pdCA9IG5vbmxpdGVyYWxzWy0xXQogICAgICAgICAgICAgICAgaWYgKGxpbWl0IC0gc3RhcnQpIDwgMzoKICAgICAgICAgICAgICAgICAgICBpZHggPSBzdGFydAogICAgICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgICAgICBpZHggPSBzdGFydCArIChsaW1pdCAtIHN0YXJ0KSAvLyAyICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgcG9zICs9IGJ1Zi53cml0ZSgnICcgKiAoaWR4IC0gcG9zKSkKICAgICAgICAgICAgICAgIHBvcyArPSBidWYud3JpdGUoJ+KUlCcpCiAgICAgICAgICAgICAgICBwb3MgKz0gYnVmLndyaXRlKCfilIAnICogKGVuZCAtIDEgLSBwb3MpKQogICAgICAgICAgICAgICAgcG9zICs9IGJ1Zi53cml0ZSgn4pW0JykKICAgICAgICAgICAgICAgIHBvcyArPSBidWYud3JpdGUocmVzdWx0X3N0cikKICAgICAgICAgICAgICAgIHBvcyArPSBidWYud3JpdGUoJyDiiZQgJykKICAgICAgICAgICAgICAgIHBvcyArPSBidWYud3JpdGUoc3RyKGV2YWxlZCkpCgogICAgICAgICAgICAgICAgcmV0dXJuIGJ1ZiwgcG9zCgogICAgICAgICAgICB3aGlsZSBub25saXRlcmFsczoKICAgICAgICAgICAgICAgIGJ1ZiwgcG9zID0gbWFrZV9iYXJzX2J1Zihub25saXRlcmFscywgbGVuKHJlc3VsdF9zdHIpICsgNCwgbm9ubGl0ZXJhbHNbLTFdWzBdKQogICAgICAgICAgICAgICAgeWllbGQgYnVmLmdldHZhbHVlKCkKICAgICAgICAgICAgICAgIGxhc3QgPSBub25saXRlcmFscy5wb3AoKQoKICAgIGRlZiBhc3NlcnRfZXF1YWwoKiwgd2FudCwgZ290LCBvdXQ9c3lzLnN0ZG91dCk6CiAgICAgICAgaWYgd2FudCA9PSBnb3Q6CiAgICAgICAgICAgIHByaW50KCJUZXN0IGNhc2UgcGFzc2VkLiIpCiAgICAgICAgICAgIHJldHVybgoKICAgICAgICBmcmFtZSA9IGluc3BlY3QuY3VycmVudGZyYW1lKCkuZl9iYWNrCgogICAgICAgIGJveF9wYWRkaW5nID0gMgogICAgICAgIGhlYWRlciA9ICIgVGVzdCBjYXNlIGZhaWxlZC4gIgogICAgICAgIHdhbnRfbGluZSA9IGYie2JveF9wYWRkaW5nICogJyAnfVdhbnQ6IHtyZXByKHdhbnQpfSAodHlwZToge3R5cGUod2FudCkuX19uYW1lX199KSIKICAgICAgICBnb3RfbGluZSA9IGYie2JveF9wYWRkaW5nICogJyAnfUdvdDogIHtyZXByKGdvdCl9ICh0eXBlOiB7dHlwZShnb3QpLl9fbmFtZV9ffSkiCiAgICAgICAgCiAgICAgICAgaWYgY2FuX2Fubm90YXRlKGZyYW1lKToKICAgICAgICAgICAgYXNzZXJ0X2xpbmUgPSBmIntib3hfcGFkZGluZyAqICcgJ30+Pj4ge2FzdC51bnBhcnNlKGdldF9hc3NlcnRfbGluZShmcmFtZSkpfSIKICAgICAgICBlbHNlOgogICAgICAgICAgICBhc3NlcnRfbGluZSA9ICIiCiAgICAgICAgICAgIAogICAgICAgIGRlYnVnX2xpbmVzID0gbGlzdChhbm5vdGF0ZV9jYWxsKGZyYW1lKSkKICAgICAgICBpZiBkZWJ1Z19saW5lczoKICAgICAgICAgICAgZ290X2xpbmUgKz0gIiDihpAgIgogICAgICAgICAgICBwYWRkaW5nID0gbGVuKGdvdF9saW5lKQogICAgICAgICAgICBnb3RfbGluZSArPSBkZWJ1Z19saW5lc1swXQoKICAgICAgICBwYWRkZWRfZGVidWdfbGluZXMgPSBbXQogICAgICAgIGZvciBpLCBsaW5lIGluIGVudW1lcmF0ZShkZWJ1Z19saW5lcyk6CiAgICAgICAgICAgICAgICBpZiBpID09IDA6CiAgICAgICAgICAgICAgICAgICAgY29udGludWUKICAgICAgICAgICAgICAgIHBhZGRlZF9kZWJ1Z19saW5lcy5hcHBlbmQoJyAnICogcGFkZGluZyArIGxpbmUpCiAgICAgICAgICAgICAgICAKICAgICAgICBsaW5lX21heF9sZW4gPSBtYXgobGVuKGwpICsgYm94X3BhZGRpbmcgZm9yIGwgaW4gKGFzc2VydF9saW5lLCB3YW50X2xpbmUsIGdvdF9saW5lLCAqcGFkZGVkX2RlYnVnX2xpbmVzKSkKICAgICAgICBsaW5lX21heF9sZW4gPSBtYXgoMzIsIGxpbmVfbWF4X2xlbikKICAgICAgICBoZWFkZXJfZGFzaGVzID0gbGluZV9tYXhfbGVuIC0gbGVuKGhlYWRlcikKCgogICAgICAgIHByaW50KGZpbGU9b3V0KQogICAgICAgIHByaW50KCctJyAqIChoZWFkZXJfZGFzaGVzIC8vIDIpLCBlbmQ9IiIsIGZpbGU9b3V0KQogICAgICAgIHByaW50KGhlYWRlciwgZW5kPSIiLCBmaWxlPW91dCkKICAgICAgICBwcmludCgnLScgKiAoKGhlYWRlcl9kYXNoZXMgKyAxKSAvLyAyKSwgZW5kPSIiLCBmaWxlPW91dCkKICAgICAgICBwcmludChmaWxlPW91dCkKICAgICAgICBwcmludChmaWxlPW91dCkKCiAgICAgICAgCiAgICAgICAgaWYgYXNzZXJ0X2xpbmU6CiAgICAgICAgICAgIHByaW50KGFzc2VydF9saW5lLCBmaWxlPW91dCkKICAgICAgICAgICAgcHJpbnQoZmlsZT1vdXQpCgogICAgICAgIHByaW50KHdhbnRfbGluZSwgZmlsZT1vdXQpCiAgICAgICAgcHJpbnQoZ290X2xpbmUsIGZpbGU9b3V0KQogICAgICAgIGZvciBsaW5lIGluIHBhZGRlZF9kZWJ1Z19saW5lczoKICAgICAgICAgICAgcHJpbnQobGluZSwgZmlsZT1vdXQpCiAgICAgICAgCiAgICAgICAgcHJpbnQoZmlsZT1vdXQpCiAgICAgICAgcHJpbnQoJy0nICogbGluZV9tYXhfbGVuLCBmaWxlPW91dCkKICAgICAgICBwcmludChmaWxlPW91dCkKICAgICAgICAKICAgIERFQlVHR0FCTEVfQVJHUyA9ICJfZGVidWdnYWJsZV9hcmdzIgogICAgREVCVUdHQUJMRV9LV0FSR1MgPSAiX2RlYnVnZ2FibGVfa3dhcmdzIgoKICAgIGRlZiBkZWJ1Z2dhYmxlKGYpOgogICAgICAgIEBmdW5jdG9vbHMud3JhcHMoZikKICAgICAgICBkZWYgZygqYXJncywgKiprd2FyZ3MpOgogICAgICAgICAgICB0cnk6CiAgICAgICAgICAgICAgICBhcmdzX2NvcHkgPSBjb3B5LmRlZXBjb3B5KGFyZ3MpCiAgICAgICAgICAgICAgICBrd2FyZ3NfY29weSA9IGNvcHkuZGVlcGNvcHkoa3dhcmdzKQogICAgICAgICAgICBleGNlcHQgRXhjZXB0aW9uOgogICAgICAgICAgICAgICAgYXJnc19jb3B5ID0gTm9uZQogICAgICAgICAgICAgICAga3dhcmdzX2NvcHkgPSBOb25lCiAgICAgICAgICAgIHJlc3VsdCA9IGYoKmFyZ3MsICoqa3dhcmdzKQogICAgICAgICAgICBzZXRhdHRyKGcsIERFQlVHR0FCTEVfQVJHUywgYXJnc19jb3B5KQogICAgICAgICAgICBzZXRhdHRyKGcsIERFQlVHR0FCTEVfS1dBUkdTLCBrd2FyZ3NfY29weSkKICAgICAgICAgICAgcmV0dXJuIHJlc3VsdAogICAgICAgIHJldHVybiBnCiAgICAKICAgIHJldHVybiBhc3NlcnRfZXF1YWwsIGRlYnVnZ2FibGUKCmFzc2VydF9lcXVhbCwgZGVidWdnYWJsZSA9IG1ha2VfcHJldHR5X2Fzc2VydCgpCg==",
)
for code in CODE:
exec(base64.b64decode(code), globals, locals)
f(globals(), locals())
del f
def uh(b64):
return eval(base64.b64decode(b64))
def h(code):
return base64.b64encode(code)
def sae(*, want, got):
assert_equal(want=sorted(want), got=sorted(got))
Day 17, Lab B: Dijkstra's Algorithm¶
1 Dijkstra's Algorithm¶
Dijkstra's algorithm finds the shortest path between a given source node and all the other nodes in a graph. Thus, it allows us to find the shortest path between any two nodes.
Edges connecting the nodes in a graph are weighted with a number. The weights can represent the "cost" to travel between the two nodes via that edge.
For example, to get from UWI Mona to Downtown Kingston, there are many paths. UWI Mona and Downtown Kingston are nodes in a graph. The different streets are edges. Each street might take a different amount of time, so the weight of the edges in the graph represent time in this example. Shortest path algorithms like Dijkstra's Algorithm helps us to find the fastest path to get from UWI Mona to Downtown Kingston.
1.1 Algorithm Overview¶
Dijkstra's works by visiting nodes in increasing order of their distance from the source node. Dijkstra's repeatedly visits the unvisited node with the smallest distance from the shortest node. When Dijkstra's visits a node $u$, it inspects all its neighbors $v$ to see if a new shortest path to $v$ can be discovered using the edge from $u \to v$.
After visiting all nodes, Dijkstra's returns the dist dictionary, which contains the distance (length of the shortest path) from the source node to all other nodes.
1.2 An Example¶
For example, in the following weighted undirected graph, we have five nodes: $A$, $B$, $C$, $D$, and $E$. Let's see how we can use Dijkstra's algorithm to find the distances and shortest paths from node $A$ to all other nodes.
First, we initialize the distance from $A$ to all other nodes to $\infty$, and the distance from $A$ to itself to $0$. As Dijkstra's traverses the graph, these distances will converge to their true values. We also set all nodes to unvisited.
| Node | Distance | Visited |
|---|---|---|
| $A$ | $0$ | False |
| $B$ | $\infty$ | False |
| $C$ | $\infty$ | False |
| $D$ | $\infty$ | False |
| $E$ | $\infty$ | False |
Now, we start traversing the graph by visiting the closest (by distance) unvisited node. Looking at the table of distances, that node is node $A$:
| Node | Distance | Visited |
|---|---|---|
| $A$ | $0$ | False |
| $B$ | $\infty$ | False |
| $C$ | $\infty$ | False |
| $D$ | $\infty$ | False |
| $E$ | $\infty$ | False |
First, we set $A$ to visited:
| Node | Distance | Visited |
|---|---|---|
| $A$ | $0$ | True |
| $B$ | $\infty$ | False |
| $C$ | $\infty$ | False |
| $D$ | $\infty$ | False |
| $E$ | $\infty$ | False |
Next, we look at all of $A$'s neighbors and see whether we have discovered a new shortest path to that neighbor. $A$ has two neighbors, $B$, and $D$.
- Edge $A \to B$: We know the shortest path to $A$ has $0$ distance (by looking up that distance in the distance dictionary). The edge $A \to B$ has length $6$, so there exists a path from the source node $A$ to $B$ with length $6 = 0 \text{ (distance from $A$)} + 6 \text{ (length of edge $A \to B$)}$. This is shorter than the current known distance from $A$ to $B$, $\infty$ (again looking up in the distance table). So we can set the distance to $B$ to $6$.
- Edge $A \to D$. By the same logic as above, there must exist a path from $A$ to $D$ with length $1$. Since $1 < \infty$ (the current distance for $D$), so we can update the distance to $D$ to $1$ as well.
After the above distance updates, the new distance and visited table looks like:
| Node | Distance | Visited |
|---|---|---|
| $A$ | $0$ | True |
| $B$ | $6$ | False |
| $C$ | $\infty$ | False |
| $D$ | $1$ | False |
| $E$ | $\infty$ | False |
Here's our distance and visited table on the second iteration of Dijkstra's:
| Node | Distance | Visited |
|---|---|---|
| $A$ | $0$ | True |
| $B$ | $6$ | False |
| $C$ | $\infty$ | False |
| $D$ | $1$ | False |
| $E$ | $\infty$ | False |
Next, the unvisited node with the shortest distance from the source node is $D$ with distance $1$. Thus, we visit $D$:
| Node | Distance | Visited |
|---|---|---|
| $A$ | $0$ | True |
| $B$ | $6$ | False |
| $C$ | $\infty$ | False |
| $D$ | $1$ | True |
| $E$ | $\infty$ | False |
Next, we consider $D$'s neighbors. $D$ has three neighbors: $A$, $B$, and $E$.
- Edge $D \to A$: This edge has weight $1$. We know that there is a path from $A$ to $D$ with length $1$ (because that is $D$'s distance in the distance table). Then there must be a path from $A$ to $A$ with length $2 = 1 + 1$. But $2$ is larger than the distance already stored in the table (which again is the length of the shortest path), so we don't update $A$'s distance in the table.
- Edge $D \to B$: This edge has weight $2$. That means that there must be a path from $A$ to $B$ through $D$ with length $3 = 1 + 2$. This is better than the distance to $B$ stored in the above table ($3 < 6$), so we update $B$'s distance in the table again.
- Edge $D \to E$. This edge has weight $1$. That means that there must be a path from $A$ to $E$ through $D$ with length $2 = 1 + 1$. This is better than the length of the current best path to $E$, $\infty$, so we also update $E$'s distance in the table.
Our new table looks like
| Node | Distance | Visited |
|---|---|---|
| $A$ | $0$ | True |
| $B$ | $3$ | False |
| $C$ | $\infty$ | False |
| $D$ | $1$ | True |
| $E$ | $2$ | False |
On the start of our third iteration of Dijkstra's, our table looks like
| Node | Distance | Visited |
|---|---|---|
| $A$ | $0$ | True |
| $B$ | $3$ | False |
| $C$ | $\infty$ | False |
| $D$ | $1$ | True |
| $E$ | $2$ | False |
What is the next closest unvisited node?
If you answered $E$, you're correct. We visit $E$ and consider all its neighbors:
- Edge $E \to B$: weight $2$. The distance from $A$ to $E$ is $2$, so there exists a path from $A$ to $B$ through $E$ with length $4 = \text{dist}[E] + 2 = 2 + 2$. But $4$ is not smaller than the shortest distance to $B$ in our table ($3$), so we do not update this distance in the table.
- Edge $E \to C$: weight $5$. This means there is a path from $A$ to $C$ through $E$ with length $7 = \text{dist}[E] + 5 = 2 + 5$. Since $7$ is better than our current distance from $A$ to $C$, we update it in the table.
- Edge $E \to D$: weight $1$. This means there is a path from $A$ to $D$ through $E$ with length $3$. But this is no better than our current best distance from $A$ to $D$ of length $1$, so we don't update $D$'s distance in the table.
Now, our distance table looks like:
| Node | Distance | Visited |
|---|---|---|
| $A$ | $0$ | True |
| $B$ | $3$ | False |
| $C$ | $7$ | False |
| $D$ | $1$ | True |
| $E$ | $2$ | True |
Next, we visit the next closest unvisited node, $B$. Think through what happens at this step. After we visit $B$, our table looks like
| Node | Distance | Visited |
|---|---|---|
| $A$ | $0$ | True |
| $B$ | $3$ | True |
| $C$ | $7$ | False |
| $D$ | $1$ | True |
| $E$ | $2$ | True |
Finally, the only unvisited node is C. We update our table with the same logic above. (We've omitted it for brevity; try working through the logic yourself.)
| Node | Distance | Visited |
|---|---|---|
| $A$ | $0$ | True |
| $B$ | $3$ | True |
| $C$ | $7$ | True |
| $D$ | $1$ | True |
| $E$ | $2$ | True |
Thus, the distance from $A$ to all nodes is stored in the above table.
1.2 Graph, with weights¶
We reimplemented the class Graph from yesterday afternoon's lab. We want to make our graphs weighted so that we will do our Dijkstra's algorithm on them.
We've modified the functions to handle the added weights to the edges. In addition, there's a new get_edge_weight function.
Take a moment to look at the implementation and notice the difference from yesterday's lab.
In [ ]:
class Graph:
"""Represents a graph consisting of nodes and edges."""
def __init__(self):
"""Initializes an empty graph."""
# Neighbors maps a node to its neighbors.
self.neighbors = {}
# Weights maps a edge represented as a node tuple (e.g. ("A", "B"))
# to the weight of that edge.
self.weights = {}
def add_node(self, node_label):
"""Adds a node to the graph.
The node is associated with a string node_label which is used to add
edges to it later. If a node associated with node_label already exists,
does nothing.
Arguments:
node_label (string).
Effects: Modifies the graph. If the node already exists, does nothing.
"""
# First, check if a node associated with node_label already exists
# Hint: The expression "k in dict" is True if dict has a key called 'k' (else False).
# If the node doesn't already exist, add it by initializing an empty adjacency list []
if not node_label in self.neighbors:
self.neighbors[node_label] = []
def add_edge(self, node1, node2, weight):
"""Connects node1 and node2 with an edge.
Arguments:
node1 (string): Label of the first node
node2 (string): Label of the second node.
Effects:
Modifies the graph by adding an edge from node1 to node2. If an edge
already exists, does nothing.
"""
# First, check if the nodes are already connected
# Hint: The expression "x in list" is True if list contains the element 'x' (else False).
# If they aren't already connected, connect them by adding each to the other's adjacency list.
if not node2 in self.neighbors[node1] and not node1 in self.neighbors[node2]:
self.neighbors[node1] += [node2]
self.neighbors[node2] += [node1]
self.weights[(node1, node2)] = weight
self.weights[(node2, node1)] = weight
def get_nodes(self):
"""Returns a list of all nodes in the graph.
Returns: (list[str]): Labels of all nodes in the graph.
"""
return list(self.neighbors.keys())
def get_neighbors(self, node):
"""Returns list of neighbors of node.
Arguments:
node (str): The node whose neighbors to retrieve.
Returns (list[str]): A list of that node's neighbors.
"""
return self.neighbors[node]
def get_edge_weight(self, node1, node2) :
"""Returns the weight of the edge connecting node1 and node2.
Arguments:
node1 (str): The first node in the edge.
node2 (str): The second node in the edge.
Returns: int or None.
"""
edge = (node1, node2)
if edge in self.weights:
return self.weights[edge]
return None
def draw(self):
"""Prints a visual representation of the graph.
Effects: Prints the graph as output.
"""
# Create set of edges
# Create nx graph
g = nx.Graph()
for node in self.get_nodes():
g.add_node(node)
for (u, v), weight in self.weights.items():
if u > v:
continue
g.add_edge(u, v, weight=weight)
pos = nx.nx_agraph.graphviz_layout(g, prog="dot")
edge_labels = nx.get_edge_attributes(g, "weight")
nx.draw_networkx_nodes(g, pos)
nx.draw_networkx_labels(g, pos)
nx.draw_networkx_edges(g, pos)
nx.draw_networkx_edge_labels(g, pos, edge_labels)
graph = Graph()
graph.add_node("A")
graph.add_node("B")
graph.add_node("C")
graph.add_node("D")
graph.add_node("E")
graph.add_edge("A", "D", 1)
graph.add_edge("A", "B", 6)
graph.add_edge("D", "E", 1)
graph.add_edge("D", "B", 2)
graph.add_edge("E", "B", 2)
graph.add_edge("E", "C", 5)
graph.add_edge("B", "C", 5)
graph.draw()
1.3 Some Help¶
To help you implement Dijkstra's, first implement the helper functions below.
In [ ]:
def initialize_visited(graph):
"""Initializes a visited dictionary.
The visited dictionary should map each node to whether it has been
visited or not. At the time of initialization, no nodes should be
marked as visited.
Arguments:
graph (Graph): The graph whose nodes are keys in this visited mapping.
Returns (dict[str, bool]):
A visited dictionary where no nodes are marked as visited
"""
visited = {}
# YOUR CODE HERE
want_visited = {
"A": False,
"B": False,
"C": False,
"D": False,
"E": False,
}
assert_equal(want=want_visited, got=initialize_visited(graph))
In [ ]:
def initialize_dist(graph, source):
"""Initializes the dist dictionary.
The dist dictionary should map each node in the graph to the length
of the shortest known path from the source to that node. At the
time of initialization, the length of the shortest known path to all
nodes should be infinite (float('inf')), except the length of the
shortest path to the source node itself, which should be 0.
Arguments:
graph (Graph): The graph whose nodes are keys in this distance mapping.
source: The source node.
Returns (dict[str, number]):
A dist dictionary where all nodes are infinite distance away, except the
source node, which is 0 distance away.
"""
dist = {}
# YOUR CODE HERE
want_dist = {
"A": 0,
"B": float('inf'),
"C": float('inf'),
"D": float('inf'),
"E": float('inf'),
}
assert_equal(want=want_dist, got=initialize_dist(graph, "A"))
In [ ]:
def find_closest_unvisited(visited, dist):
"""Finds the label of a unvisited node with a least distance.
If there are multiple unvisited nodes with the same distance, return
any one. If there are no unvisited nodes, return None.
Arguments:
visited (dict[str, bool]): A visited mapping.
dist (dict[str, number]): A dist mapping.
"""
# YOUR CODE HERE
visited = {
"A": True,
"B": False,
"C": False,
"D": True,
"E": True,
}
dist = {
"A": 0,
"B": 3,
"C": 7,
"D": 1,
"E": 2,
}
assert_equal(want="B", got=find_closest_unvisited(visited, dist))
1.4 Dijkstra's¶
Now, using the above functions and the Graph class, implement Dijkstra's algorithm.
In [ ]:
@debuggable
def dijkstra(graph, source) :
"""Computes the length of the shortest paths from the source node to all nodes.
Arguments:
graph (Graph): The input graph to find shortest paths.
source (str): The label of the source node.
Returns (dict[str, number]):
A mapping from node labels to the length of the shortest path from the source to
that node. If there is no path from the source to a node, its distance from the
source is infinite.
"""
visited = initialize_visited(graph)
dist = initialize_dist(graph, source)
current = ___________________________________ # YOUR CODE HERE
while current is not None:
# Mark the current node as visited.
_________________________ # YOUR CODE HERE
neighbors = _________________________ # YOUR CODE HERE
for neighbor in neighbors:
weight = _________________________ # YOUR CODE HERE
possible_path_length = _________________________ # YOUR CODE HERE
if _________________ < _________________: # YOUR CODE HERE
dist[neighbor] = _________________ # YOUR CODE HERE
current = ___________________________________ # YOUR CODE HERE
return dist
In [ ]:
graph1 = Graph()
graph1.add_node("A")
graph1.add_node("B")
graph1.add_node("C")
graph1.add_node("D")
graph1.add_node("E")
graph1.add_node("F") # Disconnected!
graph1.add_edge("A", "D", 1)
graph1.add_edge("A", "B", 6)
graph1.add_edge("D", "E", 1)
graph1.add_edge("D", "B", 2)
graph1.add_edge("E", "B", 2)
graph1.add_edge("E", "C", 5)
graph1.add_edge("B", "C", 5)
graph1.draw()
dists = dijkstra(graph1, "A")
assert_equal(want=0, got=dists["A"])
assert_equal(want=3, got=dists["B"])
assert_equal(want=7, got=dists["C"])
assert_equal(want=1, got=dists["D"])
assert_equal(want=2, got=dists["E"])
assert_equal(want=float('inf'), got=dists["F"])
In [ ]:
graph2 = Graph()
graph2.add_node("A")
graph2.add_node("B")
graph2.add_node("C")
graph2.add_node("D")
graph2.add_node("E")
graph2.add_edge("A", "B", 10)
graph2.add_edge("B", "C", 2)
graph2.add_edge("A", "C", 3)
graph2.add_edge("C", "D", 9)
graph2.add_edge("B", "D", 1)
graph2.draw()
distsA = dijkstra(graph2, "A")
assert_equal(want=0, got=distsA["A"])
assert_equal(want=5, got=distsA["B"])
assert_equal(want=3, got=distsA["C"])
assert_equal(want=6, got=distsA["D"])
assert_equal(want=float('inf'), got=distsA["E"])
distsB = dijkstra(graph2, "B")
assert_equal(want=5, got=distsB["A"])
assert_equal(want=0, got=distsB["B"])
assert_equal(want=2, got=distsB["C"])
assert_equal(want=1, got=distsB["D"])
assert_equal(want=float('inf'), got=distsB["E"])
In [ ]: