]> granicus.if.org Git - re2c/commit
projects / re2c / commit
? search:
summary | shortlog | log | commit | commitdiff | tree
(parent: 68a88d1) | patch
Use Goldberg-Radzik shortest path algorithm for closure construction.
authorUlya Trofimovich <skvadrik@gmail.com>
Tue, 6 Jun 2017 07:53:36 +0000 (08:53 +0100)
committerUlya Trofimovich <skvadrik@gmail.com>
Tue, 6 Jun 2017 10:27:15 +0000 (11:27 +0100)
commit97d04e39cb7625c7862e61d9fde7f7d2f67e3e2d
tree046d79a98faf4069b02b2880a4edeaf9c11d4212tree | snapshot
parent68a88d109e07cb2861aadda7d9653df499a14d37commit | diff
Use Goldberg-Radzik shortest path algorithm for closure construction.

It has O(M*N) worst-case complexity, where M is the number of nodes (states)
and N is the number of arcs (transitions).

Papers: 1993, "A heuristic improvement of the Bellman-Ford algorithm"
by Goldberg, Radzik and 1996, Shortest paths algorithms: Theory and
experimental evaluation" by Cherkassky, Goldberg, Radzik.
re2c/src/dfa/closure.cc diff | blob | history
re2c/src/dfa/tagpool.cc diff | blob | history
re2c/src/dfa/tagpool.h diff | blob | history
re2c/src/nfa/nfa.h diff | blob | history
re2c/test/posix_captures/gor1.i--posix-captures.c [new file with mode: 0644] blob
re2c/test/posix_captures/gor1.i--posix-captures.re [new file with mode: 0644] blob
re2c/test/posix_captures/gor2.i--posix-captures.c [new file with mode: 0644] blob
re2c/test/posix_captures/gor2.i--posix-captures.re [new file with mode: 0644] blob
re2c/test/posix_captures/gor3.i--posix-captures.c [new file with mode: 0644] blob
re2c/test/posix_captures/gor3.i--posix-captures.re [new file with mode: 0644] blob
Unnamed repository; edit this file 'description' to name the repository.