[joss] Solving simple tasks

Review the retworkx examples and the related discussions in #509 and #512, focusing on the requested connected-components, incident-edge, edge-betweenness, attribute, and plotting APIs. Determine which usability concerns represent concrete library changes and which are design questions. Done requires an agreed scope and maintainer-approved acceptance criteria; the issue alone does not define a single implementation or test target.

This is not a bug report, but a request to review my solution to a few simple tasks using retworkx. Most of these tasks were thought up before I looked at retworkx at all, and they help me judge how usable the library is.

Forgive my horrible Python—I'm not fluent in this language, as you can see. I'd especially appreciate comments on whether these tasks have a simpler / better solution in retworkx.

---

import retworkx as rx
from retworkx.visualization import mpl_draw

import numpy as np
import matplotlib.pyplot as plt

Plot the degree distribution of a graph

n = 10000
g = rx.undirected_gnm_random_graph(n, 2*n)

degs = [g.degree(v) for v in g.node_indexes()] 

plt.hist(degs, bins=range(max(degs)+1))

Getting the degree sequence seemed a bit more verbose than what I expected. Is there a simpler way?

Giant component transition

n = 10000
xx = np.arange(0, 2, 0.01)
res = []
for x in xx:
    g = rx.undirected_gnm_random_graph(n, round(x*n))
    gcsize = max(map(len, rx.weakly_connected_components(g.to_directed())))
    res.append(gcsize)
    
plt.plot(xx, res)

There seems to be no connected components function for undirected graphs, so we convert to directed first.

Isolate the giant component

n = 100
g = rx.undirected_gnm_random_graph(n, n)

gcomp = max(rx.weakly_connected_components(g.to_directed()), key=len)
g = g.subgraph(list(gcomp))

Compute the node betweenness and store it in a node attribute

betw = rx.betweenness_centrality(g)

for v, c in betw.items():
    g[v] = {'betweenness': c}

Will this format for attribute storage become standard in the future? Suppose you add importers for various graph file formats. Most can store named attributes. It seems to me that if the library is meant to be usable for network analysis, it won't be possible to avoid standardizing on some attribute storage format.

Mean neighbour degree

from statistics import mean

mean_nei_degs = []
for v in g.node_indexes():
    mean_nei_degs.append(mean([g.degree(u) for u in g.neighbors(v)]))
    
print(mean_nei_degs)

Undirected connected components from scratch

from collections import deque, defaultdict

def conn_comps(graph: rx.PyGraph):
    membership = [0] * graph.num_nodes() # membership[v] is the 1-based component index of vertex v
    component_index = 0
    queue = deque()
    
    for v in range(graph.num_nodes()):
        if not membership[v]:
            # we do a BFS for each not-yet-visited vertex
            
            component_index += 1
            
            queue.append(v)
            membership[v] = component_index
            while queue:
                u = queue.popleft()
                for w in graph.neighbors(u):
                    if not membership[w]:
                        queue.append(w)
                        membership[w] = component_index

    comps = defaultdict(set)
    for i, c in enumerate(membership):
        comps[c-1].add(i)
        
    return comps

n = 20
g = rx.undirected_gnm_random_graph(n, n)

print(conn_comps(g))

I was looking to program a Dijsktra as well, but I'm not sure how to get the incident edge list, a critical ingredient. See #509

Targeted attack

Remove nodes in order of highest betweenness, and record in what order they were removed.

This would be much more interesting for edges and edge betweenness (it would implement Girvan-Newman community detection), but edge betweenness is not yet available. See also #512

def betw_order(graph):
    g = graph.copy()

    for i in range(g.num_nodes()):
        g[i] = i # payload keeps track of which node was which during removals

    order = []

    while g.num_nodes() > 0:
        betw = rx.betweenness_centrality(g)
        top_node = max(betw, key=lambda key: betw[key])

        order.append(g[top_node])
        g.remove_node(top_node)

    return order

n = 20
g = rx.undirected_gnm_random_graph(n, 3*n)

betw_order(g)

Visualize centrality measures

Betweenness

g = rx.generators.grid_graph(7,7)

betw = rx.betweenness_centrality(g)
mpl_draw(g, node_color=[betw[v] for v in g.node_indexes()])

Here, one comment is that the result is returned as a dictionary between vertex indices and centrality values. It takes extra work to convert this to the list representation required by mpl_draw(). I am wondering if the dictionary is the best return format for retworkx. networkx does it because it does not have consistent vertex and edge orderings, but in retworkx vertex and edge indices are important, and appear to be the best way to refer to vertices/edges.

Degree

g = rx.undirected_gnm_random_graph(20, 30)

degs = [g.degree(i) for i in g.node_indexes()]
mpl_draw(g, node_color = np.array(degs) / max(degs))

Highlight a spanning tree

g = rx.undirected_gnm_random_graph(10,20)
spanning_edges = rx.minimum_spanning_edges(g)
print(spanning_edges)

We need to convert these edges specifications to indices in some way so that they can be used for plotting. Is there a simpler way to do this? See #512.

ei = g.edge_index_map()
edges_to_indices = dict(zip(ei.values(), ei.keys()))

cols = ['blue'] * g.num_edges()
widths = [1] * g.num_edges()
for edge in spanning_edges:
    cols[edges_to_indices[edge]] = 'red'
    widths[edges_to_indices[edge]] = 2.5

mpl_draw(g, edge_color = cols, width=widths)