we will build our model from data relative to the road network and optionally from other localized information such as living or working areas.

A shapefile is mainly constituted of three files: one contains the attribute table (.dbf), another contains the geometric data 
(.shp) and the third is an index allowing matching entries of the first with those of the second.

A shapefile contains only the geometric description of objects through a collection of 2D or 3D coordinates that represents, according to the layer type, a cloud of points, open polygon lines (for networks or closed polygon lines to describe the boundary of surfaces. The topological information, which describes in geomatics the relationships between the geometric entities, such as connections of edges with nodes in a graph or the adjacency between zones in a surface partition, is absolutely not present in a shapefile, and must therefore be computed by our application form the raw geometry of the imported data.

To build a realistic representation of the traffic network of an important urban agglomeration able to simulate the circulation of tens of thousand of vehicles, we had to conceive a network layer structure both complex and efficient. 

Furthermore, the importation of data coming from existing data provider such as IGN, *NAVTEQ* or Tele Atlas, we had to deal with the way each modeled things in their solutions.

## ! C. Urban Network Structure Specifications

A road network is modeled according to specifications that are in part common to any network and in part dependent on decisions made by the data producer.

1) *General specifications* A road network shares the properties of any geographic network. It is constituted of two main geometric entities: *lines*, 
linear components, comprised of several shape points, and nodes, point components that join or terminate lines.

These two entities are joined in an *oriented multigraph* where S is the set of vertices, associated to the geometric nodes, while the set A of edges is associated to the geometric lines, while function associates to each edge one initial and one final vertex.

Unlike most other geographic information layer, a road network may not be planar: two lines can intersect in their planar projection without modeling an intersection in the real world. This happens when these lines are at different altitudes such as in bridges, tunnels, or motorway embranchments.

Furthermore, geographic graph are *topological graph* differ from usual graph in that they are associated to one geometric representation, called the *embedding* of the graph. Only vertices of degree 3 or more are considered to be true vertex, those of degree 2 being seen as *shape points*, useful for the geometric information they bring, but not "true" connectors. The geometric representation of the graph is always present to the mind of the geographer, which may create misunderstandings with other scientists more used to a more abstract representation of graph, with *planar* graph rather than plane graph. As previously said, it is also sometimes extended G = (S,A, f )
f : A " S \# S
!

to non planar graph: the geometric information in the shapefile represents in that case the projection on a connected compact 2-manifold of a graph embedded in a connected compact 3manifold (intuitively: a 3D graph is drawn on a surface).

The attribute table associated to the network will contain all the traffic related information, such as the number of lanes, speed limits, sense of travel etc. Nonetheless this information may not be associated to elementary lines or nodes. For example major roads may contain different lines and important roundabout may contain different nodes and lines. We therefore defined the notion of super-nodes that relate to several nodes (and the assorted sub-graph) and super-edges that relate to several edges (and the assorted sub-graph). G is therefore a hypergraph in these conditions. Whether these are met or not depend on modeling decisions made by the data provider.

2) *Geographic data based specifications* There are different ways of structuring the geographic information in a shapefile to model a network.

For example *NAVTEQ* chose in its Navstreets product to create a node for each intersecting link, even if the road they model are not connected. Another layer represents the relative elevation of the entities of this first layer. Both must therefore be used to correctly build the road network in our simulation. Another example is the orientation of the edges, as the links are oriented following another convention (called "Reference nodes") than what could be used in a shapefile, and the edge must therefore be computed following this convention.

## D. Building The Topology From The Geometry.

Building a topology from the geometric information contained for example in a shapefile depends on the kind of spatial organization we want to represent.

1) *Planar mesh* In the case of a surface mesh (ex: limits of countries, of urban areas, of town quarters etc.), we aim at rebuilding the boundaries and the junction nodes between them from closed polygonal chains (aka polylines). The layer we produce is thereafter structured around a planar multigraph of vertices, edges and faces, and with each oriented edge associated to 2 vertices (initial and terminal) and to 2 faces (left and right).

The building algorithm uses a quadtree and a tree connecting each point, in which all the points of the shapefile are organized. Each leaf of the quadtree contains a point Pi and 4 branches for the 4 quadrants of space (NE, SE, SW, 
NW) surrounding Pi. When a branch is a leaf, it contains a point belonging to right quadrant relatively to its father, and vice versa. This structure allows for a quick detection of the multiplicity of points. For example, a point with a multiplicity of 3 or more will be associated to a vertex, while a point of multiplicity of 2 will be a shape point of an edge. Furthermore, the connection tree allows the quick detection of adjacent points along a polyline, and detecting the superposition of two lines forming the boundaries of two zones, or the succession of angular sectors around a vertex common to three polygons or more.