Original Publication Date: 2003-Jan-23
Included in the Prior Art Database: 2003-Jan-23
Straight paths are a class of paths between a source and a destination defined as follows.
First definition For s belonging to N, an s-straight path between a source and a destination is a path for which there is no way of replacing any sequence of t or more nodes in the path by a sequence of t-1 or less nodes such that the resulting path is still a path (and this operation cannot be applied again for this resulting path), for any t such that 1<= t <= s.
In other words, if there exists a way to replace a sequence of nodes according to the rule above, and the resulting path cannot be reduced further, then the original path is not straight. The above definition is correct for s=1, but is not sufficient for s>1. Therefore we introduce a more accurate version:
Formal definition A path is s-straight (degree of straightness equal to s) if there is no possible s-projection of this path that would lead to a path that cannot be s-projected further. A s-projection is defined as a set of mutually independent t-reductions, each t-reduction being the replacement of a sequence of t or more contiguous nodes (t can be different for each reduction) on the original path with t-1 or less nodes such that the reduced path is still a path, for t such that 1<= t <= s. The mutual independence of the reductions means that for each reduction in the projection, the nodes at each extremity of the sequence (but not included in the sequence) must always belong to the original path. Note that sequences cannot be overlapping, as otherwise the reduction of a sequence of nodes would remove some nodes (the overlapping nodes) of another sequence.
Transposition of paths and projections in G into node and edges in G' Assume S the set of all paths without loops (S0 ) in a graph G between a pair of nodes (s,d). Another graph Gs ' can be created for which each node is a path in G, and each directed edge between a source node and a destination node indicates that a possible s-projection exists from the path corresponding to the source node to the path corresponding to the destination node. Note that G s' is a DAG (Directed Acyclic Graph).
The graph Gs ' is unique given G, (s,d), and a desired degree of straightness. From each node in the graph G s ', it is possible to determine whether the corresponding path in G is s-straight using the following rules once all edges in G s' have been found: All nodes without children are straight. All nodes that have at least one straight child are not straight otherwise they are straight. Note that G s ' does not contain directed loops (each edge correspond to a projection, so that the resulting path is shorter than the original path, and therefore no projection can lead back to a previous (longer) path). The state of a node (straight or not straight) depends on the state of its children. Given that
there is no directed loop in G s ', it is possible to progressively define the state of each node, start...