Route# is an application for loading complex networks and find minimal paths. The application is able to provide high performance algorithms in order to reach this goal and lets the user choose the way to do that.

Netfile syntax

Route# needs to build the graph representing the network to traverse in order to find minimal paths. In order to do so a step-by-step process is considered in order to produce an Adjacency Matrix and, from this, the collection of nodes and connections that will form the final network. The first stage is loading nodes and connection from the user. the simplest way is through a declarative language defined ad-hoc to specify the most important elements in the network. The file is checked and parsed and its data loaded.

This important file is called “netfile” and it must be present when running the application. It generally has the “.net” extension.

What can I specify in the netfile?

In the netfile it is possible to specify the following information using a simple line-based language:

  • Nodes: The nodes in the network. Every node needs to have an identifier. This identifier must be unique in the network, otherwise the file parsing process and the network creation processes will fail.
  • Connections: The connections between two nodes in the network. Please remember that a connection has these information associated:
    • Source node: The node the connection starts from.
    • Destination node: The node the connection ends into.
    • Cost/Weight: Every connection is walked through a cost that determines the effort in walking that path from the source node to the destination node.

The network can be created using these information.

Syntax specification

The netfile is written in route# a small line-based language with a very small keyword-set.

There are only 5 keywords in the language and the possibility to create comments. The language allows the possibility to write using spaces. To better examine the keywords, it is better to follow a functionality-based description flow.

Language characteristics

The language has a small set of properties:

Property Value
Case sensitive Yes
Allowed character set {[a-z], [A-Z], [0-9], “;”}
Reserved words node, connection, from, to, with
Comments Line comment + finite comment

Declaring nodes

In order to declare a node it is possible to use this syntax:

node <Node name>;

By using the node keyword it is possible to instruct the compiler to create a record for the specified node. This will enable the compiler to recognize the node when used in a connection. Note that it is necessary to insert the name of the node between angle brackets <>. Everything inside the angle brackets will be considered as the name of the node. For this reason please remember not to begin or end the name using spaces. The following declarations are correct and incorrect:

node <NodeA>; /* Correct */
node <Node A>; /* Correct */
node < NodeA>; /* Incorrect */
node <NodeA >; /* Incorrect */
node < NodeA >; /* Incorrect */

Please consider that the keyword node is case sensitive. Please remember also to end a node declaration with a semicolon ; or the instruction will not be correctly interpreted.

Declaring full nodes

A full node declaration is a node declaration where the position of the node, in a normed bidimensional space, is specified as following:

node <Node name> at (X Y);

Remember that X and Y are floating! So these examples will tell more:

node <NodeA> at (1 2); /* Incorrect: Coordinates are not float */
node <NodeA> at (1.0 2.0); /* Correct */
node <NodeA> at (1.0 2); /* Incorrect */
node <NodeA> at (1.0, 2.0); /* Incorrect: No comma as separator of coordinates */

When a brief node declaration is written, it is automatically converted with a full node declaration where X=0.0 and Y=0.0 are set, so:

node <NodeA>; /* It will be converted with the second line */
node <NodeA> at (0.0 0.0);

Declaring connections

To declare a connection it is possible to use the following syntax:

connection from <Node A name> to <Node B name> with “xx.yy”;

The from clause determines the start point of the connection. the to keyword defines the end point for the connection being specified. The with clause specifies the cost associated to the connection, the weight is encoded as a double precision number using the dot . as delimiter for decimal digits.

The rules for node names are the same here. The following expressions are correct and incorrect:

connection from <NodeA> to <NodeB> with “12”; /* Correct */
connection from <Node A> to <Node B> with “123.23”; /* Correct */
connection from < Node A > to <Node B> with “45.00”; /* Incorrect: invalid node name */
connection from <Node A> to <NodeB> with “13,34”; /* Incorrect: invalid weight value */

When processing a connection clause, the compiler will reserve a record for the specified connection.

No top down processing

It is very important to underline that the compiler does not follow a top-down processing flow. So, if a connection definition comes before nodes definition, the compilation process will be ok anyway. Please consider the example below:

connection from <NodeA> to <NodeB> with “12”; /* NodeA and NodeB have not been defined yet */
node <NodeA>; /* Definition here */
node <NodeB>; /* Definition here */

This example will compile correctly.

Declaring queries

A query is a request for a path finding. In the netfile it is possible to specify also the paths one is looking for. The syntax is the following:

pathquery from <Node A name> to <Node B name>;

All queries are evaluated after nodes and connections being parsed. Queries are processed in the order of appearance from top to bottom. A list of paths is returned.

Comments

As shown before the language lets the user create two types of comments:

  • Line comments: This comments consider all the line
  • In-Token comments/finite comments: These comments have a start point and an end point inside a token.

Here it is possible to consider some examples:

// This is a line comment
connection from <NodeA> to <NodeB> with “23.1”; /* This is a finite comment */
node <NodeA>; /* Another finite comment */
node <NodeB>; /* The last finite comment */

Comments are not processed by the compiler.

Last edited Mar 24, 2011 at 8:34 AM by andry87, version 16

Comments

No comments yet.