# analyzing a graph, using Blender

Hallo,
Trying to compute the longest path of streets (from the game “Die Siedler”) I have
used Blender with its Python Api as ‘graph helper’

I have a planar graph of alone edges (see picture)
First problem solved: find all connected vertices :yes:.
The pictures shows above the result in the console: one click on ‘Run Script’
and below the graph used …
Dijkstras- shortest path algorithm used and then analyzing the result(s) ‘suitable’
Nice, isn’t it.

Remark by the way, the latest Blender of today is not content with my used show vertex-indices addon Api has changed again …so find the adjustmensts Peter!

Meaning too, that Blender can be used as tool for graph-theory.

interesting but not into the graph math thing!

is this the opposite of the minimum distance for the traveling salemans algo ?

happy 2.5

Just as I sad: Dijkstra Algorithm for shortest Path is used as basic tool, result is used in an iterative process to discover the not connected (but in itself connected) parts (do not know the graph theoretic way of naming …[ too lazy ])

It is the prepartion for finding the longest street for the game: Die Siedler von Cartan (is to be found on the WWW)

is there any python script to find the min or max path with mesh i guess ?

might be usefull later on for futur script

thanks and happy 2.5

What are you doing actually (mind showing the script)? The “longest path of a given graph” Problem is NP complete and therefore a bit difficult to tackle - if you’re dealing with arbitrary graphs. If you have an acyclic one, you can simply use Dijkstra to find it. Or even better methods, as far as I can remember…I can’t really remember the algorithm, though, maybe a search will help.

Do you have the code? Or you need it? Or need ideas on HOW-TO do this in Blender? I mean that (due to Blender data, which exists anyway) maybe your quoted algorithm won’t be the fastest…

Regards,

speed is function of the algo and qty of vertex needed

so depends really on max quantity of vertex

but also may depends if there are constraints added which then may become a nightmare!

happy 2.5

Thanks for the info, Ricky! It is correct BUT Im speaking for situations of applying two (or more) alcorithms (scripts) on same mesh (graph) in Blender. My math is good and I know there are algorithms that are proven to be the best for their purpose in math, in particular: in graph theory, BUT Im speaking of using Blender existing data MAY BE makes the things different…

Only a proper testing will show if YES or NO.

Regards,

does anybody has a simple algo for min or max for a limted qty of vertex and no constraints?

seems that algo from linear progammation is good up to about 20 vertices!
but who knows there might be an algo in python already done that can go up to may be 100 or 200 !

might be fun to test this and might be usefull in futur anyway!

happy 2.5

I think, PKHG should lead here… And BTW there isnt a limit for algorithms of that kind in math

Thanks, indeed.

The graph I want to tackle is comming form the game (Siedler…) and therefor guaranteed small, such that NP problem is not relevant.
Furthermore, all vertices will have index 1, 2 or 3 (meaning = number of edges coming from a vertex , the game ‘lays’ streets = one egde)

But because there are cycles small with 6 edges only (like honeycomb) and ‘bigger ones eventually’, and several small ones as neighbors … one has to ‘find’ all cycles (I am nearly sure)… and before of that the connected ‘edges’ … start of this thread!

My ‘indirect’ question for this thread … what graph-algorithms exist for BLENDER?
I have one for Dijkstra’s shortest path , taken a ‘general description’ from a wikipedia page
to some extent easy to implement with the help of blender mesh representation and Python tools…

not certain here
if less then 20 might go with the optimun solution to get exact one
the other one is only approximative check out the wiki page for this

now only thing left is how long to do each of those also

i do have a link for an algo python for this Dijkstra algo
or you can write your own

but would like to see the exact algo solution one

so let me know if you want this link for Dijkstra algo
now i but did not test it and not certain what precision you get
only way to test is to check against the real one with exact solution i guess

if anybody has an algo for the exact solution with N < 20 let us knnow!

good luck
happy 2.5

Here’s a script doing the task on any mesh:

``````from Blender import *

#
# Script made by Emil Lozanov, a.k.a. Abidos @ Blender Artists Forum
#
#   ***   August 2010   ***
#

############################################

def Make_viv(me):
viv = {}
for edge in me.edges:
v1 = edge.v1.index
v2 = edge.v2.index
try: viv[v1].append(v2)
except KeyError: viv[v1]=[v2]
try: viv[v2].append(v1)
except KeyError: viv[v2] = [v1]
return viv

def Get_next_i(dv_bool,i):
for i in range(len(dv_bool)):
if not dv_bool[i]:
return i
return -1

viv = Make_viv(me)
d = {}
lst = []  # list of verts-indeces connected to currently processed vertex
k = 0  # number of verts already processed
vi = 0  # index of currently processed vertex
i = 0  # index of currently processed vertex-index from lst
nv = len(me.verts)
dv_bool = dict([ind,False] for ind in range(nv))
while (vi&lt;&gt;-1):
lst.extend(viv[vi])
for v_ind in lst:
dv_bool[v_ind] = True
j = 0
fl_go = True
while fl_go:
n = len(lst)
dv_bool[vi] = True
for j in range(n):
for v_ind in viv[lst[j]]:
if not (v_ind in lst):
if not dv_bool[v_ind]:
lst.append(v_ind)
dv_bool[v_ind] = True
fl_go = (n&lt;&gt;len(lst))  # i.e. something new is added
d[vi] = lst
k += len(lst)
lst = []
if (vi&lt;nv):
vi = Get_next_i(dv_bool,vi)

return d

############################################

editmode = Window.EditMode()
Window.EditMode(0)
Window.WaitCursor(1)

t1 = sys.time()
sce = Scene.GetCurrent()
ob = Object.GetSelected()[0]
me = ob.getData(mesh=1)

t2 = sys.time()
T = 1000*(t2-t1)

lst_rows = []
for ind,data in d.items():
lst = [ind]
lst.extend(d[ind])
lst_rows.append(lst)
nv,ne,nf = len(me.verts),len(me.edges),len(me.faces)
print nv,ne,nf
print T
for elem in lst_rows:
print elem
print

#Redraw()
Window.WaitCursor(0)
Window.EditMode(editmode)

``````

I guess it works at a mesh with “special” cases (not tested yet due to lack of time) such as isolated verts or verts with just 1 neighbor in the group or even in cases of overlapped edges. The latter doesnt really matter in our task, right?

Script gives results such as:

``````20 32 16
0.220186997467
[0, 1, 3, 4, 2, 5, 7, 6]
[8, 9, 11, 12, 19, 10, 13, 18, 15, 16, 14, 17]
``````

meaning it gives processing times of about 0.3 milliseconds when applied on a mesh of 20 verts (2 parts it the above example). Lists of vertices in the “connected” groups are not sorted - it is relatively easy, I think

Sorry PKHG - script is 2.49 style - you know Im still with 2.49

Script give processing time of about 16 milliseconds on a mesh with about 500 verts (on my comp). But increasing N_vets to some 4000-5000 results in a very prolonged processing time of about 11-12 seconds! This is due the fact I produced the script fairly quickly using the straight-forward approach. Also due to Python specifics - dealing with BIG-BIG list and a lot of IFs is real time-pain, ok?

If you’re planning to use the script on meshes with N_verts < 500, NO real improvements are needed!!! Trully!!! Just please report any BUG noticed

Some vers may also NOT needed for the script work - just havent had time to purge ALL these but - if any such vars - they dont mess script work :rolleyes:

For real BIG N_meshes with N_verts > 2000, improvments lye at re-working the Get_next_i proc - may result of about 10-20% improvement. Greater improvement at BIG meshes may come when re-working the main cycle to directly collecting info about verts indices to be added in the final list by using TREE structure of dictionaries, for example. I expect the use of a TREE-like data structure to result to linear relationship between N_vert and processing time, rather than exponential one as it is now.

As the role of passing a second var to the proc Get_next_i is to start from there to the end (abandoned in my solution above), perhaps, a better solution for the Get_next_i proc is (not tested yet):

``````def Get_next_i(dv_bool,j):
for i in range(j,len(dv_bool)):
if not dv_bool[i]:
return i
return -1

``````

Script is planned to work with ANY mesh, not only 2D…

@ PKHG - I studied Applied Math some time ago. May be I will have time to implement your suggested algorithm and compare the timings one day! Hope the above helps you!

Regards,

On which algo did you base your script algo

if more then 20 i guess this is sort of an heuristic algo

but seems to be very fast also !

and i’m surpise a bit cause there was so much warning about the time to process this
type of algo!

have to test this against the other algo i dound for this

do you mind if i try to port it to 2.5 if not too difficult ?

happy 2.5

here is a site for an application giving results
http://www.codeproject.com/KB/recipes/GcDijkstra.aspx

but not certain i think you need to include this int a VB or C++ may be to make it work with Activx!

i;ll try to test it and may be it can work !

salutations

@Abidos,
I will try to translate your code to blender 2.5 …
looks good in 2.49 and probably smarter. then my implementation

Start:

``````
import bpy
print("======start=======")
obj = bpy.context.active_object
mesh = obj.data

def Make_viv(me):
viv = {}
for edge in me.edges:
v1 = edge.verts[0]
v2 = edge.verts[1]
try: viv[v1].append(v2)
except : viv[v1]=[v2]
try: viv[v2].append(v1)
except : viv[v2] = [v1]
return viv
res = Make_viv(mesh)
print(res)

``````

a list of neigbours of each vertex (nice!) … (will go on later)

@ Ricky - I mentioned already I have produced the above code thinking on solving the issue and using a quite straight-forward approach (as usual) - nothing else special.

@ PKHG - Thanks for your effort on translating the code in 2.5 My second version of the Get_next_i proc works fine and a bit faster - noticable when N_verts goes > 1000-2000.

Works perfect in blender 2.5

``````
import bpy
from time import time

print("======start=======")
obj = bpy.context.active_object
mesh = obj.data

def Make_viv(me):
viv = {}
for edge in me.edges:
v1 = edge.verts[0]
v2 = edge.verts[1]
try: viv[v1].append(v2)
except : viv[v1]=[v2]
try: viv[v2].append(v1)
except : viv[v2] = [v1]
return viv
#res = Make_viv(mesh)
#print(res)

def Get_next_i(dv_bool,i):
for i in range(len(dv_bool)):
if not dv_bool[i]:
return i
return -1

viv = Make_viv(me)
d = {}
lst = []  # list of verts-indeces connected to currently processed vertex
k = 0  # number of verts already processed
vi = 0  # index of currently processed vertex
i = 0  # index of currently processed vertex-index from lst
nv = len(me.verts)
dv_bool = dict([ind,False] for ind in range(nv))
while (vi != -1):
lst.extend(viv[vi])
for v_ind in lst:
dv_bool[v_ind] = True
j = 0
fl_go = True
while fl_go:
n = len(lst)
dv_bool[vi] = True
for j in range(n):
for v_ind in viv[lst[j]]:
if not (v_ind in lst):
if not dv_bool[v_ind]:
lst.append(v_ind)
dv_bool[v_ind] = True
fl_go = (n != len(lst))  # i.e. something new is added
d[vi] = lst
k += len(lst)
lst = []
if (vi&lt;nv):
vi = Get_next_i(dv_bool,vi)

return d

#starttime = time() ; print(starttime)

t1 = time()
#d = Make_viv(mesh)

t2 = time()
T = 1000 * (t2 - t1)
print(T)

lst_rows = []
for ind,data in d.items():
lst = [ind]
lst.extend(d[ind])
lst_rows.append(lst)
nv,ne,nf = len(mesh.verts),len(mesh.edges),len(mesh.faces)
print (nv,ne,nf)
print (T)
for elem in lst_rows:
print(elem)
print()

``````

only small changes needed e.g. <> != … :yes:

:edit:
above shorter possibility and easier
v1,v2 = edge.verts

by the way is this algo giving the min or max path ?

thanks

@RickyBlender
Try it!