chocoteam / choco-graph Goto Github PK

Bonjour,
j'ai voulu générer le jar choco-graph avec la commande suivante (dans le répertoire idoine):
mvn clean install -DskipTests=true
toutefois la génération du jar échoue car elle attend dans le dépot maven choco-solver version 3.2.1-SNAPSHOT . En modifiant le pom.xml pour prendre en compte la version 3.2.1 la génération est opérationnelle.

I tried using the LearnCBJ learner in choco-solver, but it seemed to choke on graph variables. Would it make sense to adapt the CBJ implementation in choco-solver to support graph variables, or is that a PhD thesis? :)

Hi, interesting project, wondering if it's possible to use this for the Max Flow problem with xor path segments?

Thanks

Hi!
It's me again. I think I found one more bug.

public class Test {
    public static void main(String[] args) {
        Solver solver = new Solver();
        BoolVar[] isVertexPresent = VF.boolArray("v_pr", 4, solver);
        BoolVar[] isEdgePresent = VF.boolArray("e_pr", 3, solver);
        IntVar[] actVertW = new IntVar[4];
        IntVar[] actEdgeW = new IntVar[3];
        int[] vw = new int[]{-3, -2, 1, 1};
        int[] ew = new int[]{2, 3, -3};
        int[][] edges = new int[][]{new int[]{0, 2}, new int[]{2, 3}, new int[]{3, 1}};
        for(int i = 0; i < 4; i++){
            actVertW[i] = VF.enumerated("act_v[" + i + "]", new int[]{0, vw[i]}, solver);
            ICF.arithm(actVertW[i], "=", vw[i]).reifyWith(isVertexPresent[i]);
        }
        for(int i = 0; i < 3; i++){
            actEdgeW[i] = VF.enumerated("act_e[" + i + "]", new int[]{0, ew[i]}, solver);
            ICF.arithm(actEdgeW[i], "=", ew[i]).reifyWith(isEdgePresent[i]);
            BoolVar conj = VF.bool("conj", solver);
            SatFactory.addBoolAndArrayEqVar(new BoolVar[]{isVertexPresent[edges[i][0]], isVertexPresent[edges[i][1]]}, conj);
            SatFactory.addBoolOrArrayEqualTrue(new BoolVar[]{isEdgePresent[i].not(), conj});
        }
        UndirectedGraph UB = new UndirectedGraph(solver, 4, SetType.BIPARTITESET, false);
        UndirectedGraph LB = new UndirectedGraph(solver, 4, SetType.BIPARTITESET, false);
        for (int i = 0; i < 4; i++) {
            UB.addNode(i);
        }
        for(int i = 0; i < 3; i++){
            UB.addEdge(edges[i][0], edges[i][1]);
        }
        IUndirectedGraphVar sol = GraphVarFactory.undirected_graph_var("solution", LB, UB, solver);
        solver.post(GCF.connected(sol));
        solver.post(GCF.nodes_channeling(sol, isVertexPresent));
        for(int i = 0; i < 3; i++){
            solver.post(GCF.edge_channeling(sol, isEdgePresent[i], edges[i][0], edges[i][1]));
        }
        IntVar sum = VF.integer("sum", -50, 50, solver);
        List<IntVar> merged = new ArrayList<>();
        merged.addAll(Arrays.asList(actEdgeW));
        merged.addAll(Arrays.asList(actVertW));
        IntVar[] toSum = merged.toArray(new IntVar[0]);
        solver.post(ICF.sum(toSum, sum));
        //SatFactory.addFalse(isVertexPresent[0]);
        //SatFactory.addFalse(isVertexPresent[1]);
        solver.findOptimalSolution(ResolutionPolicy.MAXIMIZE, sum);
        System.out.println(sum);
    }
}

Sorry for such complex sample. As you can see program prints that 4 is optimal solution, but if you uncomment strings before finding solution, it prints that 5 is optimal solution, although we reduced domain. That is this solution is possible but not to be chosen as optimal. I think it is strange behavior.

Thanks and excuse my bad English.

Many methods in IGraphVarFactory translate a graph into a (set of) Vars.
Example: IntVar IGraphVarFactory.nbLoops(GraphVar)

The [Directed|Undirected]?GraphVar could propose this access, that is with the GraphVar parameter being this.

typically the corresponding field would be (in GraphVar)

@Getter(lazy=true) 
private final IntVar nbLoops = getModel().nbLoops(this);

1. The @getter is from lombok, so you need to have the lombodk dependency, but set it to optional since it's not used by other projects.
2. it also requires the getModel() to return a casted GraphModel (and the constructor to require a graphmodel)
3. This would actually create a meaninglessvariable, and also a accessor that checks and instantiates that variable when called in a synced block.
4. The modification is made at compile time, lombock rewrites the instruction tree. The only issue is that the sources won't show it, but your exported jar will actually contain the modified instructions.

The other trivial methods could be

@Getter(lazy=true) 
private final IntVar nbNodes = getModel().nbNodes(this);

@Getter(lazy=true) 
private final SetVar nodeSet = getModel().nodeSet(this);

@Getter(lazy=true) 
private final SetVar loopSet = getModel().loopSet(this);

if you want the accessors to keep the variable names (so nbNodes() instead of getNbNodes() ) you can add @accessors(fluent=true) to the class or the field.

@jgFages Now that the code has been moved to choco-solver, I suppose we can archive this repository.
Are you ok?

minimal problem : 3 nodes {0, 1, 2} ; one arc from each node to the next and reciprocally. The node 1 is mandatory. Then I add the circuit constraint.

@Test
	public void test3steps() {
		GraphModel model = new GraphModel();
		DirectedGraph lb = new DirectedGraph(3, SetType.BITSET, false);
		lb.addNode(1);
		DirectedGraph ub = new DirectedGraph(3, SetType.BITSET, true);
		ub.addArc(0, 1);
		ub.addArc(1, 0);
		ub.addArc(1, 2);
		ub.addArc(2, 1);
		DirectedGraphVar graphVar = model.digraphVar("route", lb, ub);
		model.circuit(graphVar).post();
	
		model.getSolver().findSolution();
	}	

The initial problem is a bit more complex since I add a gain variable to maximize, that is the sum of the nodes of the graph index :

		IntVar sumPoints = model.intVar("points", 0, Integer.MAX_VALUE / 2);
		model.sumElements(model.nodeSet(graphVar), new int[] { 0, 1, 2 }, sumPoints).post();
		model.getSolver().findOptimalSolution(sumPoints, true);

In both cases I get the same exception

FAILED: test3steps
java.lang.UnsupportedOperationException: It is forbidden to remove an element from a constant set (Set_CstInterval)
at org.chocosolver.util.objects.setDataStructures.constant.Set_CstInterval.remove(Set_CstInterval.java:65)
at org.chocosolver.util.objects.graphs.DirectedGraph.removeNode(DirectedGraph.java:129)
at org.chocosolver.graphsolver.variables.GraphVar.removeNode(GraphVar.java:128)
at org.chocosolver.graphsolver.cstrs.degree.PropNodeDegree_AtLeast_Incr.checkAtLeast(PropNodeDegree_AtLeast_Incr.java:165)
at org.chocosolver.graphsolver.cstrs.degree.PropNodeDegree_AtLeast_Incr.lambda$new$0(PropNodeDegree_AtLeast_Incr.java:74)
at org.chocosolver.graphsolver.variables.delta.GraphDeltaMonitor.forEachArc(GraphDeltaMonitor.java:123)
at org.chocosolver.graphsolver.cstrs.degree.PropNodeDegree_AtLeast_Incr.propagate(PropNodeDegree_AtLeast_Incr.java:129)
at org.chocosolver.solver.propagation.hardcoded.SevenQueuesPropagatorEngine.propagate(SevenQueuesPropagatorEngine.java:201)
at org.chocosolver.solver.search.loop.propagate.PropagateBasic.execute(PropagateBasic.java:27)
at org.chocosolver.solver.Solver.propagate(Solver.java:411)
at org.chocosolver.solver.Solver.searchLoop(Solver.java:294)
at org.chocosolver.solver.Solver.solve(Solver.java:264)
at org.chocosolver.solver.search.IResolutionHelper.findSolution(IResolutionHelper.java:91)

Adding an arc from 0 to 2 solves the issue; but it's a different problem.

@Test
	public void test3steps() {
		GraphModel model = new GraphModel();
		DirectedGraph lb = new DirectedGraph(3, SetType.BITSET, false);
		lb.addNode(1);
		DirectedGraph ub = new DirectedGraph(3, SetType.BITSET, true);
		ub.addArc(0, 1);
		ub.addArc(1, 0);
		ub.addArc(1, 2);
		ub.addArc(2, 1);
		ub.addArc(0, 2);
		DirectedGraphVar graphVar = model.digraphVar("route", lb, ub);
		model.circuit(graphVar).post();

		// model.getSolver().findSolution();

		IntVar sumPoints = model.intVar("points", 0, Integer.MAX_VALUE / 2);
		model.sumElements(model.nodeSet(graphVar), new int[] { 0, 1, 2 }, sumPoints).post();
		model.getSolver().findOptimalSolution(sumPoints, true);
	}

I am trying to use choco-graph with version 3.3.2 of choco3, and am running into the following compile errors. Can this please be looked into?

[ERROR] diagnostic: /home/ezulkosk/idea/choco-graph-fork/src/main/java/org/chocosolver/solver/variables/GraphVar.java:36: error: cannot find symbol
import org.chocosolver.solver.explanations.VariableState;
^
symbol: class VariableState
location: package org.chocosolver.solver.explanations
[ERROR] diagnostic: /home/ezulkosk/idea/choco-graph-fork/src/main/java/org/chocosolver/solver/variables/GraphVar.java:207: error: cannot find symbol
public void explain(ExplanationEngine xengine, VariableState what, Explanation to) {
^
symbol: class VariableState
location: class org.chocosolver.solver.variables.GraphVar
[ERROR] diagnostic: /home/ezulkosk/idea/choco-graph-fork/src/main/java/org/chocosolver/solver/variables/GraphVar.java:212: error: cannot find symbol
public void explain(ExplanationEngine xengine, VariableState what, int val, Explanation to) {
^
symbol: class VariableState
location: class org.chocosolver.solver.variables.GraphVar
[ERROR] diagnostic: /home/ezulkosk/idea/choco-graph-fork/src/main/java/org/chocosolver/solver/search/GraphDecision.java:31: error: cannot find symbol
import org.chocosolver.solver.explanations.Deduction;
^
symbol: class Deduction

Hi

I'm trying to understand and use choco-solver, but I can't understand:
I'm executing example program "TransitiveClosure". It finds the solution, I can see value of edgeCount var, but graphVar is not instantiated, so I can see only lower and upper bounds of it. How can I get the solution, i.e. the certain graph, which is transitive and is upper bound to my source graph?

Hi! This is not really a bug report, but more a question regarding the readme:

This extension of Choco Solver works with choco-solver-4.0.0-SNAPSHOT (not released yet, to be compiled from github sources) and associated dependencies. It requires JDK 1.8+

I noticed that choco-solver has a 4.0.0-SNAPSHOT release:

https://oss.sonatype.org/content/repositories/snapshots/org/choco-solver/choco-solver/4.0.0-SNAPSHOT/

With that dependency satisfied, would you consider releasing 4.0.0.a or a compatible SNAPSHOT of choco-graph to https://oss.sonatype.org/content/repositories/snapshots/org/choco-solver/choco-graph?