Loading...
墨滴

张春成

2021/07/07  阅读:36  主题:默认主题

图的距离度量

图的距离度量

本文将在上文《最小连通图》的基础上,介绍图距离度量理念及方法。


图上点的距离

距离是简单的概念,但在图论中却与日常的三维空间具有区别。

  • 在三维空间中

    两个点之间的距离是它们三维坐标的二次模数

  • 在图空间中

    图上节点之间的距离可以通过节点之间经过的最小边数来定义

  • 举个例子

    当你要从家打车到公司,软件会预估一个收费距离,这个距离会是在三维空间中的直线距离吗?

    不会!

    它会怎么做?它会规划路线并计算这些路线的路程总和。

    这就是图空间中距离度量的直观理解。

当然可以通过下图得到较为直观的定义

DistanceGraph
DistanceGraph

图中我们试图度量节点8641之间的距离。

由于节点之间的“通路”只能通过“边”来构造,因此从一点到另一点也只能通过边来实现。

由于我们找到了最小长度的通路,也就是最少数量的边数。 因此我们可以说,所经过的边数即是两个点之间的距离。

代码实现

我们可以通过简单的代码实现上述功能。

def mk_routeDict(route):
    '''
    Method: mk_routeDict

    Make Dict of Route [route]

    Args:
    - @route

    Outputs:
    - The Dict

    '''


    rd = dict()
    for r in route:
        assert(r[1not in rd)
        rd[r[1]] = r[0]

    return rd


def trace_route(start, end, rd):
    '''
    Method: trace_route

    Trace the Length from [start] to [end],
    using the Route Dict [rd]

    Args:
    - @start, end, rd

    Outputs:
    - The Length

    '''


    if start == end:
        return [start]

    trace0 = [start]
    while True:
        if trace0[-1not in rd:
            break
        trace0.append(rd[trace0[-1]])

    trace1 = [end]
    while True:
        if trace1[-1not in rd:
            break
        trace1.append(rd[trace1[-1]])

    x = []
    while True:
        if not trace0:
            break
        if not trace1:
            break
        if trace0[-1] == trace1[-1]:
            trace0.pop(-1)
            x = [trace1.pop(-1)]
        else:
            break

    return trace0 + x + trace1[::-1]


# Make Routing Dictionary
rd = mk_routeDict(route)

# Compute A Path to Make Example
# And Draw the Plot
a, b = [np.random.randint(0, len(nodes)) for _ in range(2)]
trace = trace_route(a, b, rd)
print(trace[0], trace[-1], len(trace))

_nodes = nodes.loc[trace]
_nodes['name'] = _nodes.index
fig11 = px.scatter(_nodes, x='x', y='y', text='name')

fig2 = px.line(links, x='x', y='y', line_group='group', color='label')

fig = go.Figure()

for d in fig11.data:
    fig.add_trace(d)

for d in fig2.data:
    d['line']['width'] = 0.5
    fig.add_trace(d)

fig.update_layout({'title''Least Length Route {} -> {}'.format(a, b)})
fig.show()

当然,如果眼力足够好,您也许会发现连接这些节点的边有了一些颜色,这不全是为了美观,而是为了明天的工作做准备。

张春成

2021/07/07  阅读:36  主题:默认主题

作者介绍

张春成