.. _graf-d-una-expressio:

.. py:module:: graf_exp

Graf d'una expressió
====================

Una expressió es pot representar com un graf dirigit (digraf), els
vèrtexs del qual corresponen o bé a una de les operacions de
l'expressió, o bé a una de les variables que intervenen en
l'expressió. Per exemple, l'expressió ``(c+b)*a`` es representa
mitjançant el digraf següent:

.. figure:: Graf_subexp.svg
   :alt: Representació d'una expressió mitjançant un digraf.

   Representació d'una expressió mitjançant un digraf.

El vèrtex ``(c+b)*a`` correspon al producte de ``c+b`` per ``a``, el
vèrtex ``c+b`` correspon a la suma de ``c`` amb ``b`` i els vèrtexs
``a``, ``b`` i ``c`` corresponen a les variables que apareixen en
l'expressió.

Observeu que en aquest digraf les variables es caracteritzen per tenir
grau de sortida (*out degree*) zero i que l'expressió completa es
caracteritza per tenir grau d'entrada (*in degree*) zero. Les
subexpressions tenen tant el grau d'entrada com el de sortida diferent
de zero.

A més, un mateix digraf pot representar més d'una expressió, per exemple:

.. figure:: Graf_exps.svg
   :alt: Digraf que representa dues expressions.

   Digraf que representa dues expressions.

Per dissenyar les funcions d'aquest exercici podeu utilitzar alguns
dels mètodes de la classe :py:ref:`DiGraph <networkx:digraph>`.
   
Deseu les funcions següents al mòdul :file:`graf_exp.py`.

#. Dissenyeu la funció següent:

   .. py:function:: crea_digraf_exps(le)

   A partir d'una llista de parelles d'*strings* que són els arcs d'un
   digraf que representa una expressió retorna un digraf amb aquests
   arcs. Per exemple:

   .. literalinclude:: graf_exp-1.txt
      :language: python3
      :lines: 1-

   .. note::
        Disposeu de jocs de prova al fitxer :download:`graf_exp-1.txt<graf_exp-1.txt>`
   
#. Dissenyeu la funció següent:

   .. py:function:: crea_digraf_camins(le)

   A partir d'una llista de camins que parteixen d'expressions, passen
   per subexpressions i arriben a variables retorna un digraf amb
   aquests camins. Cada camí és una llista d'*strings*. Per exemple:

   .. literalinclude:: graf_exp-2.txt
      :language: python3
      :lines: 1- 

   .. note::
        Disposeu de jocs de prova al fitxer :download:`graf_exp-2.txt<graf_exp-2.txt>`

#. Dissenyeu la funció següent:

   .. py:function:: vars_usades(g)

   Retorna la llista de les variables del digraf ``g``. Recordeu que
   les variables d'un digraf que representa una expressió són els
   vèrtex del digraf que tenen grau de sortida igual a zero. La llista
   ha d'estar ordenada lexicogràficament. Per exemple:

   .. literalinclude:: graf_exp-3.txt
      :language: python3
      :lines: 1- 

   .. note::
        Disposeu de jocs de prova al fitxer :download:`graf_exp-3.txt<graf_exp-3.txt>`

#. Dissenyeu la funció següent:

   .. py:function:: vars_mes_usades(g)

   Retorna la llista de les variables del digraf ``g`` més usades
   directament en les expressions de ``g``. Direm que una variable
   s'usa directament en una expressió si existeix un arc de
   l'expressió a la variable. La llista ha d'estar ordenada
   lexicogràficament. Per exemple:

   .. literalinclude:: graf_exp-4.txt
      :language: python3
      :lines: 1- 

   .. note::
        Disposeu de jocs de prova al fitxer :download:`graf_exp-4.txt<graf_exp-4.txt>`

#. Dissenyeu la funció següent:

   .. py:function:: vars_directes(g, e)

   Retorna la llista de les variables de ``g`` que apareixen
   directament a l'expressió ``e``. Una variable apareix directament
   en una expressió si hi ha una aresta del graf que parteix de
   l'expressió i arriba a la variable. La llista ha d'estar ordenada
   lexicogràficament. Per exemple:
   
   .. literalinclude:: graf_exp-5.txt
      :language: python3
      :lines: 1-
	      
   .. note::
        Disposeu de jocs de prova al fitxer :download:`graf_exp-5.txt<graf_exp-5.txt>`
   
#. Dissenyeu la funció següent:

   .. py:function:: exps_mes_usades(g)

   Retorna la llista de les expressions del digraf ``g`` més usades
   directament en altres expressions de ``g``. Direm que una expressió
   *a* s'usa directament en una altra expressió *b* si existeix un arc
   de l'expressió *b* cap a l'expressió *a*. Per exemple:
   
   .. literalinclude:: graf_exp-6.txt
      :language: python3
      :lines: 1- 

   .. note::
        Disposeu de jocs de prova al fitxer :download:`graf_exp-6.txt<graf_exp-6.txt>`

#. Dissenyeu la funció següent:

   .. py:function:: vars_expr(g, e)

   Retorna la llista de les variables de ``g`` que apareixen en
   l'expressió ``e``. Per exemple:

   .. literalinclude:: graf_exp-7.txt
      :language: python3
      :lines: 1- 

   Per resoldre aquest problema podeu usar les funcions de
   :py:ref:`recorregut d'un digraf <networkx:traversal>` tant en
   profunditat com en amplada a més de mètodes bàsics de
   :py:ref:`DiGraph <networkx:digraph>`.

   .. note::
        Disposeu de jocs de prova al fitxer :download:`graf_exp-7.txt<graf_exp-7.txt>`

#. Dissenyeu la funció següent:

   .. py:function:: exps_completes(g)

   Retorna la llista de les expressions completes del digraf
   ``g``. Recordeu que les expressions completes no són subexpressió
   de cap altra expressió. Per exemple:

   .. literalinclude:: graf_exp-8.txt
      :language: python3
      :lines: 1- 

   .. note::
        Disposeu de jocs de prova al fitxer :download:`graf_exp-8.txt<graf_exp-8.txt>`


#. Dissenyeu la funció següent:

   .. py:function:: ordre_avaluacio(g, e)

   Retorna la llista de les variables i expressions de ``g`` en
   l'ordre adequat per tal d'avaluar l'expressió ``e``. L'ordre és
   l'adequat si totes les subexpressions d'una expressió apareixen
   abans que ella a la llista. Per exemple:
   
   .. literalinclude:: graf_exp-9.txt
      :language: python3
      :lines: 1- 

   Per resoldre aquest problema podeu usar la funció de
   :py:func:`recorregut en profunditat en post-ordre d'un digraf
   <networkx.algorithms.traversal.depth_first_search.dfs_postorder_nodes>`.

   .. note::
        Disposeu de jocs de prova al fitxer :download:`graf_exp-9.txt<graf_exp-9.txt>`

#. Dissenyeu la funció següent:

   .. py:function:: exps_depenen(g, v)

   Retorna la llista de les expressions de ``g`` que depenen
   directament o indirectament de la variable ``v``. Per exemple:
   
   .. literalinclude:: graf_exp-10.txt
      :language: python3
      :lines: 1- 

   Per resoldre aquest problema podeu usar les funcions de
   :py:ref:`recorregut d'un digraf <networkx:traversal>` tant en
   profunditat com en amplada. Però el recorregut cal fer-lo sobre el
   :py:meth:`graf invers <networkx.DiGraph.reverse>`.

   .. note::
        Disposeu de jocs de prova al fitxer :download:`graf_exp-10.txt<graf_exp-10.txt>`

.. rubric:: Solució
	       
Disposeu d'una solució a  :download:`graf_exp.py <solucio/graf_exp.py>`.