数理解析研究所講究録 1325 巻 2003 年 152-157

152
表編集のアルゴリズム
本橋友江

谷聖一

関東学院大学工学部

日本大学文理学部

土田賢省

夜久竹夫

東洋大学工学部

日本大学文理学部

Algorithms for Thble Transformation
Tomoe Motohashi, Kanto Gakuin University
Sei’ichi Tani, Nihon University
Kensei Tsuchida, Toyo University
andTakeo Yaku, Nihon University
Abstract:
Tables with heterogeneous cells are commonly used in computer human interface
and documentation. We proposed an attribute multi edge graph representation fortables that considers editing and drawing in [7]. In this paper, we give algorithms
for basic operations in table editing.
We provide acell unification algorithm that runs in $O(1)$ time. We also provide aheterogenious tables.
column insertion algorithm that runs in $O(n+m)$ , for$O(\sqrt{N})$ time for $N=n\mathrm{x}n$runsinalgorithm
It is noted that the column insertion
cell square tables. while known methods require $O(N)$ time$n\mathrm{x}m$

Keywords: Data structures and algorithms, graphs, table interface

1Introduction
In this PaPer, we deal with the representation of tables while considering editing and drawing.
Several representation methods have been proposed for tables: rectangular duals of planar graphs[1], and quadtrees [3]. Although, we do not know which representation method is used in present
table processing systems.
In this Paper, we considers another graph representation [7] for tables, in which the table
editing is executed efficiently. For drawing and editing problems, see $[4, 5]$ .
.This paper partly appeared in our previous study Tomoe Motohashi, Kensei Tsuchida and T. Yaku, Algorithm
on attribute graphs for table editing, The 3rd Hungarian-Japanese Sumpos. Discrete Math. &Its Appl. and [6]153

Figure 1:$\mathrm{A}$:ATabular Diagram$D_{1}$$\mathrm{B}$:ATabular Diagram$D_{1p}$In Section 2, we propose arepresentation of tables by an attribute multi edge graph. Several
properties of the graphs are shown. In Section 3, we show several algorithms that execute table
editing based on the representation. We provide algorithms for unifying cells, changing column
width, and insertion column. Section 4provides conclusions.

2ATTRIBUTE GRAPHS FOR TABLES
We described several definitions concerning tables in [7]. We represent atable by acertain typeof tabular diagram satisfying Condition 2.1 in [7]. That is, the tabular diagrams have perimeter
cells.
Example 2.1 Figure 1A illustrates atabular diagram $D_{1}=(T_{1}, P_{1},g_{1})$ , where $P_{1}=$. Agrid$\{\{(1,1), (2,1)\}, \{(1,2)\}, \{(1,3)\}, \{(2,2), (2,3)\}\}$ is apartition over a $(2, 3)$ table$g_{1\mathrm{c}olumn}(0)=0$, column (1) $=2$ ,is defined icy $g_{1\mathrm{r}ow}(0)=0,g_{1tow}(1)=1$ , $g_{1row}(2)=2$ , and$g_{1\mathrm{c}olumn}(2)=4$ , and $g_{1column}(3)=6$ .
For acell $c=\{(2,2), (2, 3)\}$ , we define the north wall$nw(c)=g_{1row}(1)=1$ , south wall $sw(c)=g_{1row}(2)=2$ , east wall $ew(c)=g_{1column}(3)=6$ , andwith perimeterwest wall $.ww(c)=g_{1column}(1)=2$ . Figure 1B illustrates atabular diagram.
cells. For the table drawing, it corresponds toThen,
we show how to represent atabular diagram
Now, we introduce an attribute graph.
as an attribute graph.
Definition 2.1 An attribute graph is a6-tuple $G=(V, E,L,\lambda, A, \alpha)$ , where$(V, E)$ is amulti-edge undirected graph,is the set of labels for edges, A: $Earrow L$ is the label
function, is the set of attributes, and : $Varrow A$ is the attribute map.
Atabular diagram $D=(T, P,g)$ is represented as an attribute graph, whereis identified by apartition $P$ (we denote anode coraperimeter node (resp. inner $nde$ ) if isby , we call
responding to acell inis defined by Rules 1\sim 4, $L=$ {enrn, $esw$ , eern, $eww$ },aperimeter cell (resp. inner cell) ,are defined by:: $E_{D}arrow L$ is defined by Rules 1-4, $A=R^{4}$ , and$T_{1}$$g_{1}$$D_{1p}$$D_{1}$$L$$A$$\alpha$$G_{D}=(\mathrm{V}, E_{D},L, \lambda_{D}, A, \alpha_{D})$

$P$

$c$

$V_{D}$$)$$\lambda_{D}$$c$$v_{c}$$v_{c}$$E_{D}$$\alpha D$$V_{D}arrow R^{4}$$\alpha D(v_{c})=$$(nw(c), sw(c),ew(c),ww(c))$ .

Rule 1If $nw(c)=nw(d)$ and there is no cell between and having an equal north wall,is called anorth wall edge.
and $\lambda_{D}[v_{c}, v_{d}]=enw$ . In this case,thenis in
Similarly, Rules 2, 3and 4define the south wall, east wall, and west wall edges, respectively.
of each node
An attribute graphis called atessellation graph. Note that the degreeinis at most 8. The location vlues of the inner cells are evaluated from the location valuesof perimeter cells and linked edges. So, we assume in the latter part of this paper, that thevalues of the inner cells are null.
Note that we consider tabular diagrams with perimeter cells. Then$c$$[v_{\mathrm{C}}, vd]$

$E_{D}$$G_{D}$$v$$d$$[v_{\mathrm{C}}, v_{d}]$$\# v$$G_{D}$$\alpha D$

154
Figure 2: Tabular Diagram and Its Corresponding Tessellation Graph

Figure 3: Change of Vertical Edges of$v_{d}$

be a tessellation gmph for a tabular diagram $D$ of an $(n, m)-table$ .
Proposition 2.1 Let, we haveof edges in. For the number
Let be the number of inner cells in$2\# E_{D}=6(2n-4)+6(2m-4)+8k+16$ .
$G_{D}$$G_{D}$$\# E_{D}$$G_{D}$$k$

3ALGORITHMS
This section provides algorithms for tessellation graphs. The following algorithm execute unification of two adjacent inner cells in the tabular diagram.

ALGORITHM
INPUT$\mathrm{U}\mathrm{N}1\mathrm{F}\mathrm{Y}\mathrm{C}\mathrm{E}\mathrm{L}\mathrm{L}\mathrm{S}(G_{D}, v_{c}, v_{d}, G_{E})$: atessellation graph for a tabular diagram $D$ , : anode incorresponding to an inner cell which is: anode incorresponding to an inner cell ,adjacent to the south wall of that is $ww(c)=ww(d)$ , $ew(c)=ew(d)$ , $sw(c)=nw(d)$ .
OUTPUT: atessellation graph for atabular diagram , where is obtaind$D$ by the unification of cells
and to .
from$G_{D}=(V_{D}, E_{D}, L, \lambda_{D}, A, \alpha_{D})$$G_{D}$$v_{\mathrm{c}}$

$c$

$d$

$G_{D}$

$vd$

$c$

$E$

$G_{E}=(V_{E}, E_{E}, L, \lambda_{E}, A, \alpha_{E})$

$d$

$c$

METHOD
begin
Initially let$F_{\lrcorner}$$c$;of vertical edges concerning to $d*/$
from
and:
delete two vertical edges between;
and toadd edges between;
put; (Seeand fromdelete two vertical edges between$c*/$of south wall edges concerning tochoose two nodes and $f’(f\neq f’)$ such that;
anddelete south wall edges$\lambda_{E}[f,f’]arrow esw$ ;add an edge $[f,f’]$ to $E’E$ and putof south wall edge concerning to $d*/$$G_{E}arrow$ $G_{D}$$/*\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}$$v_{d}$$a$$v_{c}$$E_{E}$$a(\neq v_{\mathrm{c}})$$E_{E}$$\lambda_{E}[v_{c}, a]arrow\lambda_{D}[v_{d}, a]$$v_{c}$$v_{d}$$E_{E}$$\mathrm{F}\mathrm{i}\mathrm{g}.3$)$/*\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}$$\lambda_{D}[f, v_{\mathrm{r}}]=\lambda_{D}[\uparrow)_{\mathrm{C}}, f’]=esw$$f$$[f, v_{c}]$$/*\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}$$[\iota_{\mathrm{c}}" f’]$;

155
choose two nodes and $h’(h\neq h’)$ such that;
delete south wall edges $[h, vd]$ andput
and
toand
add, $\lambda[v_{c}, h’]arrow esw$ ;$d*/$of north wall edges concerning tochoose two nodes and $g’(g\neq g’)$ such that $\lambda_{D}[g, v_{d}]=\lambda_{D}[v_{d},g’]=enw$ ;;delete north wall edges $[g, vd]$ and $[v_{d},g’]$ from$\lambda_{E}[g,g’]arrowerrw$;
and put
add an edge $[g,g’]$ todelete anode$\lambda_{D}[h, v_{d}]=\lambda_{D}[v_{d}, h’]=esw$$h$;$[v_{d}, h’]$$[h, v_{c}]$$\lambda_{E}[h, v_{c}]arrow esw$

$E_{E}$$[v_{\mathrm{c}}, h’]$$/*\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}$$g$$E_{E}$$E_{E}$$d$end.
be a tabular diagram, and be a cell in D. Suppose that there is an
Theorem 3.1 Let
adjacent cell at sovth side in such that $ew(c)=ew(d)$ , $ww(c)=ww(d)$ and $sw(c)=nw(d)$ .
Let $E$ be a tabular diagram obtained from $D$ by the unification of cells and to . Letinis obtained frombe the tessellation graphs for $D$ and $E$ , respectively. Thenandconstant time.
$D$

$c$

$D$

$d$

$c$

$d$

$c$

$G_{D}$$G_{E}$$G_{E}$$G_{D}$

Theorem 3.2 Let $D$ be a tabular diagram, and be an inner cell in D. Let be a movement
value. Suppose $\Delta+\delta>0_{f}$ where $\Delta>0$ is the width of a perimeter cell in the column which
has equal east wall to . Let $E$ be a tabular diagram obtained from $D$ by the changing width
be the tessellation graphs
andusing of cells that have the equal east wall for . Let$O(n+m)$time by the algorithm
inis obtained fromfor $D$ and respectively. Then$D$
CHANGECOLUMNWIDTH , where is the number of rows in .
$\delta$$c$$c$$G_{D}$$G_{E}$$E_{f}$$G_{E}$$G_{D}$$c$$\delta$$n$$[\delta]$

The following algorithm executes insertion of acolumn at the west side of afocused cell into
the tabular diagram.
ALGORITHM INSERTCOLUMN $(GD,vc’ GE)$INPUT

corresponding: atessellation graph for atabular diagram $D=(T, P,g)$ , : anode in,exists.
ofwest-sideatthelocatedto acell , where the cell, that is adjacently
OUTPUTby insertionis atabular diagram obtained from: atessellation graph for , wherecell in theaperimeterofwidththeisof acolumn with width at the west side of , wherecolumn including .
METHOD
begin
Initially, put $G_{E}arrow G_{D}$ ;until aperin eter node ’(see Fig.5) ;traverse upward through the west wall edges from;let be the width of the cell corresponding to;
add anode;putacolumn $*/$
while anode :is not the lowermost node do begin
be an adjacently west-side node linked to :by anorth wall edge ;letdelete the north wall edge between :and ;;add anorth wall edge between :andsimilarly for asouth wall edge ;deform

$G_{D}$$G_{D}$$v_{c}$

$c$

$c$

$E$

$G_{E}$$D$$F_{\lrcorner}$$\delta$$\delta$$c$$c$$v_{c}$$\delta$$v\mathit{0}$$u\mathit{0}$$iarrow$$0$$/*\mathrm{i}\mathrm{n}\mathrm{s}\mathrm{e}\mathrm{r}\mathrm{t}$

$v$

$v$

$w_{\dot{l}}$

$w$

$w$

$G_{E}$$v_{i}$$u_{\dot{1}}$$\iota_{0}$156

Figure 4: Insertion of the Column at the West-Side of

add anorth wall edge and south wall edge between :and
let $v:+1$ be alower node linked to by awest wall edge ;add anode . ;andadd awest wall edge and east wall edge between
$u$

$vj$;

$u_{i+1}$;$c$$v_{i}$$u_{\+1}$$u_{i}$$iarrow i+1$

end ;(see Fig.6)
for the lowermost node , similarly for the noth and south wall edge;
deformexisting column shifts to the eastbe the uppermost node in ui’s ;letbe adjacently west-side node linked to the node in the northeast corner inlet$G_{E}$$v_{i}$$*/$$/*\mathrm{t}\mathrm{h}\mathrm{e}$$u\mathit{0}$$G_{E}$$v_{x}$

put $G_{R}arrow G_{E;}$

CHANGECOLUMNWIDTH$(G_{R},v_{x},\delta,G_{E})$

;

;

put;
be anode adjacently west-side oflet
put $iarrow 0$ ;while $ww(u_{0})\leq ww(x_{i})$ do begin;
let $x:+1$ be an adjacently west-side node linked to :by anorth wall edge ;put $iarrow i+1$ ;end ;put $G_{E}arrow G_{E:}$$G_{E_{0}}arrow G_{E;}$$v_{oe}$$x_{0}$$\mathrm{M}\mathrm{o}\mathrm{V}\mathrm{E}\mathrm{E}\mathrm{A}\mathrm{S}\mathrm{T}\mathrm{W}\mathrm{A}\mathrm{L}\mathrm{L}(G_{E}, x_{i}, \delta, G_{E}.):+1$

$x$

end.
is thebe a tabular diagram, and be a cell in D. Suppose thatTheorem 3.3 Let
by insertion of a column with width 6at the west side of thetabular diagram obtained frvym
column including where is the width of a perimeter cell of the column including . Letin
is obtained fromand , respectively. Thenbe the tessellation graphs forand$D$ , respectively.
incolumnsrows
andnumberaretheand$O(n+m)$ time, whereof
$D$

$E$

$c$

$D$

$c$

$\delta$$G_{D}$$c_{J}$$D$$G_{E}$$n$$E$$G_{E}$$G_{D}$$m$

It is noted that the column insertion algorithm runs in $O(\sqrt{N})$ time for $N=n\mathrm{x}n$ cellsquare diagrams, while known methods require $O(N)$ time. The following table illustrates thefeatures of representation methods for $N$ cell square tables with respect to the column insertion157 157

4CONCLUSION
that,
We introduced attribute graphs and algorithms for table drawing and editing. We note
we have determined the necessary and sufficient condition where an attribute graph represents
atabular diagram by agraph grammar. [9]. We are designing aprocessing system for table
editing based on our model in [8].
The authors thank to Prof. Tominaga of Tokyo University of Technology for valuable discussionwith him.

References[1] K. KOZMINSKI, E. KINNEN, Rectangular Duals of Planar Graphs, Networks 15 (1985)

145-157.
[2] FRANZ J. BRANDENBURG, Designing Graph Drawings by Layout Graph Grammers, Proc.
Graph Dra wing ’94, LNCS 894 (1994) 416-427.
[3] M. DE BERG, M.VAN KREVELD, M. oVERMATS AND O. SCHWARZKOPH, Computational
Geometry -Algorithms and Applications, Springer (1997)[4] T. ARITA, K. TSUCHIDA, T. YAKU ET. AL. ’ Syntactic proccessing of diagrams by graphgrammers, Proc. IFIP World Computer Congress ICS2000(2000) $145- 151$ .
[5] A. AMANO, N. ASADA, T. MOTOYAMA, T. SUMIYOSHI, K. Suzuki, Table Form Document Systhesis by Grammar-Based Structure Analysis, -th Internal Conference on Document Analysis and Recognition (ICDAR) (2001) 533-537$\theta$[6] T. MOTOHASHI, K. Tsuchida, T. Yaku, Attribute Graphs and Their Algorithms for
Table Interface, TECHNICAL REPORT OF IEICE SS2002-1 (2002).
[7] T. MOTOHASHI, K. TsucHlDA, T. Yaku, Proc. Attribute Graphs for Tables and Their近代科学社)
Algorithms, fose 2002 (2002), (井上克郎編、 ソフトウエア工学の基礎 IX、$\backslash$

183-186.

[8] T. KIRISHIMA, T. MOTOHASHI, K. TsucHlDA, T. Yaku, Attribute Graph for Table andTheir Applications, Proc. IASTED International Conference on Software Engineering andApplications SEA 2002 (2002), 317- 322.
[9] T. KIRISHIMA, T. ARITA, T. MOTOHASHI, K. TSUCHIDA AND T. Yaku, Syntax forTables, Proc. IASTED International Conference on Applied Info rmatics AI 2003 (2003),to appear