# Description

Identify the differences between the two types of iafit function. What is the difference of performing Dijkstra algorithm in the full graph or in the MST graph.

# Load data and define distance metric

``` 1 from numpy import *
2 from iaOPF import *
3 from scikits.learn import datasets
4
7     labels = iris.target
8     feats = iris['data']
9     return feats, labels
10
11 def euclidian(X, Y):
12     E = X - Y
13     return sqrt(dot(E, E))
14
```

# Fit via IFT full graph

```1 t = time.time()
2 OPF = iafit(feats, labels, euclidian)
3 print "Fit via IFT full graph: time elapsed: %f secs" % (time.time()-t)
4 print OPF[0].shape
5 print 'costs to root: ', OPF[0]
6 print 'parents: ', OPF[1]
7 print 'labels: ', OPF[2]
```
```Fit via IFT full graph: time elapsed: 0.235389 secs
(150,)
costs to root:  [ 0.2236068   0.2236068   0.2236068   0.2236068   0.2236068   0.34641016
0.2236068   0.2236068   0.2236068   0.2236068   0.2236068   0.2236068
0.2236068   0.24494897  0.41231056  0.36055513  0.34641016  0.2236068
0.34641016  0.24494897  0.3         0.24494897  0.45825757  0.          0.3
0.2236068   0.2         0.2236068   0.2236068   0.2236068   0.2236068
0.3         0.34641016  0.34641016  0.2236068   0.2236068   0.3
0.2236068   0.2236068   0.2236068   0.2236068   0.6244998   0.2236068
0.2236068   0.36055513  0.2236068   0.24494897  0.2236068   0.2236068
0.2236068   0.31622777  0.31622777  0.31622777  0.31622777  0.31622777
0.3         0.31622777  0.38729833  0.31622777  0.38729833  0.38729833
0.31622777  0.48989795  0.33166248  0.42426407  0.31622777  0.2
0.31622777  0.50990195  0.31622777  0.          0.33166248  0.
0.33166248  0.31622777  0.31622777  0.31622777  0.          0.33166248
0.34641016  0.31622777  0.31622777  0.31622777  0.          0.
0.37416574  0.31622777  0.50990195  0.31622777  0.31622777  0.31622777
0.33166248  0.31622777  0.38729833  0.31622777  0.31622777  0.31622777
0.31622777  0.          0.31622777  0.42426407  0.          0.4
0.36055513  0.36055513  0.52915026  0.          0.43588989  0.55677644
0.63245553  0.2236068   0.34641016  0.36055513  0.26457513  0.48989795
0.37416574  0.36055513  0.81853528  0.52915026  0.          0.36055513
0.31622777  0.52915026  0.24494897  0.36055513  0.4         0.24494897
0.14142136  0.36055513  0.4         0.43588989  0.81853528  0.36055513
0.          0.53851648  0.53851648  0.37416574  0.36055513  0.
0.36055513  0.36055513  0.36055513  0.          0.36055513  0.36055513
0.36055513  0.24494897  0.          0.37416574  0.28284271]
parents:  [   7.    9.   47.   29.    0.   10.   47.   26.   38.   30.   48.    7.
9.   38.   33.   33.   10.    7.    5.   48.   27.   19.    6.   23.
11.   30.   23.    0.    0.   11.   29.   20.   46.   32.   30.   49.
10.   30.   42.    7.    0.    8.   47.   26.   46.    1.   19.    3.
27.    7.   52.   75.   77.   89.   58.   66.   51.   98.   65.   89.
93.   96.   92.   78.   82.   86.   84.   82.   72.   89.   70.   97.
72.   63.   75.   65.   58.   77.   61.   81.   89.   69.   69.   83.
84.   56.   52.   68.   96.   94.   55.   78.   69.   57.   90.   96.
94.   74.   98.   94.  136.  101.  120.  116.  128.  107.  106.  125.
128.  143.  147.  147.  139.  101.  121.  110.  147.  105.  122.  119.
140.  101.  105.  126.  120.  102.  127.  138.  103.  125.  107.  117.
128.  133.  103.  130.  148.  116.  138.  145.  104.  145.  101.  140.
140.  147.  123.  147.  115.  127.]
labels:  [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  1.  1.  1.
1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.
1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.
1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  2.  2.  2.  2.  2.  2.  2.  2.
2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.
2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.
2.  2.  2.  2.  2.  2.]
```

# Fit via IFT MST graph

```1 t = time.time()
2 OPF2 = iafit(feats, labels, euclidian,True)
3 print "Fit via IFT MST graph: time elapsed: %f secs" % (time.time()-t)
4 print 'costs to root: ', OPF2[0]
5 print 'parents: ', OPF2[1]
6 print 'labels: ', OPF2[2]
```
```Fit via IFT MST graph: time elapsed: 0.173009 secs
costs to root:  [ 0.2236068   0.2236068   0.2236068   0.2236068   0.2236068   0.34641016
0.2236068   0.2236068   0.2236068   0.2236068   0.2236068   0.2236068
0.2236068   0.24494897  0.41231056  0.36055513  0.34641016  0.2236068
0.34641016  0.24494897  0.3         0.24494897  0.45825757  0.          0.3
0.2236068   0.2         0.2236068   0.2236068   0.2236068   0.2236068
0.3         0.34641016  0.34641016  0.2236068   0.2236068   0.3
0.2236068   0.2236068   0.2236068   0.2236068   0.6244998   0.2236068
0.2236068   0.36055513  0.2236068   0.24494897  0.2236068   0.2236068
0.2236068   0.31622777  0.31622777  0.31622777  0.31622777  0.31622777
0.3         0.31622777  0.38729833  0.31622777  0.38729833  0.38729833
0.31622777  0.48989795  0.33166248  0.42426407  0.31622777  0.2
0.31622777  0.50990195  0.31622777  0.          0.33166248  0.
0.33166248  0.31622777  0.31622777  0.31622777  0.          0.33166248
0.34641016  0.31622777  0.31622777  0.31622777  0.          0.
0.37416574  0.31622777  0.50990195  0.31622777  0.31622777  0.31622777
0.33166248  0.31622777  0.38729833  0.31622777  0.31622777  0.31622777
0.31622777  0.          0.31622777  0.42426407  0.          0.4
0.36055513  0.36055513  0.52915026  0.          0.43588989  0.55677644
0.63245553  0.2236068   0.34641016  0.36055513  0.26457513  0.48989795
0.37416574  0.36055513  0.81853528  0.52915026  0.          0.36055513
0.31622777  0.52915026  0.24494897  0.36055513  0.4         0.24494897
0.14142136  0.36055513  0.4         0.43588989  0.81853528  0.36055513
0.          0.53851648  0.53851648  0.37416574  0.36055513  0.
0.36055513  0.36055513  0.36055513  0.26457513  0.36055513  0.36055513
0.36055513  0.24494897  0.          0.37416574  0.28284271]
parents:  [  39.    9.   47.   29.    0.   10.   47.   26.   38.   30.   48.    7.
1.   38.   33.   33.   10.    0.    5.   48.   27.   19.    6.   23.
11.    9.   23.    0.   27.   11.   29.   20.   46.   32.    1.   49.
10.    1.   42.    7.   17.    8.   47.   26.   46.    1.   19.    3.
27.    7.   52.   75.   77.   89.   58.   66.   51.   98.   75.   89.
93.   96.   92.   91.   82.   86.   84.   92.   72.   92.   70.   97.
72.   63.   75.   65.   58.   77.   61.   81.   69.   80.   92.   83.
84.   56.   52.   68.   96.   69.   55.   78.   99.   57.   90.   96.
99.   74.   98.   94.  136.  101.  120.  116.  132.  107.  106.  125.
128.  143.  147.  147.  139.  101.  121.  110.  147.  105.  122.  119.
140.  101.  105.  126.  120.  102.  127.  138.  103.  125.  107.  117.
128.  133.  103.  130.  148.  116.  138.  145.  112.  145.  113.  120.
140.  147.  123.  147.  115.  127.]
labels:  [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.
0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  1.  1.  1.
1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.
1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  1.
1.  1.  1.  1.  1.  1.  1.  1.  1.  1.  2.  2.  2.  2.  2.  2.  2.  2.
2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.
2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.  2.
2.  2.  2.  2.  2.  2.]
```

# Results Comparation

```1 print 'Is iafit full graph == iafit MST:'
2 print '    - costs to root: ', (abs(OPF[0]-OPF2[0])<0.1).all()
3 print '    - parents: ', (abs(OPF[1]-OPF2[1])<0.1).all()
4 print '    - labels: ', (abs(OPF[2]-OPF2[2])<0.1).all()
```
```Is iafit full graph == iafit MST:
- costs to root:  False
- parents:  False
- labels:  True
```