simetri.helpers.graph

  1"""Graph related functions and classes. Uses NetworkX for graph operations."""
  2
  3from dataclasses import dataclass
  4from typing import Sequence
  5
  6import networkx as nx
  7
  8from ..graphics.common import common_properties, Point
  9from ..graphics.all_enums import Types
 10from ..settings.settings import defaults
 11from ..geometry.geometry import distance, close_points2
 12
 13
 14@dataclass
 15class GraphEdge:
 16    """Edge in a graph. It has a start and end point as nodes."""
 17
 18    start: Point
 19    end: Point
 20
 21    def __post_init__(self):
 22        """Initialize the GraphEdge with start and end points."""
 23        self.length = distance(self.start.pos, self.end.pos)
 24        common_properties(self)
 25
 26    @property
 27    def nodes(self):
 28        """Return the start and end nodes of the edge."""
 29        return (self.start, self.end)
 30
 31
 32def edges2nodes(edges: Sequence[Sequence]) -> Sequence:
 33    """
 34    Given a list of edges, return a connected list of nodes.
 35
 36    Args:
 37        edges (Sequence[Sequence]): List of edges.
 38
 39    Returns:
 40        Sequence: Connected list of nodes.
 41    """
 42    chain = longest_chain(edges)
 43    closed = chain[0][0] == chain[-1][-1]
 44    if closed:
 45        nodes = [x[0] for x in chain[:-1]]
 46    else:
 47        nodes = [x[0] for x in chain] + [chain[-1][1]]
 48    if closed:
 49        last_edge = chain[-1]
 50        if last_edge[1] == nodes[-1]:
 51            nodes.extend(reversed(last_edge))
 52        elif last_edge[0] == nodes[-1]:
 53            nodes.extend(last_edge)
 54        elif last_edge[0] == nodes[0]:
 55            nodes.extend(reversed(last_edge))
 56        elif last_edge[1] == nodes[0]:
 57            nodes.extend(last_edge)
 58
 59    return nodes
 60
 61
 62def get_cycles(edges: Sequence[GraphEdge]) -> Sequence[GraphEdge]:
 63    """
 64    Computes all the cycles in a given graph of edges.
 65
 66    Args:
 67        edges (Sequence[GraphEdge]): List of graph edges.
 68
 69    Returns:
 70        Sequence[GraphEdge]: List of cycles if any cycle is found, None otherwise.
 71    """
 72    nx_graph = nx.Graph()
 73    nx_graph.add_edges_from(edges)
 74    cycles = nx.cycle_basis(nx_graph)
 75    res = None
 76    if cycles:
 77        for cycle in cycles:
 78            cycle.append(cycle[0])
 79
 80        res = cycles
 81    return res
 82
 83
 84# find all open paths starting from a given node
 85def find_all_paths(graph, node):
 86    """
 87    Find all paths starting from a given node.
 88
 89    Args:
 90        graph (nx.Graph): The graph.
 91        node: The starting node.
 92
 93    Returns:
 94        List: All paths starting from the given node.
 95    """
 96    paths = []
 97    for node_ in graph.nodes():
 98        for path in nx.all_simple_paths(graph, node, node_):
 99            if len(path) > 1:
100                paths.append(path)
101    return paths
102
103
104def is_open_walk2(graph, island):
105    """
106    Given a NetworkX Graph and an island, return True if the given island is an open walk.
107
108    Args:
109        graph (nx.Graph): The graph.
110        island: The island.
111
112    Returns:
113        bool: True if the island is an open walk, False otherwise.
114    """
115    degrees = [graph.degree(node) for node in island]
116    return set(degrees) == {1, 2} and degrees.count(1) == 2
117
118
119def longest_chain(edges: Sequence[Sequence]) -> Sequence:
120    """
121    Given a list of graph edges, return a list of connected nodes.
122
123    Args:
124        edges (Sequence[Sequence]): List of graph edges.
125
126    Returns:
127        Sequence: List of connected nodes.
128    """
129
130    def add_edge(edge, chain, index, processed):
131        nonlocal no_change
132        if index == 0:
133            chain.insert(0, edge)
134        elif index == -1:
135            chain.append(edge)
136        processed.append(set(edge))
137        no_change = False
138
139    chain = []
140    processed = []
141    while len(chain) < len(edges):
142        no_change = True
143        for edge in edges:
144            if set(edge) in processed:
145                continue
146            if not chain:
147                add_edge(edge, chain, -1, processed)
148            else:
149                if edge[0] == chain[-1][1]:
150                    add_edge(edge, chain, -1, processed)
151                elif edge[0] == chain[0][0]:
152                    add_edge((edge[1], edge[0]), chain, 0, processed)
153                elif edge[1] == chain[0][0]:
154                    add_edge(edge, chain, 0, processed)
155                elif edge[1] == chain[-1][1]:
156                    add_edge((edge[1], edge[0]), chain, -1, processed)
157        if no_change:
158            break
159    return chain
160
161
162def is_cycle(graph: nx.Graph, island: Sequence) -> bool:
163    """
164    Given a NetworkX Graph and an island, return True if the given island is a cycle.
165
166    Args:
167        graph (nx.Graph): The graph.
168        island (Sequence): The island.
169
170    Returns:
171        bool: True if the island is a cycle, False otherwise.
172    """
173    degrees = [graph.degree(node) for node in island]
174    return set(degrees) == {2}
175
176
177def is_open_walk(graph: nx.Graph, island: Sequence) -> bool:
178    """
179    Given a NetworkX Graph and an island, return True if the given island is an open walk.
180
181    Args:
182        graph (nx.Graph): The graph.
183        island (Sequence): The island.
184
185    Returns:
186        bool: True if the island is an open walk, False otherwise.
187    """
188    if len(island) == 2:
189        return True
190    degrees = [graph.degree(node) for node in island]
191    return set(degrees) == {1, 2} and degrees.count(1) == 2
192
193
194def graph_summary(graph: nx.Graph) -> str:
195    """
196    Return a summary of a graph including cycles, open walks and degenerate nodes.
197
198    Args:
199        graph (nx.Graph): The graph.
200
201    Returns:
202        str: Summary of the graph.
203    """
204    lines = []
205    for island in nx.connected_components(graph):
206        if len(island) > 8:
207            island = list(island)
208            lines.append(f"Island: {island[:4]}, ... , {island[-4:]}")
209        else:
210            lines.append(f"Island: {island}")
211        if is_cycle(graph, island):
212            lines.append(f"Cycle: {len(island)} nodes")
213        elif is_open_walk(graph, island):
214            lines.append(f"Open Walk: {len(island)} nodes")
215        else:
216            degenerates = [node for node in island if graph.degree(node) > 2]
217            degrees = f"{[(node, graph.degree(node)) for node in degenerates]}"
218            lines.append(f"Degenerate: {len(island)} nodes")
219            lines.append(f"(Node, Degree): {degrees}")
220        lines.append("-" * 40)
221    return "\n".join(lines)
222
223
224@dataclass
225class Node:
226    """
227    A Node object is a 2D point with x and y coordinates.
228    Used in graphs corresponding to shapes and batches.
229
230    Attributes:
231        x (float): X coordinate.
232        y (float): Y coordinate.
233    """
234
235    x: float
236    y: float
237
238    def __post_init__(self):
239        """Initialize the Node with x and y coordinates."""
240        common_properties(self)
241
242    @property
243    def pos(self):
244        """Return the position of the node."""
245        return (self.x, self.y)
246
247    def __eq__(self, other: object) -> bool:
248        """
249        Check if two nodes are equal.
250
251        Args:
252            other (object): The other node.
253
254        Returns:
255            bool: True if the nodes are equal, False otherwise.
256        """
257        return close_points2(self.pos, other.pos, dist2=defaults["dist_tol"] ** 2)
258
259
260@dataclass
261class Graph:
262    """
263    A Graph object is a collection of nodes and edges.
264
265    Attributes:
266        type (Types): The type of the graph.
267        subtype (Types): The subtype of the graph.
268        nx_graph (nx.Graph): The NetworkX graph object.
269    """
270
271    type: Types = "undirected"
272    subtype: Types = "none"  # this can be Types.WEIGHTED
273    nx_graph: "nx.Graph" = None
274
275    def __post_init__(self):
276        """Initialize the Graph with type and subtype."""
277        common_properties(self)
278
279    @property
280    def islands(self):
281        """
282        Return a list of all islands both cyclic and acyclic.
283
284        Returns:
285            List: List of all islands.
286        """
287        return [
288            list(island) for island in self.nx_graph.connected_components(self.nx_graph)
289        ]
290
291    @property
292    def cycles(self):
293        """
294        Return a list of cycles.
295
296        Returns:
297            List: List of cycles.
298        """
299        return nx.cycle_basis(self.nx_graph)
300
301    @property
302    def open_walks(self):
303        """
304        Return a list of open walks (aka open chains).
305
306        Returns:
307            List: List of open walks.
308        """
309        res = []
310        for island in self.islands:
311            if is_open_walk(self.nx_graph, island):
312                res.append(island)
313        return res
314
315    @property
316    def edges(self):
317        """
318        Return the edges of the graph.
319
320        Returns:
321            EdgeView: Edges of the graph.
322        """
323        return self.nx_graph.edges
324
325    @property
326    def nodes(self):
327        """
328        Return the nodes of the graph.
329
330        Returns:
331            NodeView: Nodes of the graph.
332        """
333        return self.nx_graph.nodes