TCG_graph.py

# -*- coding: utf-8 -*-
"""
@author: Victor Barres

TCG graph operations

Uses networkx
"""
from __future__ import division
from networkx import DiGraph
from networkx.algorithms import isomorphism

## Find subgraph isomorphisms ###
def find_sub_iso(G_subgraphs, G_pat, node_match=None, edge_match=None):
    """
    Returns the list of all the graph isomorphisms between one of the subgraphs of G in G_subgraphs and the graph pattern G_pat. 
    Each isomorphim is defined as a dictionary with keys "nodes" itself a dictionary mapping G_pat nodes to G nodes, and "edges" a dictionary mapping G_pat edges to G edges.
    
    Args:
        - G_subgraphs([NetworkX.DiGraph]): List of subgraphs
        - G_pat(NetworkX.DiGraph)
        - node_match (callable): node_match should be either "None" or networkx isomorphisms matching functions generated by node_iso_match().
        - edge_match (callable): edge_match should be either "None" or networkx isomorphisms matching functions generated by edge_iso_match().
        - subgraph_filter (callable): subgraph_filter should be a callable that takes on a subgraph and returns True or False. Only the subgraphs that return True
                                        are considered for subgraph isomorphism matching. By default returns always True.
    """
    sub_iso = []
    mappings = []
    for subgraph in G_subgraphs:
            DiGM = isomorphism.DiGraphMatcher(subgraph, G_pat, node_match=node_match, edge_match=edge_match)
            if DiGM.is_isomorphic():
                mappings.append(DiGM.mapping)
                
    for mapping in mappings:
        iso = {"nodes":{}, "edges":{}}
        for key in mapping:
            iso["nodes"][mapping[key]] = key # reverse mapping for convenience (SemFrame -> SemRep)        
        for edge in G_pat.edges(): # Add mapping between edges
            iso["edges"][edge] = (iso["nodes"][edge[0]], iso["nodes"][edge[1]])
        sub_iso.append(iso)
    
    return sub_iso
    
def build_subgraphs(G, induced='vertex', subgraph_filter=lambda x:True):
    """
    Returns the list of subgraphs of G filtered by subgraph_filter
    induced:
        -> 'vertex': vertex induced subgraphs + single nodes
        -> 'node': node induced subgraphs.
    """
    if induced == 'node':
        node_power_set = list_powerset(G.nodes())
        subgraphs = [G.subgraph(nbunch) for nbunch in node_power_set] # Builds all the node induced subgraphs.
    if induced == 'vertex':
        vertex_powerset = list_powerset(G.edges(data=True))
        subgraphs = []
        for v_list in vertex_powerset:
            subG = DiGraph(v_list) # Creating subraph from vertices
            for n in subG.node.keys():
                subG.node[n] = G.node[n] # Transfering node attributes
            subgraphs.append(subG)
            
        # Adding single nodes
        for n, d in G.nodes(data=True):
            subG = DiGraph()
            subG.add_node(n,d)
            subgraphs.append(subG)
    
    # Filtering
    subgraphs = [subG for subG in subgraphs if subgraph_filter(subG)]
    
    return subgraphs
        
def list_powerset(lst):
    """
    Returns the powerset of all the elements in lst
    """
    result = [[]]
    for x in lst:
        result.extend([subset + [x] for subset in result])
    return result

def node_iso_match(attr, attr_default, op):
    """
    Returns an node_match function that can be used in find_sub_iso()
    
    Args: 
        - attr: the name (or list of names) of attributes to consider.
        - attr_default: default value (or list of values) for attributes
        - op: a callable boolean function.
    
    Note: This function in its current form is just a wrapper around networkx.isomorphism.generic_node_match()
    """
    nm = isomorphism.generic_node_match(attr, attr_default, op)
    return nm

def edge_iso_match(attr, attr_default, op):
    """
    Returns an edge_match function that can be used in find_sub_iso()
    
    Args:
        - attr: the name (or list of names) of attributes to consider.
        - attr_default: default value (or list of values) for attributes
        - op: a callable boolean function.
    
    Note: This function in its current form is just a wrapper around networkx.isomorphism.generic_edge_match()
    """
    em = isomorphism.generic_edge_match(attr, attr_default, op)
    return em
###############################################################################
if __name__=="__main__":
    import networkx as nx    
    # Main graph
    G = nx.DiGraph()
    
    G.add_node(0, attr=0)
    G.add_node(1, attr=0)
    G.add_node(2, attr=0)
    G.add_node(3, attr=0)
    
    G.add_edge(0,1, attr=-1)
    G.add_edge(1,2, attr=-1)
    G.add_edge(2,0, attr=-1)
    
    nx.draw(G)
    
    # Graph pattern
    G_pat= nx.DiGraph()
    
    G_pat.add_node("a", attr=0)
    G_pat.add_node("b", attr=0)
    G_pat.add_node("c", attr=0)
    
    G_pat.add_edge("a","b", attr=-1)
    G_pat.add_edge("b","c", attr=-1)
    
    nx.draw(G_pat)
    
    G_subgraphs = build_subgraphs(G, induced='vertex') # In this example, if induced = 'nodes' it won't find any isomorphisms.
    
    # Categorical match functions
    nm_cat = isomorphism.categorical_node_match("attr", 1)
    em_cat = isomorphism.categorical_edge_match("attr", 1)
    
    print find_sub_iso(G_subgraphs, G_pat, node_match = nm_cat, edge_match=em_cat)
    
    # Numerical match functions
    nm_num = isomorphism.numerical_node_match("attr", 0, atol=0.5, rtol=1e-05) # Matches if |x-y|<= atol + abs(y)*rtol
    print find_sub_iso(G_subgraphs, G_pat, node_match = nm_num, edge_match=None)
    
    # Generic match functions
    op = lambda x,y: x >= y
    nm_gen = isomorphism.generic_node_match("attr", 0, op)
    sub_iso = find_sub_iso(G_subgraphs, G_pat, node_match = nm_gen, edge_match=None)
    
    if sub_iso:
        print sub_iso[0]["nodes"].values()