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:

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:

Digraf que representa dues expressions.

Per dissenyar les funcions d’aquest exercici podeu utilitzar alguns dels mètodes de la classe DiGraph.

Deseu les funcions següents al mòdul graf_exp.py.

1. Dissenyeu la funció següent:

   graf_exp.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:

   >>> from graf_exp import crea_digraf_exps
   
   >>> le = [('a*(b+c)-c/b', 'a*(b+c)'), ('a*(b+c)-c/b', 'c/b'),
   ... ('a*(b+c)', 'a'), ('a*(b+c)', 'b+c'),
   ... ('c/b', 'c'), ('c/b', 'b'),
   ... ('b+c', 'b'), ('b+c', 'c')]
   >>> g = crea_digraf_exps(le)
   >>> sorted(g.nodes())
   ['a', 'a*(b+c)', 'a*(b+c)-c/b', 'b', 'b+c', 'c', 'c/b']
   >>> for i, e in enumerate(sorted(g.edges())):
   ...   print(e)
   ('a*(b+c)', 'a')
   ('a*(b+c)', 'b+c')
   ('a*(b+c)-c/b', 'a*(b+c)')
   ('a*(b+c)-c/b', 'c/b')
   ('b+c', 'b')
   ('b+c', 'c')
   ('c/b', 'b')
   ('c/b', 'c')
   

   Nota

   Disposeu de jocs de prova al fitxer graf_exp-1.txt

2. Dissenyeu la funció següent:

   graf_exp.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:

   >>> from graf_exp import crea_digraf_camins
   
   >>> lc = [
   ... ['a*(b+c)-c/b', 'a*(b+c)', 'a'],
   ... ['a*(b+c)-c/b', 'c/b', 'b'],
   ... ['a*(b+c)', 'b+c'],
   ... ['b+c', 'b'],
   ... ['b+c', 'c'],
   ... ['c/b', 'c']]
   >>> g = crea_digraf_camins(lc)
   >>> sorted(g.nodes())
   ['a', 'a*(b+c)', 'a*(b+c)-c/b', 'b', 'b+c', 'c', 'c/b']
   >>> for i, e in enumerate(sorted(g.edges())):
   ...   print(e)
   ('a*(b+c)', 'a')
   ('a*(b+c)', 'b+c')
   ('a*(b+c)-c/b', 'a*(b+c)')
   ('a*(b+c)-c/b', 'c/b')
   ('b+c', 'b')
   ('b+c', 'c')
   ('c/b', 'b')
   ('c/b', 'c')
   

   Nota

   Disposeu de jocs de prova al fitxer graf_exp-2.txt

3. Dissenyeu la funció següent:

   graf_exp.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:

   >>> from graf_exp import *
   
   >>> lc = [
   ... ['a*(b+c)-c/b', 'a*(b+c)', 'a'],
   ... ['a*(b+c)-c/b', 'c/b', 'b'],
   ... ['a*(b+c)', 'b+c'],
   ... ['b+c', 'b'],
   ... ['b+c', 'c'],
   ... ['c/b', 'c']]
   >>> g = crea_digraf_camins(lc)
   >>> vars_usades(g)
   ['a', 'b', 'c']
   

   Nota

   Disposeu de jocs de prova al fitxer graf_exp-3.txt

4. Dissenyeu la funció següent:

   graf_exp.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:

   >>> from graf_exp import *
   
   >>> le = [('a*(b+c)-c/b', 'a*(b+c)'), ('a*(b+c)-c/b', 'c/b'),
   ... ('a*(b+c)', 'a'), ('a*(b+c)', 'b+c'),
   ... ('c/b', 'c'), ('c/b', 'b'),
   ... ('b+c', 'b'), ('b+c', 'c')]
   >>> g = crea_digraf_exps(le)
   >>> vars_mes_usades(g)
   ['b', 'c']
   
   

   Nota

   Disposeu de jocs de prova al fitxer graf_exp-4.txt

5. Dissenyeu la funció següent:

   graf_exp.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:

   >>> from graf_exp import *
   
   >>> lc = [
   ... ['a*(b+c)-c/b', 'a*(b+c)', 'a'],
   ... ['a*(b+c)-c/b', 'c/b', 'b'],
   ... ['a*(b+c)', 'b+c'],
   ... ['b+c', 'b'],
   ... ['b+c', 'c'],
   ... ['c/b', 'c']]
   >>> g = crea_digraf_camins(lc)
   >>> vars_directes(g, 'b+c')
   ['b', 'c']
   >>> vars_directes(g, 'a*(b+c)')
   ['a']
   >>> vars_directes(g, 'a*(b+c)-c/b')
   []
   

   Nota

   Disposeu de jocs de prova al fitxer graf_exp-5.txt

6. Dissenyeu la funció següent:

   graf_exp.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:

   >>> from graf_exp import *
   
   >>> lc = [
   ... ['a*(b+c)-c/b', 'a*(b+c)', 'a'],
   ... ['a*(b+c)-c/b', 'c/b', 'b'],
   ... ['a*(b+c)', 'b+c'],
   ... ['(b+c)*(c/b)','c/b'],
   ... ['(b+c)*(c/b)','b+c'],
   ... ['b+c', 'b'],
   ... ['b+c', 'c'],
   ... ['c/b', 'c']]
   >>> g = crea_digraf_camins(lc)
   >>> lemu = exps_mes_usades(g)
   >>> print (sorted(lemu))
   ['b+c', 'c/b']
   

   Nota

   Disposeu de jocs de prova al fitxer graf_exp-6.txt

7. Dissenyeu la funció següent:

   graf_exp.vars_expr(g, e)

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

   >>> from graf_exp import *
   
   >>> lc = [
   ... ['a*(b+c)-c/b', 'a*(b+c)', 'a'],
   ... ['a*(b+c)-c/b', 'c/b', 'b'],
   ... ['a*(b+c)', 'b+c'],
   ... ['b+c', 'b'],
   ... ['b+c', 'c'],
   ... ['c/b', 'c']]
   >>> g = crea_digraf_camins(lc)
   >>> lve = vars_expr(g, 'b+c')
   >>> print (sorted(lve))
   ['b', 'c']
   >>> lve = vars_expr(g, 'a*(b+c)')
   >>> print (sorted(lve))
   ['a', 'b', 'c']
   >>> lve = vars_expr(g, 'a*(b+c)-c/b')
   >>> print (sorted(lve))
   ['a', 'b', 'c']
   

   Per resoldre aquest problema podeu usar les funcions de recorregut d’un digraf tant en profunditat com en amplada a més de mètodes bàsics de DiGraph.

   Nota

   Disposeu de jocs de prova al fitxer graf_exp-7.txt

8. Dissenyeu la funció següent:

   graf_exp.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:

   >>> from graf_exp import *
   
   >>> le = [('a*(b+c)', 'a'), ('a*(b+c)', 'b+c'),
   ... ('c/b', 'c'), ('c/b', 'b'),
   ... ('b+c', 'b'), ('b+c', 'c')]
   >>> g = crea_digraf_exps(le)
   >>> lec = exps_completes(g)
   >>> print (sorted(lec))
   ['a*(b+c)', 'c/b']
   

   Nota

   Disposeu de jocs de prova al fitxer graf_exp-8.txt

9. Dissenyeu la funció següent:

   graf_exp.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:

   >>> from graf_exp import *
   
   >>> le = [('a*(b+c)-c/b', 'a*(b+c)'), ('a*(b+c)-c/b', 'c/b'),
   ... ('a*(b+c)', 'a'), ('a*(b+c)', 'b+c'),
   ... ('c/b', 'c'), ('c/b', 'b'),
   ... ('b+c', 'b'), ('b+c', 'c')]
   >>> g = crea_digraf_exps(le)
   >>> loa = ordre_avaluacio(g, 'b+c')
   >>> loa in (
   ... ['c', 'b', 'b+c'],
   ... ['b', 'c', 'b+c'],
   ... )
   True
   >>> loa = ordre_avaluacio(g, 'a*(b+c)')
   >>> loa in (
   ... ['a', 'b', 'c', 'b+c', 'a*(b+c)'],
   ... ['a', 'c', 'b', 'b+c', 'a*(b+c)'],
   ... ['b', 'a', 'c', 'b+c', 'a*(b+c)'],
   ... ['b', 'c', 'a', 'b+c', 'a*(b+c)'],
   ... ['c', 'a', 'b', 'b+c', 'a*(b+c)'],
   ... ['c', 'b', 'a', 'b+c', 'a*(b+c)'],
   ... ['b', 'c', 'b+c', 'a', 'a*(b+c)'],
   ... ['c', 'b', 'b+c', 'a', 'a*(b+c)'],
   ... )
   True
   >>> loa = ordre_avaluacio(g, 'a*(b+c)-c/b')
   >>> loa in (
   ... ['a', 'b', 'c', 'c/b', 'b+c', 'a*(b+c)', 'a*(b+c)-c/b'],
   ... ['a', 'c', 'b', 'c/b', 'b+c', 'a*(b+c)', 'a*(b+c)-c/b'],
   ... ['b', 'a', 'c', 'c/b', 'b+c', 'a*(b+c)', 'a*(b+c)-c/b'],
   ... ['c', 'a', 'b', 'c/b', 'b+c', 'a*(b+c)', 'a*(b+c)-c/b'],
   ... ['b', 'c', 'a', 'c/b', 'b+c', 'a*(b+c)', 'a*(b+c)-c/b'],
   ... ['c', 'b', 'a', 'c/b', 'b+c', 'a*(b+c)', 'a*(b+c)-c/b'],
   ... ['b', 'c', 'c/b', 'a', 'b+c', 'a*(b+c)', 'a*(b+c)-c/b'],
   ... ['c', 'b', 'c/b', 'a', 'b+c', 'a*(b+c)', 'a*(b+c)-c/b'],
   ... ['b', 'c', 'c/b', 'b+c', 'a', 'a*(b+c)', 'a*(b+c)-c/b'],
   ... ['c', 'b', 'c/b', 'b+c', 'a', 'a*(b+c)', 'a*(b+c)-c/b'],
   ... ['a', 'b', 'c', 'b+c', 'c/b', 'a*(b+c)', 'a*(b+c)-c/b'],
   ... ['a', 'c', 'b', 'b+c', 'c/b', 'a*(b+c)', 'a*(b+c)-c/b'],
   ... ['b', 'a', 'c', 'b+c', 'c/b', 'a*(b+c)', 'a*(b+c)-c/b'],
   ... ['c', 'a', 'b', 'b+c', 'c/b', 'a*(b+c)', 'a*(b+c)-c/b'],
   ... ['b', 'c', 'a', 'b+c', 'c/b', 'a*(b+c)', 'a*(b+c)-c/b'],
   ... ['c', 'b', 'a', 'b+c', 'c/b', 'a*(b+c)', 'a*(b+c)-c/b'],
   ... ['b', 'c', 'b+c', 'a', 'c/b', 'a*(b+c)', 'a*(b+c)-c/b'],
   ... ['c', 'b', 'b+c', 'a', 'c/b', 'a*(b+c)', 'a*(b+c)-c/b'],
   ... ['b', 'c', 'b+c', 'c/b', 'a', 'a*(b+c)', 'a*(b+c)-c/b'],
   ... ['c', 'b', 'b+c', 'c/b', 'a', 'a*(b+c)', 'a*(b+c)-c/b'],
   ... ['a', 'b', 'c', 'b+c', 'a*(b+c)', 'c/b', 'a*(b+c)-c/b'],
   ... ['a', 'c', 'b', 'b+c', 'a*(b+c)', 'c/b', 'a*(b+c)-c/b'],
   ... ['b', 'a', 'c', 'b+c', 'a*(b+c)', 'c/b', 'a*(b+c)-c/b'],
   ... ['c', 'a', 'b', 'b+c', 'a*(b+c)', 'c/b', 'a*(b+c)-c/b'],
   ... ['b', 'c', 'a', 'b+c', 'a*(b+c)', 'c/b', 'a*(b+c)-c/b'],
   ... ['c', 'b', 'a', 'b+c', 'a*(b+c)', 'c/b', 'a*(b+c)-c/b'],
   ... ['b', 'c', 'b+c', 'a', 'a*(b+c)', 'c/b', 'a*(b+c)-c/b'],
   ... ['c', 'b', 'b+c', 'a', 'a*(b+c)', 'c/b', 'a*(b+c)-c/b'],
   ... )
   True
   

   Per resoldre aquest problema podeu usar la funció de recorregut en profunditat en post-ordre d'un digraf.

   Nota

   Disposeu de jocs de prova al fitxer graf_exp-9.txt

10. Dissenyeu la funció següent:

    graf_exp.exps_depenen(g, v)

    Retorna la llista de les expressions de g que depenen directament o indirectament de la variable v. Per exemple:

    >>> from graf_exp import *
    
    >>> le = [('a*(b+c)-c/b', 'a*(b+c)'), ('a*(b+c)-c/b', 'c/b'),
    ... ('a*(b+c)', 'a'), ('a*(b+c)', 'b+c'),
    ... ('c/b', 'c'), ('c/b', 'b'),
    ... ('b+c', 'b'), ('b+c', 'c')]
    >>> g = crea_digraf_exps(le)
    >>> led = exps_depenen(g, 'b')
    >>> print (sorted(led))
    ['a*(b+c)', 'a*(b+c)-c/b', 'b', 'b+c', 'c/b']
    >>> led = exps_depenen(g, 'a')
    >>> print (sorted(led))
    ['a', 'a*(b+c)', 'a*(b+c)-c/b']
    

    Per resoldre aquest problema podeu usar les funcions de recorregut d’un digraf tant en profunditat com en amplada. Però el recorregut cal fer-lo sobre el graf invers.

    Nota

    Disposeu de jocs de prova al fitxer graf_exp-10.txt

Solució

Disposeu d’una solució a graf_exp.py.