BUG: Fix Graph Functions (#283)

- Fix some issues in graph.py 1. Fix typos in docstrings. 2. Fix typo in function name triangle -> triangle 3. Fix a bug in graph visualization where some edges would not be drawn. Some other things have been fixed as they were discovered during this PR: 1. Fix a bug in function to convert edge index to triangles (it would find the same triangle twice in a different order). 2. Add tests. Co-authored-by: John Pocock <John-P@users.noreply.github.com> Co-authored-by: Shan Raza <13048456+shaneahmed@users.noreply.github.com> Co-authored-by: Dang Vu <24943262+vqdang@users.noreply.github.com>
shaneahmed · May 5, 2023 · Feb 1, 2022 · Feb 2, 2022 · Feb 2, 2022 · Feb 7, 2022
commit fbce1b75dacd0dffbe4acb306cfd22574ea7e813
diff --git a/tests/test_graph.py b/tests/test_graph.py
@@ -10,7 +10,7 @@
     affinity_to_edge_index,
     delaunay_adjacency,
     edge_index_to_triangles,
-    traingle_signed_area,
+    triangle_signed_area,
 )
 
 
@@ -92,7 +92,7 @@ def test_affinity_to_edge_index_fuzz_output_shape():
         n = len(affinity_matrix)
         two, m = edge_index.shape
         assert two == 2
-        assert 0 <= m <= n ** 2
+        assert 0 <= m <= n**2
 
 
 def test_affinity_to_edge_index_invalid_fuzz_input_shape():
@@ -118,34 +118,68 @@ def test_edge_index_to_triangles_invalid_input():
         edge_index_to_triangles(edge_index)
 
 
-def test_traingle_signed_area():
+def test_triangle_signed_area():
     """Test that the signed area of a triangle is correct."""
     # Triangle with positive area
     points = np.array([[0, 0], [1, 0], [0, 1]])
-    area = traingle_signed_area(points)
+    area = triangle_signed_area(points)
     assert area == 0.5
 
     # Triangle with negative area
     points = np.array([[0, 0], [1, 0], [0, -1]])
-    area = traingle_signed_area(points)
+    area = triangle_signed_area(points)
     assert area == -0.5
 
     # Triangle with co-linear points
     points = np.array([[0, 0], [1, 1], [2, 2]])
-    area = traingle_signed_area(points)
+    area = triangle_signed_area(points)
     assert area == 0
 
     # Triangle with larger area
     points = np.array([[0, 0], [2, 0], [0, 2]])
-    area = traingle_signed_area(points)
+    area = triangle_signed_area(points)
     assert area == 2
 
 
-def test_traingle_signed_area_invalid_input():
+def test_triangle_signed_area_invalid_input():
     """Test that the signed area of a triangle with invalid input fails."""
     points = np.random.rand(3, 3)
     with pytest.raises(ValueError, match="3x2"):
-        traingle_signed_area(points)
+        triangle_signed_area(points)
+
+
+def test_edge_index_to_trainangles_single():
+    """Test edge_index_to_triangles with a simple 2XM input matrix.
+
+    Basic test case for a single triangle.
+
+    0 -- 1
+    |   /
+    | /
+    2
+    """
+    edge_index = np.array([[0, 1], [0, 2], [1, 2]]).T
+    triangles = edge_index_to_triangles(edge_index)
+    assert triangles.shape == (1, 3)
+    assert np.array_equal(triangles, np.array([[0, 1, 2]]))
+
+
+def test_edge_index_to_trainangles_many():
+    """Test edge_index_to_triangles with a simple 2XM input matrix.
+
+    Moderate test case for a few trainangles.
+
+    4 -- 3
+    |  / |
+    |/   |
+    0 -- 1
+    |   /
+    | /
+    2
+    """
+    edge_index = np.array([[0, 1], [0, 2], [1, 2], [0, 3], [1, 3], [0, 4], [4, 3]]).T
+    triangles = edge_index_to_triangles(edge_index)
+    assert triangles.shape == (3, 3)
 
 
 def pytest_generate_tests(metafunc):
@@ -210,7 +244,7 @@ def test_build(graph_constructor):
         two, m = edge_index.shape
         n = len(x)
         assert two == 2
-        assert 0 <= m <= n ** 2
+        assert 0 <= m <= n**2
 
     @staticmethod
     def test_visualise(graph_constructor):
@@ -279,5 +313,5 @@ def test_visualise_invalid_input(graph_constructor):
             graph_constructor.visualise({})
         with pytest.raises(ValueError, match="must contain edge_index"):
             graph_constructor.visualise({"x": []})
-        with pytest.raises(ValueError, match="must contain coords"):
+        with pytest.raises(ValueError, match="must contain coordinates"):
             graph_constructor.visualise({"x": [], "edge_index": []})
diff --git a/tiatoolbox/tools/graph.py b/tiatoolbox/tools/graph.py
@@ -95,14 +95,14 @@ def delaunay_adjacency(points: ArrayLike, dthresh: Number) -> list:
     return adjacency
 
 
-def traingle_signed_area(triangle: ArrayLike) -> int:
+def triangle_signed_area(triangle: ArrayLike) -> int:
     """Determine the signed area of a triangle.
 
     Args:
         triangle (ArrayLike): A 3x2 list of coordinates.
 
     Returns:
-        int: The signed area of the triange. It will be negative if
+        int: The signed area of the triangle. It will be negative if
              the triangle has a clockwise winding, negative if the
              triangle has a counter-clockwise winding, and zero if the
              triangles points are collinear.
@@ -121,7 +121,7 @@ def traingle_signed_area(triangle: ArrayLike) -> int:
 
 
 def edge_index_to_triangles(edge_index: ArrayLike) -> ArrayLike:
-    """Convert an edged index to traingle simplices.
+    """Convert an edged index to triangle simplices (triplets of coordinate indices).
 
     Args:
         edge_index (ArrayLike):
@@ -151,13 +151,13 @@ def edge_index_to_triangles(edge_index: ArrayLike) -> ArrayLike:
     # Remove any nodes with less than two neighbours
     nodes = [node for node in nodes if len(neighbours[node]) >= 2]
     # Find the triangles
-    triangles = []
+    triangles = set()
     for node in nodes:
         for neighbour in neighbours[node]:
             overlap = neighbours[node].intersection(neighbours[neighbour])
             while overlap:
-                triangles.append([node, neighbour, overlap.pop()])
-    return np.array(triangles, dtype=np.int32, order="C")
+                triangles.add(frozenset({node, neighbour, overlap.pop()}))
+    return np.array([list(tri) for tri in triangles], dtype=np.int32, order="C")
 
 
 def affinity_to_edge_index(
@@ -217,7 +217,7 @@ def _umap_reducer(graph: Dict[str, ArrayLike]) -> ArrayLike:
         Args:
             graph (dict):
                 A graph with keys "x", "edge_index", and optionally
-                "coords".
+                "coordinates".
         Returns:
             ArrayLike: A UMAP embedding of `graph["x"]` with shape (N, 3)
                 and values ranging from 0 to 1.
@@ -241,7 +241,7 @@ def build(
     ) -> Dict[str, ArrayLike]:
         """Build a graph via hybrid clustering in spatial and feature space.
 
-        The graph is constructed via hybrid heirachical clustering followed
+        The graph is constructed via hybrid hierarchical clustering followed
         by Delaunay triangulation of these cluster centroids.
         This is part of the SlideGraph pipeline but may be used to construct
         a graph in general from point coordinates and features.
@@ -254,7 +254,7 @@ def build(
         Points which are spatially further apart than
         `neighbour_search_radius` are given a similarity of 1 (most
         dissimilar). This significantly speeds up computation. This distance
-        metric is then used to form clusters via hierachical/agglomerative
+        metric is then used to form clusters via hierarchical/agglomerative
         clustering.
 
         Next, a Delaunay triangulation is applied to the clusters to connect
@@ -283,7 +283,7 @@ def build(
             feature_range_thresh (Number):
                 Minimal range for which a feature is considered significant.
                 Features which have a range less than this are ignored.
-                Defaults to 1e-4. If falsey (None, False, 0, etc.), then
+                Defaults to 1e-4. If falsy (None, False, 0, etc.), then
                 no features are removed.
 
         Returns:
@@ -319,8 +319,8 @@ def build(
 
         # Build a kd-tree and rank neighbours according to the euclidean
         # distance (nearest -> farthest).
-        ckdtree = cKDTree(points)
-        neighbour_distances_ckd, neighbour_indexes_ckd = ckdtree.query(
+        kd_tree = cKDTree(points)
+        neighbour_distances_ckd, neighbour_indexes_ckd = kd_tree.query(
             x=points, k=len(points)
         )
 
@@ -396,7 +396,7 @@ def build(
         return {
             "x": feature_centroids,
             "edge_index": edge_index,
-            "coords": point_centroids,
+            "coordinates": point_centroids,
         }
 
     @classmethod
@@ -411,7 +411,7 @@ def visualise(
         """Visualise a graph.
 
         The visualisation is a scatter plot of the graph nodes
-        and the connections bneewn them. By default, nodes are coloured
+        and the connections between them. By default, nodes are coloured
         according to the features of the graph via a UMAP embedding to
         the sRGB color space. This can be customised by passing a color
         argument which can be a single color, a list of colors, or a
@@ -428,7 +428,7 @@ def visualise(
                     - :class:`numpy.ndarray` - edge_index:
                         Edge index matrix defining connectivity.
                         Required
-                    - :class:`numpy.ndarray` - coords:
+                    - :class:`numpy.ndarray` - coordinates:
                         Coordinates of each node within the WSI (mean of point
                         in a cluster).
                         Required
@@ -464,35 +464,36 @@ def visualise(
             >>> plt.show()
 
         """
+        from matplotlib import collections as mc
+
         # Check that the graph is valid
         if "x" not in graph:
             raise ValueError("Graph must contain x")
         if "edge_index" not in graph:
             raise ValueError("Graph must contain edge_index")
-        if "coords" not in graph:
-            raise ValueError("Graph must contain coords")
+        if "coordinates" not in graph:
+            raise ValueError("Graph must contain coordinates")
         if ax is None:
             _, ax = plt.subplots()
         if color is None:
             color = cls._umap_reducer
 
+        nodes = graph["coordinates"]
+        edges = graph["edge_index"]
+
         # Plot the edges
-        triangles = edge_index_to_triangles(graph["edge_index"])
-        # Ensure triangles are counter-clockwise
-        for i, tri in enumerate(triangles):
-            if traingle_signed_area(graph["coords"][tri]) < 0:
-                triangles[i] = triangles[i][::-1]
-        ax.triplot(
-            graph["coords"][:, 0], graph["coords"][:, 1], triangles, color=edge_color
+        line_segments = nodes[edges.T]
+        edge_collection = mc.LineCollection(
+            line_segments, colors=edge_color, linewidths=1
         )
+        ax.add_collection(edge_collection)
 
         # Plot the nodes
-        ax.scatter(
-            graph["coords"][:, 0],
-            graph["coords"][:, 1],
+        plt.scatter(
+            *nodes.T,
             c=color(graph) if isinstance(color, Callable) else color,
             s=node_size(graph) if isinstance(node_size, Callable) else node_size,
-            zorder=1,
+            zorder=2,
         )
 
         return ax