On Sun, Jan 05, 2014 at 08:25:12AM -0800, GerdP wrote:
The question is:
If you get a list of oneway road (parts) which create routing islands,
is it really the only conclusion that these oneways are wrong?
I cannot think of any other conclusion in the practice. See below for a
somewhat artificial example.
Before I left the academic world 10 years ago, I implemented Tarjan's
algorithm for strongly connected components in a model checker tool. It
was applied to the graph of reachable states (reachability graph) of the
modelled system, which would typically be a high-level model of a
distributed system or protocol.
A desired property of any distributed algorithm is that its state
diagram is strongly connected, that is, you can get from any valid state
to any other valid state by performing a number of possible actions.
When the reachability graph of a distributed system is not strongly
connected, it usually means that one or more actors (processes, threads,
whatever) are stuck. The system as a whole might not be in a deadlock,
if some processes can keep doing something.
There is a class of distributed algorithms called self-stabilizing
algorithms. They have the additional property that you can get from any
state (including invalid states) to the valid states. In the
reachability graph of this kind of a distributed algorithm you would
have a very large number of initial states (all possible states of the
distributed system), and there would a strongly connected component of
the valid states.
Now, let me get back to the OSM domain. I guess we could think of a
restricted area that only defines oneway exits to the public road
network, but the entry roads are well-kept secrets (maybe enforced by
law). If the road network within the restricted area is mapped, then it
would form its own strongly connected component from which you can get
to the strongly connected component of the public road network, but not
vice versa. (By definition, the graph of strongly connected components
is acyclic.)
Marko
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
