The graphs handled by Metanet are directed or undirected multigraphs (loops are allowed). A graph is a set of arcs and nodes.
A graph must have at least one arc. We call arc a directed link between two nodes. For instance the arc (i,j) goes from tail node i to head node j. We call edge the corresponding undirected link. A minimal way to represent a graph is to give the number of nodes, the list of the tail nodes and the list of the head nodes. Each node has a number and each arc has a number. The numbers of nodes are consecutive and the number of arcs are consecutive. In Scilab, these lists are represented by row vectors. So, if we call tail and head these row vectors, the arc number i goes from node number tail(i) to node number head(i). Moreover, it is necessary to give the number of nodes, because isolated nodes (without any arc) can exist. The size of the vectors tail and head is the number of edges of the graph. This is the standard representation of graphs in Metanet as it is described in the graph list (see 1.1). There are functions to compute other representations better suited for some algorithms (see 1.2).
The distinction between edges and arcs is meaningful when we deal with undirected graphs. This distinction is not needed when we only use the standard functions of Metanet. There is no distinction between an arc and a directed edge . We will often use indistinctly these two terms.
A new object, the graph list data structure, is defined in Scilab to handle graph. It is described below.