1.1 The graph list data structure

Metanet uses the graph list data structure to represent graphs. With this type of description (see 1.2), we can have directed or undirected multigraphs and multiple loops are allowed. The graph list data structure is a typed list. As usual, the first element of this object is itself a list which defines its type, 'graph', and all the access functions to the other elements. The graph list has 33 elements (not counting the first one defining the type). Only the first five elements must have a value in the list, all the others can be given the empty vector [] as a value, and then a default is used. These five required elements are:

name

name of the graph (a string)

directed

flag equal to 1 if the graph is directed or equal to 0 if the graph is undirected

node_number

number of nodes

tail

row vector of the tail node numbers

head

row vector of the head node numbers

A graph must at least have one arc, so tail and head cannot be empty.

For instance, you can define a graph list (see 2.1) by

g=make_graph('min',1,1,[1],[1]);

which is the simplest graph you can create (it is directed, has one node and one loop arc on this node).

Each element of the list can be accessed by using its name. For instance, if g is a graph list and you want to get the node_number element, you only have to type:
g('node_number')
and if you want to change this value to 10, you only have to type:
g('node_number')=10

The check_graph function checks a graph list to see if there are inconsistencies in its elements. Checking is not only syntactic (number of elements of the list, compatible sizes of the vectors), but also semantic in the sense that check_graph checks that node_number, tail and head elements of the list can really represent a graph. This checking is automatically made when calling functions with a graph list as an argument.

You will find below the description of all the elements of a graph list. Each element is described by one or more lines. The first lines give the name of the element and its definition, with its Scilab type if needed. The last line gives the default for elements that can have one. The name of the element is used to access the elements of the list.

name

Name of the graph; a string with a maximum of 80 characters (REQUIRED).

directed

Flag giving the type of the graph; it is equal to 1 if the graph is directed or equal to 0 is the graph is undirected (REQUIRED).

node_number

Number of nodes (REQUIRED).

tail

Row vector of the tail node numbers (REQUIRED).

head

Row vector of the head node numbers (REQUIRED).

node_name

Row vector of the node names; they MUST be different.

Default is the node numbers as node names.

node_type

Row vector of the node types; the type is an integer from 0 to 2:

0:

plain node

1:

sink node

2:

source node

This element is mainly used to draw the nodes in the Metanet window. A plain node is drawn as a circle. A sink or source node is a node where extraneous flow goes out the node or goes into the node; it is drawn differently (a circle with an outgoing or ingoing arrow).

Default is 0 (plain node).

node_x

Row vector of the x coordinates of the nodes.

Default is computed when showing the graph in the Metanet window (see 3).

node_y

Row vector of the y coordinates of the nodes.

Default is computed when showing the graph in the Metanet window (see 3).

node_color

Row vector of the node colors; the color is an integer from 0 to 16:

0:

black

1:

navyblue

2:

blue

3:

skyblue

4:

aquamarine

5:

forestgreen

6:

green

7:

lightcyan

8:

cyan

9:

orange

10:

red

11:

magenta

12:

violet

13:

yellow

14:

gold

15:

beige

16:

white

Default is 0 (black).

node_diam

Row vector of the sizes of the node diameters in pixels (a node is drawn as a circle).

Default is the value of element default_node_diam.

node_border

Row vector of the sizes of the node borders in pixels.

Default is the value of element default_node_border.

node_font_size

Row vector of the sizes of the font used to draw the name or the label of the node; you can choose 8, 10, 12, 14, 18 or 24.

Default is the value of element default_font_size.

node_demand

Row vector of the node demands.

The demands of the nodes are used in functions min_lcost_cflow, min_lcost_flow1, min_lcost_flow2, min_qcost_flow and supernode.

Default is 0.

edge_name

Row vector of the edge names; edge names need not be different.

Default is the edge numbers as edge names.

edge_color

Row vector of the edge colors; the color is an integer from 0 to 16 (see node_color).

Default is 0 (black).

edge_width

Row vector of the sizes of the edge widths in pixels.

Default is the value of element default_edge_width.

edge_hi_width

Row vector of the sizes of the highlighted edge widths in pixels.

Default is the value of element default_edge_hi_width.

edge_font_size

Row vector of the sizes of the font used to draw the name or the label of the edge; you can choose 8, 10, 12, 14, 18 or 24.

Default is the value of element default_font_size.

edge_length

Row vector of the edge lengths.

The lengths of the edges are used in functions graph_center, graph_diameter, salesman and shortest_path.

Default is 0.

edge_cost

Row vector of the edge costs.

The costs of the edges are used in functions min_lcost_cflow, min_lcost_flow1 and min_lcost_flow2.

Default is 0.

edge_min_cap

Row vector of the edge minimum capacities.

The minimum capacities of the edges are used in functions max_flow, min_lcost_cflow, min_lcost_flow1, min_lcost_flow2 and min_qcost_flow.

Default is 0.

edge_max_cap

Row vector of the edge maximum capacities.

The maximum capacities of the edges are used in functions max_cap_path, max_flow, min_lcost_cflow, min_lcost_flow1, min_lcost_flow2 and min_qcost_flow.

Default is 0.

edge_q_weight

Row vector of the edge quadratic weights. It corresponds to w(u) in the value of the cost on edge u with flow $\varphi(u)$: $\frac{1}{2}w(u)(\varphi(u)-w_0(u))^2$.

The quadratic weights of the edges are used in function min_qcost_flow.

Default is 0.

edge_q_orig

Row vector of the edge quadratic origins. It corresponds to w₀(u) in the value of the cost on edge u with flow $\varphi(u)$: $\frac{1}{2}w(u)(\varphi(u)-w_0(u))^2$.

The quadratic origins of the edges are used in function min_qcost_flow.

Default is 0.

edge_weight

Row vector of the edge weights.

The weights of the edges are used in function min_weight_tree.

Default is 0.

default_node_diam

Default size in pixels of the node diameters of the graph.

Default is 20.

default_node_border

Default size in pixels of the node borders of the graph.

Default is 2.

default_edge_width

Default size in pixels of the edge widths of the graph.

Default is 1.

default_edge_hi_width

Default size in pixels of the highlighted edge widths of the graph.

Default is 3.

default_font_size

Default size of the font used to draw the names or the labels of nodes and edges.

Default is 12.

node_label

Row vector of the node labels.

Node labels are used to draw a string in a node. It can be any string. An empty label can be given as a blank string ' '.

edge_label

Row vector of the edge labels.

Edge labels are used to draw a string on an edge. It can be any string. An empty label can be given as a blank string ' '.