pyrox.dev
1from toolz import curried as tlz
2from toolz import curry
3
4from .lib import (
5 debug,
6 debug_plot,
7 DEBUG_PLOT,
8 find_vertex_by_name_or_none,
9 graph_is_empty,
10 is_None,
11 subcomponent_multi,
12 unnest_iterable
13)
14
15
16@curry
17def coerce_to_singly_rooted_graph(fake_root_name, graph):
18 """Add single root to the graph connected to all existing roots.
19
20 If graph has only one root, return the graph unchanged and the name
21 of the root vertex.
22
23 Otherwise return a modified graph (copy) and a name of the added root
24 vertex.
25 """
26 roots = graph.vs.select(lambda v: len(graph.predecessors(v)) == 0)
27 root_names = roots["name"]
28
29 if len(root_names) == 1:
30 return graph, root_names[0]
31 else:
32 edges = [(fake_root_name, v) for v in root_names]
33 graph_with_root = graph + fake_root_name + edges
34 return graph_with_root, fake_root_name
35
36
37@curry
38def remove_vertex(vertex_name, graph):
39 """Remove vertex with given name, returning copy of input graph if vertex
40 with given name is found in the graph
41 """
42 vertex = find_vertex_by_name_or_none(graph)(vertex_name)
43
44 return graph - vertex_name if vertex else graph
45
46
47def get_children_of(graph, vertex_names):
48 return unnest_iterable(map(
49 graph.successors,
50 tlz.remove(
51 is_None,
52 map(
53 find_vertex_by_name_or_none(graph),
54 vertex_names
55 )
56 )
57 ))
58
59
60def as_list(x):
61 return x if isinstance(x, list) else [x]
62
63
64@curry
65def split_path_spec_to_indices(graph, split_path_spec):
66 debug("split_path_spec", split_path_spec)
67 if isinstance(split_path_spec, dict):
68 if "children_of" in split_path_spec:
69 children_of = split_path_spec["children_of"]
70
71 return get_children_of(graph, as_list(children_of))
72 else:
73 raise Exception(
74 "Unexpected split path spec: dict with invalid keys."
75 "Valid: [\"children_of\"]"
76 )
77 else:
78 vertex = find_vertex_by_name_or_none(graph)(split_path_spec)
79 return [] if is_None(vertex) else [vertex.index]
80
81
82call_count = 0
83
84
85@curry
86def split_paths(split_paths, graph_in):
87 debug("____")
88 debug("split_paths:", split_paths)
89 debug("graph_in:", graph_in)
90
91 if DEBUG_PLOT:
92 global call_count
93 graph_name_prefix = f"split_paths_{call_count}_"
94 call_count += 1
95
96 # Convert list of split_paths into list of vertex indices. Ignores
97 # split_paths which don"t match any vertices in the graph.
98 # All edges pointing at the indices will be deleted from the graph.
99 split_path_indices = list(unnest_iterable(map(
100 split_path_spec_to_indices(graph_in),
101 split_paths
102 )))
103
104 debug("split_path_indices:", split_path_indices)
105
106 # Short circuit if there is nothing to do (split_paths didn"t match any
107 # vertices in the graph).
108 if len(split_path_indices) == 0:
109 if DEBUG_PLOT:
110 layout = graph_in.layout('tree')
111 debug_plot(graph_in, f"{graph_name_prefix}input", layout=layout)
112 debug_plot(graph_in, f"{graph_name_prefix}result", layout=layout)
113
114 return {"rest": graph_in}
115
116 # If graph has multiple roots, add a single one connecting all existing
117 # roots to make it easy to split the graph into 2 sets of vertices after
118 # deleting edges pointing at split_path_indices.
119 fake_root_name = "__root__"
120 graph, root_name = coerce_to_singly_rooted_graph(fake_root_name, graph_in)
121
122 debug("root_name", root_name)
123
124 if (
125 find_vertex_by_name_or_none(graph)(root_name).index
126 in split_path_indices
127 ):
128 if DEBUG_PLOT:
129 layout = graph_in.layout('tree')
130 debug_plot(graph_in, f"{graph_name_prefix}input", layout=layout)
131 debug_plot(
132 graph_in,
133 f"{graph_name_prefix}result",
134 layout=layout,
135 vertex_color="green"
136 )
137
138 return {"main": graph_in}
139
140 # Copy graph if coerce_to_singly_rooted_graph has not already created
141 # a copy, since we are going to mutate the graph and don"t want to
142 # mutate a function argument.
143 graph = graph if graph is not graph_in else graph.copy()
144
145 if DEBUG_PLOT:
146 layout = graph.layout('tree')
147 debug_plot(graph, f"{graph_name_prefix}input", layout=layout)
148
149 # Get incidences of all vertices which can be reached split_path_indices
150 # (including split_path_indices). This is a set of all split_paths and their
151 # dependencies.
152 split_off_vertex_indices = frozenset(
153 subcomponent_multi(graph, split_path_indices))
154 debug("split_off_vertex_indices", split_off_vertex_indices)
155
156 # Delete edges which point at any of the vertices in split_path_indices.
157 graph.delete_edges(_target_in=split_path_indices)
158
159 if DEBUG_PLOT:
160 debug_plot(graph, f"{graph_name_prefix}deleted_edges", layout=layout)
161
162 # Get incidences of all vertices which can be reached from the root. Since
163 # edges pointing at split_path_indices have been deleted, none of the
164 # split_path_indices will be included. Dependencies of rest_with_common will
165 # only be included if they can be reached from any vertex which is itself
166 # not in split_off_vertex_indices.
167 rest_with_common = frozenset(graph.subcomponent(root_name, mode="out"))
168 debug("rest_with_common", rest_with_common)
169
170 # Get a set of all dependencies common to split_path_indices and the rest
171 # of the graph.
172 common = split_off_vertex_indices.intersection(rest_with_common)
173 debug("common", common)
174
175 # Get a set of vertices which cannot be reached from split_path_indices.
176 rest_without_common = rest_with_common.difference(common)
177 debug("rest_without_common", rest_without_common)
178
179 # Get a set of split_path_indices and their dependencies which cannot be
180 # reached from the rest of the graph.
181 split_off_without_common = split_off_vertex_indices.difference(common)
182 debug("split_off_without_common", split_off_without_common)
183
184 if DEBUG_PLOT:
185 def choose_color(index):
186 if (index in split_off_without_common):
187 return "green"
188 elif (index in rest_without_common):
189 return "red"
190 else:
191 return "purple"
192
193 vertex_color = [choose_color(v.index) for v in graph.vs]
194
195 debug_plot(
196 graph,
197 f"{graph_name_prefix}result",
198 layout=layout,
199 vertex_color=vertex_color
200 )
201
202 # Return subgraphs based on calculated sets of vertices.
203
204 result_keys = ["main", "common", "rest"]
205 result_values = [
206 # Split paths and their deps (unreachable from rest of the graph).
207 graph.induced_subgraph(split_off_without_common),
208 # Dependencies of split paths which can be reached from the rest of the
209 # graph.
210 graph.induced_subgraph(common),
211 # Rest of the graph (without dependencies common with split paths).
212 graph.induced_subgraph(rest_without_common),
213 ]
214
215 debug('result_values', result_values[0].vs["name"])
216
217 return tlz.valfilter(
218 tlz.complement(graph_is_empty),
219 dict(zip(
220 result_keys,
221 (
222 result_values if root_name != fake_root_name
223 # If root was added, remove it
224 else tlz.map(remove_vertex(fake_root_name), result_values)
225 )
226 ))
227 )