JPH061484B2 - State transition diagram display processing method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Outline] Regarding a state transition diagram display processing method, the number of transitions for each of the states is obtained for the purpose of making it easier to see the state transitions by reducing the intersections of arrows indicating the state transitions. The decision section,
A display position determination unit that determines a display position on the circumference according to the number of the states, and a state arrangement determination unit that determines the arrangement position of the state in correspondence with the display position. The unit is configured to determine the arrangement position based on the number of transitions.

[Industrial application field]

 The present invention relates to a state transition diagram display processing method.

The state transition diagram is a graph in which the state transition functions are graphed and the relationships between the states are displayed in an easy-to-understand manner, and is widely used in the design and analysis of programs and sequential circuits.

[Conventional technology]

Conventionally, when the state transition function (state transition table) as shown in FIG. 9 is made into a state transition diagram by graphing, it is conventionally done as follows.

FIG. 10 is an explanatory view of a conventional technique and shows an example of a conventional state transition diagram.

Conventionally, the states a to d to be displayed are arranged on a straight line (FIG. 10 (A)) or on a circumference (FIG. 10 (B)) either randomly or in the order in which they appear. After this, according to the state transition table, directed arrows and inputs are displayed as indicating the state transition between the states. For example, when the state “a” has an input “0”, the state is changed to “a”. Is displayed as.

[Problems to be Solved by the Invention]

According to the above-mentioned conventional technique, since the respective states to be displayed are arranged randomly or in the order in which they appear, the arrows intersect as shown in FIGS. 10 (A) and 10 (B). Then, as the number of states increases and the state transition becomes more complicated, the number of intersections of arrows may increase.

If the number of crossed arrows increases, even if a state transition diagram is created from the state transition table, the state transitions are difficult to see and difficult to understand.

It is an object of the present invention to provide a state transition diagram display processing method that makes it easier to see the state transition by reducing the intersection of arrows indicating the state transition.

[Means for Solving the Problems]

FIG. 1 is a block diagram of the principle of the present invention, showing a data processing apparatus according to the present invention.

In FIG. 1, 1 is a processing device including a central processing unit (CPU) and a memory, 2 is a transition number determination unit, 3 is a state arrangement determination unit, 4 is a display position determination unit, 5 is a state number counting unit, 6
Reference numerals 8 to 8 are a memory unit, 9 is a display information unit, 10 is an arrow addition unit, 11 is a display control unit, 12 is a graphic library, and 13 is a display device having a display screen.

A state transition table, which is an object to be displayed as a graph, such as that shown in FIG. 9, is stored in the memory unit 6.

The number-of-transitions determining unit 2 obtains the number of transitions between states based on the state transition table of the memory unit 6, creates a table of the number of transitions as shown in FIG. 2, and stores this in the memory unit 7. Here, the number of transitions means the number of arrows added when the state transition diagram is created. For example, since the state transition table of Fig. 9 is used now, Are two (the number of transitions is 2). Therefore, the total number Si of transitions regarding the state a is set to 4, and the state a and the state a,
The number of transitions between b, c, and d is 0, 2, 2, and 0, respectively. In addition, the total number Si of transitions is, in fact, when the state arrangement determination unit 3 determines the state arrangement. It is required as a pretreatment.

The state number counting unit 5 obtains the number of states (to be displayed) included in the state transition table of the memory unit 6 from the state transition table.

The display position determination unit 4 determines a plurality of positions (display positions) (display positions) where a state should be displayed on the display screen by designating its coordinates. The display position is determined based on the number of states from the state number counting section 5, the size of the display screen from the display information section 9, and the like. Information about the display position is stored in the memory unit 8 as a layout table.

The state arrangement determination unit 3 sets 1 for each display position of the memory unit 8.
The arrangement position of each state is determined by associating the states to be displayed. This is performed by referring to the memory unit 7 and using (the size of) the number of transitions. As a result, a layout table in which the coordinates of the display position and the state are associated with each other is obtained in the memory unit 8.

The arrow addition unit 10 is arranged in the memory unit 8 and the memory unit 6.
With reference to the state transition table of, the information which adds the arrow and the input which shows a state transition between each state to the arrangement table is created.

The display control unit 11 refers to the graphic library 12 that is a screen creation tool, creates screen information based on the information from the arrow addition unit 10, and transmits the screen information to the display device 13. The graphic library 12 is used for each display device 1.
It is provided corresponding to 3.

[Action]

 FIG. 3 is an explanatory view of the operation of the present invention.

The state transition table shown in FIG. 9 is stored in the memory unit 6. Based on this, the transition number determination unit 2 creates a transition number table shown in FIG. 2 and stores it in the memory unit 7. On the other hand, the state number counting unit 5 knows that the number of states is “4”.

Next, the display position determination unit 4 determines the display position 131 of the state on the display screen 130 as shown in FIG. That is, first, the display information section 9 gives information about the size of the display screen 130 and the like. Based on this, the radius R,
A circle having a center O is defined, and four display areas 131 are located on the circumference of this one circle. Next, the circumference is equally divided by the number of states (in this case, equal to 4), and the distances between the display areas 131 are made equal. (When the number of states is n, each vertex of an n-sided polygon inscribed in a circle having a radius R is a display position.) Information (coordinates) about the display position is stored in the memory unit 8.

Next, the state placement determination unit 3 performs placement processing as shown in FIGS. 3 (B) to (D).

First, the state arrangement determination unit 3 refers to the table of the number of transitions in the memory unit 7, obtains the total number Si of transitions for each state, and selects one state having the maximum number. In this case, all are “4”, but the state a is selected. And state a is 4
The data is stored in the memory unit 8 so as to be associated with any one (or a predetermined) one of the three display positions 131. If this is shown as a screen, it becomes like FIG. 3 (B).

Next, referring again to the transition number table, the remaining states b,
From c and d, one state with the maximum number of transitions to the state a and one state with the next largest transition number are selected. In this case, the number of transitions between states a and b and the number of transitions between states a and c are both “2”, but state b is the maximum state, state c
Is selected as the next largest state. Then, the states b and c are associated with the adjacent display positions 131 in the clockwise direction and the counterclockwise direction (or the opposite direction) of the state a.
Similar to the above, this correspondence is stored in the memory unit 8 and the screen is as shown in FIG. 3 (C).

Next, the remaining state d and the display position 131 are associated with each other as shown in FIG. 3 (D), and the state arrangement is completed.

If the number of states is large, the process is continued as follows. That is, first, one state having the maximum number of transitions to the state b (referred to as state b ') is selected, and this is made to correspond to the adjacent display position of the state b. In this selection, the states a and c that have already been selected once are excluded from the target (the same applies hereinafter). Next, similarly, the state c ′ is made to correspond to the display position adjacent to the state c. After that, the same arrangement processing is performed in the order of the state b ′ side and the state c ′ side, and the process is repeated until the state disappears.

After that, the arrow adding unit 10 refers to the state transition table of the memory unit 6 and adds an arrow and an input. Then, when this is displayed on the screen, it becomes as shown in FIG.

According to the above processing, the ones having a large number of transitions (there are many arrows) are made to be adjacent to each other. As a result, as can be understood from the comparison between FIG. 3 (E) and FIG. 10, the intersections of the arrows indicating the state transitions can be reduced to make the state transitions easier to see. In particular, when the number of states is small, it is possible to eliminate the intersection of the arrows. Further, the arrangement of the states for these can be automatically determined, and the user is not burdened.

The dotted line in FIG. 3, the arrow indicating the radius R, the letters R and O are not displayed on the display screen 130.

〔Example〕

As an embodiment of the present invention, the data processing device shown in FIG. 1 will be described in detail.

First, determination of the number of transitions will be described with reference to FIGS. 4 and 5.

FIG. 4 is an explanatory diagram of the embodiment, and shows the configurations of the memory unit 6, the transition number determination unit 2, and the memory unit 7. In FIG. 4, 14 and 16 are address control units, 15 and 17 are read control units, 18 is a write control unit, 19 is an adder, and 20.
Numerals 28 to 28 are registers.

FIG. 5 is an explanatory view of the memory section, and in particular, FIG. 5 (A) shows an example of the state transition table stored in the memory section 6, and FIG.
(B) shows an example of a table of the number of transitions stored in the memory unit 7. The state transition table is as shown in Fig. 5 (A).
The number of states is 1 to n (n) and a ₁ to a _k (k) are input (input alphabet). The transition number determination unit 2 uses the state transition table of the memory unit 6 to determine the number of states n,
The number of inputs k is known and stored in the registers 20 and 21.

The address control unit 14 writes “0” as the number of transitions (initial value) to each address by setting the states 1 to n as X and Y addresses based on the number of states n as a table of the number of transitions in the memory unit 7. Create a stuff. The address control unit 14 also generates a two-dimensional (X and Y) address for reading the contents of the state transition table from the memory unit 6. This address generation is sequentially incremented in the X and Y directions to read the entire contents of the state transition table.

It is now assumed that the address control unit 14 generates an input alphabet a _i as an X address and a state j (hereinafter, such an address is described as (X, Y) = (a _i , j)) as an Y address. Addresses a _i and j are in registers 22 and 23
Stored in. The read control unit 15 accesses the state transition table of the memory unit 6 according to the contents of the registers 22 and 23 to read the contents of the address (a _i , j). This content indicates the state to be transited to next when the input alphabet a _i is input to the state j, and in this case, it is the state m. The read content (state m) is stored in the register 24.

Next, the address control unit 16 accesses the memory unit 7 using the contents of the registers 23 and 24.

The state (j) used for accessing the state transition table of the memory unit 6 and the read state (m) are used for generating the two-dimensional address of the memory unit 7. The address control unit 16 selects (X, Y) = (m, j) and (m, j) from the two states.
One address is sequentially generated and stored in the registers 25 and 26.

That is, first, the state m as an X address and the state j as a Y address are stored in the registers 25 and 26. Based on this, the read control unit 17 accesses the table of the number of transitions of the memory unit 7 and reads the content S _o of the address (m, j). The content S _o indicates the number of transitions between the states m and j, and in this case, the initial value “0”.
It is said that. The read content S _o is stored in the register 27. In response to this. The adder 19 adds the content “1” of the register 28 to the content (S _o ) of the register 27. Upon receiving this addition result (S _o +1), the write control unit 18
The original address (m,
Write the addition result in j).

Next, the states j as the X address and the state m as the Y address are stored in the registers 25 and 26. After that, the contents S of the address (j, m) are processed in the same manner as described above.
₁ (in this case, the initial value "0") is read, set as S ₁ +1 and rewritten to the same address.

A table of the number of transitions is created by repeating the above.

Next, determination of the display position will be described with reference to FIGS. 6 and 7.

FIG. 6 shows a display position determination flow.

FIG. 7 is a diagram for explaining the display position. Particularly, FIG. 7 (A) shows the display position on the screen, and FIG. 7 (B) shows the memory section 8.
3 shows an example of a layout table stored in the.

The coordinates (C _x , C _y ) of the center O of the circle on the screen and the radius R are determined mainly based on the size of the display screen 130. At this time, the X and Y coordinates are determined, for example, as shown in FIG. 7 (A).

Next, in order to display the states at equal intervals on the circumference according to the number of states n, Rad = 2π / n is obtained, and i = 0.

Using Rad and i, S and C are calculated according to a predetermined formula.

Using the center coordinates (C _x , C _y ) of the circle, the radius R, and the S and C, the coordinates of one point on the circumference of the circle according to a predetermined formula
_Find (X _{i + 1} , Y _{i + 1} ).

For example, when i = 0, s = 0 and c = 1, so (X ₁ ,
Y ₁ ) = (C _x , C _y -R).

Next, after i = i + 1, the above processes and are repeated while i is smaller than n. When i becomes n or more, the process is terminated. As a result, the coordinates (X ₁ , Y ₁ ) to (X _n , Y _n ) of _n points arranged at equal intervals on the circumference of the circle are obtained.

The display position determination unit 4 performs the above process and sequentially stores the coordinates obtained by the process in the memory unit 8. And
An area for storing the state corresponding to each coordinate is provided, and the arrangement table shown in FIG. 7 (B) is created.

In this embodiment, as shown in FIG. 7 (A), n coordinates (X ₁ , Y ₁ ) to (X _n , Y _n ) are used to draw a small circle around each of them. . This small circle is an area 131 for displaying the state shown in FIG. 3 on the screen. The size of the small circle is determined by the display information unit 9, for example.

Next, determination of the state arrangement will be described with reference to FIG.

FIG. 8 shows a state arrangement determination flow. The state arrangement determining unit 3 reserves n flag areas according to each of the n states and sets all flags to “0” (clear). When the flag is "0", it indicates that the arrangement has not been determined for the state corresponding to the flag, that is, that the arrangement table of the memory unit 8 has not input the corresponding coordinates.

The state allocation determining unit 3 obtains the total number Si of transitions for each state using the table of the number of transitions in the memory unit 7, and stores it in an appropriate storage area (for example, in the memory unit 7 as shown in FIG. 2). Hold)

After that, the state allocation determining unit 3 determines the total number S of flags and transitions.
The table of the number of transitions in the memory unit 7 (FIG. 5 (B)) is accessed using i or the like, and the following processing is performed.

A state in which the total number Si of transitions is the maximum (for example, state a) is selected from the states in which the corresponding flag is “0” (from the initial state to all states).

State a is assigned to the initial position (X ₁ , Y ₁ ). That is, the seventh
In the arrangement table of FIG. (B), the state a is associated with the coordinates (X ₁ , Y ₁ ).
Is entered. In response to this, the flag a corresponding to the state a is set to "1". When the flag is "1", it indicates that the arrangement of the corresponding state is completed.

From the states in which the corresponding flag is “0”, the state in which the number of transitions to and from the state a is the largest and the second largest is selected.
For this purpose, the table of the number of transitions in the memory unit 7 is accessed as an address (X, Y) = (Y _j , a) (where j = 1 to n). That is, the Y address is fixed to the state a, the X address is sequentially changed from the state 1 to the state n, and the access is performed.
The content (that is, the number of transitions between state a and each state) is read. Then, the states (for example, state b and state c) corresponding to the maximum and second largest transition numbers are selected, respectively.

The states b and c are respectively moved to the position (X
₂ and Y ₂ ) and the position (X _n , Y _n ) adjacent to the counterclockwise direction. In response to this, the flags b and c are set to "1".

It is determined whether all the flags are "1". When all the flags are "1", the processing is finished assuming that the assignment of all the states is finished.

From the states in which the corresponding flag is “0”, the state in which the number of transitions with the state b is the maximum is selected. For this purpose, the table of the number of transitions in the memory unit 7 is changed to the address (X,
Y) = (X _j , b) (where j = 1 to n)
Read its contents. Then, the state corresponding to the maximum number of transitions (for example, state b ′) is selected.

When the state b does not have a transition relation with states other than the state a, an arbitrary 1 is selected from a plurality of states in which the number of transitions is 0.
One will be chosen (as state b '). In such a case, assigning state b'to a position adjacent to state b is prohibited. The table of the number of transitions in the memory unit 7 is accessed as an address (X, Y) = (b ', b), and the content (that is, the number of transitions between states b and b') is read. When the read content is 0, the following processing is omitted for the above reason to prohibit the allocation of the state b ', and the processing is also omitted because at least one state (b') remains unallocated.

When the read content is not zero, assign the status b 'to the position of the clockwise neighboring state _{b (X 3, Y 3)} . Flag b'is "1"
It is said that

The same processing as the processing is performed.

The same process as the process for state c is performed, and the state having the maximum number of transitions with state c (for example, state c ′)
Select.

With respect to the relationship between the states c and c ′, the same processing as the processing is performed for the same reason, and the value of the number of transitions between the states c and c ′ is known.

When this value is 0, the following processing is omitted.

When the value is not 0, the state c'is assigned to the position (X _n-1 , Y _n-1 ) adjacent to the state c counterclockwise. Flag c'is "1"
It is said that

Since the processings b and c'are repeated, the processing targets are b'and c '.

Pay and refer again).

When either the number of transitions read by the process or is not 0, either the state b'or the state c'is assigned, so that the state is processed and / or processed.

When the number of transitions read by processing and is 0, states b and c
The following process is repeated for the states that have no transition relation with.

The same process as the process is performed.

If the state of the flag "0" remains, the process and the following are repeated for that state. States b'and c'are also left as targets.

With the above, the determination of the state arrangement is completed.

As can be understood from the processing, when there is no transition relationship between the unallocated state and the two most recently arranged states, the total number Si of transitions is the maximum among the unallocated states. Is selected. And this state is
It is arranged at both ends or the center of the remaining arrangement position. After this,
Processing The following is performed.

The arrow addition unit 10 adds an arrow between each state and adds an input to this to complete the state transition diagram.

When a certain state has an arrow that returns to itself due to an input, the number of transitions by this arrow may not be included in the calculation of the total number Si of transitions. The arrow is displayed outside the circle of radius R.

〔The invention's effect〕

As described above, according to the present invention, the number of transitions is obtained and used in the state transition diagram display processing method that graphically shows the relationship between states based on the state transition table (or function). This makes it possible to obtain a state transition diagram in which the states having a large number of transitions are adjacent to each other and the states having a small number of transitions are not adjacent to each other to reduce the intersection of the arrows indicating the state transitions to make it easier to see. The efficiency of circuit design and analysis can be improved.

[Brief description of drawings]

FIG. 1 is a block diagram of the principle of the present invention, FIG. 2 is a diagram showing a table of the number of transitions, FIG. 3 is an operation explanatory diagram of the present invention, FIG. 4 is an explanatory diagram of an embodiment, and FIG. FIG. 6, FIG. 6 is a diagram showing a display position determination flow, FIG. 7 is a display position explanatory diagram, FIG. 8 is a diagram showing an arrangement position determination flow, FIG. 9 is a diagram showing a state transition table, and FIG. 1 is a processing device including a central processing unit and a memory, 2 is a transition number determination unit, 3 is a state arrangement determination unit, 4 is a display position determination unit,
Reference numeral 5 is a state number counting unit, 6 to 8 are memory units, 9 is a display information unit, 10 is an arrow addition unit, 11 is a display control unit, and 12 is a display control unit.
Is a graphic library, and 13 is a display device.

Claims (1)

[Claims] 1. A transition number determination processing unit (2) for obtaining the number of mutual transitions between the state and another state for each of a plurality of states and storing the number in a memory, and a circle according to the number of the states. A display position determination processing unit (4) for determining a display position on the circumference, and a state arrangement determination processing unit (3) for determining the arrangement position by associating the state with the display position, the state arrangement determination The processing unit (3) secures a flag area indicating whether or not the arrangement position of the state is determined corresponding to each state on the memory, and the maximum number of transitions among the number of transitions of each area stored in the memory. Is selected first and assigned to the initial display position, and the flag of the selected state is changed to the determined state, and thereafter, the unselected remaining state in which the flag indicates that the placement is undecided Has a transition relation with the determined state in The two states having the maximum and the next largest number of transitions are selected, and the two states are respectively assigned to adjacent display positions on both sides of the display position of the previously selected state, and the two selected states are selected. Change the state flag to the determined state, and thereafter have a transition relationship with the state determined immediately before among the remaining display position undetermined states, and select the state with the largest number of transitions sequentially, State transition diagram display processing method characterized by processing so as to determine the display position in the direction of the display position where the state display has not been determined.