<br> I will bite... :) follow my thoughts:<br><br>(1) Is this a good problem for rules?<br> <br> Yes, I would prefer to solve this with rules instead of with an algorithm. Reasons are because it is well defined problem, it is expressed as a set of rules by business, it will be easier to implement and maintain long term, and it is likely that the rules might change over time. The drawbacks are that the declarative solution will be heavier than the algorithmic solution, but since it is not a critical path problem and results can even be cached and only recalculated when data changes, that will probably not be a problem for your application.<br>
<br>(2) How you would do it?<br><br> There is only one thing that is tricky in this problem for a declarative solution to deal with, and that is the recursiveness of departments, as you can have an arbitrary number of departments in the hierarchy, and you need to define relationships between managers and employees in different levels of the hierarchy. To solve that the best way I know of is by calculating the transitive closure, either for departments or for employees/managers. Since you will have a lot less departments than employees, best is to do it for departments. The closure can easily be calculated with 2 rules, but could also be calculated in an external procedure and asserted as data into the working memory. I am doing it in the rules.<br>
<br> Other than that, there are several strategies to model the solution on a forward chaining engine. In my case, I am opting for finding all eligible approvers first and then eliminating the "false positives" and finally electing the best (nearest manager) among the remaining approvers. This could be done in several other ways, including finding conflicts first and then the actual approvers or taking incremental approaches.<br>
<br> Also, just to simplify the example, I am using salience as a conflict resolution, but on a real application I would prefer to use ruleflow-groups.<div><br></div><div> Let me know what do you think... :)</div><div>
<br></div><div> Cheers,</div><div> Edson</div><div><br></div><div>-------<br> <br> With your example dataset, my result was:<br><br><font class="Apple-style-span" face="'courier new', monospace">Employee: Mike Approver: Hilary<br>
Employee: John Approver: Hilary<br>Employee: Kate Approver: Hilary<br>Employee: Janet Approver: Jessica<br>Employee: Jessica Approver: Kate<br>Employee: Jane Approver: Erica<br>Employee: Erica Approver: Kate</font><br><br>
Domain model (pseudo-code):<br><br><font class="Apple-style-span" face="'courier new', monospace">Person { name }<br>Department { name, parent, managers, employees }<br>Approver { employee, manager, distance }<br>
DepartmentHierarchy { parent, sub, distance }</font><br><br> Rules (actual code):<br><br>============<br><font class="Apple-style-span" face="'courier new', monospace"><div>package org.drools.approver</div><div>
<br></div><div>dialect "mvel"</div><div><br></div><div>/*********************************************************</div><div> * Calculate the transitive closure for the Departments </div><div> *********************************************************/</div>
<div>rule "Create direct department hierarchy"</div><div>when</div><div> $d : Department( parent != null )</div><div> not( DepartmentHierarchy( parent == $d.parent, sub == $d ) )</div><div>then</div><div> insert( new DepartmentHierarchy( $d, $d, 0 ) );</div>
<div> insert( new DepartmentHierarchy( $d.parent, $d, 1 ) );</div><div>end</div><div><br></div><div>rule "Create transitive department hierarchy"</div><div>when</div><div> $dh1 : DepartmentHierarchy( )</div>
<div> $dh2 : DepartmentHierarchy( parent == $dh1.sub )</div><div> not( DepartmentHierarchy( parent == $dh1.parent, sub == $dh2.sub ) )</div><div>then</div><div> insert( new DepartmentHierarchy( $dh1.parent, $dh2.sub, $dh1.distance + $dh2.distance ) );</div>
<div>end</div><div><br></div><div>/*********************************************************</div><div> * Business Rules </div><div> *********************************************************/</div><div>rule "1. Define eligible approvers"</div>
<div> @doc( "An eligible approver must be a direct or indirect manager of the Person" )</div><div>when</div><div> // there is a person</div><div> $e : Person( )</div><div> // that is either an employee or a manager in department d1</div>
<div> $d1 : Department( employees contains $e || managers contains $e )</div><div> // and there is a department d2 in which that employee is not a manager of</div><div> $d2 : Department( managers not contains $e ) </div>
<div> // and the department d2 is a parent department of the department d1 in the hierarchy</div><div> $dh : DepartmentHierarchy( parent == $d2, sub == $d1 )</div><div> // and there is a manager on the department d2</div>
<div> $m : Person( this memberOf $d2.managers )</div><div>then</div><div> // this manager is an eligible approver for the employee</div><div> insert( new Approver( $e, $m, $dh.distance ) );</div><div>end</div><div>
</div><div>rule "2.a. Approver cannot be himself"</div><div> @doc( "An approver cannot be the employee himself" )</div><div>when</div><div> $a : Approver( employee == manager )</div><div>then</div>
<div> retract( $a );</div><div>end</div><div><br></div><div>rule "2.b. Approver cannot be a peer"</div><div> @doc( "An approver cannot be a peer of the employee" )</div><div>when</div><div> $a : Approver()</div>
<div> Department( employees contains $a.employee, employees contains $a.manager ) or</div><div> Department( managers contains $a.employee, managers contains $a.manager )</div><div>then</div><div> retract( $a );</div>
<div>end</div><div><br></div><div>rule "3.a. Approver cannot report to the employee"</div><div> @doc( "An approver cannot report to the employee" )</div><div>when</div><div> $a : Approver()</div>
<div> $dh : DepartmentHierarchy()</div><div> $d1 : Department( this == $dh.parent, managers contains $a.employee )</div><div> $d2 : Department( this == $dh.sub, managers contains $a.manager || employees contains $a.manager )</div>
<div>then</div><div> retract( $a );</div><div>end</div><div><br></div><div>rule "3.b. An approver cannot be the peer to someone who reports to the manager"</div><div> @doc( "An approver cannot be the peer to someone who reports to the manager" )</div>
<div>when</div><div> // An approver</div><div> $a : Approver()</div><div> // That is a manager of a department</div><div> $d : Department( managers contains $a.manager )</div><div> // Cannot have a peer</div>
<div> $p : Person( this memberOf $d.managers, this != $a.manager )</div><div> // That reports to the employee in another department</div><div> $dh : Department( managers contains $a.employee, employees contains $p ) </div>
<div>then</div><div> retract( $a );</div><div>end</div><div> </div><div>rule "Approvers are the nearest managers"</div><div> @doc( "From all eligible approvers, the actual approver is the nearest manager in the hierarchy" )</div>
<div> salience -10</div><div>when</div><div> $a : Approver()</div><div> exists( Approver( employee == $a.employee, distance < $a.distance ) )</div><div>then</div><div> retract( $a );</div><div>end</div><div>
<br></div><div><br></div><div>/*******************************************************</div><div> * Define the dataset</div><div> *******************************************************/</div><div>rule "Setup"</div>
<div> salience 100</div><div>then</div><div> hilary = new Person( "Hilary" );</div><div> john = new Person( "John" );</div><div> jane = new Person( "Jane" );</div><div> mike = new Person( "Mike" );</div>
<div> kate = new Person( "Kate" );</div><div> jessica = new Person( "Jessica" );</div><div> janet = new Person( "Janet" );</div><div> erica = new Person( "Erica" );</div>
<div> a = new Department( "A", null );</div><div> a1 = new Department( "A1", a );</div><div> a12 = new Department( "A12", a1 );</div><div> a2 = new Department( "A2", a );</div>
<div> a21 = new Department( "A21", a2 );</div><div> a22 = new Department( "A22", a2 );</div><div> a.managers.add( hilary );</div><div> a1.managers.add( john );</div><div> a1.managers.add( jane );</div>
<div> a12.managers.add( mike );</div><div> a12.employees.add( john );</div><div> a12.employees.add( mike );</div><div> a2.managers.add( kate );</div><div> a21.managers.add( jessica );</div><div> a21.employees.add( janet );</div>
<div> a22.managers.add( erica );</div><div> a22.employees.add( jane );</div><div> </div><div> insert( hilary );</div><div> insert( john );</div><div> insert( jane );</div><div> insert( mike );</div><div>
insert( kate );</div><div> insert( jessica );</div><div> insert( janet );</div><div> insert( erica );</div><div> insert( a );</div><div> insert( a1 );</div><div> insert( a12 );</div><div> insert( a2 );</div>
<div> insert( a21 );</div><div> insert( a22 );</div><div>end</div><div><br></div><div>/*********************************************************</div><div> * Printing the result </div><div> *********************************************************/</div>
<div>// in a real application, this would probably be a query instead</div><div>// that would be invocated on demand by the application</div><div>rule "Print all"</div><div> salience -20</div><div>when</div><div>
$a : Approver()</div><div>then</div><div> System.out.println( "Employee: "+$<a href="http://a.employee.name">a.employee.name</a>+" Approver: "+$<a href="http://a.manager.name">a.manager.name</a> );</div>
<div>end</div><div><br></div></font><br>-- <br> Edson Tirelli<br> JBoss Drools Core Development<br> JBoss by Red Hat @ <a href="http://www.jboss.com">www.jboss.com</a><br><br></div>