339 results about "Depth-first search" patented technology

Systems and methods for providing a boundary scan test of a wired or wireless network having a plurality of network nodes are presented. The system includes a test station communicatively coupled with the network. The test station creates a MAC layer scan test route sequence that includes each link in the network and is independent of the routing mechanism and protocol used for the network. The test station also creates a test agent that is configured to traverse each link in the scan test route sequence. The test agent is then deployed on the network and information about a link is reported back to the test station after the test agent examines the link. The scan test route sequence can be created by sending out a series of broadcast messages from one or more nodes in the network, sequentially applying a network tour to cover the entire network, or performing a depth first search on the entire network.

Systems and methods for providing a boundary scan test of a wired or wireless network having a plurality of network nodes are presented. The system includes a test station communicatively coupled with the network. The test station creates a MAC layer scan test route sequence that includes each link in the network and is independent of the routing mechanism and protocol used for the network. The test station also creates a test agent that is configured to traverse each link in the scan test route sequence. The test agent is then deployed on the network and information about a link is reported back to the test station after the test agent examines the link. The scan test route sequence can be created by sending out a series of broadcast messages from one or more nodes in the network, sequentially applying a network tour to cover the entire network, or performing a depth first search on the entire network.

The invention discloses a method and device for optimizing multi-constraint quality of service (QoS) routing selection. The method comprises the following steps: acquiring the topological structure and link parameters of an existing network in accordance with information of a prediction model; creating a corresponding multi-constraint QoS routing model in accordance with the determined topological structure and link parameters, and constructing penalty functions to transform multi-constraint conditions, as well as constructing fitness functions for evaluating paths; using a depth-first search method to acquire initial feasible paths and initializing particle swarms; calculating the fitness value of each particle, and finding out the optimal fitness value of the particle adjacent to each particle; using the generation algorithm and the genetic algorithm-particle swarm optimization (GA-PSO) to carry out iterative solution at the beginning of the initial feasible paths, and carrying out natural selection and variation operations; and finding out paths which meet conditions and are provided with the optimal fitness values, realizing optimal routing selection under the multi-constraint condition, and executing in accordance with the found routings.

A high-speed shape-based router is applicable to standard-cell digital designs, chip-level-block assembly designs, and other styles of design. In a flow of the invention, the technique establishes an initial structure for each net to be routed. Nets or parts of them are ordered. Each part of the net may be routed using a spine routing search, depth first search, or a space flood search, or any combination of these. Where sections fail or an error occurs, conflicts are identified, and the technique tries routing again.

The invention relates to a path planning method for mobile robots based on a particle swarm optimization algorithm. The prior path planning method for the mobile robots has single path selection and is easy to come to a dead end. The method comprises the concrete steps of: modeling the environment first; using a polygon to represent an obstacle; using a point to represent a robot, using a small square frame to represent the original position of the robot; and using a cross to represent a target point, wherein a starting point of the robot is marked as S, and the target point is marked as G; planning paths of the robot by utilizing the particle swarm optimization algorithm; and finally performing the deep first search on the planned paths. The method adds the deep first search into a polar coordinate particle swarm. By the method, the robot can effectively find one collision-free path in most of complex environments, and finally reach target points.

A system and method are described for ordering a database flush sequence prior to committing transaction changes to a database. In one embodiment, a plurality of data operations modifying persistent data objects are performed in a sequential order within an object-oriented environment. Relational dependencies between the persistent data objects are evaluated and the changes to the data objects are reordered based on the relational dependencies. Once reordered, the changes are committed to the database. In one embodiment, a depth first search algorithm is employed to determine the appropriate order to commit the data to the database.

A software testing method based on a model includes the following steps that S1, software to be tested is analyzed, and a test object and test characteristics are determined; S2, a UML model is selected and constructed; S3, verification is performed on the UML model, and correctness of the UML model is guaranteed; S4, traversal is performed on the UML model through a depth-first search algorithm, a test case is automatically generated, a relevant coverage rate is calculated according to sufficiency criteria such as a statement coverage criterion, a judgment coverage criterion, a condition coverage criterion and a route coverage criterion, so that assessment of the test case is finished; S5, a test script is generated according to a program to be tested and the test case obtained through the UML model, the test script is automatically executed, and an actual output result obtained through execution of the test script is stored; S6, according to comparison between actual output and anticipated output of the test case, a test result is obtained, and then according to the test object and a preset stopping criterion, whether the model or the program to be tested needs to be modified or not is determined.

A hybrid sphere decoding method is disclosed. Received data is processed to obtain preliminary parameters. Mbf layers are determined to use breadth-first search and Mdf layers to use depth-first search. A search process is implemented based on the preliminary parameters, in which Mbf layers are searched using breadth-first search and Mdf layers are searched using depth-first search.

The invention relates to a model conversion proposal from mechanical-electrical transient to electromagnetic transient and an implementation method to realize simulated electric fence model conversion from mechanical-electrical transient to electromagnetic transient, in particular to an electric fence model conversion proposal and an implementation method based on mechanical-electrical transient simulation tool BPA to electromagnetic transient simulation tool PSCAD / EMTDC. According to incidence matrix of graph theory and depth first search theory, the method generates node branch incidence matrix based on the electric fence structure of BPA data documents, and determines the sequence of electric fence branch nodes by carrying out depth first search and combining the node branch incidence matrix until a complete branch of the electric fence structure is searched. According to the searched node sequence, the node branch incidence matrix is adjusted, and according to the new incidence matrix after adjustment, nodes, loads, branches and other electric elements are added until the reconstruction of all nodes and branches is completed and a new network model structure under the electromagnetic transient simulation tool PSCAD / EMTDC is formed. The network model structure has the same network topology as the electric fence structure of the original BPA data documents, and the parameters of all elements remain consistent.

A method for determining a target path for a model-based control system. The model-based control system includes a directed acyclic graph, where the directed acyclic graph includes a plurality of vertices interconnected by a plurality of edges. The method includes the steps of performing a depth-first search of the directed acyclic graph for the target path. The depth-first search is operative to return an explicit solution or an implicit solution, wherein the implicit solution is determined using a heuristic. The method further includes determining if the depth-first search returned an explicit solution or an implicit solution, and if the depth-first search returned an implicit solution, constructing the target path from the implicit solution. The method may further include constructing a pattern database.

One embodiment of the invention is a method of specifying routes for a group of nets. The method specifies a total cost. It then performs a first depth-first search to identify, for the group of nets, a complete routing solution that has a cost that does not exceed the total cost. A routing solution for a set of nets includes a route for each net in the set. If the search does not find the complete routing solution, the method then increments the total cost and performs a second depth-first search to identify a complete routing solution for the group of nets that has a cost that does not exceed the incremented total cost.

A system and method to integrate breadth-first and depth-first strategies in a single search technique or routine is provided. It combines the complementary strengths of both strategies to achieve significantly improved speed over either strategy used alone. The new algorithm can be used to efficiently find solutions to the treewidth problem that has applications in areas such as diagnosis using probabilistic inferences.

Database objects, having interdependent relationships, are transferred for replication from a publisher to a subscriber in the order of a topological sort using a depth first search algorithm. When the depth first search algorithm attempts to enumerate all outgoing edges (dependencies) of a given node (database object), a request is made to begin an atomic transaction and then a temporary copy (e.g., via a T-SQL command) of the node / database object is created under a different name. The temporary copy is used to store dependency information that could otherwise be impaired by the replication process. Dependencies amongst database objects are thus preserved during the replication process through use of the temporary copy, as well as by transferring the database objects according to the topological sort order.

A method, system and computer program product for building decision diagrams efficiently in a structural network representation of a digital circuit using a dynamic resource constrained and interleaved depth-first-search and modified breadth-first-search schedule is disclosed. The method includes setting a first size limit for a first set of one or more m-ary decision representations describing a logic function and setting a second size limit for a second set of one or more m-ary decision representations describing a logic function. The first set of m-ary decision representations of the logic function is then built with one of the set of a depth-first technique or a breadth-first technique until the first size limit is reached, and a second set of m-ary decision representations of the logic function is built with the other technique until the second size limit is reached. In response to determining that a union of first set and the second set of m-ary decision representations do not describe the logic function, the first and second size limits are increased, and the steps of building the first and second set are repeated. In response to determining that the union of the first set of m-ary decision representations and the second set of m-ary decision representations describe the logic function, the union is reported.

Methods and apparatus are provided for discovering minimal conditional functional dependencies (CFDs). CFDs extend functional dependencies by supporting patterns of semantically related constants, and can be used as rules for cleaning relational data. A disclosed CFDMiner algorithm, based on techniques for mining closed itemsets, discovers constant minimal CFDs. A disclosed CTANE algorithm discovers general minimal CFDs based on the levelwise approach. A disclosed FastCFD algorithm discovers general minimal CFDs based on a depth-first search strategy, and an optimization technique via closed-itemset mining to reduce search space.

According to an embodiment of the present invention, a filer or other storage server is coupled to a network to store files for users of the network. An agent is coupled to the filer, and performs a scan or file walk for a Multi-Appliance Management Application (MMA) which is coupled to the filer and can monitor and manage the filer. The agent assigns identification (ID) numbers to the directories while scanning them. The ID numbers are assigned in a depth first search (DFS) order to reduce the amount of resources required for specific queries that may later be required. Several types of queries, including determining the parent of a node, determining all of the children of a node, determining the immediate children of a node, and determining all of the ancestors of a node may be easily accomplished using the ID numbers.

The invention relates to a traffic playback method and system for a virtual network. The traffic playback method includes a first step of capturing and processing real traffic, extracting a real IP address set R_IP, a second step of conducting depth-first search on a bipartite graph which is generated by real traffic communication relationships, dividing the real IP address set R_IP into two disjoint sets, namely, a set R_IPA and a set R_IPB, a third step of dividing all virtual nodes which are in communication through any virtual network routing interface v_interfacei into two disjoint sets, namely a set V_IPAi and a set V_IPBi, a fourth step of calculating similarities of all the virtual network routing interfaces and a real traffic collecting point, a fifth step of selecting a virtual network interface which is most similar to the real traffic collecting point to be used as a mapping node of the traffic collecting point, conducting IP address mapping based on the mapping mode, and a sixth step of traversing the real traffic again to achieve real traffic playback in the virtual network. When the traffic is played back in the virtual network through the traffic playback method and system for the virtual network, the real traffic communication environment is restored as good as possible, and the virtual network traffic system is improved.

The invention belongs to the field of electric power system distribution automation, and particularly relates to a pattern and model verifying method of a distribution automation master station system and a geographical information system. The method comprises the following steps that firstly, a model and a pattern file are guided out of the geographical information system; secondly, the distribution automation master station system obtains the pattern and the pattern file of the geographical information system through an information interaction bus; thirdly, the distribution automation master station system automatically analyzes a pattern and a model file online based on an adjacent matrix according to the depth-first search algorithm, and the pattern and model verification is carried out. A power grid topological structure is simplified through the depth-first search algorithm, accordingly, the pattern and model verification between the distribution automation master station system and the geographical information system is carried out, the working efficiency is improved, the pattern and model correction period is shortened, and the defect that a traditional topological method is low in searching efficiency is overcome.

The invention discloses a search method for the shortest path passing through necessary vertices. The implementation steps are: (1) Construct a weighted directed graph that satisfies the path relationship; (2) Find the shortest path between the search starting point and each necessary vertex; (3) Determine whether the path exists; (4) If it exists , then use the necessary vertex as the new search starting point, and continue to search for the path; (5) if it does not exist, then go back to the previous necessary vertex, and select the next shortest path to continue searching; (6) search the last found necessary vertex to the destination The shortest path between vertices; (7) The path can be found by combining the shortest paths found between all necessary vertices. By comparing the present invention with the depth-first search method, the genetic method and the ant colony method through experiments, it can be found that the present invention has the advantages of fast solution speed, good stability and the like.

A system and method to integrate breadth-first and depth-first strategies in a single search technique or routine is provided. It combines the complementary strengths of both strategies to achieve significantly improved speed over either strategy used alone. The new algorithm can be used to efficiently find solutions to the treewidth problem that has applications in areas such as diagnosis using probabilistic inferences.

The invention relates to the technology of topology analysis in the field of an electric power system, and specifically relates to a method for rapid topology analysis and the establishment of a topological island based on a graph theory. The method includes three steps: modeling, generating topology points, and generating the topological island. According to the method, topology analysis of the electric power system can be conducted via a graph theory recognition analysis method; advantages and disadvantages of breadth and depth first search algorithms can be comprehensively considered, and search advantages of depth first for a ring network are fully used; rapid topology analysis of the electric power network and the establishment of the topological island are realized, and the accuracy and rapidity of the topology analysis result of the electric power network are greatly improved.

An integration component assists in the integration of information distribution systems (IDSs). The integration component may help to identify the scope of the systems that are to be integrated using a multi-level top-down approach. The multi-level top-down approach may include five levels: a system software level, a business process level, a business rule level, an interface function level, and a data level. A fault detection component may then check the identified systems to identify potential faults. This check can be performed by representing the business rules as a Transition-Directed-Graph (TDG) and then processing the TDG using generic depth-first search (DFS)-based algorithms.

The invention relates to the technical field of electric power system analysis and control and provides an online automatic generation method for a black-start scheme. The online automatic generation method comprises the following steps: acquiring a QS formatted file in an E language from 'intelligent power grid dispatching technical support system for state grid' through a file transmission protocol and analyzing the QS formatted file in a C# language; constructing a topology map by taking a node in the power grid as a vertex and a power transmission line or transformer as a border; adopting the shortest path algorithm or depth-first search algorithm for calculating a black-start recovering path from a power point to a to-be-recovered unit / load; calling ATP-EMTP and PSD-BPA7 for performing simulating calculation; introducing a class library Microsoft.Office.Interop.Word for automatically writing a simulated result into a Word file in the form of graph, word and table, thereby forming the black-start scheme. Compared with the existing method for forming the black-start scheme by manually adopting the tool, such as PSD-BPA or ATP-EMTP, which is time-wasting and labor-wasting and has the defect of inferior applicability of independently developed simulated program, the online automatic generation method has the advantage that the efficiency and credibility of the generated black-start scheme are increased. The online automatic generation method has significance in failure recovery of a power system.

A method and apparatus for performing a paging operation on a tree having a plurality of nodes is provided. A preorder number and a subtree size are maintained in a machine-readable medium for each of the plurality of nodes of the tree. The preorder number associated with a particular node of the tree identifies a position for the particular node in a depth-first search ordering of the plurality of nodes of the tree. The subtree size associated with a particular node of the tree identifies a count of all the nodes in a subtree rooted at the particular node. In response to receiving a request to perform a paging operation on the plurality of nodes of the tree, a set of nodes that satisfy the paging operation may be determined using the preorder number and the subtree size associated with each node of the tree.

The invention provides a method for detecting spherical decode based on depth-first search, which comprises the following steps: A, performing QR deposition on a channel matrix; B, multiplying a conjugate transpose and a received signal of a Q matrix to obtain an equalizing signal rho; C, setting an initial search radius; D, executing the depth-first search according to the initial search radius, an R matrix and the rho, and updating the search radius; E, setting an upper limit value M of the search total node number and an upper limit value Ki of the ith layer search node number; F, executing the depth-first search according to the current search radius, the R matrix and the rho, and when the search gets to the ith layer, judging whether the searched node number on the ith layer is equal to Ki or not, otherwise, executing the search on the ith layer, and if so, getting to search the i+1th layer; and G, repeating the step F until the searched total node number is equal to M or all the layers cannot be searched any more, and outputting a decoding result. The method can effectively reduce the operation complexity of the sphere decoding, and is easy to achieve through hardware.

The invention relates to a method for converting a ladder diagram into a PLC (Programmable Logic Controller) program command, which comprises the following steps of: 1, presenting a topological structure of a ladder diagram by using a directed graph; 2, traversing a transposed graph GL <T> by using a depth-first search method, storing a topological sorting relation of parallel-connection peaks and coil peaks in a queue Q; 3, carrying out breadth-first search on the parallel-connection peaks according to a connection relation of the directed graph GL, carrying out depth-first search on serial-connection peaks adjacently connected with the parallel-connection peaks, generating an AND expression of the directed graph GL on the whole serial-connection path and an OR expression of the serial-connection peaks; 4, generating a final expression of the maximum combining item of the parallel-connection peaks; 5, carrying out breadth-first search on a connection relation graph Gp by using the Q,figuring out an OR expression of the corresponding parallel-connection peaks and verifying, finally, constructing the maximum combining item into the AND expression to form a final result; 6, judgingwhether a queue Q' is empty; and 7, processing a starting peak. The invention can be widely applied to the process of converting the ladder diagram into the PLC program command.

The invention discloses a generating method for a power grid topological relationship based on Arcgis. The generating method comprises a step of achieving generating a power grid resource space connecting relationship automatically based on an Arcgis space analysis, and a step of generating a network topological relationship based on a depth preferential search. The technical proposal provided bythe invention automatically maintains the power grid resource space connecting relationship based on a space connecting relationship of Arcgis elements and service attributes of the elements, and uses a depth preferential algorithm to quickly generate the network topological relationship according to the correct connecting relationship. The technical proposal solves the problems that the maintenances for the connecting relationship of devices in the power grid are complicated and a network topology of the power grid is reconstructed after the power grid changes. The technical proposal is usedto solve the applications such as power supply tracing, a power supply range, a power supply radius, a power failure imitation and the like in a city power distribution grid.

The invention provides an implementing method for a web crawler based on search engines. The web crawler comprises a socket function module, an http function module, a regular expression function module, a depth-first search function module and a breadth-first search function module. In order to overcome the defects that a fixed search strategy is adopted in a traditional web crawler technology and is lacking in adaptability, the implementing method for the web crawler based on the search engines can meet various requirements of customers, and therefore the web crawler technology which enables data to be updated in real time is achieved.