Cil*_*yan 8 python algorithm graph
我正在分析一个功能的控制流图,它基本上将输入数据映射到输出数据.大多数块都像这样:
if (input_variable == SPECIFIC_CONSTANT) {
output_variable = TRUE;
}
else {
output_variable = FALSE;
}
此类代码的典型控制流程图如下图所示
digraph G {
2 -> 3 -> 5;
2 -> 4 -> 5;
}
执行3和4由其价值决定input_variable但是5独立的.
给定有向图和起始节点,如何找到最近的节点,使得起始节点的任何路径都通过该节点？
示例:给定此图如何6从开始2或12从开始查找8？
我可以反转最低共同祖先算法并且它会有效吗？喜欢
for each node in graph:
ancestors = node.get_all_ancestors()
lca = find_lowest_common_ancestor(ancestors)
junction_node[lca] = node
get_junction_point(node):
return junction_node[node]
我的编程语言是Python,我刚刚发现了NetworkX,但任何算法都会受到赞赏.我不习惯图论,我想我会错过基本词汇表来找到我正在寻找的东西.
谢谢你的帮助!
阅读了您提出的所有解决方案后，我想到了一个想法。我给第一个节点的数量为 1。递归地，所有子节点都会收到该数量的等分部分。反过来，他们则减少了这笔金额。如果孩子总共收到 1（起始金额），那么它就是“连接点”。这是我的实现（欢迎评论！！）。
我希望 BFS 构造能够限制访问的节点数量。
class Node(object):
"""
Object representing a node in a graph where we search the junction node that
concentrates all paths starting from a start node.
``reference``: Attaches the real object that contains the relationships.
``initial_value``: Initial amount for the node. Typically 1 for the start
node, 0 for the others.
``path``: Set of already traversed nodes that reached the node. Used to
prune circular dependencies.
"""
def __init__(self, reference, initial_value, path=set()):
self.reference = reference
# See dispatch() for explaination
self.value_can_dispatch = self.value_has_received = initial_value
self.path = path
def receive(self, value):
"""
Give ``value`` to the node. If the node received 1 (or more for security)
in total, it will return True. Else it returns False.
"""
self.value_has_received += value
self.value_can_dispatch += value
if self.value_has_received >= 1.:
return True
return False
def dispatch(self, children):
"""
Dispatch the value received to the children.
Returns a filtered list of ``children`` where children involved in a
circular dependency are removed.
If one child signals that it has received a total of 1, the function will
stop and return this one child.
"""
# Filter successors that are in the path used to access this node so to cut
# out cycles
true_successors = [child for child in children if child not in self.path]
# Cut the received value into equal pieces
amount = self.value_can_dispatch/len(true_successors)
# We transmit only the value received after the last time it was dispatched
# because paths may lead to the same node at different iterations (path
# through one node may be longer than through another) and thus the same
# node can be asked to dispatch to its children more than once.
# The total amount of received value is kept in value_has_received because
# the node may receive the complete amount in several steps. Thus, part of
# its value may have been dispatched before we notice that the node received
# the total amount of 1.
self.value_can_dispatch = Fraction(0)
for child in true_successors:
# If child signaled that he received 1, then raise the winner
if child.receive(amount):
return child
return set(true_successors)
def touch(self, other_node):
"""
"Touches" a node with another, notifying that the node is reachable
through another path than the known ones.
It adds the elements of the new path as ancestors of the node.
"""
self.path |= other_node.path | {other_node}
def make_child(self, reference):
"""
Creates a child of the node, pointing to reference. The child receives
its path from the current node.
"""
# This is were the algorithm can go mad. If child is accessed through two
# paths, the algorithm will only protect recursion into the first
# path. If the successors recurse into the second path, we will not detect
# it. => We should update the child's path when a second path reaches it.
return self.__class__(reference, Fraction(0), self.path | {self})
def __repr__(self):
return "<{} {}>".format(self.__class__.__name__, self.reference)
def find_junction_node(first_reference, get_uid, get_successors, max_iterations=100):
"""
Find the junction node of all paths starting from ``first_reference`` in
a directed graph. ``get_uid`` is a function accepting a reference to a node
in your graph and returning a unique identifier for this reference.
``get_successors`` is a function accepting a reference to a node in your
graph. It should return a list of references to all its the children nodes.
It may return None if the node has no child.
``max_iterations`` limits the number of pass the algorithm use to find the
junction node. If reached, the funciton raises a RuntimeError.
Returns ``(jp, ln)`` where ``jp`` is a reference to a node in your graph
which is the junction node and ``ln`` the list of nodes in the subgraph
between the start node and the junction node.
"""
# Mapping to already created nodes
nodes = {}
# Initialise first node with an amount of 1
node = Node(first_reference, Fraction(1, 1))
nodes[get_uid(first_reference)] = node
# Initialise first iteration of DFS
successors = set()
successors.add(node)
# Max iteration provides security as I'm not sure the algorithm cannot loop
for i in range(max_iterations):
next_successors = set()
# Process one level of nodes
for node in successors:
# Find successors in data graph
sub_references = get_successors(node.reference)
# This happens when we reach the end of the graph, node has no children
if sub_references is None:
continue
# Make a list of Node that are children of node
children = set()
for reference in sub_references:
uid = get_uid(reference)
# Does it exist?
child = nodes.get(uid, None)
if not child:
child = node.make_child(reference)
nodes[uid] = child
else:
child.touch(node)
children.add(child)
# Dispatch the value of node equally between its children
result = node.dispatch(children)
#print("Children of {}: {!r}".format(node, result)) # DEBUG
# If one child received a total of 1 from its parents, it is common to
# all paths
if isinstance(result, Node):
return result.reference, [node.reference for node in result.path]
# Else, add the filtered list of children to the set of node to process
# in the next level
else:
next_successors |= result
successors = next_successors
# Reached end of graph by all paths without finding a junction point
if len(successors) == 0:
return None
raise RuntimeError("Max iteration reached")