Join edges/discard degree-two nodes

[tomalrussell]

To create single edge where node offers no choice of route.

Consider how best to merge or concatenate data/metadata.

[tomalrussell]

Suggest something like:

Find set s of degree-2 nodes.
Pop a node n, find longest 2-degree path that it's part of:

• create list of nodes in path p, initialise with n
• create set of candidates c, initialise with n
• do while c is not empty:
  • pop a node n from c
  • find the two edges in/out from n
  • if the endpoints of either of those edges are in s and not in p, remove from s and add to p and c
  • [add edges to path for convenience here too]
  • if the either endpoint is not in s, add to p (this will be one endpoint of the path)

Output path.
Repeat until s is empty.
Then for each path, drop their constituent edges from the graph, replace with single edge consisting of combined geometry/metadata.

TODO - is there prior art for this or similar (?), check for correctness (!)

Would also be useful to inject a condition somewhere here - e.g. so as not to collapse edges with differing attributes.

[ElcoK]

One function to find the connectivity degree:

def node_connectivity_degree(node,snNW):
    return len(
            snNW.edges[
                (snNW.edges.from_id == node) | (snNW.edges.to_id == node)
            ]
    )

And a function to actually merge edges:

def merge_edges(snNW):
    
    if 'degree' not in snNW.nodes.columns:
        snNW.nodes['degree'] = snNW.nodes.id.apply(lambda x: 
                                                 node_connectivity_degree(x,snNW))
    
    
    degree2 = list(snNW.nodes.id.loc[snNW.nodes.degree == 2])
    d2_set = set(degree2)
    node_paths = []
    edge_paths = []

    while d2_set:
        popped_node = d2_set.pop()
        node_path = [popped_node]
        candidates = set([popped_node])
        while candidates:
            popped_cand = candidates.pop()
            matches = list(np.unique(snNW.edges[['from_id','to_id']].loc[((snNW.edges.from_id.isin([popped_cand])) 
                                              | (snNW.edges.to_id.isin([popped_cand])))].values))
            matches.remove(popped_cand)
            for match in matches:
                if match in node_path:
                    continue

                if match in degree2:
                    candidates.add(match)
                    node_path.append(match)
                    d2_set.remove(match)
                else:
                    node_path.append(match)
        if len(node_path) > 2:
            node_paths.append(node_path)
            edge_paths.append(snNW.edges.loc[((snNW.edges.from_id.isin(node_path)) & (snNW.edges.to_id.isin(node_path)))])

    concat_edge_paths = []
    unique_edge_ids = set()
    for edge_path in edge_paths:
        unique_edge_ids.update(list(edge_path.id))
        concat_edge_paths.append(edge_path.dissolve(by='infra_type', aggfunc='first'))         

    edges_new = snNW.edges.copy()
    edges_new = edges_new.loc[~(edges_new.id.isin(list(unique_edge_ids)))]
    snNW.edges = pd.concat([edges_new,pd.concat(concat_edge_paths).reset_index()],sort=False)
    
    nodes_new = snNW.nodes.copy()
    snNW.nodes = nodes_new.loc[~(nodes_new.id.isin(list(degree2)))]
    
    return snNW

[ElcoK]

Possible addition:

if function returns ValueError: No objects to concatenate, it means there are no degree 2 nodes in the geodataframe. we may want to catch this error and just print the statement that the network is already 'clean'

[tomalrussell]

Recent issue with current implementation noted by @amanmajid - code assumes 'bridge' and 'infra_type' attributes.

Note #33 here too - should be able to handle this generically.