fastiso 0.1

Fast subgraph isomorphism (C++ backend) for Python

fastiso

This is a Python module built on CPython that provides bindings for the C++ solver FASTiso.
The library supports:

• Graph isomorphism
• Subgraph isomorphism
• Monomorphism (Non-induced subgraph isomorphism)

Author

Camille Coti. Vladimir Reinharz and Wilfried Agbeto.

Installation

pip install --index-url https://test.pypi.org/simple/ --extra-index-url https://pypi.org/simple/ fastiso

Usage

CSV interface

fastiso accept csv format.

import fastiso

pattern = ['3', '0,1,B53', '1,2,CWW']
target = ['4', 'a,b,B53', 'b,c,CWW', 'c,d,CHH']
"""
csv_iso(
    pattern:iterable,
    target:iterable,
    algo:"iso|sub-iso|monomorphism",
    format:"csv|ucsv",
    get_all_solution:bool, 
    count_solution:bool
)
"""
print(fastiso.csv_iso(pattern, target, "sub-iso", "csv", 0, 1)) #get 1
print(fastiso.csv_iso(pattern, target, "monomorphism", "csv", 1, 0)) #get [{'0': 'a', '1': 'b', '2': 'c'}]

NetworkX interface

fastiso integrates natively with networkx.Graph (networkx.MultiGraph) or nx.DiGraph (networkx.MultiDiGraph) objects.

import networkx as nx
import fastiso

pattern = nx.DiGraph()
pattern.add_edge(0, 1, label="B53")
pattern.add_edge(1, 2, label="CWW")

target = nx.DiGraph()
target.add_edge("a", "b", label="B53")
target.add_edge("b", "c", label="CWW")
target.add_edge("c", "d", label="CHH")
"""
nx_iso(        
    pattern:NetworkxGraph, 
    target:NetworkxGraph, 
    algo="iso|sub-iso|monomorphism", 
    all_solution:bool, 
    count_solution:bool,
    node_label_key=None, 
    edge_label_key=None,
    node_label_eq_fn=None, 
    edge_label_eq_fn=None 
)
"""
print(fastiso.nx_iso(pattern, target, "sub-iso", all_solution=0, count_solution=1, edge_label_key="label")) #get 1
print(fastiso.nx_iso(pattern, target, "monomorphism", all_solution=1, count_solution=0, edge_label_key="label")) #get [{'0': 'a', '1': 'b', '2': 'c'}]

Node & edge attributes

In many applications, it is often useful to assign labels to nodes or edges. You can use the parameters node_label_key and edge_label_key to specify which node or edge attributes should be used as labels.

FASTiso operates on the principle of node and edge "coloring" based on these labels. Two nodes or edges can only be mapped if they share the same color (label). By default, this is determined by strict equality (label1 == label2).

Through the node_label_eq_fn and edge_label_eq_fn parameters, you can define custom logic for label equality, allowing for more flexible comparisons. However, please note that your custom comparison method must not violate the property of disjoint color classes: each node or edge must belong to exactly one color class. FASTiso does not support cases where a node could belong to multiple color classes simultaneously.

def eq_fn(label1, label2) -> bool:
    ...

True → same color
False → different colors

import networkx as nx
import fastiso

pattern = nx.DiGraph()
pattern.add_node(1, type='Fe')
pattern.add_node(2, type='O')
pattern.add_edge(1, 2)
pattern.add_edge(2, 1)

target = nx.DiGraph()
target.add_node("a", type='Cu')
target.add_node("b", type='N')
target.add_edge("a", "b")
target.add_edge("b", "a")

print(fastiso.nx_iso(pattern, target, "iso", all_solution=0, count_solution=1, node_label_key="type")) #get 0
##grouping labels by families
def are_same_family(label1, label2):
    families = {
        'Fe': 'Metal', 'Cu': 'Metal',
        'O': 'Non-Metal', 'N': 'Non-Metal'
    }
    return families.get(label1) == families.get(label2)
print(fastiso.nx_iso(pattern, target, "sub-iso", all_solution=0, count_solution=1, node_label_key="type", node_label_eq_fn=are_same_family)) #get 1

File Formats

CSV

The CSV format is recommended for labeled graphs, each line represents an edge or a node, except the first line gives the number n of nodes.

unlabeled graph,

• edge : "node1_id,node2_id"
• node : "node_id"

3
0,1
1,0
1,2
2,1
0,2
2,0

node label

to add a node label, put a semicolon (;) after node id.

• edge : "node1_id;node1_label,node2_id;node2_label"
• node : "node_id;node_label"

3
0;a,1;b
1;b,0;a
1;b,2;a
2;a,1;b
0;a,2;a
2;a,0;a

edge label

To add an edge label, add a third column : "node1_id;node1_label,node2_id;node2_label",edge_label.

6
0,1,s
1,0,s
1,2,t
2,1,t
0,2,d1
2,0,d2
3,2,t
2,3,t
4,1,s
1,4,s
5

By default, the CSV format is for directed graphs. for undirected graphs use UCSV.