Shortest path between nodes

The shortest path between nodes described here uses the depth search principle but with alterations to improve search performance. Using the straight algorithms for recursive searches involves considerable amounts of resources and time with large scale nodes networks. What we present here is a complete PHP class to minimize searches and search time reaching the shortest path possible.

If you want to see the application document click here.

If you want to download the class, sample code and documentation presented here click Download code and document

Or if you want to use it online see it in action with our online nodes form for the examples listed here.

The nodes PHP Class.

The functionality of the nodes class includes the following

• Recursive search among connected nodes
• Visited nodes improved tracking
• Visited nodes dynamic limit
• Distance Breaks of current vs found paths.
• Navigation control
• Dynamic shorting of nodes prior processing
• Dynamic removal of reversed node connects
• Adjacent nodes filtering
• Closest node to target tracking when no path is found
• Dynamic optimization of paths by tracking visited node segments
• Tracking of alternative paths generation
• Progressive removal and replacement of visited nodes belong to found paths
• Automatic generation of random nodes
• File saving and loading of paths.
• Controls of debug, display and optimizations

Lets discuss each of these key elements of the our nodes search.

Recursive search

This is the main principle of a depth search. For each node the algorithm calls itself with each connected node as argument until a path is found or a limit is reached. The limit can be the number of recursions or the number of visited nodes thus far or some other mechanism.

Visited nodes tracking

In our nodes class a recursive limit is imposed in 2 ways. The visited nodes tracking is the first one. Previously visited nodes are separately stored. For each iteration and before another recursion takes place, the node is compared against the previously visited ones. If the node was previously visited is skipped. The visited nodes tracking occurs only for the current path scan and is not applicable to the global scope of a path search. Visited node tracking is also updated by navigation control parameters. In the included sample node, vertices are the navigation control parameters.

Visited nodes dynamic limit

Another key element of our nodes algorithm is the visited nodes dynamic limit. When the nodes class is constructed the user can feed directly the maximum number of visited nodes. When a path is found between two nodes the visited node limit is automatically modified. A new limit is set based on the shortest path already found. Another feature added to the scan algorithm of nodes is an adjacent node connect inhibitor taken from basic geometry and further explained in the adjacent nodes filtering. The dynamic control of visited nodes therefore reduces the number of future path scans as the algorithm will now abort based on the new limit set by the path found as well as the collection of.visited nodes.

Distance Breaks of current vs found paths

As the algorithm processes nodes it also keeps track of the total distance covered. Distance between nodes is pre-calculated when the nodes are first created or initially processed. A distance break occurs when the distance covered is equal or longer with the distance of the shortest path previously found. The distance break is implemented in two different places. During node iteration and during node recursion.

Navigation Control

There are navigation control parameters that are application dependent and can greatly enhance search performance. With the included sample the navigation parameters are node vertices. Node vertices offer two advantages. First node vertices can accurately calculate distances between nodes in a multi-dimensional environment and the distance between any node and the target node can be calculated at any time. The node search algorithm presented uses the distance between nodes as a decision making before executing the next iteration or recursion. In other words the next visited node can be based on a shortest distance criteria instead of a default arbitrary node order. When vertices are disabled the algorithm attempts to short non-visited nodes by distance so the closest nodes to the current one are processed first. This is done to increase the visited nodes storage as much as possible therefore increasing the chances of blocking nodes in the current path and reaching the target node faster than when having a random order for node iteration.

Dynamic shorting of nodes prior processing

As mentioned in the navigation control section, shorting of nodes can alter significantly the search process. Using application specific elements nodes can be shorted in a certain way, making the depth search extremely efficient. If we consider the worst case scenario where for 2 given nodes there is no path described, the dynamic shorting can still block visited nodes more efficiently than not having a shorting mechanism. For instance by visiting the closest to the current, nodes first the number of nodes we can reduce back-tracking. If we have nodes A,B,C connected to form a triangle and where sites AC > AB then the nodes will be processed in order A->B->C.

Dynamic removal of reversed node connects

When paths are found or when certain application elements are given the algorithm, we can remove reversed connections among nodes. In the first case when a path is found from nodes 1,2,3 where the dual connections exist among nodes the reversed nodes are removed. Afterwards the algorithm will have fewer node paths to consider. In addition for the second case, application specifics can be used to determine reversed node removal. If we use vertices to reach the target node based on a distance factor, "a moving closer to the target" outcome, from an iteration or recursion, may remove a reversed connection between 2 nodes, if one exists. Removal of reversed nodes also shows why node shorting methods are very important to be determined dynamically, during searches.

Adjacent node filtering

For any node its connections to other nodes are passed with the recursion process. Therefore the next recursive node scan, cannot access adjacent nodes of its parent. In other words given a triangle with nodes ABC the distances of AB+BC is always greater than AC. Therefore there is no point for the scan process of node B to attempt a scan via node C when the scan process is starts with node A and continuous with node B. This inhibit node process is based on geometry of triangles and shortens the node scan process and further explains the default nodes shorting by distance in the sample code..

Closest node to target tracking when no path is found

This feature requires at least one navigation control element to be in place and is application specific. With the sample code the use of vertices include the coordinates of the target node. Therefore during scanning the algorithm knows for any node visited the distance from the target node and stores it separately. When no navigation element is present there is no way to use the closest node to target node feature.

Dynamic optimization of paths by tracking visited node segments

As paths among nodes are discovered the algorithm attempts a path optimization technique. Given a set of found paths future searches in process attempt to optimize existing paths by keeping track of node segments. Node segments are valid connections among nodes during recursion as the search progresses visiting new nodes. For example for a search between nodes [ 1,5] if we have found a path among nodes [1,2,3,4,5] and our current node scan is 1,2,4 the path optimization routine will alter the found path to [1,2,4,5].

Tracking of alternative paths generation

In most cases the algorithm will not find the optimum path outright. Paths found are stored in two different areas. The main paths are stored with the final results while secondary or alternative paths are stored in a separate area. Some paths among nodes can be constructed on the fly given existing paths stored and node segments in process. Distance breaks may also generate alternative paths if the current node is close enough to the target node. The alternative paths generation offers several advantages to an application. For instance if a nodes in a path must be accessed by a single entity in a given time, alternative paths allows other entities to reach the target node at the same time. Because in the end paths found are utilized by the application itself. Following the depth search principle the nodes search algorithm will stop when all the possible paths are exhausted and so alternative paths will be likely present unless there is a significant difference between nodes and the first search pass is an optimum. However to force alternative paths generation the initialization routine allows controls of distance breaks at two different levels. If a distance break is disabled the search functions will continue the nodes scan without distance control thus allowing alternative paths generation.

Progressive removal and replacement of visited nodes belong to found paths

As each node search progresses, paths found are used to mark a global area of nodes visited. The global nodes visited area is different that the visited nodes used during recursion. It allows the algorithm to know what segments are a no-go during a specific node scan and abort the search quickly saving time and memory resources. In addition the global nodes visited area is also updated during node iteration of and recursion in order to recognize new paths, construct new segments. an reform existing nodes paths stored.

Automatic generation of random nodes

For test purposes the nodes class includes an automatic method to generate node maps. The node generation can be driven by vertices or by distance. When the nodes class is to process vertices, the vertices for each node is first generated, then a random connection to a set of other nodes is created and finally the distance between nodes is derived and placed together with the nodes map. When the node generation is driven by nodes distance only, the nodes are randomly generated and a random distance is set for each node connection. Depending on the application the random generation routine can be altered and tuned to match the specifics of the environment for testing purposes. With the included sample there is also a hard-coded set of nodes along with a diagram to for demonstration purposes.

File saving and loading of paths

Nodes can be saved to a file or restored from a file. Using a couple of helper functions the class provides methods to save or load node files. Node files can also include application specific elements. The sample includes code to also store and restore vertices of a 3-D environment.

Controls of debug, display and optimizations

The nodes class also includes display, debug and general controls that can alter its behavior based on the environment used. The display controls can show the task for each iteration or recursion the nodes class performs. The display controls can show detailed statistics including the nodes area, the final visited nodes area , number of revisits, recursions, stack level, path optimizations, distance breaks from paths and many other node scan parameters.

Implementations and discussion

You may wonder what's the relationship of a nodes topic with e-commerce and content management systems? What if you have only products and want to form categories based on product associations? The nodes class paradigm can be implemented with distances replaced by product relationships and with primary or alternative paths forming categories. What if a student or a junior employee has to to read a certain number of documents from a database where the relationship cannot be easily formed using disciplines and topics? Again a document relationship can form via sequence in a non-deterministic manner with a dedicated application of the nodes class. Possibilities are endless. And of course the nodes class can be used for maze solving, bot waypoints. chart navigation and multi-client environments.

In this topic we gave a fairly detailed description of the nodes class. The next topic demonstrates the use of the nodes class with a node sample and a diagram. Click here to see the sample application.