-
Allen, Bruce (CIV) authoredAllen, Bruce (CIV) authored
graph_collapse_helpers.py 4.72 KiB
"""Provides services:
collapse_below(node): collapse_below starting at the given node
uncollapse_below(node): uncollapse at and below node
at_and_below_in(node): for selecting all IN nodes at and below node
at_and_above_in_uncollapsed(node): for selecting all IN nodes at and above node
"""
# A node's parent IN nodes
def _parent_in_nodes(node):
parents = list()
for edge in node.edge_list:
if edge.dest_node == node and edge.relation == "IN":
parents.append(edge.source_node)
return parents
# A node's child IN nodes
def _child_in_nodes(node):
children = list()
for edge in node.edge_list:
if edge.source_node == node and edge.relation == "IN":
children.append(edge.dest_node)
return children
# collapse_below starting at the given node
def collapse_below(node):
if node.node_type == "R" or node.node_type == "C":
# mark Root and Composite nodes with collapse_below flag
node.collapse_below = True
# get child IN nodes
children = _child_in_nodes(node)
for child in children:
# see if the child has a parent that is not collapsed below
parents = _parent_in_nodes(child)
can_collapse_child = True
for parent in parents:
# Root and Composite parents can collapse below
if parent.node_type == "R" or parent.node_type == "C":
if not parent.collapse_below:
# do not collapse below this child
can_collapse_child = False
if can_collapse_child:
child.collapse = True
collapse_below(child)
# uncollapse at and below node
def uncollapse_below(node):
# uncollapse the node
node.collapse = False
node.collapse_below = False
# uncollapse the node's IN children
children = _child_in_nodes(node)
for child in children:
uncollapse_below(child)
def _below_in(node, node_set):
children = _child_in_nodes(node)
for child in children:
node_set.add(child)
_below_in(child, node_set)
# for selecting all IN nodes at and below node
def at_and_below_in(node):
node_set = set()
node_set.add(node)
_below_in(node, node_set)
return node_set
# ancestors IN bout not collapsed
def _above_in_uncollapsed(node, node_set):
parents = _parent_in_nodes(node)
for parent in parents:
if not parent.collapse:
node_set.add(parent)
else:
# follow above this parent
_above_in_uncollapsed(parent, node_set)
# for selecting all IN nodes at and above node
def at_and_above_in_uncollapsed(node):
node_set = set()
if not node.collapse:
node_set.add(node)
else:
_above_in_uncollapsed(node, node_set)
return node_set
# get the set of removable_edges and addable_edge_pairs
def collapsed_edges(graph_item):
print("collapsed_edges.a")
# make sure there are edges to work with
if not graph_item.edges:
return (list(), list())
# identify the existing collapsed source_node, dest_node edge pairs
existing_edge_pairs = set()
existing_edges = dict()
for edge in graph_item.edges:
if edge.relation == "COLLAPSED_FOLLOWS":
existing_edge_pairs.add((edge.source_node, edge.dest_node))
existing_edges[(edge.source_node, edge.dest_node)] = edge
print("identified existing edge %s to %s" % (
edge.source_node.label, edge.dest_node.label))
# calculate the set of source_node, dest_node edge pairs
edge_pairs = set()
for edge in graph_item.edges:
if edge.relation == "FOLLOWS" and (edge.source_node.collapse
or edge.dest_node.collapse):
print("will add COLLAPSED_FOLLOWS to bridge: %s to %s" % (
edge.source_node.label, edge.dest_node.label))
# source and dest nodes
source_node_set = at_and_above_in_uncollapsed(edge.source_node)
dest_node_set = at_and_above_in_uncollapsed(edge.dest_node)
for source_node in source_node_set:
for dest_node in dest_node_set:
if source_node != dest_node:
print("adding %s to %s" % (
source_node.label, dest_node.label))
edge_pairs.add((source_node, dest_node))
# identify edges that need removed
removable_edges = list()
removable_pairs = existing_edge_pairs - edge_pairs
for source_node, dest_node in removable_pairs:
removable_edges.append(existing_edges[(source_node, dest_node)])
# identify edges that need added
addable_edge_pairs = edge_pairs - existing_edge_pairs
return (removable_edges, addable_edge_pairs)