CODEWITHSUNDEEP
graphnodesnetworkxedges
tartearth
tartearth

Reputation: 39

Reduce number of nodes/edges of a Graph in nedworkx

I have a Graph with many nodes of degree 2 (derived from a LineString). In order to simplify the Graph I would like to reduce it to just the nodes with a degree not equal to 2 but still containig the same overall connections. You can find an example of what I mean in the picture below. So if there are multiple nodes mit degree=2 between two nodes with the degree of 3, all the nodes and edges in the middle should be deleted and a single connection between the two deg=3 nodes should be established with the same weight as the sum of the omitted edges.

Example Picture of reduced Graph

Upvotes: 3

Views: 1234

Answers (2)

Yeow Lih Wei
Yeow Lih Wei

Reputation: 19

nx.component.connected_component_subgraphs has been deprecated. components can now be defined as:

components = [chains.subgraph(c) for c in nx.components.connected_components(chains)]

https://networkx.org/documentation/networkx-2.1/reference/algorithms/generated/networkx.algorithms.components.connected_component_subgraphs.html

Upvotes: 1

Paul Brodersen
Paul Brodersen

Reputation: 13031

You can identify chains by 1) inducing a subgraph only containing nodes with degree 2, and 2) then identifying the individual components in the induced subgraph. Then it is a simple matter of summing the weights in each chain and creating a new edge with that weight between the nodes connecting to the end points of the chain.

enter image description here

import numpy as np
import matplotlib.pyplot as plt
import networkx as nx


def contract(g):
    """
    Contract chains of neighbouring vertices with degree 2 into a single edge.

    Arguments:
    ----------
    g -- networkx.Graph or networkx.DiGraph instance

    Returns:
    --------
    h -- networkx.Graph or networkx.DiGraph instance
        the contracted graph

    """

    # create subgraph of all nodes with degree 2
    is_chain = [node for node, degree in g.degree() if degree == 2]
    chains = g.subgraph(is_chain)

    # contract connected components (which should be chains of variable length) into single node
    components = list(nx.components.connected_component_subgraphs(chains))

    hyper_edges = []
    for component in components:
        end_points = [node for node, degree in component.degree() if degree < 2]
        candidates = set([neighbor for node in end_points for neighbor in g.neighbors(node)])
        connectors = candidates - set(list(component.nodes()))
        hyper_edge = list(connectors)
        weights = [component.get_edge_data(*edge)['weight'] for edge in component.edges()]
        hyper_edges.append((hyper_edge, np.sum(weights)))

    # initialise new graph with all other nodes
    not_chain = [node for node in g.nodes() if not node in is_chain]
    h = g.subgraph(not_chain).copy()
    for hyper_edge, weight in hyper_edges:
        h.add_edge(*hyper_edge, weight=weight)

    return h

# create weighted graph
edges = np.random.randint(0, 20, size=(int(400*0.2), 2))
weights = np.random.rand(len(edges))
g = nx.Graph()
for edge, weight in zip(edges, weights):
    g.add_edge(*edge, weight=weight)
h = nx.algorithms.minimum_spanning_tree(g)

# contract
i = contract(h)

# plot
pos = nx.spring_layout(h)

fig, (ax1, ax2) = plt.subplots(1, 2, sharex=True, sharey=True)
nx.draw(h, pos=pos, ax=ax1)
nx.draw(i, pos=pos, ax=ax2)
plt.show()

Upvotes: 6

Related Questions