python - Randomized contraction algorithm for the Min Cuts in a graph -

-

i have tried write implementation of karger's algorithm solving min cut problem. here's code 

def randomvertices(g):      v1 = g.keys() [random.randint(0,len(g)-1)]     v2 = g[v1] [random.randint(0,len(g[v1])-1)]     return v1, v2   def mergevertices(g):     v1,v2 = randomvertices(g)      g[v1].extend(g[v2])      x in g[v2]:         l = g[x]         in range(0,len(l)):             if l[i] == v2:                  l[i] = v1              while v1 in g[v1]:         g[v1].remove(v1)      del g[v2]  def mincut(g):      while len(g) > 2:          mergevertices(g)     return len(g[g.keys()[0]])

it's not commented should pretty self-explanatory. 'g' dictionary keys vertices of graph, each values vertices connected to. randomvertices gives me edge want contract, while mergevertices updates dictionary (and hence graph) deleting second vertex, updating values of keys linked vertex, , getting rid of self-loops. looks okay me if run on test graph keyerror @ l = g[x] stage, , can't understand why happening. hoping of may able me. thanks.

edit: code fine, error in way loaded file adjacent list. cobarzan, thank pointing out i'm not picking edges uniformly.


Comments

Post a Comment

Popular posts from this blog

python - pip install -U PySide error -

-
does know how avoid following error when running pip install -u pyside per official website instructions here: https://pypi.python.org/pypi/pyside/#installing-pyside-on-a-mac-os-x-system note have done brew install qt successfully. you using pip version 7.0.3, version 7.1.2 available. should consider upgrading via 'pip install --upgrade pip' command. collecting pyside using cached pyside-1.2.4.tar.gz installing collected packages: pyside running setup.py install pyside complete output command /applications/anaconda/bin/python -c "import setuptools, tokenize;__file__='/private/var/folders/dy/ttgqhqqx3g9bsbsnqnxsk2z80000gq/t/pip-build-cpxemt/pyside/setup.py';exec(compile(getattr(tokenize, 'open', open)(__file__).read().replace('\r\n', '\n'), __file__, 'exec'))" install --record /var/folders/dy/ttgqhqqx3g9bsbsnqnxsk2z80000gq/t/pip-0r7hri-record/install-record.txt --single-version-externally-managed --compile: ...
Read more

arrays - C++ error: a brace-enclosed initializer is not allowed here before ‘{’ token -

-
simple question: i'm trying initialize array within c++ class declaration: using namespace std; #include <string> class myclass{ public: string myarray[] = {"a","b","c"}; }; and i'm getting error: error: brace-enclosed initializer not allowed here before ‘{’ token no, without complied c++11 compiler, cannot initialize member array in declaration. have initialize array member in constructor. , don't use open array if know number of elements initialize array.
Read more

cytoscape.js - How to add nodes to Dagre layout with Cytoscape -

-
i trying add nodes dagre graph through cityscape.js. problem nodes not painted. code have: cy.add({ group: "nodes", data: { id:"n0",name:"n0",weight: 75 }, }); $.ajax(url).done(function(jsontree){ var newnodes=[]; for(var i=1;i<6;i++){ //var child = jsontree.result[i]; newnodes.push( { group: "nodes", data: { id: "n"+i, name:"n"+i}}, { group: "edges", data: { id: "e"+i, source: "n0", target: "n"+i } } ); } cy.add(newnodes); any ideas? have used loaded function reload graph not work. not know if have use specific function reload graph. thank in advance. you need add positions new nodes. cytoscape.js docs : it important note positions of newly added nodes must defined when calling cy.add(). nodes can not placed in graph without valid position — otherwise not displayed. yo...
Read more