Package org.processmining.framework.util.search

Class MultiThreadedSearcher<N>

java.lang.Object
org.processmining.framework.util.search.MultiThreadedSearcher<N>
Type Parameters:
N -
public class MultiThreadedSearcher<N> extends Object
This class implements a multi-threaded search algorithm. Internally, each instance of this class keeps a stack of objects of type N, representing the nodes in the tree. Each thread pops an element off the stack and asks the registered NodeExpander to expand it. If the node turns out to be a leaf, the expander is asked to process the leaf. The use of this class is as follows (in pseudo-code): Collection initialSearchNodes; Collection resultCollection; NodeExpander expander = new NodeExpander(); MultiThreadedSearcher searcher = new MultiThreadedSearcher(expander, BREADTHFIRST); searcher.addInitialNodes(initialSearchNodes); searcher.startSearch(executor, progress, resultCollection); Note that if you use this code from a plugin, you can also use: searcher.startSearch(context.getExecutor(), context.getProgress(), resultCollection); The progress object given to the startSearch method is only used for cancellation checks, i.e. progress is never incremented.
Author:
bfvdonge

  • Field Details

    • DEPTHFIRST

      public static final int DEPTHFIRST
      Constant representing a DEPTH-FIRST search.
      See Also:

    • BREADTHFIRST

      public static final int BREADTHFIRST
      Constant representing a BREADTH-FIRST search.
      See Also:

  • Constructor Details

    • MultiThreadedSearcher

      public MultiThreadedSearcher(int numberOfThreads, NodeExpander<N> expander, int searchType)
      Instantiates a searcher. The searcher will use as many threads as specified. Furthermore, the given expander is used for the expansion of search nodes and the processing of leaf nodes. The searchtype can be either DEPTHFIRST, or BREADTHFIRST. In the first case, new nodes produced by the expand method of the expander are added to the bottom of the stack, whereas in the latter case, the new nodes are pushed to the top of the stack.
      Parameters:
      numberOfThreads - specifies the number of threads to use. If unsure how to set this value, use the other constructor without this parameter
      expander - The expander that will be used to expand each search node and process the leafs of the search tree
      searchType - the type of search, either DEPTHFIRST or BREADTHFIRST

    • MultiThreadedSearcher

      public MultiThreadedSearcher(NodeExpander<N> expander, int searchType)
      Instantiates a searcher. The searcher will use as many threads as the virtual machine reports to have CPUs. Furthermore, the given expander is used for the expansion of search nodes and the processing of leaf nodes. The searchtype can be either DEPTHFIRST, or BREADTHFIRST. In the first case, new nodes produced by the expand method of the expander are added to the bottom of the stack, whereas in the latter case, the new nodes are pushed to the top of the stack. By default, as many threads are used as there are CPUs reported by Runtime.getRuntime().availableProcessors()
      Parameters:
      expander - The expander that will be used to expand each search node and process the leafs of the search tree
      searchType - the type of search, either DEPTHFIRST or BREADTHFIRST

    • MultiThreadedSearcher

      public MultiThreadedSearcher(int numberOfThreads, NodeExpander<N> expander, ExpandCollection<N> expandCollection)
      Instantiates a searcher. The searcher will use as many threads as specified. Furthermore, the given expander is used for the expansion of search nodes and the processing of leaf nodes and the given expandCollection to store nodes that need to be expanded further.
      Parameters:
      numberOfThreads - specifies the number of threads to use. If unsure how to set this value, use the other constructor without this parameter
      expander - The expander that will be used to expand each search node and process the leafs of the search tree
      expandCollection - the collection to store nodes that need to be expanded

    • MultiThreadedSearcher

      public MultiThreadedSearcher(NodeExpander<N> expander, ExpandCollection<N> expandCollection)
      Instantiates a searcher. The searcher will use as many threads as specified. Furthermore, the given expander is used for the expansion of search nodes and the processing of leaf nodes and the given expandCollection to store nodes that need to be expanded further. By default, as many threads are used as there are CPUs reported by Runtime.getRuntime().availableProcessors()
      Parameters:
      expander - The expander that will be used to expand each search node and process the leafs of the search tree
      expandCollection - the collection to store nodes that need to be expanded

  • Method Details

    • addInitialNodes

      public void addInitialNodes(Collection<N> initialNodes)
      Sets the initial nodes of the search tree. Note that you can provide an empty collection, in which case the search returns immediately, without calling any methods in the expander.
      Parameters:
      initialNodes - the collection of initial nodes.

    • addInitialNodes

      public void addInitialNodes(N... initialNodes)
      Sets the initial nodes of the search tree. Note that you don't have to provide any nodes, in which case the search returns immediately, without calling any methods in the expander.
      Parameters:
      initialNodes - zero or more initial nodes.

    • startSearch

      public void startSearch(Executor executor, Progress progress, Collection<N> resultCollection) throws InterruptedException, ExecutionException
      A call to this method initiates the search. The calling thread is suspended until the search is completed, or the progress was canceled. The resultCollection given to this method is passes through to the processLeaf method of the NodeExpander, i.e. no changes to this collection are made by the searcher.
      Parameters:
      executor - The executor in which the searcher can schedule it's threads. If called from a plugin, use context.getExector() to pass to this method.
      progress - The progress which is polled for cancellation. Note that no other changes are made to the progress. If changes are necessary, this has to be handled by the NodeExpander. If called from a plugin, use context.getProgress() to pass to this method.
      resultCollection - The collection in which the final result is stored by the processLeaf method of the node expander. Note that the searcher does not change this collection in any way, nor does it handle any necessary synchronization.
      Throws:
      InterruptedException - If one of the threads was interupted;
      ExecutionException - If one of the threads threw an exception;