Graph Structure

Routing graphs are built on a node-edge model, which are stored in a web-friendly JSON format. It follows the following schema:

{
    "nodes": {},
    "pathAttributes": {}
}

The nodesobject stores all the nodes as individual objects. ThepathAttributes section holds all the attributes that can be defined for the edges, which can be filtered during routing to determine the path.

Nodes

A node consists of the following attributes:

coordinates, id, level,attributes and adjacentNodes

The nodes are internally represented as objects and linked as an adjacency list. The adjacentNodes attribute lists all nodes that are connected to the current node. The following code snippet shows an example of the structure of the node "EG_t1". The IDs are arbitrary, but should only occur once in the dataset.

{
    "nodes": {
        "EG_t1":{
            "level":"EG",
            "id":"EG_t1",
            "attributes": {
                "doorWidth":200
            },
            "coordinates": [6.939691121265676,50.94750567463683],
            "adjacentNodes": ["EG_t2"]
        }
    },
    "pathAttributes":{}
}

For example, this node seems to represent a door with a width of 200 cm. It is located on the ground floor and is connected to the neighbouring node EG_t2 (not shown here).

Edges

Edges are realised by the adjacency of the nodes. The following code snippet shows two nodes that are connected to each other by specifying each other in the adjacency list. Node EG_t1 is linked to EG_t2 in theadjacentNodes array and vice versa.

{
    "nodes": {
        "EG_t1": {
            "level": "EG",
            "id":"EG_t1",
            "attributes": {
                "doorWidth": 200
            },
            "coordinates": [6.939691121265676,50.94750567463683],
            "adjacentNodes": ["EG_t2"]
        },
        "EG_t2": {
            "level":"EG", 
            "id":"EG_t2", 
            "attributes": {
                "doorWidth": 200
            },
            "coordinates": [6.946372523305575,50.94931437616847],
            "adjacentNodes": ["EG_t1"]
        }
    },"pathAttributes": {
        "EG_t2-EG_t1": {
            "pathWidth": 200,
            "isStairsStairs": true
        }
    }
}

Path attributes can be uniquely assigned to a path by specifying the associated nodes <Node ID 1-Node ID 2> (see EG_t1-EG_t2) in thepathAttributes section. The above path contains stairs and has a path width of 200 cm. As can be seen here, both of these nodes store the same attribute doorWidth with the same value of 200.

Considering that a graph can have any number of nodes, there can be considerable redundancy with the same attributes and attribute values. The same is true for the same path attributes. Such a graph, as seen above, is called a "development graph". A later chapter will show how to eliminate these redundancies and create a more data efficient graph ("production graph").