Skip to content

Vectorized Backend

NumPy-vectorized force computation for 10-16x speedup without Cython. Uses broadcasting for pairwise operations on (N, dim) arrays.

This module is used automatically when backend="vectorized" or when backend="auto" and no Cython extension is compiled.

Note

The vectorized backend does not support Barnes-Hut approximation ā€” all repulsion is O(nĀ²) pairwise. For graphs over ~5000 nodes, the Cython backend with Barnes-Hut is significantly faster.

Functions

apply_repulsion 

apply_repulsion(positions, masses, coefficient)

Apply repulsion forces between all node pairs.

Parameters:

Name Type Description Default
positions ndarray of shape (N, dim)
required
masses ndarray of shape (N,)
required
coefficient float(scalingRatio)
required

Returns:

Name Type Description
forces ndarray of shape (N, dim)
Source code in fa2/fa2util_vectorized.py 
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def apply_repulsion(positions, masses, coefficient):
    """Apply repulsion forces between all node pairs.

    Parameters
    ----------
    positions : ndarray of shape (N, dim)
    masses : ndarray of shape (N,)
    coefficient : float (scalingRatio)

    Returns
    -------
    forces : ndarray of shape (N, dim)
    """
    n = len(positions)
    if n < 2:
        return np.zeros_like(positions)

    # Pairwise differences: (N, N, dim)
    diff = positions[:, np.newaxis, :] - positions[np.newaxis, :, :]
    # Pairwise squared distances: (N, N)
    dist2 = np.sum(diff * diff, axis=2)

    # Avoid division by zero on diagonal and coincident nodes
    mass_prod = masses[:, np.newaxis] * masses[np.newaxis, :]
    # Guard: treat zero-distance pairs (diagonal + coincident) as 1.0 for division,
    # then zero out their factors so they contribute no force
    dist2_safe = np.where(dist2 > 0, dist2, 1.0)
    factors = coefficient * mass_prod / dist2_safe
    factors[dist2 == 0] = 0.0

    # Force vectors: (N, dim)
    forces = np.sum(diff * factors[:, :, np.newaxis], axis=1)
    return forces

apply_repulsion_adjustSizes 

apply_repulsion_adjustSizes(positions, masses, sizes, coefficient)

Apply anti-collision repulsion between all node pairs.

Source code in fa2/fa2util_vectorized.py 
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
def apply_repulsion_adjustSizes(positions, masses, sizes, coefficient):
    """Apply anti-collision repulsion between all node pairs."""
    n = len(positions)
    if n < 2:
        return np.zeros_like(positions)

    diff = positions[:, np.newaxis, :] - positions[np.newaxis, :, :]
    euclidean = np.sqrt(np.sum(diff * diff, axis=2))
    distance = euclidean - sizes[:, np.newaxis] - sizes[np.newaxis, :]
    mass_prod = masses[:, np.newaxis] * masses[np.newaxis, :]

    factors = np.zeros((n, n))
    # Non-overlapping (distance > 0 strictly to avoid division by zero at touching)
    mask_pos = (distance > 0) & (euclidean > 0)
    factors[mask_pos] = coefficient * mass_prod[mask_pos] / (distance[mask_pos] ** 2)
    # Overlapping or touching (distance <= 0)
    mask_neg = (distance <= 0) & (euclidean > 0)
    factors[mask_neg] = 100.0 * coefficient * mass_prod[mask_neg]
    np.fill_diagonal(factors, 0.0)

    forces = np.sum(diff * factors[:, :, np.newaxis], axis=1)
    return forces

apply_gravity 

apply_gravity(positions, masses, gravity, scalingRatio, useStrongGravity=False)

Apply gravitational forces toward origin.

Returns:

Name Type Description
forces ndarray of shape (N, dim)
Source code in fa2/fa2util_vectorized.py 
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
def apply_gravity(positions, masses, gravity, scalingRatio, useStrongGravity=False):
    """Apply gravitational forces toward origin.

    Returns
    -------
    forces : ndarray of shape (N, dim)
    """
    if useStrongGravity:
        # F = -coefficient * mass * gravity * pos (distance-independent)
        any_nonzero = np.any(positions != 0, axis=1)
        factors = np.where(any_nonzero, scalingRatio * masses * gravity, 0.0)
        return -positions * factors[:, np.newaxis]
    else:
        # F = -mass * gravity * pos / distance
        dist = np.sqrt(np.sum(positions * positions, axis=1))
        factors = np.zeros_like(dist)
        mask = dist > 0
        factors[mask] = masses[mask] * gravity / dist[mask]
        return -positions * factors[:, np.newaxis]

apply_attraction 

apply_attraction(positions, edge_sources, edge_targets, edge_weights, masses, distributedAttraction, coefficient, edgeWeightInfluence, linLogMode=False, adjustSizes=False, sizes=None)

Apply attraction forces along all edges.

Parameters:

Name Type Description Default
positions ndarray of shape (N, dim)
required
edge_sources ndarray of shape (M,), int
required
edge_targets ndarray of shape (M,), int
required
edge_weights ndarray of shape (M,)
required
masses ndarray of shape (N,)
required
distributedAttraction bool
required
coefficient float
required
edgeWeightInfluence float
required
linLogMode bool
False
adjustSizes bool
False
sizes ndarray of shape (N,) or None
None

Returns:

Name Type Description
forces ndarray of shape (N, dim)
Source code in fa2/fa2util_vectorized.py 
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
def apply_attraction(positions, edge_sources, edge_targets, edge_weights,
                     masses, distributedAttraction, coefficient,
                     edgeWeightInfluence, linLogMode=False, adjustSizes=False,
                     sizes=None):
    """Apply attraction forces along all edges.

    Parameters
    ----------
    positions : ndarray of shape (N, dim)
    edge_sources, edge_targets : ndarray of shape (M,), int
    edge_weights : ndarray of shape (M,)
    masses : ndarray of shape (N,)
    distributedAttraction : bool
    coefficient : float
    edgeWeightInfluence : float
    linLogMode : bool
    adjustSizes : bool
    sizes : ndarray of shape (N,) or None

    Returns
    -------
    forces : ndarray of shape (N, dim)
    """
    forces = np.zeros_like(positions)

    if len(edge_sources) == 0:
        return forces

    # Compute effective weights
    if edgeWeightInfluence == 0:
        w = np.ones(len(edge_weights))
    elif edgeWeightInfluence == 1:
        w = edge_weights
    else:
        w = np.power(edge_weights, edgeWeightInfluence)

    # Distance vectors along edges
    diff = positions[edge_sources] - positions[edge_targets]
    euclidean = np.sqrt(np.sum(diff * diff, axis=1))

    if adjustSizes and sizes is not None:
        distance = euclidean - sizes[edge_sources] - sizes[edge_targets]
        active = distance > 0
    else:
        active = np.ones(len(edge_sources), dtype=bool)
        distance = euclidean

    if linLogMode:
        # F = -coeff * w * log(1 + d) ā†’ factor = -coeff * w * log(1+d)/d
        safe_dist = np.where(active & (euclidean > 0), euclidean, 1.0)
        if adjustSizes and sizes is not None:
            safe_adj = np.where(active & (distance > 0), distance, 1.0)
            log_factor = np.log(1.0 + safe_adj) / safe_adj
        else:
            log_factor = np.log(1.0 + safe_dist) / safe_dist
        if distributedAttraction:
            factors = np.where(active & (euclidean > 0),
                               -coefficient * w * log_factor / masses[edge_sources], 0.0)
        else:
            factors = np.where(active & (euclidean > 0),
                               -coefficient * w * log_factor, 0.0)
    else:
        # F = -coeff * w * d ā†’ factor = -coeff * w
        if distributedAttraction:
            factors = np.where(active, -coefficient * w / masses[edge_sources], 0.0)
        else:
            factors = np.where(active, -coefficient * w, 0.0)

    # Apply forces to source and target nodes
    force_vecs = diff * factors[:, np.newaxis]
    np.add.at(forces, edge_sources, force_vecs)
    np.add.at(forces, edge_targets, -force_vecs)

    return forces

adjustSpeedAndApplyForces 

adjustSpeedAndApplyForces(positions, forces, old_forces, masses, speed, speedEfficiency, jitterTolerance, adjustSizes=False, sizes=None)

Adjust speed and apply forces to positions.

Returns:

Name Type Description
new_positions ndarray of shape (N, dim)
speed float
speedEfficiency float
Source code in fa2/fa2util_vectorized.py 
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
def adjustSpeedAndApplyForces(positions, forces, old_forces, masses, speed, speedEfficiency,
                              jitterTolerance, adjustSizes=False, sizes=None):
    """Adjust speed and apply forces to positions.

    Returns
    -------
    new_positions : ndarray of shape (N, dim)
    speed : float
    speedEfficiency : float
    """
    n = len(positions)

    # Swing and traction per node
    swing_vecs = old_forces - forces
    tract_vecs = old_forces + forces
    node_swinging = np.sqrt(np.sum(swing_vecs * swing_vecs, axis=1))
    node_traction = np.sqrt(np.sum(tract_vecs * tract_vecs, axis=1))

    totalSwinging = np.sum(masses * node_swinging)
    totalEffectiveTraction = 0.5 * np.sum(masses * node_traction)

    # Jitter tolerance
    estimatedOptimalJitterTolerance = 0.05 * np.sqrt(n)
    minJT = np.sqrt(estimatedOptimalJitterTolerance)
    maxJT = 10.0
    if n > 0 and totalEffectiveTraction > 0:
        jt = jitterTolerance * max(minJT,
                                   min(maxJT, estimatedOptimalJitterTolerance * totalEffectiveTraction / (n * n)))
    else:
        jt = jitterTolerance * minJT

    minSpeedEfficiency = 0.05

    if totalEffectiveTraction > 0 and totalSwinging / totalEffectiveTraction > 2.0:
        if speedEfficiency > minSpeedEfficiency:
            speedEfficiency *= 0.5
        jt = max(jt, jitterTolerance)

    if totalSwinging == 0:
        targetSpeed = float('inf')
    else:
        targetSpeed = jt * speedEfficiency * totalEffectiveTraction / totalSwinging

    if totalSwinging > jt * totalEffectiveTraction:
        if speedEfficiency > minSpeedEfficiency:
            speedEfficiency *= 0.7
    elif speed < 1000:
        speedEfficiency *= 1.3

    maxRise = 0.5
    speed = speed + min(targetSpeed - speed, maxRise * speed)

    # Per-node speed factors
    per_node_swing = masses * node_swinging
    per_node_factor = speed / (1.0 + np.sqrt(speed * per_node_swing))

    if adjustSizes and sizes is not None:
        max_factor = np.where(sizes > 0, 10.0 / sizes, per_node_factor)
        per_node_factor = np.minimum(per_node_factor, max_factor)

    new_positions = positions + forces * per_node_factor[:, np.newaxis]

    return new_positions, speed, speedEfficiency