Правильная ссылка на эту страницу
http://az-design.ru/Support/DataBase/002b4300_en.shtml

How to pass by the underground?

Arkhangelskiy Andrey

Russian

       The previous example it has been shown how to construct a tree on two tables. But as the tree is a special case of the graph this way it is possible to present any graph.
       The graph are the data structure consisting of nodes, connected by edges. Edges can be routed (to admit movings on them only in one direction) and not routed (to admit moving to both directions). The quantity of edges entering a site is named as its half of degree of an input (indegree), the quantity of exiting edges is named as its half of degree of an output (outdegree). The set of the edges, allowing will move from one site to another, named by. The cycle is a path, вовращающийся to a site from which it has started, not being intersected with itself (reminds the character About, but not digit 8).
       Recursively structured links between data are either trees (hierarchies), or the generalized oriented graphs.
       Trees are characterized by a lot of specific, very useful properties.
       For example, the tree represents a circuit-free graph. It means, that any path will not turn on itself, therefore, following on it it is impossible to get in an infinite loop. Besides always it is possible to pass from the radical up to any other site of a tree. Those cases, when in To the program VAZKompl. There were infinite loops, were considered as an error of the developer of complexes and should be corrected.
       But if the generalized graph, for example, the circuit of lines of underground as in it to find path from one site to another are used, using the above described receptions. This interesting task can prompt solutions in other similar tasks.
       So, for an example we shall take the circuit of underground of Moscow and we shall present it to a DB in the form of the generalized graph and we shall find path between any two servers.
       For this purpose in one table we shall place servers, as sites of the graph, and in other link between servers, as edges. Thus transitions between servers on different lines also are considered as link.

Create table MStations
   (Code     AZInt32 not null primary key, -- код станции
    Line     AZInt32,  -- линия, на которой находится станция
    Name     AZTitle,  -- наименование станции
    Note     AZNotes); -- возможные комментарии
Commit;
Insert into MStations(Code,Line) values (0,0);
Commit;
Alter table MStations add foreign key (Line) references MStations 
                                             on update cascade;

       Table MStations very simple — only four fields which describe the server. The Line field is entered simply for convenience of mapping of servers in the form of for the user, i.e. the list of lines of the underground, and then the server on the selected line all over again shows. So for example, it is made on a site of the Moscow underground www.mosmetro.ru. However, in the further it will be shown, how it is the field can помошь in a choice of more optimal path.

Create table MEdges
   (StLeft      AZInt32 references MStations on update cascade
                                             on delete cascade,
    StRight     AZInt32 references MStations on update cascade
                                             on delete cascade,
    RouteTime   Time,
    RouteNote   AZNotes,
Primary key(StLeft,StRight));
Commit;

       Table MEdges describes links between servers. StLeft specifies the server which is on the left end of an edge (перегона between servers), and StRight — specifies the server which is on the right end of an edge. The RouteTime field defines time of finding in path between these servers. In a similar way it is possible to add and other descriptions of an edge, for example, distances between servers, etc.
       To fill these tables script MetroLines.txt is used.

Insert into MStations(Code,Line,Name)
               values(1000,0,'Сокольническая линия');
Insert into MStations(Code,Line,Name)
               values(1041,1000,'Улица Подбельского');
Insert into MStations(Code,Line,Name)
               values(1042,1000,'Черкизовская');
Insert into MStations(Code,Line,Name)
               values(1043,1000,'Преображенская площадь');

       As codes of servers are assigned manually filling of table MStations is fulfilled usual операторм Insert.

Insert into MEdges(StLeft, StRight, RouteTime)
Select Lft.Code, Rgt.Code, '00:02:30' from MStations as Lft, MStations as Rgt
 where Lft.Name ='Улица Подбельского'
   and Rgt.Name='Черкизовская';
Insert into MEdges(StLeft, StRight, RouteTime)
Select Lft.Code, Rgt.Code, '00:02:30' from MStations as Lft, MStations as Rgt
 where Rgt.Name ='Улица Подбельского'
   and Lft.Name='Черкизовская';

       On the one hand, on edges it is possible to move in both directions and it the graph not routed, but on the other hand mean, that finding of path on an edge which does not have direction, are problematic. Therefore we shall present these graph as routed, but between two tops there are two paths in different directions. It is favourable also because transitions between servers really have different length in one and in other side, as it is possible to display by means of RouteTime field. At filling this table time is underlined provisional and identical to all edges.
       Besides the table for storage of the found path as which we shall name MRoutes is required to us:

Create table MRoutes
   (Start        AZInt32 references MStations on update cascade
                                              on delete cascade,
    Finish       AZInt32 references MStations on update cascade
                                              on delete cascade,
    RouteStep    AZInt32,
    RouteNbr     AZInt32,
Primary key(Start,Finish,RouteNbr));
Commit;

       The table contains a sequential set of edges which describes path from one server to another. The RouteStep field contains number of step on which the edge is received, and the RouteNbr field — contains number of path on which the algorithm quits a site.
       Before to start construction stored procedures, we shall estimate sequence of necessary operations.
       Let's assume, that we of anything do not know about structure of the graph.
       Let's take a point of the beginning of the path (Start) and we shall find all possible paths from it. That there were no infinite loops, shall put a condition that each edge was passed only once. Thus all graph will turn to a usual tree, on one of which branches there is a point of the end of the path (Finish). If after that to this tree to apply procedure of search of the parent from point Finish we shall receive the path upside-down — from point Finish up to point Start.

SET TERM !! ;
CREATE PROCEDURE SearchRoutes (Start Integer, Fin Integer, Step Integer)
 as
DECLARE VARIABLE  SNext Integer;
DECLARE VARIABLE  TNbr Integer;
BEGIN
   TNbr = 0;
   For Select StRight from MEdges
        where StLeft=:Start
          and StRight not in (Select Finish from MRoutes where Start=:Start)
         into :SNext
    do begin
          Step = Step + 1;
          TNbr = TNbr + 1;
          Insert into MRoutes(Start,Finish,RouteStep,RouteNbr)
                       values(:Start,:SNext,:Step,:TNbr);
          If (Start=Fin) then Exit;
          Execute procedure SearchRoutes(:SNext,:Fin,:Step);
      end
END !!
SET TERM ; !!
Commit;

       For a determinancy including, that the path starts with the left point of an edge will search for the right points of all edges which quit point Start. As for us each direction has the edge their one point at least two edges quit also two enter. Thus we shall eliminate those right points which already are in the path. So the main inquiry on which procedure SearchRoutes is under construction looks. Sorting out the found points, first we shall enumerate them by means of variable TNbr, and, secondly on everyone we shall increase number of step Step.
       The found edge it is written in table MRoutes as the next step of the path. If the point in variable Start has already appeared finite point Fin, we quit procedure to not do superfluous operation. Otherwise we use the found point as new value Start recursively we call procedure SearchRoutes.
       For final search of the path we use procedure GetRoutes which represents hardly modified procedure GetParent which has been described earlier.

SET TERM !! ;
create procedure GetRoutes (Beg integer, Fin Integer, bLev Integer)
                   returns (rStart Integer, rFin Integer, rLev Integer) as
begin
   for select Start from MRoutes where Finish=:Fin into :rStart
     do begin 
        rFin = Fin;
        rLev = bLev - 1;
        suspend;
        for select rStart,rFin,rLev from GetRoutes(:Beg,:rStart,:rLev)
              into :rStart,:rFin,:rLev
          do begin
             suspend;
             If (rStart=Beg) then Exit;
             end
        end
end!!
SET TERM ; !!
Commit;

       The difference consists in two trifles:
       — The place of the parent (Parent) will borrow Beg, Start, rStart, and the place of the descendant (Child) will borrow Fin, rFin.
       — As the top is quitted with some edges of a different trend at reaching the radical of a tree (the beginning of the path) there is an infinite loop with adjacent top. To prevent it the condition is used — if the initial top is reached to complete procedure.
       For demonstrating the described algorithms small program Example10 which as a matter of fact calls two above described procedures is used and fulfils some auxiliary operations, therefore source texts here are not resulted. But they can be found on a disk in directories Example10xxx.
       Operation of the program is shown below:


Pic.4-10 The Choice of the path between two servers of the underground without optimization

       Having selected from a revealing list "FROM" the server from which movement starts, and in the list "UP TO" the server to which it is necessary to reach, we press button "Start-up" with a red inscription and in the table we receive result of the above described operations.
       At once it is visible, that the received path is far from ideal, but it has resulted in the necessary server. It is not surprising. Nothing was known to us about the column, we did not mark the passed paths камешками as the boy about a small finger, we have simply transformed the generalized oriented graph to a tree and have risen on one of branches.
       If to the description of the graph to add the information that sites and edges of a graph belong to lines that lines can have intersections, and, that there is a line which is intersected with the majority of other lines (ring) can be left before search of the path in space of search only those edges which will certainly lead to positive result. For this purpose we shall a little correct table MEdges:

Create table MEdges
   (StLeft      AZInt32 references MStations on update cascade
                                             on delete cascade,
    StRight     AZInt32 references MStations on update cascade
                                             on delete cascade,
    LnLeft      AZInt32 references MStations on update cascade
                                             on delete cascade,
    LnRight     AZInt32 references MStations on update cascade
                                             on delete cascade,
    RouteTime   Time,
    RouteNote   AZNotes,
    EdgeUse     AZInt32D0,
Primary key(StLeft,StRight));
Commit;

       First of all добавленая the information on lines to which the server belongs, — LnLeft fields, LnRight.
       In-second queue the EdgeUse field is added — to use this edge. By default value of this 0 field that prohibits it to use in search.
       And, at last, it is necessary to correct procedure SearchRoutes a little:

SET TERM !! ;
CREATE PROCEDURE SearchRoutes (Start Integer, Fin Integer, Step Integer)
 as
DECLARE VARIABLE  SNext Integer;
DECLARE VARIABLE  TNbr Integer;
BEGIN
   TNbr = 0;
   For Select StRight from MEdges
        where StLeft=:Start and EdgeUse>0
          and StRight not in (Select Finish from MRoutes where Start=:Start)
         into :SNext
    do begin
          Step = Step + 1;
          TNbr = TNbr + 1;
          Insert into MRoutes(Start,Finish,RouteStep,RouteNbr)
                       values(:Start,:SNext,:Step,:TNbr);
          If (Start=Fin) then Exit;
          Execute procedure SearchRoutes(:SNext,:Fin,:Step);
      end
END !!
SET TERM ; !!
Commit;

       Having added a condition, that in search edges, for which EdgeUse field> 0 will participate only.
       Accordingly, it is necessary to correct a little a script which fills table MEdges:

Insert into MEdges(StLeft,LnLeft,StRight,LnRight,RouteTime)
Select Lft.Code,Lft.Line,Rgt.Code,Rgt.Line,'00:02:30'
  from MStations as Lft, MStations as Rgt
 where Lft.Name ='Улица Подбельского'
   and Rgt.Name='Черкизовская';
Insert into MEdges(StLeft,LnLeft,StRight,LnRight,RouteTime)
Select Lft.Code,Lft.Line,Rgt.Code,Rgt.Line,'00:02:30'
  from MStations as Lft, MStations as Rgt
 where Rgt.Name ='Улица Подбельского'
   and Lft.Name='Черкизовская';

       Now it is possible to start search, preliminary having prepared for this purpose table MEdges.
       1) all over again we shall install value EdgeUse of all edges in 0.
       2) we Shall include in space of searching only those edges which concern or to a line on which there is an starting station, or to a line on which there is a finich station:

Update MEdges Set EdgeUse=1
Where (LnLeft=:LnStart and LnRight=:LnStart)
    or (LnLeft=:LnFin and LnRight=:LnFin);

       Where variables LnStart and LnFin contain codes of lines on which there are appropriate servers.
       3) whether Then it is necessary to define there are intersections between lines LnStart and LnFin for what the following inquiry is used:

Select Count(*) as Cnt from MEdges
Where (LnLeft=:LnStart and LnRight=:LnFin)
    or (LnLeft=:LnStart and LnRight=:LnFin);

       And, if intersections are, i.e. variable Cnt>0 it is included in space of search of the server of an intersection by inquiry:

Update MEdges set EdgeUse=2
Where (LnLeft=:LnStart and LnRight=:LnFin)
    or (LnLeft=:LnStart and LnRight=:LnFin);

       Otherwise we add in space of search the Ring line and all servers of changes which to it concern:

Update MEdges set EdgeUse=2
Where (LnLeft=5000 or LnRight=5000);

       For simplicity of an example the code of the Ring line is specified obviously.
       After all these preparations it is again executable two above described functions — SearchRoutes and GetRoutes — having pressed button " Start-up " with a green inscription. The result is shown in a figure below:


Pic.4-11 Search of the path between two servers of the underground with optimization

       Apparently from this table the result has turned out more intelligible.
       Certainly, it only an example of usage of trees in a unusual situation. But at a known ingenuity more practical variants of usage of graphs are possible also.

© 01.07.2007, Arkhangelskiy A.G.

<<Prev. Table of contents
The beginning of section
Next>>




Дата последнего изменения:
Thursday, 21-Aug-2014 09:10:44 MSK


Постоянный адрес статьи:
http://az-design.ru/Support/DataBase/002b4300_en.shtml