Feature Request: Add Subgraph Node ID Mapping in subgraph_isomorphism Output

[michaelfekadu]

Hi!

I'm currently using the subgraph_isomorphism function to find isomorphic subgraphs in a host graph. However, the current isos array returned only includes the vertex IDs from the host graph without providing a mapping to the IDs of the subgraph. This makes it challenging to reconstruct the subgraph using the host graph IDs.

Here is the code illustrating the current behavior:

G = ar.PropGraph()
src = [1, 2, 3, 2]
dst = [2, 3, 4, 7]
G.add_edges_from(ak.array(src), ak.array(dst))

subgraph = ar.PropGraph()
src = [10, 20, 30, 20]
dst = [20, 30, 40, 70]
subgraph.add_edges_from(ak.array(src), ak.array(dst))

isos = ar.subgraph_isomorphism(G, subgraph)
print(isos)

The output I get is:

[1 2 3 4 7]

With help from Oliver, I created a function that maps the subgraph IDs to the host graph IDs based on the isos output, allowing me to recreate the subgraph. Here's a concise explanation of the provided code:

The function first checks if the length of the isos array is a multiple of the number of subgraph nodes. It then iterates through each isomorphic subgraph found, creating a mapping from the subgraph node IDs to the corresponding host graph node IDs. Finally, it reconstructs the subgraph edges using the host graph node IDs.

Here's the complete code:

import arkouda as ak
import arachne as ar

ak.connect()

# Define the host graph
G = ar.PropGraph()
src_host = [1, 2, 3, 2]
dst_host = [2, 3, 4, 7]
G.add_edges_from(ak.array(src_host), ak.array(dst_host))

# Define the subgraph
subgraph = ar.PropGraph()
src_sub = [10, 20, 30, 20]
dst_sub = [20, 30, 40, 70]
subgraph.add_edges_from(ak.array(src_sub), ak.array(dst_sub))

# Find isomorphic subgraphs
isos = ar.subgraph_isomorphism(G, subgraph)
print(f"Isomorphisms found: {isos}")
isos_ndarray = isos.to_ndarray()  # Convert pdarray to ndarray

# Check if the length of isomorphisms is a multiple of the number of subgraph nodes
if len(isos) % len(subgraph) != 0:
    raise ValueError("The length of isomorphisms is not a multiple of the number of subgraph nodes.")

subgraph_nodes=[]
host_graph_nodes=[]
node_mapping={}

number_isos_found= len(isos)/len(subgraph)
for i in range(0,int(number_isos_found)):
    # Create a mapping from subgraph nodes to host graph nodes
    subgraph_nodes = sorted(list(set(src_sub + dst_sub)))
    host_graph_nodes = isos_ndarray[i*len(subgraph_nodes):i*len(subgraph_nodes) + len(subgraph_nodes)]
    node_mapping = dict(zip(subgraph_nodes, host_graph_nodes))
    print("Mapping:", node_mapping)
    # Recreate the subgraph with host graph node IDs
    mapped_src_sub = [node_mapping[node] for node in src_sub]
    mapped_dst_sub = [node_mapping[node] for node in dst_sub]

    # Output the mapped subgraph edges
    print("Mapped subgraph edges (using host graph node IDs):")
    for s, d in zip(mapped_src_sub, mapped_dst_sub):
        print(f"{s} -> {d}")

The output I get is:

Isomorphisms found: [1 2 3 4 7]
Mapping: {10: 1, 20: 2, 30: 3, 40: 4, 70: 7}
Mapped subgraph edges (using host graph node IDs):
1 -> 2
2 -> 3
3 -> 4
2 -> 7

I hope this helps to implement a mapping feature directly into the library!