# Interactive Graph Stream Analytics in Arkouda
## 5 Single Pass Regression Analysis Stream Model
### Edge-Vertex Iterator Based Triangle Counting Algorithm
Since different locales may have different edges with the same starting vertex, the interval \([StartVer..EndVer]\) of different locales may overlap. At the same time, some starting vertex in the \(SRC\) index array may not appear in \(SRC\), so we should also make sure there is no \"hole\" in the complete interval \([0..|V_{sk}|-1]\). In line 7, we will make sure all the intervals will cover all the vertices without overlapping. Our method includes the following steps: (1) If the current locale's \(StartVer\) is the same as the previous locale's \(EndVer\), this means that one vertex's edges have been partitioned into two different locales. We will set \(StartVer=StartVer+1\) to avoid two locales executing the counting on the same vertex; (2) If the current locale's \(StartVer\) is different from the previous locale's \(EndVer\), and the difference is larger than 1, this means that there is a \"hole\" between the last locale's vertices and the current locale's vertices. So we will let the current locale's \(StartVer=\) last locale's \(EndVer+1\); (3) If the current locale is the last locale, we will let its \(EndVer=\) the last vertex ID. If the current locale is the first locale, we will let \(StartVer=0\). From line 8 to line 14 we will count all the triangles starting from the vertices assigned to the current locale in parallel. In line 9 we will generate all the adjacent vertices \(u_{adj}\) of the current vertex \(u\) and its vertex ID is larger than \(u\). From line 10 to line 12, for any vertex \(v\in u_{adj}\), we will generate all the adjacent vertices \(v_{adj}\) of current vertex \(v\) and its vertex ID is larger than \(v\). So the number of vertices in \(u_{adj}\cap v_{adj}\) is the number of triangles having edge \(\langle u,v\rangle\). Since we only calculate the triangles whose vertices meet \(u<v<w\), we will not count the duplicate triangles. In this way, we can avoid the unnecessary calculation. In line 15, each locale will assign its total number of triangles to the corresponding position of array _subTrisum_. At the end in line 18, when we sum all the number of triangles of different locales, we will obtain the total number of triangles. ```
1\(TC(G_{sk}=\langle E_{sk},V_{sk}\rangle)\) /*\(G_{sk}\) is the given graph sketch partition,\(E_{sk},V_{sk}\) are edge and vertex sets. */
2 var subTriSum=0: [0..numLocales-1] int;//store each locale's number of triangles
3 corofall (loc in Locales)do
4 if(current loc is my locale)then
5 var triCount=0:int;//initialize number of local triangles
6
7 assign StartVer and EndVer based on edge index array
8 Adjust StartVer and EndVer to cover all vertices and avoid overlapping
9 forall(\(u\) in StartVer..EndVer with (+ reduce triCount))do
10\(u_{adj}=\{x|\langle u,x\rangle\in E_{sk}\wedge(x>u)\}\) //build the \(u\) adjacency vertex set in parallel
11 forall\(v\in u_{adj}\)do
12\(v_{adj}=\{x|\langle v,x\rangle\in E_{sk}\wedge(x>v)\}\) //build the \(v\) adjacency vertex set in parallel
13
14
15
16
17
18
19
20 end if
21 return\(sum(subTriSum)\)
```  
**Algorithm 1**Edge-vertex Iterator triangle counting algorithm