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.
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 2^{nd} 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 subnetwork 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 subnetwork 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 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. Interareas 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 subnetwork and to make of it a true interareas network from P to R, coordinated with the local networks of P and R. The necessary properties of such an interarea network U are the following ones:
In this case, if the area R has a central node M and P a central node L, the interareas 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 interareas networks from an area Q to P and from P to R, the multipart transports obtained by composing their lines forms an interareas 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 interareas network between them. An extreme case is that of two areas P and P' which have the same central node L without having interareas network; this is possible if the two areas have targeted networks towards the same localities.
In this case, if U' are an interareas network from an area R' towards P' and U an interareas 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 interareas 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 breakeven 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 interareas 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 15, obtained when P and P' have the same central node, and there are interareas 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.1. Category associated to a labeled graph
Here graph will always mean directed multigraph, 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:
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:
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:
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: i ® 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 colimitcone 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.
min{qiq} =max(min{qjq}, 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).
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 subgraph formed by all the arrows between the objects 1, 2, 3, 4; this subgraph is drawn and its "table" is indicated (bottom right). The subcategory P' of K generated by P is constructed (it is the full subcategory 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
(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).
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 subcategory 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 subcategory 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).
Program by J.P. Vanbremeersch (1997) 
