Description: The algorithm developed by Eppstein not looking for simple paths. In
Indeed, the paths returned by the algorithm may contain rings or
loops. It applies only on graphs where the weights are positive.
This algorithm is based on extensive use of heap. These piles will allow
construct a graph of P such that the maximum level is 4 and a path
in P corresponds to a path in the starting graph.
A Python script (ksp.py) is provided in order to test both algorithms
directly the command line. The parameters are the file name
containing the graph, the origin of the roads, the roads end and the number
paths. It should also add the -a option followed by the choice of algorithm
(Eppstein or yen). Two additional optional parameters have been added:
-s which saves the graph in an image whose name is passed
-p parameter and that saves the graph P generated Eppstein algorithm.
Both options require Graphviz to generate images and the
library PyGraphviz
To Search:
File list (Check if you may need any files):
heap.py
ksp.py
measures.py
README.txt
graphs\complete.txt
......\exampleEppstein.svg
......\exampleEppstein.txt
......\exampleEppsteinP.svg
......\exampleYen.svg
......\exampleYen.txt
......\exampleYenP.svg
......\format.txt
......\twopaths.svg
......\twopaths.txt
networkx\algorithms\approximation\clique.py
........\..........\.............\clustering_coefficient.py
........\..........\.............\dominating_set.py
........\..........\.............\independent_set.py
........\..........\.............\matching.py
........\..........\.............\ramsey.py
........\..........\.............\tests\test_approx_clust_coeff.py
........\..........\.............\.....\test_clique.py
........\..........\.............\.....\test_dominating_set.py
........\..........\.............\.....\test_independent_set.py
........\..........\.............\.....\test_matching.py
........\..........\.............\.....\test_ramsey.py
........\..........\.............\.....\test_vertex_cover.py
........\..........\.............\vertex_cover.py
........\..........\.............\__init__.py
........\..........\.ssortativity\connectivity.py
........\..........\.............\connectivity.pyc
........\..........\.............\correlation.py
........\..........\.............\correlation.pyc
........\..........\.............\mixing.py
........\..........\.............\mixing.pyc
........\..........\.............\neighbor_degree.py
........\..........\.............\neighbor_degree.pyc
........\..........\.............\pairs.py
........\..........\.............\pairs.pyc
........\..........\.............\tests\base_test.py
........\..........\.............\.....\test_connectivity.py
........\..........\.............\.....\test_correlation.py
........\..........\.............\.....\test_mixing.py
........\..........\.............\.....\test_neighbor_degree.py
........\..........\.............\.....\test_pairs.py
........\..........\.............\__init__.py
........\..........\.............\__init__.pyc
........\..........\bipartite\basic.py
........\..........\.........\basic.pyc
........\..........\.........\centrality.py
........\..........\.........\centrality.pyc
........\..........\.........\cluster.py
........\..........\.........\cluster.pyc
........\..........\.........\projection.py
........\..........\.........\projection.pyc
........\..........\.........\redundancy.py
........\..........\.........\redundancy.pyc
........\..........\.........\spectral.py
........\..........\.........\spectral.pyc
........\..........\.........\tests\test_basic.py
........\..........\.........\.....\test_centrality.py
........\..........\.........\.....\test_cluster.py
........\..........\.........\.....\test_project.py
........\..........\.........\.....\test_spectral_bipartivity.py
........\..........\.........\__init__.py
........\..........\.........\__init__.pyc
........\..........\block.py
........\..........\block.pyc
........\..........\boundary.py
........\..........\boundary.pyc
........\..........\centrality\betweenness.py
........\..........\..........\betweenness.pyc
........\..........\..........\betweenness_subset.py
........\..........\..........\betweenness_subset.pyc
........\..........\..........\closeness.py
........\..........\..........\closeness.pyc
........\..........\..........\communicability_alg.py
........\..........\..........\communicability_alg.pyc
........\..........\..........\current_flow_betweenness.py
........\..........\..........\current_flow_betweenness.pyc
........\..........\..........\current_flow_betweenness_subset.py
........\..........\..........\current_flow_betweenness_subset.pyc
........\..........\..........\current_flow_closeness.py
........\..........\..........\current_flow_closeness.pyc
........\..........\..........\degree_alg.py
........\..........\..........\degree_alg.pyc
........\..........\..........\dispersion.py
........\..........\..........\dispersion.pyc
........\..........\..........\eigenvector.py
........\..........\..........\eigenvector.pyc
........\..........\..........\flow_matrix.py
....
Download