1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB)                      */
7    	/*                                                                           */
8    	/*  Licensed under the Apache License, Version 2.0 (the "License");          */
9    	/*  you may not use this file except in compliance with the License.         */
10   	/*  You may obtain a copy of the License at                                  */
11   	/*                                                                           */
12   	/*      http://www.apache.org/licenses/LICENSE-2.0                           */
13   	/*                                                                           */
14   	/*  Unless required by applicable law or agreed to in writing, software      */
15   	/*  distributed under the License is distributed on an "AS IS" BASIS,        */
16   	/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17   	/*  See the License for the specific language governing permissions and      */
18   	/*  limitations under the License.                                           */
19   	/*                                                                           */
20   	/*  You should have received a copy of the Apache-2.0 license                */
21   	/*  along with SCIP; see the file LICENSE. If not visit scipopt.org.         */
22   	/*                                                                           */
23   	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24   	
25   	/**@file nodesel_breadthfirst.h
26   	 * @ingroup DEFPLUGINS_NODESEL
27   	 * @ingroup NODESELECTORS
28   	 * @brief node selector for breadth-first search
29   	 * @author Stefan Heinz
30   	 * @author Gregor Hendel
31   	 *
32   	 * This node selector performs breadth-first search, i.e., it completely evaluates an entire level of the search tree before
33   	 * proceeding to the next level. At one level, nodes are processed in the order they were created by the branching rule.
34   	 */
35   	
36   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37   	
38   	#include "scip/nodesel_breadthfirst.h"
39   	#include "scip/pub_message.h"
40   	#include "scip/pub_nodesel.h"
41   	#include "scip/pub_tree.h"
42   	#include "scip/scip_message.h"
43   	#include "scip/scip_nodesel.h"
44   	#include "scip/scip_tree.h"
45   	#include <string.h>
46   	
47   	#define NODESEL_NAME             "breadthfirst"
48   	#define NODESEL_DESC             "breadth first search"
49   	#define NODESEL_STDPRIORITY        -10000
50   	#define NODESEL_MEMSAVEPRIORITY  -1000000
51   	
52   	/*
53   	 * Callback methods
54   	 */
55   	
56   	/** copy method for node selector plugins (called when SCIP copies plugins) */
57   	static
58   	SCIP_DECL_NODESELCOPY(nodeselCopyBreadthfirst)
59   	{  /*lint --e{715}*/
60   	   assert(scip != NULL);
61   	   assert(nodesel != NULL);
62   	   assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
63   	
64   	   /* call inclusion method of node selector */
65   	   SCIP_CALL( SCIPincludeNodeselBreadthfirst(scip) );
66   	
67   	   return SCIP_OKAY;
68   	}
69   	
70   	/** node selection method of node selector */
71   	static
72   	SCIP_DECL_NODESELSELECT(nodeselSelectBreadthfirst)
73   	{  /*lint --e{715}*/
74   	   assert(nodesel != NULL);
75   	   assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
76   	   assert(scip != NULL);
77   	   assert(selnode != NULL);
78   	
79   	   /* siblings come before leaves at the same level. Sometimes it can occur that no leaves are left except for children */
80   	   *selnode = SCIPgetBestSibling(scip);
81   	   if( *selnode == NULL )
82   	   {
83   	      *selnode = SCIPgetBestLeaf(scip);
84   	      if( *selnode == NULL )
85   	         *selnode=SCIPgetBestChild(scip);
86   	   }
87   	   if( *selnode != NULL )
88   	   {
89   	      SCIPdebugMsg(scip, "Selecting next node number %" SCIP_LONGINT_FORMAT " at depth %d\n", SCIPnodeGetNumber(*selnode), SCIPnodeGetDepth(*selnode));
90   	   }
91   	
92   	   return SCIP_OKAY;
93   	}
94   	
95   	
96   	/** node comparison method of breadth first search: nodes with lower depth are preferred; in case of a tie, the node
97   	 *  which was created earlier (and therefore has a smaller node number) is preferred */
98   	static
99   	SCIP_DECL_NODESELCOMP(nodeselCompBreadthfirst)
100  	{  /*lint --e{715}*/
101  	   int depth1;
102  	   int depth2;
103  	
104  	   assert(nodesel != NULL);
105  	   assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
106  	   assert(scip != NULL);
107  	
108  	   depth1 = SCIPnodeGetDepth(node1);
109  	   depth2 = SCIPnodeGetDepth(node2);
110  	
111  	   /* if depths differ, prefer node with smaller depth */
112  	   if( depth1 < depth2 )
113  	      return -1;
114  	   else if( depth1 > depth2 )
115  	      return +1;
116  	   else
117  	   {
118  	      /* depths are equal; prefer node with smaller number */
119  	      SCIP_Longint number1;
120  	      SCIP_Longint number2;
121  	
122  	      number1 = SCIPnodeGetNumber(node1);
123  	      number2 = SCIPnodeGetNumber(node2);
124  	      assert(number1 != number2);
125  	
126  	      if( number1 < number2 )
127  	         return -1;
128  	      else
129  	         return +1;
130  	   }
131  	}
132  	
133  	/*
134  	 * breadth first specific interface methods
135  	 */
136  	
137  	/** creates the node selector for breadth first search and includes it in SCIP */
138  	SCIP_RETCODE SCIPincludeNodeselBreadthfirst(
139  	   SCIP*                 scip                /**< SCIP data structure */
140  	   )
141  	{
142  	   SCIP_NODESEL* nodesel;
143  	
144  	   /* include node selector */
145  	   SCIP_CALL( SCIPincludeNodeselBasic(scip, &nodesel, NODESEL_NAME, NODESEL_DESC, NODESEL_STDPRIORITY, NODESEL_MEMSAVEPRIORITY,
146  	         nodeselSelectBreadthfirst, nodeselCompBreadthfirst, NULL) );
147  	
148  	   assert(nodesel != NULL);
149  	
150  	   /* set non-fundamental callback functions via setter functions */
151  	   SCIP_CALL ( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyBreadthfirst) );
152  	
153  	   return SCIP_OKAY;
154  	}
155