0
# Warping Path Analysis
1

2
Computation and analysis of optimal warping paths between sequences. This module provides functions to calculate the full DTW matrix, extract optimal warping paths, apply penalties, and perform sequence warping transformations.
3

4
## Capabilities
5

6
### Full Warping Paths Matrix
7

8
Compute DTW distance along with the complete warping paths matrix, which contains the accumulated costs for all possible alignments between sequence elements.
9

10
```python { .api }
11
def warping_paths(s1, s2, window=None, max_dist=None, max_step=None,
12
                  max_length_diff=None, penalty=None, psi=None):
13
    """
14
    Compute DTW with full warping paths matrix.
15
    
16
    Returns both the optimal distance and the complete accumulated cost matrix,
17
    which can be used to extract alternative paths and analyze warping behavior.
18
    
19
    Parameters:
20
    - s1, s2: array-like, input sequences
21
    - window: int, warping window constraint
22
    - max_dist: float, early stopping threshold  
23
    - max_step: float, maximum step size
24
    - max_length_diff: int, maximum length difference
25
    - penalty: float, penalty for compression/expansion
26
    - psi: int, psi relaxation parameter
27
    
28
    Returns:
29
    tuple: (distance, paths_matrix)
30
        - distance: float, optimal DTW distance
31
        - paths_matrix: 2D array, accumulated cost matrix of shape (len(s1)+1, len(s2)+1)
32
    """
33

34
def warping_paths_fast(s1, s2, window=None, max_dist=None, max_step=None,
35
                       max_length_diff=None, penalty=None, psi=None):
36
    """
37
    Fast C version of warping paths computation.
38
    
39
    Same functionality as warping_paths() but uses optimized C implementation.
40
    
41
    Returns:
42
    tuple: (distance, paths_matrix)
43
    """
44
```
45

46
### Optimal Path Extraction
47

48
Extract the optimal warping path from a computed warping paths matrix, providing the sequence of coordinate pairs that define the optimal alignment.
49

50
```python { .api }
51
def warping_path(from_s, to_s, **kwargs):
52
    """
53
    Compute optimal warping path between two sequences.
54
    
55
    Returns the optimal sequence of index pairs that define how elements
56
    from the first sequence align with elements from the second sequence.
57
    
58
    Parameters:
59
    - from_s, to_s: array-like, input sequences
60
    - **kwargs: additional parameters passed to warping path computation
61
    
62
    Returns:
63
    list: sequence of (i, j) coordinate pairs representing optimal alignment
64
    """
65

66
def best_path(paths):
67
    """
68
    Compute optimal path from warping paths matrix.
69
    
70
    Traces back through the accumulated cost matrix to find the optimal
71
    warping path from end to beginning.
72
    
73
    Parameters:
74
    - paths: 2D array, warping paths matrix from warping_paths()
75
    
76
    Returns:
77
    list: sequence of (i, j) coordinate pairs representing optimal path
78
    """
79

80
def best_path2(paths):
81
    """
82
    Alternative optimal path computation with different implementation.
83
    
84
    Provides an alternative algorithm for path extraction that may be
85
    more suitable for certain matrix structures or constraints.
86
    
87
    Parameters:
88
    - paths: 2D array, warping paths matrix
89
    
90
    Returns:
91
    list: sequence of (i, j) coordinate pairs representing optimal path
92
    """
93
```
94

95
### Path Analysis and Penalties
96

97
Analyze warping paths to quantify warping behavior and apply post-calculation penalties based on path characteristics.
98

99
```python { .api }
100
def warping_path_penalty(s1, s2, penalty_post=0, **kwargs):
101
    """
102
    DTW with post-calculation penalty based on warping path characteristics.
103
    
104
    Computes DTW and then applies additional penalties based on the
105
    resulting warping path properties (e.g., excessive compression or expansion).
106
    
107
    Parameters:
108
    - s1, s2: array-like, input sequences
109
    - penalty_post: float, post-calculation penalty factor
110
    - **kwargs: additional DTW parameters
111
    
112
    Returns:
113
    list: [distance, path, path_stepsize, DTW_matrix]
114
        - distance: float, DTW distance with penalty applied
115
        - path: list, optimal warping path coordinates
116
        - path_stepsize: array, step sizes along the path
117
        - DTW_matrix: 2D array, accumulated cost matrix
118
    """
119

120
def warping_amount(path):
121
    """
122
    Count compressions and expansions in warping path.
123
    
124
    Analyzes the warping path to quantify how much compression (multiple
125
    elements from one sequence aligned to single element) and expansion
126
    (single element aligned to multiple elements) occurs.
127
    
128
    Parameters:
129
    - path: list, sequence of (i, j) coordinate pairs from warping path
130
    
131
    Returns:
132
    int: total number of warping operations (compressions + expansions)
133
    """
134
```
135

136
### Sequence Warping
137

138
Transform one sequence to match another using the optimal warping path, effectively creating a warped version of the source sequence aligned to the target.
139

140
```python { .api }
141
def warp(from_s, to_s, **kwargs):
142
    """
143
    Warp one sequence to match another using optimal DTW alignment.
144
    
145
    Transforms the first sequence by stretching and compressing it according
146
    to the optimal warping path to best match the second sequence.
147
    
148
    Parameters:
149
    - from_s: array-like, source sequence to be warped
150
    - to_s: array-like, target sequence to warp towards
151
    - **kwargs: additional DTW parameters
152
    
153
    Returns:
154
    tuple: (warped_sequence, path)
155
        - warped_sequence: array, transformed version of from_s
156
        - path: list, warping path used for transformation
157
    """
158
```
159

160
## Usage Examples
161

162
### Computing Warping Paths Matrix
163

164
```python
165
from dtaidistance import dtw
166
import numpy as np
167

168
# Create two sequences
169
s1 = [1, 2, 3, 4, 3, 2, 1]
170
s2 = [1, 3, 4, 3, 1]
171

172
# Compute warping paths matrix
173
distance, paths = dtw.warping_paths(s1, s2)
174

175
print(f"DTW distance: {distance}")
176
print(f"Paths matrix shape: {paths.shape}")
177
print("Paths matrix:")
178
print(paths)
179
```
180

181
### Extracting Optimal Path
182

183
```python
184
from dtaidistance import dtw
185

186
s1 = [0, 1, 2, 3, 2, 1, 0]
187
s2 = [1, 2, 3, 2, 1]
188

189
# Get the optimal warping path
190
path = dtw.warping_path(s1, s2)
191
print("Optimal warping path:")
192
for i, (x, y) in enumerate(path):
193
    print(f"Step {i}: s1[{x}]={s1[x] if x < len(s1) else 'end'} -> "
194
          f"s2[{y}]={s2[y] if y < len(s2) else 'end'}")
195

196
# Alternative: compute paths matrix first, then extract path
197
distance, paths_matrix = dtw.warping_paths(s1, s2)
198
optimal_path = dtw.best_path(paths_matrix)
199
print("Path from matrix:", optimal_path)
200
```
201

202
### Analyzing Warping Behavior
203

204
```python
205
from dtaidistance import dtw
206

207
# Sequences with different temporal patterns
208
s1 = [1, 1, 2, 2, 3, 3, 2, 2, 1, 1]  # Slower pattern
209
s2 = [1, 2, 3, 2, 1]                   # Faster pattern
210

211
# Compute path and analyze warping
212
path = dtw.warping_path(s1, s2)
213
warping_ops = dtw.warping_amount(path)
214

215
print(f"Warping path length: {len(path)}")
216
print(f"Total warping operations: {warping_ops}")
217

218
# Analyze compression/expansion ratios
219
compressions = sum(1 for i in range(1, len(path)) 
220
                   if path[i][0] == path[i-1][0])
221
expansions = sum(1 for i in range(1, len(path)) 
222
                 if path[i][1] == path[i-1][1])
223

224
print(f"Compressions: {compressions}")
225
print(f"Expansions: {expansions}")
226
```
227

228
### Sequence Warping Transformation
229

230
```python
231
from dtaidistance import dtw
232
import matplotlib.pyplot as plt
233

234
# Original sequences
235
source = [1, 2, 4, 3, 1, 0, 1, 2]
236
target = [1, 3, 2, 1]
237

238
# Warp source to match target
239
warped_source, path = dtw.warp(source, target)
240

241
print("Original source:", source)
242
print("Target:", target)
243
print("Warped source:", warped_source)
244
print("Warping path:", path)
245

246
# Visualize the warping transformation
247
fig, (ax1, ax2, ax3) = plt.subplots(3, 1, figsize=(10, 8))
248

249
ax1.plot(source, 'b-o', label='Original Source')
250
ax1.set_title('Original Source Sequence')
251
ax1.legend()
252

253
ax2.plot(target, 'r-o', label='Target')
254
ax2.set_title('Target Sequence')
255
ax2.legend()
256

257
ax3.plot(warped_source, 'g-o', label='Warped Source')
258
ax3.plot(target, 'r--', alpha=0.7, label='Target (reference)')
259
ax3.set_title('Warped Source vs Target')
260
ax3.legend()
261

262
plt.tight_layout()
263
plt.show()
264
```
265

266
### Post-Calculation Penalties
267

268
```python
269
from dtaidistance import dtw
270

271
s1 = [1, 2, 3, 4, 5]
272
s2 = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]  # More compressed version
273

274
# Regular DTW
275
regular_distance = dtw.distance(s1, s2)
276

277
# DTW with post-calculation penalty for excessive warping
278
results = dtw.warping_path_penalty(s1, s2, penalty_post=0.5)
279
penalized_distance, path, step_sizes, matrix = results
280

281
print(f"Regular DTW distance: {regular_distance}")
282
print(f"Penalized DTW distance: {penalized_distance}")
283
print(f"Penalty applied: {penalized_distance - regular_distance}")
284
print(f"Path step sizes: {step_sizes}")
285
```
286

287
### Performance with Large Sequences
288

289
```python
290
from dtaidistance import dtw
291
import numpy as np
292
import time
293

294
# Generate large sequences
295
np.random.seed(42)
296
s1 = np.cumsum(np.random.randn(500))
297
s2 = np.cumsum(np.random.randn(450))
298

299
# Compare performance of different methods
300
methods = [
301
    ("Python warping_paths", lambda: dtw.warping_paths(s1, s2)),
302
    ("C warping_paths_fast", lambda: dtw.warping_paths_fast(s1, s2)),
303
    ("Path only", lambda: dtw.warping_path(s1, s2))
304
]
305

306
for name, method in methods:
307
    start_time = time.time()
308
    result = method()
309
    elapsed = time.time() - start_time
310
    
311
    if isinstance(result, tuple):
312
        distance = result[0]
313
        print(f"{name}: distance={distance:.4f}, time={elapsed:.4f}s")
314
    else:
315
        print(f"{name}: path_length={len(result)}, time={elapsed:.4f}s")
316
```
317

318
## Path Visualization Integration
319

320
The warping paths functionality integrates with the visualization module for plotting warping relationships:
321

322
```python
323
from dtaidistance import dtw
324
from dtaidistance.dtw_visualisation import plot_warpingpaths, plot_warping
325

326
s1 = [0, 1, 2, 1, 0, 1, 0, 0]
327
s2 = [0, 0, 1, 2, 1, 0, 0]
328

329
# Compute paths and optimal path
330
distance, paths = dtw.warping_paths(s1, s2)
331
path = dtw.best_path(paths)
332

333
# Visualize warping paths matrix
334
plot_warpingpaths(s1, s2, paths, path)
335

336
# Visualize optimal warping between sequences  
337
plot_warping(s1, s2, path)
338
```
339

340
This integration allows for comprehensive analysis of both the numerical and visual aspects of sequence warping behavior.