#NEWLINE# def get_contraction_structure( expr ) : #NEWLINE# #INDENT# 'Determine dummy indices of ``expr`` and describe its structure\n\n    By *dummy* we mean indices that are summation indices.\n\n    The stucture of the expression is determined and described as follows:\n\n    1) A conforming summation of Indexed objects is described with a dict where\n       the keys are summation indices and the corresponding values are sets\n       containing all terms for which the summation applies.  All Add objects\n       in the SymPy expression tree are described like this.\n\n    2) For all nodes in the SymPy expression tree that are *not* of type Add, the\n       following applies:\n\n       If a node discovers contractions in one of its arguments, the node\n       itself will be stored as a key in the dict.  For that key, the\n       corresponding value is a list of dicts, each of which is the result of a\n       recursive call to get_contraction_structure().  The list contains only\n       dicts for the non-trivial deeper contractions, ommitting dicts with None\n       as the one and only key.\n\n    .. Note:: The presence of expressions among the dictinary keys indicates\n       multiple levels of index contractions.  A nested dict displays nested\n       contractions and may itself contain dicts from a deeper level.  In\n       practical calculations the summation in the deepest nested level must be\n       calculated first so that the outer expression can access the resulting\n       indexed object.\n\n    Examples\n    ========\n\n    >>> from sympy.tensor.index_methods import get_contraction_structure\n    >>> from sympy import symbols, default_sort_key\n    >>> from sympy.tensor import IndexedBase, Idx\n    >>> x, y, A = map(IndexedBase, [\'x\', \'y\', \'A\'])\n    >>> i, j, k, l = map(Idx, [\'i\', \'j\', \'k\', \'l\'])\n    >>> get_contraction_structure(x[i]*y[i] + A[j, j])\n    {(i,): set([x[i]*y[i]]), (j,): set([A[j, j]])}\n    >>> get_contraction_structure(x[i]*y[j])\n    {None: set([x[i]*y[j]])}\n\n    A multiplication of contracted factors results in nested dicts representing\n    the internal contractions.\n\n    >>> d = get_contraction_structure(x[i, i]*y[j, j])\n    >>> sorted(d.keys(), key=default_sort_key)\n    [None, x[i, i]*y[j, j]]\n\n    In this case, the product has no contractions:\n\n    >>> d[None]\n    set([x[i, i]*y[j, j]])\n\n    Factors are contracted "first":\n\n    >>> sorted(d[x[i, i]*y[j, j]], key=default_sort_key)\n    [{(i,): set([x[i, i]])}, {(j,): set([y[j, j]])}]\n\n    A parenthesized Add object is also returned as a nested dictionary.  The\n    term containing the parenthesis is a Mul with a contraction among the\n    arguments, so it will be found as a key in the result.  It stores the\n    dictionary resulting from a recursive call on the Add expression.\n\n    >>> d = get_contraction_structure(x[i]*(y[i] + A[i, j]*x[j]))\n    >>> sorted(d.keys(), key=default_sort_key)\n    [(x[j]*A[i, j] + y[i])*x[i], (i,)]\n    >>> d[(i,)]\n    set([(x[j]*A[i, j] + y[i])*x[i]])\n    >>> d[x[i]*(A[i, j]*x[j] + y[i])]\n    [{None: set([y[i]]), (j,): set([x[j]*A[i, j]])}]\n\n    Powers with contractions in either base or exponent will also be found as\n    keys in the dictionary, mapping to a list of results from recursive calls:\n\n    >>> d = get_contraction_structure(A[j, j]**A[i, i])\n    >>> d[None]\n    set([A[j, j]**A[i, i]])\n    >>> nested_contractions = d[A[j, j]**A[i, i]]\n    >>> nested_contractions[0]\n    {(j,): set([A[j, j]])}\n    >>> nested_contractions[1]\n    {(i,): set([A[i, i]])}\n\n    The description of the contraction structure may appear complicated when\n    represented with a string in the above examples, but it is easy to iterate\n    over:\n\n    >>> from sympy import Expr\n    >>> for key in d:\n    ...     if isinstance(key, Expr):\n    ...         continue\n    ...     for term in d[key]:\n    ...         if term in d:\n    ...             # treat deepest contraction first\n    ...             pass\n    ...     # treat outermost contactions here\n\n    ' #NEWLINE# if isinstance ( expr , Indexed ) : #NEWLINE# #INDENT# ( junk , key ) = _remove_repeated ( expr . indices ) #NEWLINE# return { #NEWLINE# #INDENT# ( key or None ) : { expr } , #NEWLINE# #UNINDENT# } #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if expr . is_Atom : #NEWLINE# #INDENT# return { #NEWLINE# #INDENT# None : { expr } , #NEWLINE# #UNINDENT# } #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if expr . is_Mul : #NEWLINE# #INDENT# ( junk , junk , key ) = _get_indices_Mul ( expr , return_dummies = True ) #NEWLINE# result = { #NEWLINE# #INDENT# ( key or None ) : { expr } , #NEWLINE# #UNINDENT# } #NEWLINE# nested = [ ] #NEWLINE# for fac in expr . args : #NEWLINE# #INDENT# facd = get_contraction_structure ( fac ) #NEWLINE# if ( not ( ( None in facd ) and ( len ( facd ) == 1 ) ) ) : #NEWLINE# #INDENT# nested . append ( facd ) #NEWLINE# #UNINDENT# #UNINDENT# if nested : #NEWLINE# #INDENT# result [ expr ] = nested #NEWLINE# #UNINDENT# return result #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if ( expr . is_Pow or isinstance ( expr , exp ) ) : #NEWLINE# #INDENT# ( b , e ) = expr . as_base_exp ( ) #NEWLINE# dbase = get_contraction_structure ( b ) #NEWLINE# dexp = get_contraction_structure ( e ) #NEWLINE# dicts = [ ] #NEWLINE# for d in ( dbase , dexp ) : #NEWLINE# #INDENT# if ( not ( ( None in d ) and ( len ( d ) == 1 ) ) ) : #NEWLINE# #INDENT# dicts . append ( d ) #NEWLINE# #UNINDENT# #UNINDENT# result = { #NEWLINE# #INDENT# None : { expr } , #NEWLINE# #UNINDENT# } #NEWLINE# if dicts : #NEWLINE# #INDENT# result [ expr ] = dicts #NEWLINE# #UNINDENT# return result #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if expr . is_Add : #NEWLINE# #INDENT# result = { #NEWLINE# #INDENT# #NEWLINE# #UNINDENT# } #NEWLINE# for term in expr . args : #NEWLINE# #INDENT# d = get_contraction_structure ( term ) #NEWLINE# for key in d : #NEWLINE# #INDENT# if ( key in result ) : #NEWLINE# #INDENT# result [ key ] |= d [ key ] #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# result [ key ] = d [ key ] #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# return result #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if isinstance ( expr , Piecewise ) : #NEWLINE# #INDENT# return { #NEWLINE# #INDENT# None : expr , #NEWLINE# #UNINDENT# } #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if isinstance ( expr , Function ) : #NEWLINE# #INDENT# deeplist = [ ] #NEWLINE# for arg in expr . args : #NEWLINE# #INDENT# deep = get_contraction_structure ( arg ) #NEWLINE# if ( not ( ( None in deep ) and ( len ( deep ) == 1 ) ) ) : #NEWLINE# #INDENT# deeplist . append ( deep ) #NEWLINE# #UNINDENT# #UNINDENT# d = { #NEWLINE# #INDENT# None : { expr } , #NEWLINE# #UNINDENT# } #NEWLINE# if deeplist : #NEWLINE# #INDENT# d [ expr ] = deeplist #NEWLINE# #UNINDENT# return d #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if ( not expr . has ( Indexed ) ) : #NEWLINE# #INDENT# return { #NEWLINE# #INDENT# None : { expr } , #NEWLINE# #UNINDENT# } #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# #UNINDENT# #UNINDENT# #UNINDENT# #UNINDENT# #UNINDENT# raise NotImplementedError ( ( 'FIXME: No specialized handling of type %s' % type ( expr ) ) )