This text and the simulation which illustrates it (program complex6.bas in qbasic, by J.-P. Vanbremeersch) were written in 1997 in order to give a simple example introducing to some concepts used in our Memory Evolutive Systems. They have not been published yet but should appear in the book on the MES we are in the course of drafting.

1. Transport network

Let us model the transport network of a country.

1.1. Characteristics of the net

It is formed by various regular transport lines connecting a locality (city or commune) of the country to another. Some localities are not connected; if a locality N is connected to another, there can exist one or more regular lines (the direction of a line is always specified). The cost of a transport is independent of the specific route taken from its starting point N to its end, but it depends on the means of transport and its characteristics (example: car, coach or train, duration of the travel, comfort, frequency, number of passengers…); this is evaluated by allotting to each transport g a "scale" (of comfort or convenience), represented by an integer p(g). For example a first class carriage will have a higher scale than a 2nd class one. Thus a line is characterized by the locality of departure, the locality of arrival and its scale.

If g is a line from N to N' and g' a line from N' to N", the network also makes it possible to go from N to N" by taking first g and then g'; if g and g' do not have the same scale, the scale allotted to this "multipart" line g.g' from N to N" will be the largest of their two scales (if the journey is made in first class on part of the way, the whole journey is paid at the price of the first class even if the other part is made in 2nd class). In formula:

p(g.g') = max(p(g), p(g')).

1.2. Local area network, targeted networks

The country is divided into wide areas and each area P manages its own local area network; it is a sub-network of the whole network formed of lines connecting the various localities of the area. In general P does not manage the lines connecting it to external localities. However it can exist a locality C to which a certain number of inhabitants of the area must go regularly. Let us think for example of the students of an area without university who will follow the courses of the nearest university; or of the transport of goods towards a more important trading center.

In this case to profit from a better service (more frequent lines, smaller prices), the area can, inside the total network, exploit a specific sub-network towards C, coordinated with its local network. In this targeted network, each locality Pi of the area is connected to C by a particular line (we'll say it is "targeted") qi, ran by the area; the lines qi are chosen so that the following constraint is checked: an inhabitant of Pi can, for the same price, go to C either directly via qi, or indirectly by taking first a local line f from Pi towards a Pj and then the targeted line qj from Pj to C; it means that qi has the same scale as the multipart line f.qj. In other words, the lines qi are such that the scale p(qi) is the largest of the scales of f and qj, for each local line f from Pi to Pj.

1.3. Central node

If the area P has targeted networks towards various external cities, the administration will be simplified if there is a central communication node through which its various targeted networks can transit. Such a central node will be a locality L, generally external to the area, whose site is selected so that the following conditions are satisfied:

• the area has a targeted network (li) towards L;
• to any other targeted network (qi) of P towards a locality C is associated a "central" line q from L to C through which the travelers of P can go; more precisely, an inhabitant of a locality Pi of the area can, without difference in price, go to C either directly via qi, or by using first the targeted line li and then the central line q ; thus it is necessary that the scale of qi be the largest of the scales of li and q.

The central node makes it possible for example to organize collective tours towards any of the localities C: the members of the group living in the various localities Pi will go individually to L (via the targeted lines li), then all together they will make the journey from L to C. It also allows people external to P and who should go to C crossing P to bypass it instead of penetrating in the area (thus avoiding the internal traffic): they go directly to L then use the central line q from L to C.

If none of the localities to which P is connected in the total network can play the part of a central node, the area may seek to create such a node in an adequate place, by extending the whole network by the organization of the new lines necessary for that. However this operation is not always possible, at least if one makes a point of observing the scale conditions strictly.

1.4. Inter-areas networks

Up to now we have considered a unique area P. Now we will study the transport between two areas. Various localities of P can be connected to localities of another area R by lines of the total network. But to increase their exchanges, the two areas P and R can act in concert to exploit jointly a sub-network and to make of it a true inter-areas network from P to R, coordinated with the local networks of P and R. The necessary properties of such an inter-area network U are the following ones:

• Each locality Pi of P is connected by a line u of U to at least one locality Rk of R; and if it is also connected to another locality of R by a line u' of U, then u and u' are connected by a zigzag of local lines of R.
• All the multipart lines formed by a local line of P and a line u of U, or by u and a local line of R also belong to the network U.

In this case, if the area R has a central node M and P a central node L, the inter-areas network U "is integrated " in a line û from L to M. Indeed, in this case the multipart lines made up of a line of U and a selected line from Rk to M form a selected network from P to M, and û is the corresponding central line from L to M. Thus to go from Pi to M a traveler can cross R or go directly from L towards M; indeed, he can go from Pi to L by the selected line li, and then from L to M by û (thus avoiding R), or go from Pi to Rk by a line of U and then from Rk to M by mk.

1.5. Lines between central nodes

If there are inter-areas networks from an area Q to P and from P to R, the multipart transports obtained by composing their lines forms an inter-areas network from Q to R, which is thus integrated in a transport of the central node of Q to that of R.

But the central nodes of two areas can be connected without there being an inter-areas network between them. An extreme case is that of two areas P and P' which have the same central node L without having inter-areas network; this is possible if the two areas have targeted networks towards the same localities.

In this case, if U' are an inter-areas network from an area R' towards P' and U an inter-areas network from P to R, the central nodes M' of R' and M of R are connected by the multipart line û' û; and yet R' and R are not necessarily connected by an inter-areas network. This line makes it possible to go via L without penetrating in the areas P or P'.

Remark. In the preceding example, the scale could be replaced by the break-even point of the line (representing the minimum number of passengers necessary to covering its operating costs).

1.6. How to model the network

The total network is modeled by a category K: Its objects represent the various localities N of the network, an arrow from N to N' represents a line of the network, which will be noted c: N ® N' where c is its scale; the composite of c: N ® N' with c': N' ® N" is the arrow max(c, c'): N ® N" (which represents the multipart line).

To the local network of an area P is associated a pattern of K, also noted P. A targeted network from P to C is modeled by a collective link from P to C (represented by a cone). The area has a central node L if P admits L for its colimit in K.

An inter-areas network U from P to an area R is modeled by a cluster between the patterns which represent them. If P and R have central nodes (thus colimits L and M), it is integrated in the "simple link" û from L to M.

If P does not have a colimit in K, one seeks to add one (modeling a central node) by the process of complexification of K with respect to the strategy consisting in adding a colimit to P. This process applied to several areas simultaneously leads to the introduction of "complex links" which are composites of simple links integrating nonadjacent clusters. They model the multipart lines considered in 1-5, obtained when P and P' have the same central node, and there are inter-areas networks from R' to P' and from P to R.

The conditions for an area P to have a central node in the initial network, or if not to be able to extend this network to add one, will be studied within the more general framework of categories associated with a labeled graph, and illustrated by a simulation in qbasic. In particular it will result from it that, if an area P does not have a central node, it is not always possible to add one which satisfies the constraints on the scales: it is always possible to add an L with a targeted network (li) in which the scale of each li is minimum, and a central line q from L to C for each targeted network from P to C, but the scale of this q is no more given as a function of the scales of the qi.

2. Mathematical model

2.1. Category associated to a labeled graph

Here graph will always mean directed multi-graph, i.e., the data of a set of objects and arrows between them. A category can be defined as a graph K equipped with an internal law of composition which associates to 2 consecutive arrows f: A ® B and g: B ® C an arrow f.g: A ® C. This composition must satisfy the 2 axioms:

• Associativity: (f.g).h = f.(g.h);
• Identity: for any object A it exists an "identity" arrow idA: A ® A whose composite on the right or on the left with another arrow gives again this other arrow.

To a graph G we associate a category C(G), called the category of paths of G, in the following way: It has the same objects that G and the arrows are all the paths (sequence of consecutive arrows) between its objects; the internal composition is defined by taking for the composite of two consecutive paths (f1...,fn) and (g1...,gm) their concatenation (f1...,fn,g1...,gm).

A labeled graph in a monoid H is a graph G equipped with a map p: G ® H associating to each arrow f of G an element p(f) of H, called its weight. (A monoid is a category with only one object.) These weights are extended to C(G) by taking for weight of a path the composite of the weights of its factors in the monoid. By identifying 2 paths which have the same source, the same target and the same weight, we obtain a quotient category of C(G) which has the same objects as G, and whose arrows are the classes of paths with the same weight. This category is called the category associated to the labeled graph (G,p), and it is noted K(G,p).

From now on, we take for H the monoid (N, max) of the integers equipped with the composition max(i, j). The category K(G,p) is then obtained starting from the category of paths of G by identifying 2 paths with the same weight, the weight of a path (f1,…,fn) being max(p(f1),…,p(fn)). In this category, given 2 objects i and j, there exists at most one arrow of weight c from i to j, and thus it will be noted c: i ® j.

The category modeling the transport network (cf. 1.6) is the category associated to the graph formed by the lines of the network, labeled by their scales.

2.2. Existence of a colimit

In a category K, a pattern P is a subgraph of the category which models a set of objects with some distinguished arrows (called links) between them. A collective link from P to an object C is a family of individual links Qi from i to C for each object i of P, compatible with the distinguished links of P in the sense that Qi = F.Qj if F is a distinguished link from i to j. It is represented by a cone with basis P and top C. The pattern has a colimit L in K if there is a collective link (Li) from P to L by which any other collective link (Qi) from P to C factors uniquely, i.e., there exists one and only one Q from L to C such that Qi = Li.Q for each object i of P.

Now let us take for K the category K(G,p) considered at the end of 2.1. If P is a pattern in K a collective link from P to an object C is then a family (qi: i ® C) of arrows from the objects i of P to C such that, for any distinguished link f: i ® j of P, we have qi = max(f, qj).

P admits a colimit L if there is a "canonical" collective link (li: i ® L) from P to L such that, for any collective link (qi: i ® C), there is one and only one link q: L ® C satisfying :

(1) qi = max(li, q) for any object i of P.

This condition imposes very strong constraints on P and the cones. Indeed, it is seen that it is equivalent to the conjunction of the 2 following conditions:

(a) There is a "minimum" cone (li: i ® L), in the sense that li is less or equal to qi for any cone (qi: i ® C) and any object i of P.

(b) For any other cone (qi: i ® C), one has:

• either qi = li for each i, and there is one and only one link q from L to C whose weight is equal to min(li).
• either q = min(qi) and, for any i, qi = li or qi = q.

Remark. A collective link from P to C also determines a collective link from P' to C, where P' is the pattern obtained by adding to P all the composites of its various links in the category (so that P' is the subcategory of K generated by P). Thus P and P' have the same colimit, if it exists.

2.3. Complexification

If P does not have a colimit in K, the "complexification process" makes it possible to extend K in a "minimal" way into a category K' in which P acquires a colimit. Two cases are possible:

• If there is a minimum cone (li: i ® L) which, without defining L as a colimit of P in K, satisfies the condition (1) above (but not the condition (b)), this cone defines L as a colimit of P in the category obtained by adding to K:

an object L', an arrow li: i ® L' for any object i of P, and, for any cone (qi: i ® C) the arrow min(qi): L' ® C whose composite with each li:® L is equal to qi: i ® C

This defines a category admitting K as a full subcategory and in which (li: i ® L') is a colimit-cone defining L' as the colimit of P. It is also the category associated to the labeled graph obtained by adding to G the object L' and the arrows added to K.

• In all the other cases the complexification will be built like above, but without taking account of the weights. In other words, it will be the category obtained by adding to K a new object L', a collective link from P to L' (which will become the colimit of P), and, for any collective link (qi: i ® C) a single arrow towards C which factors it via L. But this category is generally not associated to a labeled graph. Indeed, one can well weigh the collective link to L' by choosing for weight of the link li the minimum of the qi relating to the various cones q; these weights are compatible with those of the pattern, because, for any f: i ® j in P, the equalities qi = max(qj, f) involve

min{qi|q} =max(min{qj|q}, f).

But if (qi: i ® C) does not check the condition (b), one will not be able to put an adequate weight on the arrow which factors it, namely the minimum of the qi.

Let us give a counterexample: P has just 3 objects i, j, k and one arrow 3: i ® j. The other arrows of the category K form a cone of weights 3,3,5 towards C and a cone of weights 4,4,4 towards C'. Then the weights of the links to L' should be 3,3,4, but the arrow q from L' to C factoring the cone toward C cannot be weighted in an adequate way, for its weight d should check: max(d,3)= 4 = max(d,5).

3. Simulation

The construction of a colimit in the category K associated to a graph (G,p) labeled in (N, max) is simulated in "Complex6.bas".

3.1. Hypotheses

The graph G (randomly chosen) has 14 vertices, noted 1 to 14, the weights of which vary from 1 to 10. The associated category K = K(G,p) is constructed by adding to G the composites of 2 consecutive arrows (weighted by the max of their weights), then beginning anew till all the possible composites be obtained.

To simplify, it is assumed that G has at most one arrow from a vertex i to a j and that there exists no arrow from a j > 4 toward an i < 5.

The pattern P is taken as the sub-graph formed by all the arrows between the objects 1, 2, 3, 4; this sub-graph is drawn and its "table" is indicated (bottom right). The sub-category P' of K generated by P is constructed (it is the full sub-category of K with objects 1,2,3,4) by adding to P all the possible composites as above. P' is drawn.

3.2. Collective links from P toward an object C

An object C of K being selected, the arrows of the graph G from an object of P to C are drawn (their value is indicated along the table of P). Their composites with arrows of P' are constructed and drawn; the number of its arrows from i < 5 to C is indicated in the table.

All the possible sequences of 4 arrows (qi: i ® C), i < 5 are formed. Their number is noted (right top), followed by the value of C. Each such sequence is analyzed to see if it defines a collective link from P to C (cone), i.e. if qi = max(qj ,f) for each f: i ® j in P ; in this case the cone is numbered beside C with the weights of its four qi.

3.3. Search of a colimit

• If there exists no cone, P admits no colimit.
• If there are cones, the program searches if there is a "minimum" cone (li: i ® L) (condition (1) above) ; if it does not exist, P admits no colimit.
• If there is a minimum cone, for L to be a colimit of P it is also necessary that for each cone (qi: i ® C), there exists an integer n such that

(1) max(n, li) = qi for each i < 5.

If this condition is not satisfied, there is no colimit.

If it is satisfied, L is a colimit of P if for each other cone (qi), there exists one and only one arrow n: L ® C in K satisfying (1).

• If there is no minimum cone, a new object 15 is added as well as, for each i < 5, an arrow min{qi|q cone}: i ® 15 ; these arrows form a cone. There exists a complexification associated to a labeled category only if this cone factors all the other cones.

A final drawing shows the different cones and, if it exists, the colimit. The example can be stored.

Remarks. 1. Except at the end, the simulation takes no account of the arrows between objects > 5. In fact, the construction of P' and of the arrows from an i < 5 toward a C for each C is equivalent to the construction of the sub-category K' formed by the arrows with source 1, 2, 3, or 4, and their targets. So it is assumed that G is selected in such a way that K be the union of K' with the set of arrows between objects > 5. [Though values are noted for C < 4, they are not used in the computation; otherwise P' would not be a full sub-category of K and the computation would be more complicated.]

2. If there is no "labeled" complexification, it is nevertheless possible to construct a category in which P admits a colimit (cf. 2.3), but this category is no more labeled in (N, max). This case is not treated in the simulation.

3. The program is easily modified to find a colimit in the case where the labels are in (N, min) or in the additive group of the integers mod M (the "mod M" is necessary to have a finite number of arrows).

4. Program