import sys, os sys.path.append(os.path.dirname(os.path.dirname(os.path.dirname(os.path.realpath(__file__))))) from graph.DataType import PositionalPoint, Line, Pos, Point from typing import List, Dict import random as rd class ForceCalcHelper: """ 力导向计算辅助节点 """ def __init__(self, init_v: PositionalPoint): self.bind_point = init_v self.sibling_nodes: Dict[str, 'ForceCalcHelper'] = {} pass def bind_point_name(self) -> str: return self.bind_point.point_name def get_sibling_nodes(self) -> Dict[str, 'ForceCalcHelper']: return self.sibling_nodes pass def sibling_append(self, node: 'ForceCalcHelper'): self.sibling_nodes[node.bind_point_name()] = node pass class UDGGraph: force2accx_rates = 1 def __init__(self): self.random_gen = rd.Random() self.node_set: Dict[str, ForceCalcHelper] = {} pass def rebuild_from_edges(self, line_set: List[Line]): self.node_set.clear() for line in line_set: start_node = line.points()[0] if start_node.point_name not in self.node_set: pos_node = PositionalPoint(start_node.point_name, 0, 0) self.node_set[start_node.point_name] = ForceCalcHelper(pos_node) pass end_node = line.points()[1] if start_node.point_name == end_node.point_name: continue if end_node.point_name not in self.node_set: pos_node = PositionalPoint(end_node.point_name, 0, 0) self.node_set[end_node.point_name] = ForceCalcHelper(pos_node) pass start_force_point = self.node_set[start_node.point_name] other_force_point = self.node_set[end_node.point_name] start_force_point.sibling_append(other_force_point) other_force_point.sibling_append(start_force_point) pass pass def __eject_with_item(self, curr: ForceCalcHelper, node_set:Dict[str, ForceCalcHelper]) -> Pos: init_value = Pos(0, 0) for node in node_set.values(): if curr.bind_point_name() == node.bind_point_name(): continue coord_span = curr.current_pos() - node.current_pos() distance = coord_span.vec_length() force_scalar = ForceCalcHelper.eject_k / (distance**2) force_vec = coord_span.normalized() * force_scalar init_value += force_vec pass return init_value def __attract_with_item_sibs(self, curr: ForceCalcHelper) -> Pos: init_value = Pos(0, 0) for node in curr.get_sibling_nodes().values(): coord_span = curr.current_pos() - node.current_pos() distance = coord_span.vec_length() force_scalar = distance * ForceCalcHelper.attract_k force_vec = coord_span.normalized() * force_scalar init_value -= force_vec pass return init_value def __calculate_item_force(self, curr: ForceCalcHelper, node_set:Dict[str, ForceCalcHelper]) -> float: """ 计算指定节点对整个数据图节点的合力 :param times: 次数,初始迭代有特殊处理 :param curr: 当前节点 :param node_set: 所有节点 :return: 合力标量 """ eject_vec2 = self.__eject_with_item(curr, node_set) attract_vec2 = self.__attract_with_item_sibs(curr) curr.force_with_direction = eject_vec2 + attract_vec2 # 阻尼计算 f=fxG(fxg=1,m=1) fr = ForceCalcHelper.damping_k * 10 if curr.force_with_direction.vec_length() > fr: curr.force_with_direction -= curr.force_with_direction.normalized() * fr pass else: curr.force_with_direction = Pos() pass return curr.force_with_direction.vec_length() def __item_position_adjust(self, curr: ForceCalcHelper) -> None: if curr.force_with_direction.vec_length() == 0: return vec_speed = curr.force_with_direction.normalized() curr.move_by(vec_speed) pass def graph_layout(self): for curr in self.node_set.values(): random_pos = Pos(self.random_gen.random() * 100, self.random_gen.random() * 100) curr.move_by(random_pos) pass for idx in range(0, 10): for curr in self.node_set.values(): self.__calculate_item_force(curr, self.node_set) pass for curr in self.node_set.values(): self.__item_position_adjust(curr) pass pass pass def visible_positon_set(self) -> List[PositionalPoint]: retvs = [] for node in self.node_set.values(): retvs.append(node.bind_point) pass return retvs if __name__ == "__main__": list_in = [ Line(Point("a"), Point("b")), Line(Point("a"), Point("c")), Line(Point("a"), Point("d")), Line(Point("a"), Point("e")), Line(Point("d"), Point("e")), Line(Point("f"), Point("c")), ] graph = UDGGraph() graph.rebuild_from_edges(list_in) graph.graph_layout() for p in graph.visible_positon_set(): print(f"node:{p.name()}<{p.x_pos},{p.y_pos}>") pass pass