# Vertices, faces -> adjacency list

Hi

I need help with a graph problem. What is the fastest way to convert a obj style mesh information (list of vertices, list of faces) into an adjacency list (for every mesh node a list of integers indicating all the nodes that node shares edges with)? My first approach is:

• to first get all the single edges (startIndexNode, endIndexNode)
• delete the duplicates using a nested for loop
• loop over nodes and compare all edges (startIndexNode, endIndexNode) with the node index

This is expensive and takes way to long. What is a good strategy for this graph problem? Any help is very much appreciated.

M

This is what I have so far. Way too slow!
Sorry, I am new to python and just translated this from vbs.

``````def GetTriEN(Vertices):
allEdges = []
TriEInd = []
for i in range(len(Vertices)):
allEdges.append([Vertices[i][0],Vertices[i][1]])
allEdges.append([Vertices[i][1],Vertices[i][2]])
allEdges.append([Vertices[i][2],Vertices[i][0]])
for i in range(len(allEdges)):
blnDup = False
for j in range(i+1,len(allEdges)):
if ((allEdges[i][0] == allEdges[j][1]) and (allEdges[i][1] == allEdges[j][0])) or ((allEdges[i][0] == allEdges[j][0]) and (allEdges[i][1] == allEdges[j][1])):
blnDup = True
break
if not blnDup:
TriEInd.append(allEdges[i])
return TriEInd
``````

Hi Manuel,

have you tried to exchange range with xrange in your function?

Alternatively, you might be able to get the adjacent (connected) vertices and faces from a single vertex by using these methods:

``````GetConnectedVertices(vertexIndex)
GetVertexFaces(vertexIndex)
``````

Both belong to the MeshVertexList class.

c.

Thanks Clement! that’s great, I’ll take a look into this. Not experienced with RhinoCommon SDK in python. GetConnectedVertices(vertexIndex) is probably exactly what I need.

M

Hi Manuel,

take care of what it reports as connect and try it out using meshes which have unwelded or naked edges. I´ve been surprised by the outcome. You might be interested in

``````MeshTopologyEdges
MeshTopologyVertices
``````

as well. Good Luck !

c.

Do the faces in this mesh have a limit of 3 or 4 vertices per face? -or- can there be an unlimited number of vertices per face? I’m asking because the 3 or 4 vertex case is easier to deal with since it maps to what our Mesh class currently supports in RhinoCommon

For now 3 vertices per face. But for future work it would be beneficial if the mesh class would support >4 vertices per face.
Thanks
M