Generated on for Gecode by doxygen 1.17.0
open-route.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main author:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/driver.hh>
35#include <gecode/int.hh>
36
37using namespace Gecode;
38
54class OpenRoute : public Script {
55protected:
57 static const int node_count = 5;
60public:
62 enum {
65 };
66
68 OpenRoute(const Options& opt)
69 : Script(opt), route(*this,IntSet(0,node_count-1),node_count) {
70 // State 5 consumes the source node. Transitions along graph arcs consume
71 // their destination node; only node 4 is an accepting state.
72 DFA paths(5,{
73 {5,0,0},
74 {0,1,1}, {0,2,2}, {0,4,4},
75 {1,2,2}, {1,4,4},
76 {2,1,1}, {2,3,3},
77 {3,2,2}, {3,4,4}
78 },{4});
79 extensional(*this,route,paths);
80 distinct(*this,route);
81
82 // Posting the length brancher first selects a length before assigning nodes.
83 if (opt.branching() == BRANCH_LENGTH)
84 branch(*this,route.length(),INT_VAL_MIN());
86 }
87
90 route.update(*this,s.route);
91 }
92
94 Space*
95 copy(void) override {
96 return new OpenRoute(*this);
97 }
98
100 void
101 print(std::ostream& os) const override {
102 os << "\t";
103 for (int i=0; i<route.known_length(); i++) {
104 if (i > 0)
105 os << " -> ";
106 os << route[i];
107 }
108 os << " (length " << route.length() << ")" << std::endl;
109 }
110};
111
115int
116main(int argc, char* argv[]) {
117 Options opt("OpenRoute");
118 opt.solutions(0);
119 opt.branching(OpenRoute::BRANCH_INCREMENTAL);
120 opt.branching(OpenRoute::BRANCH_INCREMENTAL,"incremental",
121 "Assign the current prefix before extending the route");
122 opt.branching(OpenRoute::BRANCH_LENGTH,"length",
123 "Choose the complete route length first");
124 opt.parse_strict(argc,argv);
126 return 0;
127}
128
129// STATISTICS: example-any
Finite automaton with deterministic construction by default.
Definition int.hh:2620
static void run(const Options &opt, Script *s=nullptr)
Integer sets.
Definition int.hh:179
Open list of integer variables.
Definition int.hh:1076
Options for scripts
Definition driver.hh:447
Computation spaces.
Definition core.hpp:1787
int main(int argc, char *argv[])
Main-function.
OpenRoute(const Options &opt)
Construct the model.
Space * copy(void) override
Perform copying during cloning.
OpenIntVarList route
Node IDs in route order, including source and destination.
void print(std::ostream &os) const override
Print the materialized route (complete in a solution).
@ BRANCH_INCREMENTAL
Assign the current prefix before extending it.
@ BRANCH_LENGTH
Choose the complete route length first.
static const int node_count
Number of graph nodes and maximal route length.
OpenRoute(OpenRoute &s)
Constructor for cloning s, including the space-local open list.
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition driver.hh:1002
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
void extensional(Home home, const IntVarArgs &x, DFA d, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for extensional constraint described by a DFA.
Gecode toplevel namespace
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
Definition distinct.cpp:46
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55