Skip to content

Instantly share code, notes, and snippets.

@linanqiu

linanqiu/Edge Contraction.ipynb

Created March 15, 2017 02:34
Show Gist options
  • Save linanqiu/8677f25afd0e16654300e71181c228ec to your computer and use it in GitHub Desktop.
Save linanqiu/8677f25afd0e16654300e71181c228ec to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
Edge Contraction.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from random import randint\n",
"from math import ceil, log, pow"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"file = open(\"hw4_graph.txt\", \"r\")\n",
"\n",
"node_list = file.readlines()"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"class Node:\n",
" def __init__(self, name):\n",
" self.name = name\n",
" self.edges = {}\n",
" \n",
" def add_edge(self, n):\n",
" self.edges[n.name] = n\n",
" n.edges[self.name] = self\n",
" \n",
" def remove_edge(self, n):\n",
" self.edges.pop(n.name)\n",
" n.edges.pop(self.name)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"input_data_raw = [line.strip().split('\\t') for line in node_list]"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def construct_name_table(input_data_raw):\n",
" names_table = {}\n",
"\n",
" for line in input_data_raw:\n",
" source_name = line[0]\n",
" if source_name not in names_table:\n",
" names_table[source_name] = Node(source_name)\n",
" for target_name in line[1:]:\n",
" if target_name not in names_table:\n",
" names_table[target_name] = Node(target_name)\n",
" # don't have to add_source for names_table[target_name] because \n",
" # the defs for Node takes care of this for us\n",
" names_table[source_name].add_edge(names_table[target_name])\n",
" \n",
" return names_table"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"names_table = construct_name_table(input_data_raw)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's try contracting node 1 and node 79. First, let's check what each of those nodes are currently connected to"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"{'100': <__main__.Node at 0x111506400>,\n",
" '113': <__main__.Node at 0x111506198>,\n",
" '140': <__main__.Node at 0x1115062b0>,\n",
" '15': <__main__.Node at 0x1115061d0>,\n",
" '155': <__main__.Node at 0x1115060b8>,\n",
" '160': <__main__.Node at 0x111506358>,\n",
" '164': <__main__.Node at 0x111506080>,\n",
" '175': <__main__.Node at 0x111506278>,\n",
" '18': <__main__.Node at 0x111506208>,\n",
" '191': <__main__.Node at 0x1115063c8>,\n",
" '196': <__main__.Node at 0x111506518>,\n",
" '198': <__main__.Node at 0x1115064e0>,\n",
" '20': <__main__.Node at 0x111506470>,\n",
" '200': <__main__.Node at 0x1115062e8>,\n",
" '32': <__main__.Node at 0x1115060f0>,\n",
" '37': <__main__.Node at 0x111502fd0>,\n",
" '39': <__main__.Node at 0x111506160>,\n",
" '4': <__main__.Node at 0x111506320>,\n",
" '69': <__main__.Node at 0x1115064a8>,\n",
" '78': <__main__.Node at 0x111506240>,\n",
" '79': <__main__.Node at 0x111506048>,\n",
" '87': <__main__.Node at 0x111506128>,\n",
" '91': <__main__.Node at 0x111506438>,\n",
" '97': <__main__.Node at 0x111506390>}"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"names_table['1'].edges"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"{'1': <__main__.Node at 0x111502f60>,\n",
" '102': <__main__.Node at 0x1115074a8>,\n",
" '108': <__main__.Node at 0x1115027f0>,\n",
" '112': <__main__.Node at 0x1115075c0>,\n",
" '118': <__main__.Node at 0x111506f98>,\n",
" '122': <__main__.Node at 0x111502898>,\n",
" '135': <__main__.Node at 0x111507630>,\n",
" '139': <__main__.Node at 0x110f81e10>,\n",
" '144': <__main__.Node at 0x1115022b0>,\n",
" '145': <__main__.Node at 0x1115075f8>,\n",
" '158': <__main__.Node at 0x111507048>,\n",
" '163': <__main__.Node at 0x1115029b0>,\n",
" '164': <__main__.Node at 0x111506080>,\n",
" '172': <__main__.Node at 0x111507ac8>,\n",
" '175': <__main__.Node at 0x111506278>,\n",
" '198': <__main__.Node at 0x1115064e0>,\n",
" '20': <__main__.Node at 0x111506470>,\n",
" '200': <__main__.Node at 0x1115062e8>,\n",
" '25': <__main__.Node at 0x1115022e8>,\n",
" '35': <__main__.Node at 0x111507390>,\n",
" '37': <__main__.Node at 0x111502fd0>,\n",
" '40': <__main__.Node at 0x110f81da0>,\n",
" '42': <__main__.Node at 0x111507128>,\n",
" '56': <__main__.Node at 0x111502198>,\n",
" '57': <__main__.Node at 0x111507780>,\n",
" '62': <__main__.Node at 0x111502668>,\n",
" '68': <__main__.Node at 0x110f81ef0>,\n",
" '7': <__main__.Node at 0x111502160>,\n",
" '71': <__main__.Node at 0x1115026a0>,\n",
" '75': <__main__.Node at 0x111507588>,\n",
" '80': <__main__.Node at 0x1115072e8>,\n",
" '86': <__main__.Node at 0x111507cc0>}"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"names_table['79'].edges"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Contracting 1 and 79 should mean that all the edges that point to 1 and 79 should now point to (1+79). Since edges are bidrectional, edges that point to 1 and 79 are the edges that point from 1 and 79."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"['100',\n",
" '102',\n",
" '108',\n",
" '112',\n",
" '113',\n",
" '118',\n",
" '122',\n",
" '135',\n",
" '139',\n",
" '140',\n",
" '144',\n",
" '145',\n",
" '15',\n",
" '155',\n",
" '158',\n",
" '160',\n",
" '163',\n",
" '164',\n",
" '172',\n",
" '175',\n",
" '18',\n",
" '191',\n",
" '196',\n",
" '198',\n",
" '20',\n",
" '200',\n",
" '25',\n",
" '32',\n",
" '35',\n",
" '37',\n",
" '39',\n",
" '4',\n",
" '40',\n",
" '42',\n",
" '56',\n",
" '57',\n",
" '62',\n",
" '68',\n",
" '69',\n",
" '7',\n",
" '71',\n",
" '75',\n",
" '78',\n",
" '80',\n",
" '86',\n",
" '87',\n",
" '91',\n",
" '97']"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"test_result_expected = sorted(set([n for n in names_table['1'].edges] + [n for n in names_table['79'].edges]))\n",
"test_result_expected.remove('1')\n",
"test_result_expected.remove('79')\n",
"test_result_expected"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def contract_nodes(names_table, n, m):\n",
" nm = Node('(%s+%s)' % (n.name, m.name))\n",
" n_edges = [node for node in n.edges.values()]\n",
" for node in n_edges:\n",
" if node.name != m.name:\n",
" node.remove_edge(n)\n",
" node.add_edge(nm)\n",
" m_edges = [node for node in m.edges.values()]\n",
" for node in m_edges:\n",
" if node.name != n.name:\n",
" node.remove_edge(m)\n",
" node.add_edge(nm)\n",
" names_table.pop(n.name)\n",
" names_table.pop(m.name)\n",
" names_table[nm.name] = nm"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"test_names_table = construct_name_table(input_data_raw)\n",
"contract_nodes(test_names_table, test_names_table['1'], test_names_table['79'])"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"{'(1+79)': <__main__.Node at 0x111512198>,\n",
" '10': <__main__.Node at 0x111512b38>,\n",
" '100': <__main__.Node at 0x111512e48>,\n",
" '101': <__main__.Node at 0x111512908>,\n",
" '102': <__main__.Node at 0x11151f9e8>,\n",
" '103': <__main__.Node at 0x111512dd8>,\n",
" '104': <__main__.Node at 0x11151f2b0>,\n",
" '105': <__main__.Node at 0x11151cf28>,\n",
" '106': <__main__.Node at 0x11151cc50>,\n",
" '107': <__main__.Node at 0x11151f3c8>,\n",
" '108': <__main__.Node at 0x11151ffd0>,\n",
" '109': <__main__.Node at 0x111502e80>,\n",
" '11': <__main__.Node at 0x11151fe10>,\n",
" '110': <__main__.Node at 0x11151c860>,\n",
" '111': <__main__.Node at 0x11151c7f0>,\n",
" '112': <__main__.Node at 0x11151fb00>,\n",
" '113': <__main__.Node at 0x111512c18>,\n",
" '114': <__main__.Node at 0x11151f198>,\n",
" '115': <__main__.Node at 0x11151c278>,\n",
" '116': <__main__.Node at 0x111512c88>,\n",
" '117': <__main__.Node at 0x1115129e8>,\n",
" '118': <__main__.Node at 0x11151f438>,\n",
" '119': <__main__.Node at 0x11151fa58>,\n",
" '12': <__main__.Node at 0x111512a90>,\n",
" '120': <__main__.Node at 0x11151fc88>,\n",
" '121': <__main__.Node at 0x11151f748>,\n",
" '122': <__main__.Node at 0x11151c208>,\n",
" '123': <__main__.Node at 0x111512c50>,\n",
" '124': <__main__.Node at 0x11151fa20>,\n",
" '125': <__main__.Node at 0x11151f320>,\n",
" '126': <__main__.Node at 0x11151ce10>,\n",
" '127': <__main__.Node at 0x11151f6d8>,\n",
" '128': <__main__.Node at 0x111502eb8>,\n",
" '129': <__main__.Node at 0x11151cba8>,\n",
" '13': <__main__.Node at 0x111512898>,\n",
" '130': <__main__.Node at 0x11151f550>,\n",
" '131': <__main__.Node at 0x11151fcc0>,\n",
" '132': <__main__.Node at 0x11151c198>,\n",
" '133': <__main__.Node at 0x11151c0b8>,\n",
" '134': <__main__.Node at 0x111512d30>,\n",
" '135': <__main__.Node at 0x11151fb70>,\n",
" '136': <__main__.Node at 0x111502d30>,\n",
" '137': <__main__.Node at 0x11151c940>,\n",
" '138': <__main__.Node at 0x11151c898>,\n",
" '139': <__main__.Node at 0x11151c9b0>,\n",
" '14': <__main__.Node at 0x11151fcf8>,\n",
" '140': <__main__.Node at 0x1115126a0>,\n",
" '141': <__main__.Node at 0x111512978>,\n",
" '142': <__main__.Node at 0x11151c710>,\n",
" '143': <__main__.Node at 0x11151cf60>,\n",
" '144': <__main__.Node at 0x11151fd30>,\n",
" '145': <__main__.Node at 0x11151fb38>,\n",
" '146': <__main__.Node at 0x11151fba8>,\n",
" '147': <__main__.Node at 0x11151cbe0>,\n",
" '148': <__main__.Node at 0x11151c3c8>,\n",
" '149': <__main__.Node at 0x11151c9e8>,\n",
" '15': <__main__.Node at 0x1115125f8>,\n",
" '150': <__main__.Node at 0x11151f860>,\n",
" '151': <__main__.Node at 0x11151cdd8>,\n",
" '152': <__main__.Node at 0x11151c8d0>,\n",
" '153': <__main__.Node at 0x11151f160>,\n",
" '154': <__main__.Node at 0x111512438>,\n",
" '155': <__main__.Node at 0x111512a20>,\n",
" '156': <__main__.Node at 0x11151f9b0>,\n",
" '157': <__main__.Node at 0x11151f0b8>,\n",
" '158': <__main__.Node at 0x11151f358>,\n",
" '159': <__main__.Node at 0x1115024e0>,\n",
" '16': <__main__.Node at 0x111502d68>,\n",
" '160': <__main__.Node at 0x111512d68>,\n",
" '161': <__main__.Node at 0x11151c320>,\n",
" '162': <__main__.Node at 0x111502be0>,\n",
" '163': <__main__.Node at 0x11151c400>,\n",
" '164': <__main__.Node at 0x111512860>,\n",
" '165': <__main__.Node at 0x11151c7b8>,\n",
" '166': <__main__.Node at 0x11151fda0>,\n",
" '167': <__main__.Node at 0x11151cc88>,\n",
" '168': <__main__.Node at 0x111523080>,\n",
" '169': <__main__.Node at 0x11151c6a0>,\n",
" '17': <__main__.Node at 0x111502dd8>,\n",
" '170': <__main__.Node at 0x11151c2e8>,\n",
" '171': <__main__.Node at 0x11151f2e8>,\n",
" '172': <__main__.Node at 0x11151ce80>,\n",
" '173': <__main__.Node at 0x11151f278>,\n",
" '174': <__main__.Node at 0x11151cac8>,\n",
" '175': <__main__.Node at 0x111512630>,\n",
" '176': <__main__.Node at 0x11151f048>,\n",
" '177': <__main__.Node at 0x111512ef0>,\n",
" '178': <__main__.Node at 0x11151fe80>,\n",
" '179': <__main__.Node at 0x111512f98>,\n",
" '18': <__main__.Node at 0x1115126d8>,\n",
" '180': <__main__.Node at 0x11151cc18>,\n",
" '181': <__main__.Node at 0x11151c780>,\n",
" '182': <__main__.Node at 0x111512be0>,\n",
" '183': <__main__.Node at 0x111523128>,\n",
" '184': <__main__.Node at 0x11151c2b0>,\n",
" '185': <__main__.Node at 0x11151fe48>,\n",
" '186': <__main__.Node at 0x111523160>,\n",
" '187': <__main__.Node at 0x11151cb70>,\n",
" '188': <__main__.Node at 0x11151ceb8>,\n",
" '189': <__main__.Node at 0x11151c358>,\n",
" '19': <__main__.Node at 0x11151fa90>,\n",
" '190': <__main__.Node at 0x11151f080>,\n",
" '191': <__main__.Node at 0x111512f60>,\n",
" '192': <__main__.Node at 0x11151c6d8>,\n",
" '193': <__main__.Node at 0x11151f6a0>,\n",
" '194': <__main__.Node at 0x11151f208>,\n",
" '195': <__main__.Node at 0x11151c1d0>,\n",
" '196': <__main__.Node at 0x111512fd0>,\n",
" '197': <__main__.Node at 0x11151cd30>,\n",
" '198': <__main__.Node at 0x111512e80>,\n",
" '199': <__main__.Node at 0x111523048>,\n",
" '2': <__main__.Node at 0x1115127f0>,\n",
" '20': <__main__.Node at 0x111512f28>,\n",
" '200': <__main__.Node at 0x111512588>,\n",
" '21': <__main__.Node at 0x11151c518>,\n",
" '22': <__main__.Node at 0x11151fef0>,\n",
" '23': <__main__.Node at 0x11151f908>,\n",
" '24': <__main__.Node at 0x11151c5f8>,\n",
" '25': <__main__.Node at 0x11151fd68>,\n",
" '26': <__main__.Node at 0x11151fdd8>,\n",
" '27': <__main__.Node at 0x11151feb8>,\n",
" '28': <__main__.Node at 0x11151c4a8>,\n",
" '29': <__main__.Node at 0x11151f588>,\n",
" '3': <__main__.Node at 0x1115128d0>,\n",
" '30': <__main__.Node at 0x111502c18>,\n",
" '31': <__main__.Node at 0x11151ff60>,\n",
" '32': <__main__.Node at 0x111512ac8>,\n",
" '33': <__main__.Node at 0x11151c668>,\n",
" '34': <__main__.Node at 0x11151ce48>,\n",
" '35': <__main__.Node at 0x11151f8d0>,\n",
" '36': <__main__.Node at 0x111512a58>,\n",
" '37': <__main__.Node at 0x1115129b0>,\n",
" '38': <__main__.Node at 0x11151c240>,\n",
" '39': <__main__.Node at 0x111512b70>,\n",
" '4': <__main__.Node at 0x1115125c0>,\n",
" '40': <__main__.Node at 0x11151c978>,\n",
" '41': <__main__.Node at 0x111502c88>,\n",
" '42': <__main__.Node at 0x11151f518>,\n",
" '43': <__main__.Node at 0x111512940>,\n",
" '44': <__main__.Node at 0x11151c748>,\n",
" '45': <__main__.Node at 0x11151ca90>,\n",
" '46': <__main__.Node at 0x11151c128>,\n",
" '47': <__main__.Node at 0x111512828>,\n",
" '48': <__main__.Node at 0x111502cc0>,\n",
" '49': <__main__.Node at 0x111502e10>,\n",
" '5': <__main__.Node at 0x111512e10>,\n",
" '50': <__main__.Node at 0x11151c390>,\n",
" '51': <__main__.Node at 0x111512ba8>,\n",
" '52': <__main__.Node at 0x11151fc50>,\n",
" '53': <__main__.Node at 0x11151c080>,\n",
" '54': <__main__.Node at 0x11151f240>,\n",
" '55': <__main__.Node at 0x11151f898>,\n",
" '56': <__main__.Node at 0x11151fc18>,\n",
" '57': <__main__.Node at 0x11151cb38>,\n",
" '58': <__main__.Node at 0x11151c908>,\n",
" '59': <__main__.Node at 0x11151ccc0>,\n",
" '6': <__main__.Node at 0x11151f978>,\n",
" '60': <__main__.Node at 0x11151f780>,\n",
" '61': <__main__.Node at 0x11151cf98>,\n",
" '62': <__main__.Node at 0x11151c160>,\n",
" '63': <__main__.Node at 0x11151cef0>,\n",
" '64': <__main__.Node at 0x11151c048>,\n",
" '65': <__main__.Node at 0x11151f1d0>,\n",
" '66': <__main__.Node at 0x11151f128>,\n",
" '67': <__main__.Node at 0x11151ca58>,\n",
" '68': <__main__.Node at 0x11151ca20>,\n",
" '69': <__main__.Node at 0x111512cf8>,\n",
" '7': <__main__.Node at 0x11151fbe0>,\n",
" '70': <__main__.Node at 0x11151f0f0>,\n",
" '71': <__main__.Node at 0x11151ff28>,\n",
" '72': <__main__.Node at 0x11151c828>,\n",
" '73': <__main__.Node at 0x11151f400>,\n",
" '74': <__main__.Node at 0x11151c5c0>,\n",
" '75': <__main__.Node at 0x11151fac8>,\n",
" '76': <__main__.Node at 0x11151f390>,\n",
" '77': <__main__.Node at 0x111512b00>,\n",
" '78': <__main__.Node at 0x1115127b8>,\n",
" '8': <__main__.Node at 0x11151ff98>,\n",
" '80': <__main__.Node at 0x11151f828>,\n",
" '81': <__main__.Node at 0x11151f7b8>,\n",
" '82': <__main__.Node at 0x11151c550>,\n",
" '83': <__main__.Node at 0x11151c4e0>,\n",
" '84': <__main__.Node at 0x11151f710>,\n",
" '85': <__main__.Node at 0x11151cb00>,\n",
" '86': <__main__.Node at 0x1115230b8>,\n",
" '87': <__main__.Node at 0x111512cc0>,\n",
" '88': <__main__.Node at 0x11151c588>,\n",
" '89': <__main__.Node at 0x11151cda0>,\n",
" '9': <__main__.Node at 0x11151c0f0>,\n",
" '90': <__main__.Node at 0x11151c438>,\n",
" '91': <__main__.Node at 0x111512da0>,\n",
" '92': <__main__.Node at 0x11151cfd0>,\n",
" '93': <__main__.Node at 0x11151f940>,\n",
" '94': <__main__.Node at 0x11151c630>,\n",
" '95': <__main__.Node at 0x11151ccf8>,\n",
" '96': <__main__.Node at 0x11151cd68>,\n",
" '97': <__main__.Node at 0x111512eb8>,\n",
" '98': <__main__.Node at 0x1115230f0>,\n",
" '99': <__main__.Node at 0x11151f7f0>}"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"test_names_table"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": false,
"scrolled": true
},
"outputs": [
{
"data": {
"text/plain": [
"['100',\n",
" '102',\n",
" '108',\n",
" '112',\n",
" '113',\n",
" '118',\n",
" '122',\n",
" '135',\n",
" '139',\n",
" '140',\n",
" '144',\n",
" '145',\n",
" '15',\n",
" '155',\n",
" '158',\n",
" '160',\n",
" '163',\n",
" '164',\n",
" '172',\n",
" '175',\n",
" '18',\n",
" '191',\n",
" '196',\n",
" '198',\n",
" '20',\n",
" '200',\n",
" '25',\n",
" '32',\n",
" '35',\n",
" '37',\n",
" '39',\n",
" '4',\n",
" '40',\n",
" '42',\n",
" '56',\n",
" '57',\n",
" '62',\n",
" '68',\n",
" '69',\n",
" '7',\n",
" '71',\n",
" '75',\n",
" '78',\n",
" '80',\n",
" '86',\n",
" '87',\n",
" '91',\n",
" '97']"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"test_result_actual = sorted(set([name for name in test_names_table['(1+79)'].edges]))\n",
"test_result_actual"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"test_result_expected == test_result_actual"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.5.1"
},
"widgets": {
"state": {},
"version": "1.1.1"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment