def __validate_coloring(self):
log.debug("validating red-blue coloring; this could take a while (forever) if your graph is too big")
# All red paths to a vertex should be disjoint from all blue paths
# to the same vertex, except for red-blue links and their incident nodes
red_dag = self.get_red_graph()
blue_dag = self.get_blue_graph()
source = self.root
for dst in self.graph.nodes():
if dst == source:
continue
red_paths = list(nx.all_simple_paths(red_dag, source, dst))
red_nodes = set(n for p in red_paths for n in p)
red_edges = set(e for p in red_paths for e in zip(p, p[1:]))
blue_paths = list(nx.all_simple_paths(blue_dag, source, dst))
blue_nodes = set(n for p in blue_paths for n in p)
blue_edges = set(e for p in blue_paths for e in zip(p, p[1:]))
redblue_edges = red_edges.intersection(blue_edges)
redblue_nodes = red_nodes.intersection(blue_nodes)
redblue_nodes.remove(source)
redblue_nodes.remove(dst)
assert all(self._get_edge_color(e) == 'red-blue' for e in redblue_edges),\
"invalid coloring: non cut link shared by red and blue paths!"
# every shared node has at least one incident cut link
# TODO: finish this? unclear it's necessary as it just validates consistency of coloring not actual correctness of properties
# assert all(any(self._get_edge_color(e) == 'red-blue' for e in
# list(self.graph.successors(n)) + list(self.graph.predecessors(n)))
# for n in redblue_nodes), "invalid coloring of nodes: shares a non-cut node!"
# verify each red-blue edge or node is a cut edge/node
for cut_node in redblue_nodes:
g = self.graph.subgraph(n for n in self.graph.nodes() if n != cut_node)
# could induce an empty (or near-empty) graph
if source not in g or dst not in g:
continue
assert not nx.has_path(g, source, dst), "invalid coloring: non cut node shared by red and blue paths!"
for cut_link in redblue_edges:
g = self.graph.edge_subgraph(e for e in self.graph.edges() if e != cut_link)
# could induce an empty (or near-empty) graph
if source not in g or dst not in g:
continue
assert not nx.has_path(g, source, dst), "invalid coloring: non cut link shared by red and blue paths!"
# draw_overlaid_graphs(self.graph, [red_dag, blue_dag])
return True
评论列表
文章目录
