i want to group a network of nodes by their connection. furthermore i want to index inside the subgroups.
i have pairs resembling connections between elements. lets say i know that
A->B, B->C, C->D, E->F, F->G.
- i want to destinguish the two distinct networks, e.g.
A->B->C->D E->F->G
input:
import networkx as nx df = pd.DataFrame( {"source": ["A", "B", "C", "E", "F"], "destination": ["B", "C", "D", "F", "G"]} ) G = nx.Graph() G.add_nodes_from(df.source.append(df.destination).unique()) G.add_edges_from(df.to_records(False)) groups = list(nx.algorithms.components.connected_components(G)) df["group"] = [ groups.index(group) for element in df.source for group in groups if element in group ] df output:
source destination group 0 A B 0 1 B C 0 2 C D 0 3 E F 1 4 F G 1 - furthermore i want to extract an index that follows the ordering and topology of the pairs, so that the nodes are numbered from one side to the other.
desired output:
source destination group index 0 A B 0 0 1 B C 0 1 2 C D 0 2 3 E F 1 0 4 F G 1 1 no circular networks are possible in my data.
any advice?
3 Answers
Nodes can be ordered using topological_sort
for group in groups: subgraph = nx.subgraph(G, group) node_order = nx.topological_sort(subgraph) In general, edges cannot be sorted unambiguously in the same way, unless each subgraph in your graph is indeed a chain (as in your toy example). In that case, you can then convert the node order into a sorted list of edges using:
edge_order = list(zip(node_order[:-1], node_order[1:])) @Paul as well as the docs led me to the solution. Thank you very much!
(I slightly changed the ordering of rows in the example)
# %% import networkx as nx df = pd.DataFrame( {"source": ["B", "A", "C", "E", "F"], "destination": ["C", "B", "D", "F", "G"]} ) # generate both directed and undirected graph G = nx.Graph() NG = nx.DiGraph() for graph in G, NG: graph.add_nodes_from(df.source.append(df.destination).unique()) graph.add_edges_from(df.to_records(False)) # task 1: get distinct path groups (usage of G) groups = list(nx.algorithms.components.connected_components(G)) df["group"] = [ groups.index(group) for element in df.source for group in groups if element in group ] # task 2: get within path index (usage of NG) # roots = (v for v, d in NG.in_degree() if d == 0) # leaves = [v for v, d in NG.out_degree() if d == 0] # all_paths = [] # for root in roots: # paths = nx.all_simple_paths(NG, root, leaves) # all_paths.extend(paths) # all_paths # use paul brodersen more elegant code to feed a list all_paths = [] for group in groups: subgraph = nx.subgraph(NG, group) node_order = nx.topological_sort(subgraph) all_paths.append(list(node_order)) path_index = pd.concat([pd.DataFrame(x) for x in all_paths]).reset_index().rename(columns={'index': 'path_index', 0:'source'}) df = df.merge(path_index, on = 'source') df gives me
source destination group path_index 0 B C 0 1 1 A B 0 0 2 C D 0 2 3 E F 1 0 4 F G 1 1 I tested the script with real world data, and as it is more messy than the play data, i wont get the output i like. Lets say i have got this
df = pd.DataFrame([('A', 'B'), ('A', 'C'), ('B', 'A'), ('C', 'A'), ('C', 'L'), ('D', E'), ('D', 'F'), ('E', 'D'), ('E', 'G'), ('F', 'D'), ('F', 'J'), ('G', 'E'), ('G', K'), ('H', 'I'), ('I', 'H'), ('I', 'J'), ('J', 'F'), ('J', 'I'), ('K', 'G'), ('L', C'), ('M', 'N'), ('N', 'M'), ('N', 'O'), ('O', 'N'), ('O', 'P'), ('P', 'O'), ('P', Q'), ('Q', 'P'), ('Q', 'R'), ('R', 'Q'), ('S', 'T'), ('T', 'S')],, columns=['source','destination']) drawed as
Although grouping works, the inner group index wont.
It throws
raise nx.NetworkXUnfeasible( "Graph contains a cycle or graph changed during iteration" ) I know that in the data, A->B as well as B->A is present, therefore the cycle error.
My first idea was to remove the duplicated lines, but how would i know whether i can keep one or the other?
At the lower left, we see: If L->C and C->A, i got rows for C->L and A->C as well in the data. Therefore after dups removal i could end up with C->L and C->A, but what i want is the real path of L->C and C->A. It seems to identify the path and index from it, i have to know the path beforehand for dups removal?
Is this complicated or am i thinking just too complicated?
NB: nx.topological_sort(subgraph) does not do what i think it would do. It does not care about the path, leading to 'A', 'B', 'C', 'L' for the lower left, instead of 'B', 'A', 'C', 'L'. But the docs clearly state This ordering is valid only if the graph has no directed cycles. RTFM
