1. LSGraphSolver ls();
2. VarRootedSpanningTree tr(ls,g,s,t);
3. PreferredReplacingEdges prefReplacing(tr);
4. PreferredReplacableEdges prefReplacable(tr);
5. forall(ei in prefReplacing.getSet())
6. forall(eo in prefReplacable.getSet(ei))
7. d = C.getReplaceEdgeDelta(tr,eo,ei);
Figure 3: Exploring the basic neighborhood
(for instance, the sum of weights of all the edges of a graph, the diameter of a tree, etc.). *GraphConstraint* and *GraphObjective* are concepts describing differentiable objects which maintain some properties (for instance, the number of violations of a constraint or the value of an objective function) of a dynamic graph. The main feature of *GraphConstraint* and *GraphObjective* is the interface, allowing to query the impact of local moves (modification of the dynamic graph) on these properties. Some *GraphConstraints* and *GraphObjectives* have been designed and implemented over *VarRootedSpanningTree*. For instance, PathCostOnEdges(tr,k) 2is an abstraction representing the total weight accumulated along the path induced by tr, MinEdgeCost(tr,k), MaxEdgeCost(tr,k) are abstractions representing the minimal and maximal weight of edges on the path induced by tr. NodesVisited(tr,S) is an abstraction representing the number of nodes of S visited by the path induced by tr. These abstractions are example of *GraphObjectives* which are fundamental when modeling Constrained Optimum Path problems. For example, in QoS, we consider shortest path from an origin to a destination with constraints over bandwidth which is defined to be the minimum weight of edges on the specified path. The framework provides flexibility for modeling various Constrained Optimum Path problems. We can easily combine
(with +,-,* operator) and state basic constraints (for instance, <=,>=,==) over these abstractions.

PathEdgeDisjoint(tr) is another *GraphConstraint* which is defined over an array of paths (the i th path is induced by tr[i]) and specifies that these paths are mutually edge-disjoint.

In order to illustrate the modeling, we give a snippet (see Figure 3) which explores the basic neighborhood. Line 1 initializes a LSGraphSolver object ls which manages all the VarGraph, *VarTree*,
GraphInviants, *GraphConstraint*s and *GraphObjective*s and relations (dependency graph) between these objects. Line 2 declares and initializes randomly a VarRootedSpanningTree tr rooted at t of the input graph g which represents the path from the source node s to t. prefReplacing and prefReplacable are *GraphInvariants* which maintain the set of *preferred replacing* edges3and *preferred replacable* edges
(lines 3-4). Lines 5-7 explore the basic neighborhood and evaluate the quality of moves with respect to a GraphConstraint C. The getReplaceEdgeDelta (line 7) method returns the variation of the number of violations of C when the *preferred replacable* edge eo is replaced by the *preferred replacing* edge ei on tr.

## 5 Application: The Edp Problem

Given an undirected graph G = (V,E), and a set T = {< si,ti >| si 6= ti ∈ V} representing a list of commodities (]T = k). EDP consists of finding a maximal cardinality set of mutually edge-disjoint paths