001/*
002 * Java Genetic Algorithm Library (jenetics-8.1.0).
003 * Copyright (c) 2007-2024 Franz Wilhelmstötter
004 *
005 * Licensed under the Apache License, Version 2.0 (the "License");
006 * you may not use this file except in compliance with the License.
007 * You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 *
017 * Author:
018 *    Franz Wilhelmstötter (franz.wilhelmstoetter@gmail.com)
019 */
020package io.jenetics.ext;
021
022import static java.lang.String.format;
023
024import io.jenetics.util.ISeq;
025import io.jenetics.util.RandomRegistry;
026
027import io.jenetics.ext.util.TreeNode;
028
029/**
030 * Swaps two, randomly chosen, nodes (subtrees) from two given trees.
031 * <pre> {@code
032 *     Tree A                 Tree B
033 *   0                      a
034 *   ├── 1                  ├── b
035 *   │   ├── 4              │   ├── e
036 *   │   └── 5              │   └── f
037 *   ├── 2                  ├── c
038 *   │   └── 6              │   └── g
039 *   └── 3                  └── d
040 *       ├── 7                  ├── h
041 *       │   ├── 10             │   ├── k
042 *       │   └── 11             │   └── l
043 *       ├── 8                  ├── i
044 *       └── 9                  └── j
045 *
046 *     Swap node "3" of A with node "c" of B
047 *
048 *   0                      a
049 *   ├── 1                  ├── b
050 *   │   ├── 4              │   ├── e
051 *   │   └── 5              │   └── f
052 *   ├── 2                  ├── 3
053 *   │   └── 6              │   ├── 7
054 *   └── c                  │   │   ├── 10
055 *       └── g              │   │   └── 11
056 *                          │   ├── 8
057 *                          │   └── 9
058 *                          └── d
059 *                              ├── h
060 *                              │   ├── k
061 *                              │   └── l
062 *                              ├── i
063 *                              └── j
064 * } </pre>
065 *
066 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
067 * @version 5.0
068 * @since 3.9
069 */
070public class SingleNodeCrossover<
071        G extends TreeGene<?, G>,
072        C extends Comparable<? super C>
073>
074        extends TreeCrossover<G, C>
075{
076
077        public SingleNodeCrossover(double probability) {
078                super(probability);
079        }
080
081        public SingleNodeCrossover() {
082                this(DEFAULT_ALTER_PROBABILITY);
083        }
084
085        @Override
086        protected <A> int crossover(final TreeNode<A> that, final TreeNode<A> other) {
087                return swap(that, other);
088        }
089
090        // The static method makes it easier to test.
091        static <A> int swap(final TreeNode<A> that, final TreeNode<A> other) {
092                assert that != null;
093                assert other != null;
094
095                final var random = RandomRegistry.random();
096
097                final ISeq<TreeNode<A>> seq1 = that.breadthFirstStream()
098                        .collect(ISeq.toISeq());
099
100                final ISeq<TreeNode<A>> seq2 = other.breadthFirstStream()
101                        .collect(ISeq.toISeq());
102
103                final int changed;
104                if (seq1.length() > 1 && seq2.length() > 1) {
105                        final TreeNode<A> n1 = seq1.get(random.nextInt(seq1.length() - 1) + 1);
106                        final TreeNode<A> p1 = n1.parent().orElseThrow(AssertionError::new);
107
108                        final TreeNode<A> n2 = seq2.get(random.nextInt(seq2.length() - 1) + 1);
109                        final TreeNode<A> p2 = n2.parent().orElseThrow(AssertionError::new);
110
111                        final int i1 = p1.indexOf(n1);
112                        final int i2 = p2.indexOf(n2);
113
114                        p1.insert(i1, n2.detach());
115                        p2.insert(i2, n1.detach());
116
117                        changed = 2;
118                } else {
119                        changed = 0;
120                }
121
122                return changed;
123        }
124
125        @Override
126        public String toString() {
127                return format("SingleNodeCrossover[%f]", _probability);
128        }
129
130}