# Mesh as Graph

The approach I have chosen for mesh segmentation involves representing the mesh as a graph. This graph will allow for algorithms such as Dijkstra’s shortest path and Floyd-Warshall all-pair-shortest-path to be calculated.

What is a graph?
A graph is a set of nodes (depending on your convention you can call them nodes or vertices) connected by pairwise relations. You can have as many lines as you want coming in and out of a node, but each line can only be connected to two nodes, creating a pair. These lines are called edges (or arcs) and can have an weighting associated with them, and it is this weighting makes graph such a powerful concept.

Representing a graph!
A graph may be represented either as an adjacency list or and adjacency matrix. Some graph calculations require adjacency lists and others require adjacency matrices, neither of which are difficult concepts or difficult to implement.

An adjacency lists will conceptually show us the node Id and what nodes it is connected to. Lets say that London is a node, and from London you can travel to Oslo, Berlin and Paris. This would be written as:

London = Oslo, Berlin, Paris

We have now described the edges between our node (London), but we can also associate a weighting for the edges, represented as flight time from our node to the connected nodes:

London = (Oslo, 2h), (Berlin, 1h), (Paris, 1.5h)

Adjacency lists are commonly represented as dictionaries in python, as shown here:

```# Initialize our adjacency list graph.
graph = {}

graph['London'] = ('Oslo', 'Berlin', 'Paris')

# Update the node to associate weightings with its edges.
graph['London'] = (('Oslo', 2), ('Berlin', 1), ('Paris', 1.5))

print graph
# {'London': (('Oslo', 2), ('Berlin', 1), ('Paris', 1.5))}
```

Matrix!

You better have a basic understanding of matrices, if not, they can be explained as a grid of size ij. That is i wide and j high, correct terms would be i rows and j columns( a matrix is denoted Mij). An adjacency matrix is always square because it represents all the nodes in i and in j, so i and j = number of nodes on the graph. When you view an adjacency matrix it will remind you a bit of a identity matrix where all diagonal elements are 1, just that in adjacency matrix all diagonal elements are 0. If we have an graph, represented by text as:

1. London = Oslo, Berlin, Paris

2. Oslo = London

3. Berlin = London

4. Paris = London, Berlin, Oslo

We can see that we have 4 nodes (London, Oslo, Berlin, Paris), so we would have an adjacency matrix of size i = 4 and j =4 (Mij = M44).

```   1  2  3  4
1  0, 0, 0, 0
2  0, 0, 0, 0
3  0, 0, 0, 0
4  0, 0, 0, 0
```

If we put our data into the matrix we would receive:

```   1  2  3  4
1  0, 1, 1, 1
2  1, 0, 0, 1
3  1, 0, 0, 1
4  1, 1, 1, 0
```

To represent a mesh as a graph in adjacency list form and adjacency matrix form we loop all the faces of the mesh. Check which faces faceN is connected to, this would be the edges our current node has. Calculate the distance between faceN and its edges. apply this to a adjacency list and a adjacency matrix.

```import maya.OpenMaya as om
import maya.cmds as cmds

def selectObj():
####### Querying a selected object
cmds.FreezeTransformations()
# Turns on the option for maya to track what order you selected things in
om.MGlobal.setTrackSelectionOrderEnabled(True)

# 1 # Initialize a selectionList object
selectionLs = om.MSelectionList()
# 2 # Populate the selectionList with current selected objects
om.MGlobal.getActiveSelectionList(selectionLs)
# 3 # create an iterator from our queried selection list, and give it an filter to only iterate kmesh
iterSel = om.MItSelectionList(selectionLs, om.MFn.kMesh)
# 4 # initialize a dagObject object
dagObject = om.MdagObject()
# 5 # populate the dag path object
iterSel.getdagObject(dagObject)
return dagObject

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

def objToGraph(dagObject):
"""
Returns an adjacency list representing the inputed dagObject
Creates a node for each face and calculates weightings
between nodes based on distance from the center of
faceN1 to center of edgeN to the canter of faceN2

weighting = |-----------------|-----------------|
f1.center -> edge.center <- f2.center

"""
# initialize iterators
mitFace = om.MItMeshPolygon(dagObject)
mitEdge = om.MItMeshEdge(dagObject)

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

#### Faces
# iterate over all the faces

faceFace = om.MIntArray()
faceId = om.MIntArray()

faceRel = []    # keep a list of which faces are connected to face N.
facePos = []    # hold the centroid position of each face.

mitFace.reset()
while not mitFace.isDone():

# get the connected faces of the current face
mitFace.getConnectedFaces(faceFace)
faceRel.append(list(faceFace))

# get the center of the face
fcenter = mitFace.center()
facePos.append(fcenter)

mitFace.next()

# iterate over all the edges
mitEdge.reset()
while not mitEdge.isDone():

# get the faces connected to the edge
mitEdge.getConnectedFaces(faceId)

# check if the edge is valid i.e. must have two faces connected to it
if faceId.length() == 2:

# get the center of the current edge
edgeCenter =  mitEdge.center()

# holder variables for the two faces in question
f1 = faceId[0]
f2 = faceId[1]

#### Length weighting Calculation

# retrieve the center of the face from our queried list
p1 = facePos[f2]
p2 = facePos[f1]

# calculate the face-to-edge length
fe1 = p1 - edgeCenter
fe2 = p2 - edgeCenter

# the total length for the weighting from one node to the other
fLength = fe1.length() + fe2.length()