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_dfs.c
26   	 * @ingroup DEFPLUGINS_NODESEL
27   	 * @brief  node selector for depth first search
28   	 * @author Tobias Achterberg
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "scip/nodesel_dfs.h"
34   	#include "scip/pub_message.h"
35   	#include "scip/pub_nodesel.h"
36   	#include "scip/pub_tree.h"
37   	#include "scip/scip_message.h"
38   	#include "scip/scip_nodesel.h"
39   	#include "scip/scip_tree.h"
40   	#include <string.h>
41   	
42   	#define NODESEL_NAME             "dfs"
43   	#define NODESEL_DESC             "depth first search"
44   	#define NODESEL_STDPRIORITY           0
45   	#define NODESEL_MEMSAVEPRIORITY  100000
46   	
47   	
48   	/*
49   	 * Callback methods
50   	 */
51   	
52   	/** copy method for node selector plugins (called when SCIP copies plugins) */
53   	static
54   	SCIP_DECL_NODESELCOPY(nodeselCopyDfs)
55   	{  /*lint --e{715}*/
56   	   assert(scip != NULL);
57   	   assert(nodesel != NULL);
58   	   assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
59   	
60   	   /* call inclusion method of node selector */
61   	   SCIP_CALL( SCIPincludeNodeselDfs(scip) );
62   	
63   	   return SCIP_OKAY;
64   	}
65   	
66   	
67   	/** node selection method of node selector */
68   	static
69   	SCIP_DECL_NODESELSELECT(nodeselSelectDfs)
70   	{  /*lint --e{715}*/
71   	   assert(nodesel != NULL);
72   	   assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
73   	   assert(scip != NULL);
74   	   assert(selnode != NULL);
75   	
76   	   *selnode = SCIPgetPrioChild(scip);
77   	   if( *selnode == NULL )
78   	   {
79   	      *selnode = SCIPgetPrioSibling(scip);
80   	      if( *selnode == NULL )
81   	      {
82   	         SCIPdebugMsg(scip, "select best leaf\n");
83   	         *selnode = SCIPgetBestLeaf(scip);
84   	      }
85   	
86   	      SCIPdebugMsg(scip, "select best sibling leaf\n");
87   	   }
88   	
89   	   return SCIP_OKAY;
90   	}
91   	
92   	
93   	/** node comparison method of node selector */
94   	static
95   	SCIP_DECL_NODESELCOMP(nodeselCompDfs)
96   	{  /*lint --e{715}*/
97   	   int depth1;
98   	   int depth2;
99   	
100  	   assert(nodesel != NULL);
101  	   assert(strcmp(SCIPnodeselGetName(nodesel), NODESEL_NAME) == 0);
102  	   assert(scip != NULL);
103  	
104  	   depth1 = SCIPnodeGetDepth(node1);
105  	   depth2 = SCIPnodeGetDepth(node2);
106  	   if( depth1 > depth2 )
107  	      return -1;
108  	   else if( depth1 < depth2 )
109  	      return +1;
110  	   else
111  	   {
112  	      SCIP_Real lowerbound1;
113  	      SCIP_Real lowerbound2;
114  	
115  	      lowerbound1 = SCIPnodeGetLowerbound(node1);
116  	      lowerbound2 = SCIPnodeGetLowerbound(node2);
117  	      if( lowerbound1 < lowerbound2 )
118  	         return -1;
119  	      else if( lowerbound1 > lowerbound2 )
120  	         return +1;
121  	      else
122  	         return 0;
123  	   }
124  	}
125  	
126  	
127  	/*
128  	 * dfs specific interface methods
129  	 */
130  	
131  	/** creates the node selector for depth first search and includes it in SCIP */
132  	SCIP_RETCODE SCIPincludeNodeselDfs(
133  	   SCIP*                 scip                /**< SCIP data structure */
134  	   )
135  	{
136  	   SCIP_NODESEL* nodesel;
137  	
138  	   /* include node selector */
139  	   SCIP_CALL( SCIPincludeNodeselBasic(scip, &nodesel, NODESEL_NAME, NODESEL_DESC, NODESEL_STDPRIORITY, NODESEL_MEMSAVEPRIORITY,
140  	          nodeselSelectDfs, nodeselCompDfs, NULL) );
141  	
142  	   assert(nodesel != NULL);
143  	
144  	   SCIP_CALL( SCIPsetNodeselCopy(scip, nodesel, nodeselCopyDfs) );
145  	
146  	   return SCIP_OKAY;
147  	}
148