# Path Algorithms for Contact Sequence Temporal Graphs +
## 2 Materials and Methods
### TRG Data Structures
#### 2.1.2 TRG_Zschoche  
Similar to TSG_Wu, TRG_Zchoche [9] removes the temporal information from the edges and adds them to the vertices. Here, the authors assume that all edge weights are integer and strictly positive. In TRG_Zchoche, for each \(u\in V\), the \(V_{in}(u)\) and \(V_{out}(u)\) vertices are put into a single directed chain in increasing order of time rather than into two separate chains as in TRG_Wu and that is the main difference between the two models. Let \(G^{\prime\prime}=(V^{\prime\prime},E^{\prime\prime})\) be the TRG_Zscoche transformation of \(G\). The following describes how to construct \(G^{\prime\prime}\) from \(G\).  
1. The first step is to construct an intermediate graph \(G_{1}=(V_{1},E_{1})\), in which each edge \((u,v,t,w)\) with \(w>1\) is replaced by two edges \((u,v_{New},t,1)\) and \((v_{New},v,t+w-1,1)\). It is guaranteed that every path in \(G\) that uses the original \((u,v,t,w)\) gets to \(v\) at time \(t+w\) in \(G_{1}\).
2. For each vertex \(u\in V_{1}\), let \(\Phi(u)=T_{in}(u)\cup T_{out}(u)\). For each \(t\in\Phi(u)\) add a vertex \((u,t)\) to \(V^{\prime\prime}\).
3. For each \(u\in V_{1}\), sort the vertices \((u,*)\) in ascending order of time and make a chain by connecting each vertex to the next one using a directed zero-weight edge.
4. For each edge \((u,v,t,w)\in E_{1}\) add a directed edge of weight \(=w\) from \((u,t)\in V^{\prime\prime}\) to \((v,t+w)\in V^{\prime\prime}\).  
The TRG_Zschoche transformation of Figure 1a is shown in Figure 1d. Nodes \((B_{n},*)\) are the \(B_{new}\) nodes added to the graph in step 1. TRG_Zschoche can be shown to have the same time-respecting properties as TRG_Wu. Bounds on \(|V^{\prime\prime}|\) and \(|E^{\prime\prime}|\) are computed below.  
1. \(|V_{1}|=|V|+D\) and \(|E_{1}|=|E|+D\) where \(D\leq|E|\) is the number of edges in \(G\) with weight \(>1\).
2. \(|V^{\prime\prime}|=\Sigma_{u\in V_{1}}|\Phi(u)|=\Sigma_{u\in V_{1}}(|T_{in}(u) \cup T_{out}(u)|)\leq 2|E_{1}|=2|E|+2D\leq 4|E|\).
3. The number of chain edges is \(\Sigma_{u\in V_{1}}(|\Phi(u)|-1)=\Sigma_{u\in V_{1}}((|T_{in}(u)\cup T_{out}(u )|)-1)\leq 2|E_{1}|-|V_{1}|=2|E|+2D-|V|-D\leq 3|E|-|V|\). The number of other edges in \(E^{\prime\prime}\) is \(|E_{1}|\leq 2|E|\). So, \(|E^{\prime\prime}|\leq 5|E|-|V|\).  
In TRG_Zschoche, all edge weights are either 0 or 1. We have shown that there are higher bounds on the number of vertices and edges in TRG_Zschoche than in TRG_Wu. However, that does not necessarily mean that the number of nodes and edges is always higher for TRG_Zschoche. As shown by our experimental datasets (Section 3.1) there are contact sequence temporal graphs for which TRG_Wu has more vertices and edges than TRG_Zschoche and vice-versa.  
We look closer at the special case when all edge weights are 1. This special case is of interest because the experimental datasets used in [8] were derived from real-world temporal sequence graphs by setting all weights to 1 (the original weights were 0 as the original graphs modeled instantaneous communication); we use \(11\) of these datasets in our experiments of Section 3.1. When all edges have \(w=1\), \(D=0\). Hence, \(|V_{1}|=|V|\) and \(|V^{\prime\prime}|=\Sigma_{u\in V}(|T_{in}(u)\cup T_{out}(u)|)\leq\Sigma_{u\in V }(|T_{in}(u)|+|T_{out}(u)|)=|V^{\prime}|\). Also, \(|E_{1}|=|E|\) and \(|E^{\prime\prime}|=|E|+\Sigma_{u\in V}((|T_{in}(u)\cup T_{out}(u)|)-1)\leq|E|-| V|+\Sigma_{u\in V}(|T_{in}(u)|+|T_{out}(u)|\leq|E^{\prime}|\), whenever \(\sum\min\{|T_{in}(u)|,|T_{out}(u)|\geq|V|\}\). For most temporal graphs, we expect the sum of the minimums of the in and out degrees to exceed \(|V|\). So, when all edges have \(w=1\), TRG_Zschoche never has more vertices than TRG_Wu and almost always has fewer edges. This conclusion is borne out by the vertex and edge counts reported in Section 3.1.  
Note, however, that in the more general case when edge weights are not restricted to 1, either data structure may have a lower vertex and/or edge count, and the upper bound on these counts is higher for TRG_Zschoche than for TRG_Wu.