# Looking for a particular generalization of the concept of a mathematical graph

I'm am trying to define a data structure to represent road networks. The immediately obvious structure is that of a graph - a set of nodes and edges that connect pairs of nodes. The nodes would represent things like intersections, and the edges would represent lanes.

However, the basic concept of a graph is insufficient to describe what I want. I also want to be able to describe how certain lanes are "reachable" or "adjacent" to other lanes. (Imagine parallel lanes with no median between them. You can just switch lanes.) This seems to imply a need to have some sort of meta-edge that connects pairs of edges. Is there any mathematical structure that sounds like this? Is this reducible to the standard concept of a graph? Thanks.

-
Do switchable lanes need to be distinguishable? – kennytm Aug 20 '10 at 15:14
Yes, we must have lane-level information for my application. – John Berryman Aug 20 '10 at 15:41

## 3 Answers

You could make the lanes themselves nodes as well

-
So that there would be lane nodes, and location nodes, and edges to connect them all? Perhaps. I'll have to think about that some more. – John Berryman Aug 20 '10 at 15:44
More specifically, points along the lanes... hmm, this is starting to remind me of the Unreal bot navigation nodes... – SamB Dec 4 '10 at 23:45

May be you can use a colored graph with the convention that if there are more than edges from point A to point B, they are switchable inbetween.

Edit (after comment that A and B may not be same):

Let me know if I am wrong, but geographically close points may be quite far apart topologically (i.e. when they have many intermediate closely situated points).

So the problem boils down to given a standard graph, for each edge how to best store which edges are 'reachable'.

Reachability seems to be a reflexive and commutative relation (i.e. a is reachable from b implies b is reachable from a). If reachability is also a transitive relation (i.e. if i can reach b from a and c from b then i can reach c from a), then you can still use the coloring approach. All you need to do is to divide the edges into equivalence classes, and assign separate colors for each equivalence class.

On the other hand, if it is not transitive, then the only option I see is for each edge to store a list of edges that are reachable from it.

-
Unfortunately this won't work for the current application because each lane must end with a different node because the end of the lane has a different geographical location than the end of the neighboring lane. Good thought though. – John Berryman Aug 20 '10 at 15:37
Just to clarify, so if I have two lanes from A to B which are switchable inbetween, you have two copies of A and B? – KalEl Aug 20 '10 at 15:45
Not two copies, two different nodes A1 and A2 and two different nodes B1 and B2. A1 is geographically close to A2, but not the same as A2. – John Berryman Aug 20 '10 at 15:51
Thanks. Please see edited answer. – KalEl Aug 20 '10 at 16:53
Unfortunately the assumptions about commutativity and transitivity won't hold. For instance, on an interstate with a middle, left, and right lane, you can move from left to middle and from middle to right, but you can't teleport directly from left to right (as transitivity would indicate). Rather you have to go through the middle lane. – John Berryman Aug 20 '10 at 17:43

It's not clear whether nodes for intersections are necessary.

You need a data structure that can accomodate (state transitions resulting from) the operations continue and switch lanes. The minimal set of states needed is: those pieces of road where, if you continue driving along them, the set of "switch" options is constant. This is the smallest set of states such that any switch operation is between different states.

You could impose additional nodes thought of as STATIONARY states of motion or FIXED-LOCATION geographic data, to express starting points, destinations, intersections, stopovers or geographic locations, but only the lanes on which a traveller moves are logically necessary. At a road intersection, one can switch from lane A on one road to lane B on another road, which is expressible as a single state transition, without going through an "inside the intersection" state. Having an intersection state may be troublesome, as passing through the intersection within different lane-to-lane transition paths will equate situations inside the intersection that are logically different (they support different switch options).

-