Re: [jep-users] Cascading dependencies and auto-evaluation

[Richard Morris]

Hi,

This seems to be a recurring question. A similar question has been
asked a couple of times before see
https://groups.google.com/group/jep-users/browse_thread/thread/3073eb988a6a2523
and
https://groups.google.com/group/jep-users/browse_thread/thread/29d15e5f6284881b

I'll work on a slightly tidier solution but it may take a day or so.

Rich

On Wed, Jun 20, 2012 at 4:24 PM, <he...@anthologique.net> wrote:
> Hello,
>
> Let's say we have the following exemple :
>
> a = b + c
> b = 5
> c = 2 * d
> d = 10
>
> Consider we have a Jep with everything parsed and evaluated
> Then we change the value of d (either by re-parsing a new string or doing an
> add variable)
> Is it possible to have the correct value of "a" without re-evaluating
> everything ?
>
> There are some discussions here about out-of-order variable evaluations not
> possible in Jep, so I imagine there is no dependancy resolution system that
> would solve my needs ?
>
> Thanks !
>
> --
> You received this message because you are subscribed to the Google Groups
> "Jep Java Users" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/jep-users/-/1Ba1lnFqudoJ.
> To post to this group, send email to jep-...@googlegroups.com.
> To unsubscribe from this group, send email to
> jep-users+...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/jep-users?hl=en.

[Richard Morris]

Christophe 

It is certainly possible to build such a system. Essentially the set of equations form a Directed Acyclic Graph (http://en.wikipedia.org/wiki/Directed_acyclic_graph) which I'm working on implementing at the moment. With such a data structure it relatively easy to follow a change of a variable value through the graph and re-evaluate all the equations necessary. 

XJep worked in a top down fashion, if the variable 'a' was requested it would descend through the tree re-evaluating variables as needed. You can also have a bottom up solution where a change in a variable will cause the other variables which depend on it to be re-evaluated.

I'll let you know progress on a solution.

Richard

[Richard Morris]

Christophe

Its taken a while to develop a flexible solution to the problem. Below
is a class which handles the dependancy of a set of equations. Its
based around creating a Directed Acyclic Graph from the set of nodes.
Key algorithms produce a topological order for the expressions so the
expressions can be evaluated in turn and algorithms which find all the
expressions which depend on a variable or all expressions a variable
depends on. You could combine the results of these to find which
expressions need to be updated when a variable changes.

You might want to roll your own solution which is more specific to
your needs. The key finding the variables on the left and right of the
assignment. The following code fragment does this
Variable lhsName;
Set<Variable> rhsNames;
Operator assign=jep.getOperatorTable().getAssign();
boolean isEqn = assign.equals(eqn.getOperator());
boolean isAssignmentEqn = isEqn && (eqn.jjtGetChild(0) instanceof ASTVarNode);
if(isAssignmentEqn) {
lhsName = eqn.jjtGetChild(0).getVar();
TreeAnalyzer ta = new TreeAnalyzer(eqn.jjtGetChild(1));
rhsNames = ta.getVariables().keySet();
}
else {
lhsName = null;
TreeAnalyzer ta = new TreeAnalyzer(eqn);
rhsNames = ta.getVariables().keySet();
}

You could then use this information to build your own graph structure.
JGraphT http://jgrapht.org/ is a powerful library for working with
graph structures.

I hope this is the kind of thing your thinking of.

Richard

package com.singularsys.jep.misc.eqntiondependance;

import java.util.AbstractCollection;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import com.singularsys.jep.Jep;
import com.singularsys.jep.JepComponent;
import com.singularsys.jep.JepException;
import com.singularsys.jep.Operator;
import com.singularsys.jep.OperatorTableI;
import com.singularsys.jep.Variable;
import com.singularsys.jep.parser.ASTVarNode;
import com.singularsys.jep.parser.Node;
import com.singularsys.jep.walkers.TreeAnalyzer;

/**
* <p>
* A collection of equations ordered so they can be evaluated in turn.
* Equations are added to the class using the {@link #add add(Node)} method
* and an ordered sequence of equations is obtained
* from a {@link Iterator Iterator<Node>} returned by the {@link
#iterator()} method.
* This gives the order of the equations will be such that they can be
evaluated in turn.
* The {@link #topolologicalOrder()} method returns the same list as
the Iterator.
* </p>
*
* <p>
* The equations added should typically be of the form "b=a+1" with a
single variable on the left hand side
* of the equals sign and an expression using other variables on the right.
* The ordering will be such that for "b=a+1", "a=1" as "a" is on the
RHS of the first equation and the LHS of the second
* the first equation depends on the second so the final order will be
"a=1", "b=a+1". Equations need not contain an
* assignment.
* </p>
* <p>
* If the set of equations have a cycle (like "a=b+1", "b=c+1", "c=a+1") then
* the {@link #isGood} method returns false, the iterator will include
all nodes but with no guarantee of order.
* </p>
*
* <p>
* A typical use of the class might be:
* <pre>
// Setup
Jep jep = new Jep();
DAG dag=new DAG(jep);

// Parse a set of equations and add them to the collection
String[] eqns=new String[]{"d=b+c","a=1","b=a+1","c=a+2"};
for(String s:eqns) {
Node n=jep.parse(s);
dag.add(n);
if(!dag.isGood())
System.out.println("Cycle in equations");
}

// Evaluate the equations in turn
Iterator<Node> itt=dag.iterator();
while(itt.hasNext()) {
Node n=itt.next();
Object res = jep.evaluate(n);
jep.print(n);
System.out.println("\tvalue "+res);
}
* </pre>
* @author rich
*
*/

public class DAG extends AbstractCollection<Node> implements
JepComponent,DependancyTableI {
private static final long serialVersionUID = 350L;
protected Jep jep;
protected Operator assign;
/** Whether the dag contains cycles */
protected boolean good;
List<Node> topOrder=null;
/**
* The underlying list of nodes
*/
protected LinkedList<DAGNode> list=new LinkedList<DAGNode>();
/**
* Lookup table for variables
*/
protected Map<Variable,DAGNode> vmap=new HashMap<Variable,DAGNode>();
/**
* Lookup table for expressions
*/
protected Map<Node,DAGNode> nmap=new HashMap<Node,DAGNode>();


public DAG() {

}

public DAG(Jep jep) {
super();
this.jep = jep;
init(jep);
}

@Override
public void init(Jep j) {
this.jep = j;
OperatorTableI ot = jep.getOperatorTable();
assign = ot.getAssign();
}

@Override
public JepComponent getLightWeightInstance() {
return null;
}


/**
* Represents a node in the graph.
* Nodes can either be for assignment equations "b=c+1", non-assignment
* equations "a+b+c", or variables without equations "c".
* @author rich
*
*/
public static class DAGNode {
/** Node this node depends on, i.e. variables the equation depends on. */
Set<DAGNode> in=new HashSet<DAGNode>();
/** Nodes that depend on this node, i.e. expressions which depend on
this variable. */
Set<DAGNode> out=new HashSet<DAGNode>();
Variable lhsvar;
Node eqn;
boolean done;
static int anonNum=0;
/** A unique number for non assignment expressions */
int num;

/** Construct a node with an equation and a variable (which can be null). */
public DAGNode(Node n, Variable v) {
super();
this.eqn = n;
this.lhsvar = v;
if(v==null)
num=anonNum++;
}
/** Construct a node with just a variable. */
public DAGNode(Variable v) {
this.lhsvar = v;
}
/** a unique identifier, either the lhs variable name or a unique number. */
@Override
public String toString() {
if(lhsvar!=null) return lhsvar.getName() + ":";
return "#"+num;
}

}

public Set<Variable> rhsVariables(Node eqn) throws JepException {
Set<Variable> rhsVars=null;

boolean isEqn = assign.equals(eqn.getOperator());
boolean isAssignmentEqn = isEqn && (eqn.jjtGetChild(0) instanceof ASTVarNode);
if(isAssignmentEqn) {
TreeAnalyzer ta = new TreeAnalyzer(eqn.jjtGetChild(1));
rhsVars = ta.getVariables().keySet();
}
else {
TreeAnalyzer ta = new TreeAnalyzer(eqn);
rhsVars = ta.getVariables().keySet();
}
return rhsVars;
}

public Variable lhsVariable(Node eqn) {
Variable lhsV=null;

boolean isEqn = assign.equals(eqn.getOperator());
boolean isAssignmentEqn = isEqn && (eqn.jjtGetChild(0) instanceof ASTVarNode);
if(isAssignmentEqn) {
return eqn.jjtGetChild(0).getVar();
}
return null;
}

/**
* Add an expression to the list.
* If a cycle is found in the set of expressions it still returns
true, use {@link #isGood isGood()} to
* determine if their is a cycle.
* @return true
* @throws IllegalArgumentException if an error processing the expression
*/
@Override
public boolean add(Node eqn) {
Variable lhsV=lhsVariable(eqn);
Set<Variable> rhsVars;
try {
rhsVars=rhsVariables(eqn);
} catch (JepException e) {
throw new IllegalArgumentException(e);
}

this.topOrder=null;

boolean isNew=true;
DAGNode dn= lhsV!=null ? vmapGet(lhsV) : null;
if(dn!=null) {
if(dn.eqn!=null)
nmapRemove(dn.eqn);
dn.eqn=eqn;
nmapPut(eqn, dn);
isNew=false;
for(DAGNode dn2:dn.in) {
dn2.out.remove(dn);
}
dn.in.clear();
} else {
dn=new DAGNode(eqn,lhsV);
nmapPut(eqn, dn);
if(lhsV!=null)
vmapPut(lhsV, dn);
}
for(Variable v:rhsVars) {
DAGNode dn2=getOrMake(v);
dn.in.add(dn2);
dn2.out.add(dn);
}
if(isNew)
return add(dn);
good=fixList();
return true;
}



/**
* Returns an {@link Iterator Iterator<Node>} over the ordered set of
equations.
* The iterator implements <code>hasNext<code> and <code>next</code>
but not <code>remove</code>.
* @return an iterator
*/
@Override
public Iterator<Node> iterator() {
return topolologicalOrder().iterator();
}

/**
* An unmodifiable list of nodes in the topological order.
*/
@Override
public List<Node> topolologicalOrder() {
if(topOrder!=null)
return topOrder;

List<Node> res=new ArrayList<Node>();
for(DAGNode dn:list) {
if(dn.eqn!=null)
res.add(dn.eqn);
}
topOrder=Collections.unmodifiableList(res);
return topOrder;
}


/**
* Remove a node from the list.
* @param o the node to be removed
* @return
*/
@Override
public boolean remove(Object o) {
if(o instanceof Node)
return remove((Node) o);
return false;
}

public boolean remove(Node n) {
this.topOrder=null;

DAGNode dn=nmapRemove(n);
if(dn==null) return false;
for(DAGNode dn2:dn.in) {
dn2.out.remove(dn);
}
if(dn.out.isEmpty()) {
list.remove(dn);
} else {
dn.in.clear();
dn.eqn=null;
}
good=fixList();
return true;
}




@Override
public Set<Node> directDependants(Variable v) throws JepException {
DAGNode dn=vmapGet(v);
if(dn==null)
throw new JepException("Variable "+v.getName()+" not in collection");
Set<Node> res=new HashSet<Node>();
for(DAGNode out:dn.out) {
if(out.eqn!=null)
res.add(out.eqn);
}
return res;
}

@Override
public Set<Node> deepDependants(Variable v) throws JepException {
Set<Node> res=new HashSet<Node>();
DAGNode dn=vmapGet(v);
if(dn==null)
throw new JepException("Variable "+v.getName()+" not in collection");

for(DAGNode dn2:list) dn2.done=false;
Queue<DAGNode> queue=new LinkedList<DAGNode>();
for(DAGNode out:dn.out) {
queue.add(out);
}
while(!queue.isEmpty()) {
DAGNode dn2=queue.remove();
dn2.done=true;
for(DAGNode out:dn2.out) {
if(!out.done)
queue.add(out);
}
if(dn2.eqn!=null)
res.add(dn2.eqn);
}
return res;
}


@Override
public Set<Variable> dependsOn(Node n) throws JepException {
DAGNode dn=nmapGet(n);
if(dn==null)
throw new JepException("Node "+jep.toString(n)+" not in collection");
Set<Variable> res= new HashSet<Variable>();
for(DAGNode dn2:dn.in) {
if(dn2.lhsvar!=null)
res.add(dn2.lhsvar);
}
return res;
}


@Override
public Set<Variable> deepDependsOn(Node n) throws JepException {
DAGNode dn=nmapGet(n);
if(dn==null)
throw new JepException("Node "+jep.toString(n)+" not in collection");
Set<Variable> res= new HashSet<Variable>();

for(DAGNode dn2:list) dn2.done=false;
Queue<DAGNode> queue=new LinkedList<DAGNode>();
for(DAGNode in:dn.in)
queue.add(in);
while(!queue.isEmpty()) {
DAGNode dn2=queue.remove();
dn2.done=true;
for(DAGNode in:dn2.in) {
if(!in.done)
queue.add(in);
}
if(dn2.lhsvar!=null)
res.add(dn2.lhsvar);
}
return res;
}


@Override
public Set<Variable> allVariables() {
return vmap.keySet();
}

@Override
public Set<Variable> allLHSVariables() {
Set<Variable> res=new HashSet<Variable>();
for(DAGNode dn:list) {
if(dn.lhsvar!=null && dn.eqn!=null)
res.add(dn.lhsvar);
}
return res;
}

@Override
public Set<Variable> allRHSVariables() {
Set<Variable> res=new HashSet<Variable>();

for(DAGNode dn:list) {
if(dn.out.size()!=0) {
if(dn.lhsvar!=null)
res.add(dn.lhsvar);
}
}
return res;
}

@Override
public Set<Variable> unassignedVariables() {
Set<Variable> res=new HashSet<Variable>();

for(DAGNode dn:list) {
if(dn.eqn==null && dn.lhsvar!=null) {
res.add(dn.lhsvar);
}
}
return res;
}

public Set<Variable> unusedVariables() {
Set<Variable> res=new HashSet<Variable>();

for(DAGNode dn:list) {
if(dn.in.size()==0 && dn.out.size()==0 && dn.lhsvar!=null && dn.eqn
== null) {
res.add(dn.lhsvar);
}
}
return res;
}


public void removeUnusedVariables() {
Iterator<DAGNode> itt=list.listIterator();
boolean changed=false;
while(itt.hasNext()) {
DAGNode dn=itt.next();
if(dn.in.size()==0 && dn.out.size()==0 && dn.lhsvar!=null && dn.eqn
== null) {
itt.remove();
changed=true;
}
}
if(changed)
good=fixList();
return;
}

/** Get the equation associated with a variable.
*
* @param v the variable
* @return the node v is on the LHS or null if v not found or no
equation for the variable.
*/
public Node equationForVariable(Variable v) {
DAGNode dn=this.vmapGet(v);
if(dn==null) return null;
return dn.eqn;
}

/**
* Get the LHS variable for an equation.
* @param n the equation
* @return the variable or null if n not found or n is not an
assignment equation.
*/
public Variable variableForEquation(Node n) {
DAGNode dn=this.nmapGet(n);
if(dn==null) return null;
return dn.lhsvar;
}

/**
* Whether the graph contains cycles.
* @return false if there is a cycle
*/
public boolean isGood() {
return good;
}

/**
* The size of the list of nodes.
* @return the size
*/
@Override
public int size() {
if(this.topOrder==null)
this.topolologicalOrder();
return topOrder.size();
}


/**
* Add a new node to the list.
* If necessary calls {@link #fixList}
* @param dn
* @return true
*/
protected boolean add(DAGNode dn) {
this.topOrder=null;
if(dn.out.size()==0) {
list.add(dn);
return true;
}
else if(dn.in.size()==0) {
list.push(dn);
return true;
}
else {
list.add(dn);
}
good = fixList();
return true;
}

/**
* Fix the list so that the DAGNode are in topological order.
* <p>
* The algorithm works by building a new list, it repeatedly
* loops through the old list, checking if the current element only
depends on elements in the new list.
* When such an element is found its added to the new list and
removed from the old one. The process repeats
* until the old list is empty. This ensures no element depends on
one after it.
* If there is a cycle each element is added to the new list but
there is no guarantee of the order.</p>
* @return true if their are no cycles false otherwise.
*/
protected boolean fixList() {
this.topOrder=null;

LinkedList<DAGNode> res=new LinkedList<DAGNode>();
ListIterator<DAGNode> li=list.listIterator();
while(li.hasNext()) {
DAGNode dn=li.next();

if(dn.in.size()==0){
dn.done=true;
li.remove();
res.add(dn);
}
else
dn.done=false;
}
while(!list.isEmpty()) {
li=list.listIterator();
boolean added=false;
while(li.hasNext()) {
DAGNode dn2=li.next(); // node to test
boolean OK=true;
for(DAGNode dn3:dn2.in) { // check the outputs
if(!dn3.done) {
OK=false;
break;
}
}
if(OK) {
li.remove();
dn2.done=true;
res.add(dn2);
added=true;
break;
}
}
if(!added) {
break;
}

}

if(!list.isEmpty()) {
// failed graph has a cycle
// simple add remaining nodes
for(DAGNode dn:list)
res.add(dn);
list=res;
return false;
}

list=res;
return true;
}


/**
* Get the node corresponding to a variable, or make a new node if
the variable does not
* already exist.
* @param v
* @return an existing node if one exists or a new node
*/
protected DAGNode getOrMake(Variable v) {
DAGNode n=vmapGet(v);
if(n==null) {
n=new DAGNode(v);
vmapPut(v, n);
add(n);
}
return n;
}

/**
* Get the node corresponding to a variable
* @param v
* @return either the node or null
*/
protected DAGNode vmapGet(Variable v) {
DAGNode n=vmap.get(v);
return n;
}

protected DAGNode vmapPut(Variable lhsName, DAGNode dn) {
return vmap.put(lhsName,dn);
}

protected DAGNode nmapPut(Node eqn, DAGNode dn) {
return nmap.put(eqn, dn);
}

protected DAGNode nmapRemove(Node eqn) {
return nmap.remove(eqn);
}

protected DAGNode nmapGet(Node n) {
return nmap.get(n);
}

}

On Tue, Jun 26, 2012 at 7:39 AM, Christophe Porté <he...@anthologique.net> wrote:
> Hello,
>
> Thanks for your work, with such a feature it will certainly convince us to
> buy the library instead of rewriting something from scratch
>
> Hope it will come soon !

> --
> You received this message because you are subscribed to the Google Groups
> "Jep Java Users" group.
> To view this discussion on the web visit

> https://groups.google.com/d/msg/jep-users/-/fmLwgcZO5VsJ.