Networkx：如何将边与条件结合在一起？
Networkx: how to combine edges together with condition?
我正在使用 Open Street Data，我已经通过 NetworkX 对其进行了丰富和建模。
然而，有大量节点仅用于设计边的曲线，因为它们只有两条边。
因此，我需要通过聚合将这些节点彼此连接的边来简化图形，同时保持聚合边的属性。
这是一个可重现的例子：
import networkx as nx
from shapely.geometry import LineString, Point
G = nx.Graph()
G.add_nodes_from([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
G.add_edges_from([(1, 2, {'highway': 'primary', 'speed_kph': 90, 'slope': 1.2,
'geometry': LineString([Point(3.013832,42.785837), Point(3.010505, 42.787605)])}),
(2, 3, {'highway': 'primary', 'speed_kph': 70, 'slope': 0.8,
'geometry': LineString([Point(3.010505, 42.787605), Point(3.006227, 42.789605)])}),
(3, 4, {'highway': 'primary', 'speed_kph': 50, 'slope': -0.1,
'geometry': LineString([Point(3.006227, 42.789605), Point(3.001030, 42.789721)])}),
(4, 5, {'highway': 'secondary', 'speed_kph': 50, 'slope': 3.1,
'geometry': LineString([Point(3.001030, 42.789721), Point(3.000998, 42.79321)])}),
(5, 6, {'highway': 'primary', 'speed_kph': 70, 'slope': -1.3,
'geometry': LineString([Point(3.000998, 42.79321), Point(2.995483, 42.795675)])}),
(4, 10, {'highway': 'tertiary', 'speed_kph': 50, 'slope': 3.7,
'geometry': LineString([Point(3.001030, 42.789721), Point(2.998273, 42.787303)])}),
(10, 11, {'highway': 'tertiary', 'speed_kph': 30, 'slope': 2.9,
'geometry': LineString([Point(2.998273, 42.787303), Point(2.995231, 42.784279)])}),
(3, 7, {'highway': 'secondary', 'speed_kph': 50, 'slope': 5.6,
'geometry': LineString([Point(3.006227, 42.789605), Point(3.009407, 42.791873)])}),
(7, 8, {'highway': 'secondary', 'speed_kph': 50, 'slope': 6.4,
'geometry': LineString([Point(3.009407, 42.791873), Point(3.009217, 42.794710)])}),
(8, 9, {'highway': 'secondary', 'speed_kph': 50, 'slope': -4.3,
'geometry': LineString([Point(3.009217, 42.794710), Point(3.005858, 42.796036)])}),
(9, 5, {'highway': 'secondary', 'speed_kph': 50, 'slope': -7.2,
'geometry': LineString([Point(3.005858, 42.796036), Point(3.000998, 42.79321)])})])
nx.draw(G, with_labels=True)
plt.show()
如您所见，边 (1,2) 和 (2,3) 可以聚合在一起，以及 (4,10) 和 (10,11)，甚至 (3,7)， (7,8), (8,9), (9,5) 可以概括为一条边。
然而，在聚合时，我不想丢失 speed_kph 和 slope 属性，并选择保持合并边的平均值。
至于几何，我想结合线串。所以得到的网络应该如下
import numpy as np
from shapely.ops import linemerge
new_G = nx.Graph()
new_G.add_nodes_from([1, 3, 4, 5, 6, 11])
new_G.add_edges_from([(1, 3, {'highway': 'primary', 'speed_kph': np.mean([90, 70]), 'slope': np.mean([1.2, 0.8]),
'geometry': linemerge([LineString([Point(3.013832,42.785837), Point(3.010505, 42.787605)]),
LineString([Point(3.010505, 42.787605), Point(3.006227, 42.789605)])])}),
(3, 4, {'highway': 'primary', 'speed_kph': 50, 'slope': -0.1,
'geometry': LineString([Point(3.006227, 42.789605), Point(3.001030, 42.789721)])}),
(4, 5, {'highway': 'secondary', 'speed_kph': 50, 'slope': 3.1,
'geometry': LineString([Point(3.001030, 42.789721), Point(3.000998, 42.79321)])}),
(5, 6, {'highway': 'primary', 'speed_kph': 70, 'slope': -1.3,
'geometry': LineString([Point(3.000998, 42.79321), Point(2.995483, 42.795675)])}),
(4, 11, {'highway': 'primary', 'speed_kph': np.mean([50, 30]), 'slope': np.mean([3.7, 2.9]),
'geometry': linemerge([LineString([Point(3.001030, 42.789721), Point(2.998273, 42.787303)]),
LineString([Point(2.998273, 42.787303), Point(2.995231, 42.784279)])])}),
(3, 5, {'highway': 'primary', 'speed_kph': np.mean([50, 50, 50, 50]), 'slope': np.mean([5.6, 6.4, -4.3, -7.2]),
'geometry': linemerge([LineString([Point(3.006227, 42.789605), Point(3.009407, 42.791873)]),
LineString([Point(3.009407, 42.791873), Point(3.009217, 42.794710)]),
LineString([Point(3.009217, 42.794710), Point(3.005858, 42.796036)]),
LineString([Point(3.005858, 42.796036), Point(3.000998, 42.79321)])])}),
])
nx.draw(new_G, with_labels=True)
plt.show()
有人知道我该怎么做吗？
当然，我的想法是自动检测可组合的边缘（可能使用 degree 上的阈值），因为我正在使用比那个玩具示例高得多的边缘并且不能手动完成。
我注意到这是在 osmnx 中实现的（参见 here），但仅此而已，它仅适用于 MultiDiGraph。
我还没有找到将 networkx 图变成 osmnx 图的方法，所以我调整了 osmnx 代码并借此机会根据我的需要对其进行了调整：
def _is_endpoint(G, node, strict=True):
"""
Is node a true endpoint of an edge.
Return True if the node is a "real" endpoint of an edge in the network,
otherwise False. OSM data includes lots of nodes that exist only as points
to help streets bend around curves. An end point is a node that either:
1) is its own neighbor, ie, it self-loops.
2) or, has no incoming edges or no outgoing edges, ie, all its incident
edges point inward or all its incident edges point outward.
3) or, it does not have exactly two neighbors and degree of 2 or 4.
4) or, if strict mode is false, if its edges have different OSM IDs.
Parameters
----------
G : networkx.MultiDiGraph
input graph
node : int
the node to examine
strict : bool
if False, allow nodes to be end points even if they fail all other rules
but have edges with different OSM IDs
Returns
-------
bool
"""
neighbors = set(list(G.predecessors(node)) + list(G.successors(node)))
n = len(neighbors)
d = G.degree(node)
# rule 1
if node in neighbors:
# if the node appears in its list of neighbors, it self-loops
# this is always an endpoint.
return True
# rule 2
elif G.out_degree(node) == 0 or G.in_degree(node) == 0:
# if node has no incoming edges or no outgoing edges, it is an endpoint
return True
# rule 3
elif not (n == 2 and (d == 2 or d == 4)):
# else, if it does NOT have 2 neighbors AND either 2 or 4 directed
# edges, it is an endpoint. either it has 1 or 3+ neighbors, in which
# case it is a dead-end or an intersection of multiple streets or it has
# 2 neighbors but 3 degree (indicating a change from oneway to twoway)
# or more than 4 degree (indicating a parallel edge) and thus is an
# endpoint
return True
# rule 4
elif not strict:
# non-strict mode: do its incident edges have different OSM IDs?
osmids = []
# add all the edge OSM IDs for incoming edges
for u in G.predecessors(node):
for key in G[u][node]:
osmids.append(G.edges[u, node, key]["osmid"])
# add all the edge OSM IDs for outgoing edges
for v in G.successors(node):
for key in G[node][v]:
osmids.append(G.edges[node, v, key]["osmid"])
# if there is more than 1 OSM ID in the list of edge OSM IDs then it is
# an endpoint, if not, it isn't
return len(set(osmids)) > 1
# if none of the preceding rules returned true, then it is not an endpoint
else:
return False
def _build_path(G, endpoint, endpoint_successor, endpoints):
"""
Build a path of nodes from one endpoint node to next endpoint node.
Parameters
----------
G : networkx.MultiDiGraph
input graph
endpoint : int
the endpoint node from which to start the path
endpoint_successor : int
the successor of endpoint through which the path to the next endpoint
will be built
endpoints : set
the set of all nodes in the graph that are endpoints
Returns
-------
path : list
the first and last items in the resulting path list are endpoint
nodes, and all other items are interstitial nodes that can be removed
subsequently
"""
# start building path from endpoint node through its successor
path = [endpoint, endpoint_successor]
# for each successor of the endpoint's successor
for successor in G.successors(endpoint_successor):
if successor not in path:
# if this successor is already in the path, ignore it, otherwise add
# it to the path
path.append(successor)
while successor not in endpoints:
# find successors (of current successor) not in path
successors = [n for n in G.successors(successor) if n not in path]
# 99%+ of the time there will be only 1 successor: add to path
if len(successors) == 1:
successor = successors[0]
path.append(successor)
# handle relatively rare cases or OSM digitization quirks
elif len(successors) == 0:
if endpoint in G.successors(successor):
# we have come to the end of a self-looping edge, so
# add first node to end of path to close it and return
return path + [endpoint]
else: # pragma: no cover
# this can happen due to OSM digitization error where
# a one-way street turns into a two-way here, but
# duplicate incoming one-way edges are present
print(
f"Unexpected simplify pattern handled near {successor}")
return path
else: # pragma: no cover
# if successor has >1 successors, then successor must have
# been an endpoint because you can go in 2 new directions.
# this should never occur in practice
raise Exception(f"Unexpected simplify pattern failed near {successor}")
# if this successor is an endpoint, we've completed the path
return path
# if endpoint_successor has no successors not already in the path, return
# the current path: this is usually due to a digitization quirk on OSM
return path
def _get_paths_to_simplify(G, strict=True):
"""
Generate all the paths to be simplified between endpoint nodes.
The path is ordered from the first endpoint, through the interstitial nodes,
to the second endpoint.
Parameters
----------
G : networkx.MultiDiGraph
input graph
strict : bool
if False, allow nodes to be end points even if they fail all other rules
but have edges with different OSM IDs
Yields
------
path_to_simplify : list
"""
# first identify all the nodes that are endpoints
endpoints = set([n for n in G.nodes if _is_endpoint(G, n, strict=strict)])
print(f"Identified {len(endpoints)} edge endpoints")
# for each endpoint node, look at each of its successor nodes
for endpoint in endpoints:
for successor in G.successors(endpoint):
if successor not in endpoints:
# if endpoint node's successor is not an endpoint, build path
# from the endpoint node, through the successor, and on to the
# next endpoint node
yield _build_path(G, endpoint, successor, endpoints)
def simplify_graph(G, strict=True, remove_rings=True, aggregation={}):
"""
Simplify a graph's topology by removing interstitial nodes.
Simplifies graph topology by removing all nodes that are not intersections
or dead-ends. Create an edge directly between the end points that
encapsulate them, but retain the geometry of the original edges, saved as
a new `geometry` attribute on the new edge. Note that only simplified
edges receive a `geometry` attribute. Some of the resulting consolidated
edges may comprise multiple OSM ways, and if so, their multiple attribute
values are stored as a list.
Parameters
----------
G : networkx.MultiDiGraph
input graph
strict : bool
if False, allow nodes to be end points even if they fail all other
rules but have incident edges with different OSM IDs. Lets you keep
nodes at elbow two-way intersections, but sometimes individual blocks
have multiple OSM IDs within them too.
remove_rings : bool
if True, remove isolated self-contained rings that have no endpoints
Returns
-------
G : networkx.MultiDiGraph
topologically simplified graph, with a new `geometry` attribute on
each simplified edge
"""
if "simplified" in G.graph and G.graph["simplified"]: # pragma: no cover
raise Exception("This graph has already been simplified, cannot simplify it again.")
print("Begin topologically simplifying the graph...")
# make a copy to not mutate original graph object caller passed in
G = G.copy()
initial_node_count = len(G)
initial_edge_count = len(G.edges)
all_nodes_to_remove = []
all_edges_to_add = []
# generate each path that needs to be simplified
for path in _get_paths_to_simplify(G, strict=strict):
# add the interstitial edges we're removing to a list so we can retain
# their spatial geometry
path_attributes = dict()
for u, v in zip(path[:-1], path[1:]):
# there should rarely be multiple edges between interstitial nodes
# usually happens if OSM has duplicate ways digitized for just one
# street... we will keep only one of the edges (see below)
edge_count = G.number_of_edges(u, v)
if edge_count != 1:
print(f"Found {edge_count} edges between {u} and {v} when simplifying")
# get edge between these nodes: if multiple edges exist between
# them (see above), we retain only one in the simplified graph
edge_data = G.edges[u, v, 0]
for attr in edge_data:
if attr in path_attributes:
# if this key already exists in the dict, append it to the
# value list
path_attributes[attr].append(edge_data[attr])
else:
# if this key doesn't already exist, set the value to a list
# containing the one value
path_attributes[attr] = [edge_data[attr]]
# consolidate the path's edge segments' attribute values
for attr in path_attributes:
if attr in aggregation.keys():
# if this is an aggregation attribute, aggregate the values
path_attributes[attr] = aggregation.get(attr)(path_attributes[attr])
# # construct the new consolidated edge's geometry for this path
# path_attributes["geometry"] = LineString(
# [Point((G.nodes[node]["x"], G.nodes[node]["y"])) for node in path]
# )
# add the nodes and edge to their lists for processing at the end
all_nodes_to_remove.extend(path[1:-1])
all_edges_to_add.append(
{"origin": path[0], "destination": path[-1], "attr_dict": path_attributes}
)
# for each edge to add in the list we assembled, create a new edge between
# the origin and destination
for edge in all_edges_to_add:
G.add_edge(edge["origin"], edge["destination"], **edge["attr_dict"])
# finally remove all the interstitial nodes between the new edges
G.remove_nodes_from(set(all_nodes_to_remove))
if remove_rings:
# remove any connected components that form a self-contained ring
# without any endpoints
wccs = nx.weakly_connected_components(G)
nodes_in_rings = set()
for wcc in wccs:
if not any(_is_endpoint(G, n) for n in wcc):
nodes_in_rings.update(wcc)
G.remove_nodes_from(nodes_in_rings)
# mark graph as having been simplified
G.graph["simplified"] = True
msg = (
f"Simplified graph: {initial_node_count} to {len(G)} nodes, "
f"{initial_edge_count} to {len(G.edges)} edges"
)
print(msg)
return G
现在，我可以运行用字典指定如何聚合组合边的属性。
simplified_G = simplify_graph(nx.MultiDiGraph(G),
aggregation = {'speed_kph': np.mean,
'slope': np.mean,
'highway': mode,
'geometry': linemerge}
nx.draw(simplified_G, with_labels=True)
plt.show()
这给了我预期的结果，但作为 MultiDiGraph。
所以我需要将它转换回 Graph
simplified_G = nx.Graph(simplified_G)
然后我回到我的原始数据，按预期进行了简化。
您可以使用递归来组合边：
from collections import defaultdict
def merge(n = 1, p = [], c = []):
if len(b:=[(y, v) for x, y, v in d if x == n and x and y not in c]) == 1 and sum(y == n for _, y, _ in d) < 2:
yield from merge(n=b[0][0], p=p+[(n,b[0][-1])], c = c+[n])
else:
yield (p[0][0], n, [x for _, x in p])
for y, v in b:
yield from merge(n=y, p=[(n, v)], c=c+[n, y])
r, agg = [], {'speed_kph': np.mean, 'slope': np.mean, 'highway': mode, 'geometry': linemerge}
for a, b, c in merge():
_d = defaultdict(list)
for h in c:
for j, k in h.items():
_d[j].append(k)
r.append((a, b, {j:agg[j](k) for j, k in _d.items()}))
现在，r 相当于您所需输出中的合并数据。
import networkx as nx
import matplotlib.pyplot as plt
new_G = nx.Graph()
new_G.add_nodes_from([*{j for *b, _ in r for j in b}])
new_G.add_edges_from(r)
nx.draw(new_G, with_labels=True)
plt.show()
输出：
我正在使用 Open Street Data，我已经通过 NetworkX 对其进行了丰富和建模。 然而，有大量节点仅用于设计边的曲线，因为它们只有两条边。
因此，我需要通过聚合将这些节点彼此连接的边来简化图形，同时保持聚合边的属性。
这是一个可重现的例子：
import networkx as nx
from shapely.geometry import LineString, Point
G = nx.Graph()
G.add_nodes_from([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
G.add_edges_from([(1, 2, {'highway': 'primary', 'speed_kph': 90, 'slope': 1.2,
'geometry': LineString([Point(3.013832,42.785837), Point(3.010505, 42.787605)])}),
(2, 3, {'highway': 'primary', 'speed_kph': 70, 'slope': 0.8,
'geometry': LineString([Point(3.010505, 42.787605), Point(3.006227, 42.789605)])}),
(3, 4, {'highway': 'primary', 'speed_kph': 50, 'slope': -0.1,
'geometry': LineString([Point(3.006227, 42.789605), Point(3.001030, 42.789721)])}),
(4, 5, {'highway': 'secondary', 'speed_kph': 50, 'slope': 3.1,
'geometry': LineString([Point(3.001030, 42.789721), Point(3.000998, 42.79321)])}),
(5, 6, {'highway': 'primary', 'speed_kph': 70, 'slope': -1.3,
'geometry': LineString([Point(3.000998, 42.79321), Point(2.995483, 42.795675)])}),
(4, 10, {'highway': 'tertiary', 'speed_kph': 50, 'slope': 3.7,
'geometry': LineString([Point(3.001030, 42.789721), Point(2.998273, 42.787303)])}),
(10, 11, {'highway': 'tertiary', 'speed_kph': 30, 'slope': 2.9,
'geometry': LineString([Point(2.998273, 42.787303), Point(2.995231, 42.784279)])}),
(3, 7, {'highway': 'secondary', 'speed_kph': 50, 'slope': 5.6,
'geometry': LineString([Point(3.006227, 42.789605), Point(3.009407, 42.791873)])}),
(7, 8, {'highway': 'secondary', 'speed_kph': 50, 'slope': 6.4,
'geometry': LineString([Point(3.009407, 42.791873), Point(3.009217, 42.794710)])}),
(8, 9, {'highway': 'secondary', 'speed_kph': 50, 'slope': -4.3,
'geometry': LineString([Point(3.009217, 42.794710), Point(3.005858, 42.796036)])}),
(9, 5, {'highway': 'secondary', 'speed_kph': 50, 'slope': -7.2,
'geometry': LineString([Point(3.005858, 42.796036), Point(3.000998, 42.79321)])})])
nx.draw(G, with_labels=True)
plt.show()
如您所见，边 (1,2) 和 (2,3) 可以聚合在一起，以及 (4,10) 和 (10,11)，甚至 (3,7)， (7,8), (8,9), (9,5) 可以概括为一条边。
然而，在聚合时，我不想丢失 speed_kph 和 slope 属性，并选择保持合并边的平均值。
至于几何，我想结合线串。所以得到的网络应该如下
import numpy as np
from shapely.ops import linemerge
new_G = nx.Graph()
new_G.add_nodes_from([1, 3, 4, 5, 6, 11])
new_G.add_edges_from([(1, 3, {'highway': 'primary', 'speed_kph': np.mean([90, 70]), 'slope': np.mean([1.2, 0.8]),
'geometry': linemerge([LineString([Point(3.013832,42.785837), Point(3.010505, 42.787605)]),
LineString([Point(3.010505, 42.787605), Point(3.006227, 42.789605)])])}),
(3, 4, {'highway': 'primary', 'speed_kph': 50, 'slope': -0.1,
'geometry': LineString([Point(3.006227, 42.789605), Point(3.001030, 42.789721)])}),
(4, 5, {'highway': 'secondary', 'speed_kph': 50, 'slope': 3.1,
'geometry': LineString([Point(3.001030, 42.789721), Point(3.000998, 42.79321)])}),
(5, 6, {'highway': 'primary', 'speed_kph': 70, 'slope': -1.3,
'geometry': LineString([Point(3.000998, 42.79321), Point(2.995483, 42.795675)])}),
(4, 11, {'highway': 'primary', 'speed_kph': np.mean([50, 30]), 'slope': np.mean([3.7, 2.9]),
'geometry': linemerge([LineString([Point(3.001030, 42.789721), Point(2.998273, 42.787303)]),
LineString([Point(2.998273, 42.787303), Point(2.995231, 42.784279)])])}),
(3, 5, {'highway': 'primary', 'speed_kph': np.mean([50, 50, 50, 50]), 'slope': np.mean([5.6, 6.4, -4.3, -7.2]),
'geometry': linemerge([LineString([Point(3.006227, 42.789605), Point(3.009407, 42.791873)]),
LineString([Point(3.009407, 42.791873), Point(3.009217, 42.794710)]),
LineString([Point(3.009217, 42.794710), Point(3.005858, 42.796036)]),
LineString([Point(3.005858, 42.796036), Point(3.000998, 42.79321)])])}),
])
nx.draw(new_G, with_labels=True)
plt.show()
有人知道我该怎么做吗？
当然，我的想法是自动检测可组合的边缘（可能使用 degree 上的阈值），因为我正在使用比那个玩具示例高得多的边缘并且不能手动完成。
我注意到这是在 osmnx 中实现的（参见 here），但仅此而已，它仅适用于 MultiDiGraph。
我还没有找到将 networkx 图变成 osmnx 图的方法，所以我调整了 osmnx 代码并借此机会根据我的需要对其进行了调整：
def _is_endpoint(G, node, strict=True):
"""
Is node a true endpoint of an edge.
Return True if the node is a "real" endpoint of an edge in the network,
otherwise False. OSM data includes lots of nodes that exist only as points
to help streets bend around curves. An end point is a node that either:
1) is its own neighbor, ie, it self-loops.
2) or, has no incoming edges or no outgoing edges, ie, all its incident
edges point inward or all its incident edges point outward.
3) or, it does not have exactly two neighbors and degree of 2 or 4.
4) or, if strict mode is false, if its edges have different OSM IDs.
Parameters
----------
G : networkx.MultiDiGraph
input graph
node : int
the node to examine
strict : bool
if False, allow nodes to be end points even if they fail all other rules
but have edges with different OSM IDs
Returns
-------
bool
"""
neighbors = set(list(G.predecessors(node)) + list(G.successors(node)))
n = len(neighbors)
d = G.degree(node)
# rule 1
if node in neighbors:
# if the node appears in its list of neighbors, it self-loops
# this is always an endpoint.
return True
# rule 2
elif G.out_degree(node) == 0 or G.in_degree(node) == 0:
# if node has no incoming edges or no outgoing edges, it is an endpoint
return True
# rule 3
elif not (n == 2 and (d == 2 or d == 4)):
# else, if it does NOT have 2 neighbors AND either 2 or 4 directed
# edges, it is an endpoint. either it has 1 or 3+ neighbors, in which
# case it is a dead-end or an intersection of multiple streets or it has
# 2 neighbors but 3 degree (indicating a change from oneway to twoway)
# or more than 4 degree (indicating a parallel edge) and thus is an
# endpoint
return True
# rule 4
elif not strict:
# non-strict mode: do its incident edges have different OSM IDs?
osmids = []
# add all the edge OSM IDs for incoming edges
for u in G.predecessors(node):
for key in G[u][node]:
osmids.append(G.edges[u, node, key]["osmid"])
# add all the edge OSM IDs for outgoing edges
for v in G.successors(node):
for key in G[node][v]:
osmids.append(G.edges[node, v, key]["osmid"])
# if there is more than 1 OSM ID in the list of edge OSM IDs then it is
# an endpoint, if not, it isn't
return len(set(osmids)) > 1
# if none of the preceding rules returned true, then it is not an endpoint
else:
return False
def _build_path(G, endpoint, endpoint_successor, endpoints):
"""
Build a path of nodes from one endpoint node to next endpoint node.
Parameters
----------
G : networkx.MultiDiGraph
input graph
endpoint : int
the endpoint node from which to start the path
endpoint_successor : int
the successor of endpoint through which the path to the next endpoint
will be built
endpoints : set
the set of all nodes in the graph that are endpoints
Returns
-------
path : list
the first and last items in the resulting path list are endpoint
nodes, and all other items are interstitial nodes that can be removed
subsequently
"""
# start building path from endpoint node through its successor
path = [endpoint, endpoint_successor]
# for each successor of the endpoint's successor
for successor in G.successors(endpoint_successor):
if successor not in path:
# if this successor is already in the path, ignore it, otherwise add
# it to the path
path.append(successor)
while successor not in endpoints:
# find successors (of current successor) not in path
successors = [n for n in G.successors(successor) if n not in path]
# 99%+ of the time there will be only 1 successor: add to path
if len(successors) == 1:
successor = successors[0]
path.append(successor)
# handle relatively rare cases or OSM digitization quirks
elif len(successors) == 0:
if endpoint in G.successors(successor):
# we have come to the end of a self-looping edge, so
# add first node to end of path to close it and return
return path + [endpoint]
else: # pragma: no cover
# this can happen due to OSM digitization error where
# a one-way street turns into a two-way here, but
# duplicate incoming one-way edges are present
print(
f"Unexpected simplify pattern handled near {successor}")
return path
else: # pragma: no cover
# if successor has >1 successors, then successor must have
# been an endpoint because you can go in 2 new directions.
# this should never occur in practice
raise Exception(f"Unexpected simplify pattern failed near {successor}")
# if this successor is an endpoint, we've completed the path
return path
# if endpoint_successor has no successors not already in the path, return
# the current path: this is usually due to a digitization quirk on OSM
return path
def _get_paths_to_simplify(G, strict=True):
"""
Generate all the paths to be simplified between endpoint nodes.
The path is ordered from the first endpoint, through the interstitial nodes,
to the second endpoint.
Parameters
----------
G : networkx.MultiDiGraph
input graph
strict : bool
if False, allow nodes to be end points even if they fail all other rules
but have edges with different OSM IDs
Yields
------
path_to_simplify : list
"""
# first identify all the nodes that are endpoints
endpoints = set([n for n in G.nodes if _is_endpoint(G, n, strict=strict)])
print(f"Identified {len(endpoints)} edge endpoints")
# for each endpoint node, look at each of its successor nodes
for endpoint in endpoints:
for successor in G.successors(endpoint):
if successor not in endpoints:
# if endpoint node's successor is not an endpoint, build path
# from the endpoint node, through the successor, and on to the
# next endpoint node
yield _build_path(G, endpoint, successor, endpoints)
def simplify_graph(G, strict=True, remove_rings=True, aggregation={}):
"""
Simplify a graph's topology by removing interstitial nodes.
Simplifies graph topology by removing all nodes that are not intersections
or dead-ends. Create an edge directly between the end points that
encapsulate them, but retain the geometry of the original edges, saved as
a new `geometry` attribute on the new edge. Note that only simplified
edges receive a `geometry` attribute. Some of the resulting consolidated
edges may comprise multiple OSM ways, and if so, their multiple attribute
values are stored as a list.
Parameters
----------
G : networkx.MultiDiGraph
input graph
strict : bool
if False, allow nodes to be end points even if they fail all other
rules but have incident edges with different OSM IDs. Lets you keep
nodes at elbow two-way intersections, but sometimes individual blocks
have multiple OSM IDs within them too.
remove_rings : bool
if True, remove isolated self-contained rings that have no endpoints
Returns
-------
G : networkx.MultiDiGraph
topologically simplified graph, with a new `geometry` attribute on
each simplified edge
"""
if "simplified" in G.graph and G.graph["simplified"]: # pragma: no cover
raise Exception("This graph has already been simplified, cannot simplify it again.")
print("Begin topologically simplifying the graph...")
# make a copy to not mutate original graph object caller passed in
G = G.copy()
initial_node_count = len(G)
initial_edge_count = len(G.edges)
all_nodes_to_remove = []
all_edges_to_add = []
# generate each path that needs to be simplified
for path in _get_paths_to_simplify(G, strict=strict):
# add the interstitial edges we're removing to a list so we can retain
# their spatial geometry
path_attributes = dict()
for u, v in zip(path[:-1], path[1:]):
# there should rarely be multiple edges between interstitial nodes
# usually happens if OSM has duplicate ways digitized for just one
# street... we will keep only one of the edges (see below)
edge_count = G.number_of_edges(u, v)
if edge_count != 1:
print(f"Found {edge_count} edges between {u} and {v} when simplifying")
# get edge between these nodes: if multiple edges exist between
# them (see above), we retain only one in the simplified graph
edge_data = G.edges[u, v, 0]
for attr in edge_data:
if attr in path_attributes:
# if this key already exists in the dict, append it to the
# value list
path_attributes[attr].append(edge_data[attr])
else:
# if this key doesn't already exist, set the value to a list
# containing the one value
path_attributes[attr] = [edge_data[attr]]
# consolidate the path's edge segments' attribute values
for attr in path_attributes:
if attr in aggregation.keys():
# if this is an aggregation attribute, aggregate the values
path_attributes[attr] = aggregation.get(attr)(path_attributes[attr])
# # construct the new consolidated edge's geometry for this path
# path_attributes["geometry"] = LineString(
# [Point((G.nodes[node]["x"], G.nodes[node]["y"])) for node in path]
# )
# add the nodes and edge to their lists for processing at the end
all_nodes_to_remove.extend(path[1:-1])
all_edges_to_add.append(
{"origin": path[0], "destination": path[-1], "attr_dict": path_attributes}
)
# for each edge to add in the list we assembled, create a new edge between
# the origin and destination
for edge in all_edges_to_add:
G.add_edge(edge["origin"], edge["destination"], **edge["attr_dict"])
# finally remove all the interstitial nodes between the new edges
G.remove_nodes_from(set(all_nodes_to_remove))
if remove_rings:
# remove any connected components that form a self-contained ring
# without any endpoints
wccs = nx.weakly_connected_components(G)
nodes_in_rings = set()
for wcc in wccs:
if not any(_is_endpoint(G, n) for n in wcc):
nodes_in_rings.update(wcc)
G.remove_nodes_from(nodes_in_rings)
# mark graph as having been simplified
G.graph["simplified"] = True
msg = (
f"Simplified graph: {initial_node_count} to {len(G)} nodes, "
f"{initial_edge_count} to {len(G.edges)} edges"
)
print(msg)
return G
现在，我可以运行用字典指定如何聚合组合边的属性。
simplified_G = simplify_graph(nx.MultiDiGraph(G),
aggregation = {'speed_kph': np.mean,
'slope': np.mean,
'highway': mode,
'geometry': linemerge}
nx.draw(simplified_G, with_labels=True)
plt.show()
这给了我预期的结果，但作为 MultiDiGraph。
所以我需要将它转换回 Graph
simplified_G = nx.Graph(simplified_G)
然后我回到我的原始数据，按预期进行了简化。
您可以使用递归来组合边：
from collections import defaultdict
def merge(n = 1, p = [], c = []):
if len(b:=[(y, v) for x, y, v in d if x == n and x and y not in c]) == 1 and sum(y == n for _, y, _ in d) < 2:
yield from merge(n=b[0][0], p=p+[(n,b[0][-1])], c = c+[n])
else:
yield (p[0][0], n, [x for _, x in p])
for y, v in b:
yield from merge(n=y, p=[(n, v)], c=c+[n, y])
r, agg = [], {'speed_kph': np.mean, 'slope': np.mean, 'highway': mode, 'geometry': linemerge}
for a, b, c in merge():
_d = defaultdict(list)
for h in c:
for j, k in h.items():
_d[j].append(k)
r.append((a, b, {j:agg[j](k) for j, k in _d.items()}))
现在，r 相当于您所需输出中的合并数据。
import networkx as nx
import matplotlib.pyplot as plt
new_G = nx.Graph()
new_G.add_nodes_from([*{j for *b, _ in r for j in b}])
new_G.add_edges_from(r)
nx.draw(new_G, with_labels=True)
plt.show()
输出：