Skip to content

Index

DelaunayGraph

Bases: PlanarGraphInterface

Class to hold Delaunay triangulation.

This will be the default class in use in this package. This will also be the only class that will interact with Minimum Cost Flow (MCF) solvers for irregular grids.

Source code in src/spurt/graph/_delaunay.py 
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
47
48
49
50
51
52
53
54
55
56
57
58
59
class DelaunayGraph(PlanarGraphInterface):
    """Class to hold Delaunay triangulation.

    This will be the default class in use in this package.
    This will also be the only class that will interact with
    Minimum Cost Flow (MCF) solvers for irregular grids.
    """

    def __init__(self, xy: np.ndarray, scaling: ArrayLike = (1, 1)):
        """Create Delaunay triangulation with given coordinates and scaling."""
        self._d: Delaunay = Delaunay(xy * scaling)
        assert self._d.npoints == len(xy), "Number of points mismatch"
        self._links: np.ndarray | None = None
        self._create_links()

    @property
    def npoints(self) -> int:
        return self._d.npoints

    @property
    def points(self) -> np.ndarray:
        return self._d.points

    @property
    def cycles(self) -> np.ndarray:
        return self._d.simplices

    @property
    def boundary(self) -> np.ndarray:
        return self._d.convex_hull

    def _create_links(self) -> None:
        arcs: set[tuple[int, int]] = set()
        for s in self.cycles:
            arcs.add(order_points((s[0], s[1])))
            arcs.add(order_points((s[0], s[2])))
            arcs.add(order_points((s[1], s[2])))
        self._links = np.array(sorted(arcs))

    @property
    def links(self) -> np.ndarray:
        return self._links

__init__(xy, scaling=(1, 1))

Create Delaunay triangulation with given coordinates and scaling.

Source code in src/spurt/graph/_delaunay.py 
26
27
28
29
30
31
def __init__(self, xy: np.ndarray, scaling: ArrayLike = (1, 1)):
    """Create Delaunay triangulation with given coordinates and scaling."""
    self._d: Delaunay = Delaunay(xy * scaling)
    assert self._d.npoints == len(xy), "Number of points mismatch"
    self._links: np.ndarray | None = None
    self._create_links()

GraphInterface

Bases: Protocol

Interface to 2D graph objects.

Such objects should provide access to points (nodes or vertices), links (arcs) and cycles (simplices).

Attributes:

Name Type Description
npoints int

Number of points/ vertices/ nodes.
points ndarray

(npoints, 2) array corresponding to locations of the points.
cycles list[list[int]]

Each entry in the list represents one cycle in the graph.
links ndarray

(nlinks, 2) array. Each row contains indices into the points array.
Source code in src/spurt/graph/_interface.py 
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
47
48
49
@runtime_checkable
class GraphInterface(Protocol):
    """
    Interface to 2D graph objects.

    Such objects should provide access to points (nodes or vertices),
    links (arcs) and cycles (simplices).

    Attributes
    ----------
    npoints: int
        Number of points/ vertices/ nodes.
    points: np.ndarray
        (npoints, 2) array corresponding to locations of the points.
    cycles: list[list[int]]
        Each entry in the list represents one cycle in the graph.
    links: np.ndarray
        (nlinks, 2) array. Each row contains indices into the points array.
    """

    @property
    def npoints(self) -> int:
        """Return number of points in graph."""

    @property
    def points(self) -> np.ndarray:
        """Return points/ vertices/ nodes as (npts, 2)."""

    @property
    def cycles(self) -> np.ndarray | list[list[int]]:
        """Return cycles/ simplices as (nsimplex, ...)."""

    @property
    def links(self) -> np.ndarray:
        """Return list of links/ arcs in the graph as (nlinks, 2)."""

cycles property

Return cycles/ simplices as (nsimplex, ...).

Return list of links/ arcs in the graph as (nlinks, 2).

npoints property

Return number of points in graph.

points property

Return points/ vertices/ nodes as (npts, 2).

Hop3Graph

Bases: PlanarGraphInterface

Class to hold Hop-3 planar graph.

This will be a useful class for missions like Sentinel-1 with narrow baseline tube and when one wants to restrict the interferogram network based on temporal baseline alone.

Source code in src/spurt/graph/_hop3.py 
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class Hop3Graph(PlanarGraphInterface):
    """Class to hold Hop-3 planar graph.

    This will be a useful class for missions like Sentinel-1
    with narrow baseline tube and when one wants to restrict the
    interferogram network based on temporal baseline alone.
    """

    def __init__(self, npoints: int):
        """Create triangulation for N points and 3 hops."""
        if npoints < 4:
            errmsg = (
                f"Atleast 4 points are needed to build a 3-hop graph. Got {npoints}"
            )
            raise ValueError(errmsg)

        # Create the points as a colinear set
        self._xy: np.ndarray = np.zeros((npoints, 2), dtype=int)
        self._xy[:, 0] = np.arange(npoints, dtype=int)

        # Initialize to none
        self._cycles: np.ndarray | None = None
        self._links: np.ndarray | None = None
        self._create_cycles_and_links()

    @property
    def npoints(self) -> int:
        return self._xy.shape[0]

    @property
    def points(self) -> np.ndarray:
        return self._xy

    @property
    def cycles(self) -> np.ndarray:
        return self._cycles

    @property
    def boundary(self) -> np.ndarray:
        return np.array([[0, 1], [1, 3], [3, 0]])

    def _create_cycles_and_links(self) -> None:
        arcs: set[tuple[int, int]] = set()

        # Set size of cycles
        ncycles = 3 + (self.npoints - 4) * 2
        nlinks = 3 * self.npoints - 6
        self._cycles = np.zeros((ncycles, 3), dtype=int)

        # Initialization for first point is fixed
        self._cycles[0, :] = [0, 1, 2]
        self._cycles[1, :] = [0, 2, 3]

        for ii in range(1, self.npoints - 3):
            self._cycles[2 * ii, :] = [ii, ii + 2, ii + 3]
            self._cycles[2 * ii + 1, :] = [ii, ii + 3, ii + 1]

        # Last cycle is fixed
        self._cycles[-1, :] = [self.npoints - 3, self.npoints - 1, self.npoints - 2]

        # Set the links
        for s in self.cycles:
            arcs.add(order_points((s[0], s[1])))
            arcs.add(order_points((s[0], s[2])))
            arcs.add(order_points((s[1], s[2])))
        self._links = np.array(sorted(arcs))
        assert self._links.shape[0] == nlinks, "Not all links captured"

    @property
    def links(self) -> np.ndarray:
        return self._links

__init__(npoints)

Create triangulation for N points and 3 hops.

Source code in src/spurt/graph/_hop3.py 
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def __init__(self, npoints: int):
    """Create triangulation for N points and 3 hops."""
    if npoints < 4:
        errmsg = (
            f"Atleast 4 points are needed to build a 3-hop graph. Got {npoints}"
        )
        raise ValueError(errmsg)

    # Create the points as a colinear set
    self._xy: np.ndarray = np.zeros((npoints, 2), dtype=int)
    self._xy[:, 0] = np.arange(npoints, dtype=int)

    # Initialize to none
    self._cycles: np.ndarray | None = None
    self._links: np.ndarray | None = None
    self._create_cycles_and_links()

PlanarGraphInterface

Bases: GraphInterface, Protocol

Interface to a 2D planar graph.

This provides an additional access to the boundary (convex_hull) of the graph. This class is specifically meant for use with MCF solvers and will provide a common interface for Regular 2D grids and Delaunay triangulations. The following assumptions are made regarding our interface for ease of use with MCF solvers: - The graph is connected. - Every edge is a part of one or two cycles utmost. - The links are always oriented from lower index into the points array to the higher index. - The cycles are all oriented in a single direction - either clockwise or anti-clockwise. - All the cycles returned by the interface are of the same length.

Source code in src/spurt/graph/_interface.py 
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
@runtime_checkable
class PlanarGraphInterface(GraphInterface, Protocol):
    """
    Interface to a 2D planar graph.

    This provides an additional access to the boundary (convex_hull) of the
    graph. This class is specifically meant for use with MCF solvers and will
    provide a common interface for Regular 2D grids and Delaunay
    triangulations. The following assumptions are made regarding our interface
    for ease of use with MCF solvers:
        - The graph is connected.
        - Every edge is a part of one or two cycles utmost.
        - The links are always oriented from lower index into the points array
        to the higher index.
        - The cycles are all oriented in a single direction - either clockwise
        or anti-clockwise.
        - All the cycles returned by the interface are of the same length.
    """

    @property
    def cycles(self) -> np.ndarray:
        """Return cycles as ndarray as cycles are of same length.

        Since all cycles are assumed to be of equal length here, we can use an
        ndarray to be efficient.
        """

    @property
    def boundary(self) -> np.ndarray | list[list[int]]:
        """Return arcs in form of pair of vertices forming outer boundary of graph.

        This is only a utility and is not necessarily used in the MCF code.
        There is no concept of boundary for non-planar graphs.
        """

boundary property

Return arcs in form of pair of vertices forming outer boundary of graph.

This is only a utility and is not necessarily used in the MCF code. There is no concept of boundary for non-planar graphs.

cycles property

Return cycles as ndarray as cycles are of same length.

Since all cycles are assumed to be of equal length here, we can use an ndarray to be efficient.

Reg2DGraph

Bases: PlanarGraphInterface

Class to hold 2D regular grid.

This is a utility class to test MCF implementation against other regular 2D grid solvers. We will walk down the rows of the 2D grid to determine the order of points, links and cycles.

Source code in src/spurt/graph/_delaunay.py 
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 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
168
169
170
171
class Reg2DGraph(PlanarGraphInterface):
    """Class to hold 2D regular grid.

    This is a utility class to test MCF implementation against other
    regular 2D grid solvers. We will walk down the rows of the 2D grid
    to determine the order of points, links and cycles.
    """

    def __init__(self, shape: tuple[int, int]):
        """Create regular 2D graph of given shape."""
        self._shape = shape
        self._links: np.ndarray | None = None
        self._cycles: np.ndarray | None = None
        self._create_links()
        self._create_cycles()

    @property
    def npoints(self) -> int:
        return self._shape[0] * self._shape[1]

    @property
    def points(self) -> np.ndarray:
        """Return points in 2D grid.

        Points are returned in row-major order.
        """
        # We will just use indices here for position
        i, j = np.indices(self._shape).reshape(2, -1)
        return np.column_stack((j, i))

    def _create_cycles(self) -> None:
        """Return rectangular loops in 2D grid."""
        ncyc = self.npoints - self._shape[0] - self._shape[1] + 1
        cyc = np.zeros((ncyc, 4), dtype=int)

        ind = 0
        # Iterate over the loops for top-left corner of loop
        for ii in range(self._shape[0] - 1):
            for jj in range(self._shape[1] - 1):
                # cycles will go counter-clockwise like Delaunay
                # top-left -> bottom-left -> bottom-right -> top-right
                cyc[ind, :] = np.ravel_multi_index(
                    ((ii, ii + 1, ii + 1, ii), (jj, jj, jj + 1, jj + 1)), self._shape
                )
                ind += 1

        self._cycles = cyc

    @property
    def boundary(self) -> np.ndarray:
        """Return boundary edges in 2D grid."""
        narcs = 2 * (self._shape[0] + self._shape[1] - 2)
        arcs = np.zeros((narcs, 2), dtype=int)

        ind = 0
        # Walk along the top edge
        for ii in range(self._shape[1] - 1):
            arcs[ind, :] = (ii, ii + 1)
            ind += 1

        # Walk down the right edge
        for ii in range(self._shape[0] - 1):
            off = ii * self._shape[1] + self._shape[1] - 1
            arcs[ind, :] = (off, off + self._shape[1])
            ind += 1

        # Walk back along bottom edge
        for ii in range(self._shape[1] - 1, 0, -1):
            off = (self._shape[0] - 1) * self._shape[1]
            arcs[ind, :] = (off + ii - 1, off + ii)
            ind += 1

        # Walk back along left edge
        for ii in range(self._shape[0] - 1, 0, -1):
            off = ii * self._shape[1]
            arcs[ind, :] = (off - self._shape[1], off)
            ind += 1

        assert ind == narcs
        return arcs

    def _create_links(self) -> None:
        """Horizontal links followed by vertical links."""
        narcs = 2 * self.npoints - self._shape[0] - self._shape[1]
        arcs = np.zeros((narcs, 2), dtype=int)

        ind = 0
        # Start with horizontal links, iterate over the rows
        for ii in range(self._shape[0]):
            start = ii * self._shape[1] + np.arange(self._shape[1] - 1)
            arcs[ind : ind + start.size, 0] = start
            arcs[ind : ind + start.size, 1] = start + 1
            ind += start.size

        # Now include the vertical links, but walk along rows
        for ii in range(self._shape[0] - 1):
            start = ii * self._shape[1] + np.arange(self._shape[1])
            arcs[ind : ind + start.size, 0] = start
            arcs[ind : ind + start.size, 1] = start + self._shape[1]
            ind += start.size

        self._links = arcs

    @property
    def links(self) -> np.ndarray:
        return self._links

    @property
    def cycles(self) -> np.ndarray:
        return self._cycles

boundary property

Return boundary edges in 2D grid.

points property

Return points in 2D grid.

Points are returned in row-major order.

__init__(shape)

Create regular 2D graph of given shape.

Source code in src/spurt/graph/_delaunay.py 
70
71
72
73
74
75
76
def __init__(self, shape: tuple[int, int]):
    """Create regular 2D graph of given shape."""
    self._shape = shape
    self._links: np.ndarray | None = None
    self._cycles: np.ndarray | None = None
    self._create_links()
    self._create_cycles()

graph_laplacian(graph)

Compute the graph Laplacian.

Source code in src/spurt/graph/utils.py 
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def graph_laplacian(graph: GraphInterface) -> csc_matrix:
    """Compute the graph Laplacian."""
    links = graph.links
    nlinks = len(links)
    data = np.ones(2 * nlinks, dtype=int)
    data[0::2] = -1

    # Build the incidence matrix of the graph:
    # Columns represent nodes, rows represent links (edges)
    # Each row has one -1 and one +1 for the source/dest node index
    row_indices = np.arange(2 * nlinks, dtype=int) // 2
    col_indices = links.flatten()
    amat = csr_matrix((data, (row_indices, col_indices)))

    return amat.T.dot(amat)

order_points(p)

Order points/nodes/vertices by index.

Given a pair of numbers, return a 2-tuple so the first is lower. The use case is that the pair contains pairs of indices representing undirected links, where (a, b) is the same as (b, a). This ordering, and returning a tuple allows us to comparison with ==.

Parameters:

Name Type Description Default
p array - like[2]

Data to be ordered, must be comparable.

 required

Returns:

Type Description
(int, int) : Ordered 2-tuple.
Source code in src/spurt/graph/utils.py 
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def order_points(p: tuple[int, int]) -> tuple[int, int]:
    """Order points/nodes/vertices by index.

    Given a pair of numbers, return a 2-tuple so the first is lower. The use
    case is that the pair contains pairs of indices representing undirected
    links, where (a, b) is the same as (b, a). This ordering, and returning
    a tuple allows us to comparison with ==.

    Parameters
    ----------
    p : array-like[2]
        Data to be ordered, must be comparable.

    Returns
    -------
    (int, int) : Ordered 2-tuple.
    """
    if p[0] <= p[1]:
        return (p[0], p[1])
    return (p[1], p[0])