Information Technology Reference
In-Depth Information
paths to the length 12. The rough comparison of the complexity measured for
the sequential algorithm with the length set to 10 and 12 we can observe that
the growth is exponential.
Another approach to the problem of searching all paths lying between two
vertices in a directed graph is a direct computation using the Tarjan's algorithms
described in [18] and [19]. The algorithm works in a time complexity n
log ( m )
where n represents the number of edges in the graph and m the number of
vertices in the graph. The algorithm takes a flow graph on the input and a start
vertex and returns the path expressions (regular expressions where the letters
are edges of the flow graph) representing all paths to all vertices in a graph on the
output. A flow graph is a special type of a directed graph which allows only one
source vertex in the graph and no cycles. There exist a non-trivial transformation
of an arbitrary directed graph into a flow graph. This computational overhead
of the graph transformation is not included in the complexity of the Tarjan's
algorithm.
In the progress of the search computational complexity of our designed index
structure and algorithm a decrease of the complexity can be observed for the
graphs G5000 and G10000. As we mentioned in the previous subsection, this is
due to the underfill of the search structure. The parameter settings used to built
the ρ -indexfor each of the testing graphs were the optimal ones for each particular
graph. Again only the max size of the segment on the lowest level varied and
the rest of the parameter settings remained same for all testing graphs.
10.5.3
Search Complexity of Queries with Limited Maximal Length
To this point we always considered the maximal length of the searched path
by the search algorithm to be the same as the maximal length that was used
to create the ρ -index. In this subsection we explore the behavior of the search
algorithm when the maximal length of the searched path is its parameter.
As we refer to the maximal length l of the indexed path, we refer to the max-
imal length of a searched path as sof tL . Setting this parameter does not limit
the search to return paths longer than sof tL but again it must not necessarily
find all of them.
Thus Figure 10.12 represents searches executed on the graph G10000 and with
the parameters set to 30, 10, 5 and 2. The ρ -index was computed with l equal to
10. The x-axis then represents the values of the sof tL parameter and the curves
represent the respective algorithms used to compute the result.
To make the Tarjan's approach comparable with ours and the sequential al-
gorithm we approximated the computational complexity by limiting the input
graph to only those vertices and edges that are reachable within sof tL steps.
As for the number of the found paths, the sequential algorithm finds all paths
to the length of sof tL , our algorithm finds all the paths to the length of sof tL
and some of the paths that are longer than that. Figure 10.13 represents the
percentage of paths not found that have length greater than sof tL for each
particular length. Although we ran the experiment for the sof tL value of 3 the
curve representing returned results is not present here since it returns no paths
 
Search WWH ::




Custom Search