Hypergraph-based Object-oriented Model  for GIS Application
                    Jin ZHANG                                                                   Jianya GONG
         Dep. Of Surveying and Geomatics                        National Key Laboratory of LIESMARS
         Taiyuan University of Technology                                        Wuhan University 
          Taiyuan 030024, P.R. China                                           Wuhan 430079, P.R. China
        E-mail: zhangjin@public.ty.sx.cn                              jgong@geoc.rcgis.wutsm.edu.cn
Abstract: This paper discusses the features and relevant theories of GIS spatial data model based on hypergraph and Object-Oriented. The integrated concept model based on hypergraph and Object-Oriented model (HOOM) is proposed by author. HOOM has many advantages, such as its semantics features, its visualizing relationship among spatial objects or classes, and solving the general drawback of HBDS(Hypergraph based data structure),namely lacking math analyzing methods or theories. The principal contribution of this paper is that we study the K-section and other theories of Hypergraph.  According to research results, we can find that the K-section can simplify relationships between feature classes or objects. The representation graph of Hypergraph can help transforming the viewpoint between the feature object and feature object relationship. Viz. the feature object relationship is transformed as a feature object and the feature object as a kind of relationship. An application example using HOOM is given at the end.of the paper.
Key words: Hypergraph    Object-oriented     GIS Spatial data model        HBDS       DEM

1.	Introduction
With the developments of geomatics theories and applications, some GIS systems whose spatial data models are based on geo-relation or layer model are facing with great challenges. The GIS is used in many areas, where exist many theory problems, such as, the dynamic management of huge GIS data, the automatic generalization of GIS spatial entities and features, temporal GIS model and vector-raster integrating model, etc. All of these problems are concerned with GIS spatial model. General speaking, traditional GIS spatial model exists following primary problems[Jin ZHANG,1998a]:

    . GIS model and application used Object-oriented model and approaches are very popular in recent years, Object-oriented model and approache is one of the general method, which are lacking spatial relationship guideline in modeling spatial entities and features.
. Attributive data or thematic data and spatial data are mostly only an ID relation. 

To solve above problem, we use hypergraph data model and Object –oriented model and approaches to define spatial entities and features, called HOOM. Hypergraph model and hypergraph data structure inherite the characteristics of object model. Depending on hypergraph model, complex and composite spatial relations can be described more easily; spatial 、attributive and temporal data also can be integrated more efficiently[Jin ZHANG,1998b]. Object-orient model and approaches are used to realize above perceptions. 

2.	GIS spatial data model theories
The GIS spatial entities and features can be viewed in three abstractive levels: spatial concepts, spatial data models, and spatial data structures [E. Lynn Usery, 1996]. 

Cognizing and organizing spatial entities and features we form GIS spatial concepts, such as spatial concepts feature-based and geo-relationship-based. Formalization of the spatial concepts leads to spatial data models. The most frequent spatial formalization for geographic phenomena is based on the Euclidean geometry and geo-relationship. Frequently, the spatial data model is used to refer to the combination of spatial and nonspatial or thematic data. The formalization includes the basic elements of the spatial concepts such as the point, line, area, polygon, volume, and pixel and attributes of these objects, such as location in some spatial reference system and their interrelations, such as topology.

3. HBDS
HBDS (Hypergraph-based data structure) [F. Bouille, 1978,1994a, 1994b, 1994c] is a general model, which has been used for building an integrated object oriented platform, as a kernel of GIS. It is a knowledge model based on six basic abstract data type: class, attribute of class, link between classes, object, attribute of object, and link between objects, with some extensions. Hyperclass, hyperattribute, hyperlink, embryo, prototype, and all structure types are implicitly persistent. These types have a graphical representation allowing an ease and immediate understanding of the real world and provide a convenient communication between geographers.

HBDS makes it easy and immediate to understand the real world and provide a convenient communication between geographers, but no suitable algorithm for HBDS. Especially, in HBDS, nobody try to apply hypergraph  theory in HBDS. This paper will do so. 

The concept of attribution in hypergraph spatial data model has many meanings. It may be following items: (1)  a number; (2)  a N-dimension array; (3) the program or law; (4) a structure that can be described by hypergraph data model. Therefore attribution described not only the static character of object, but also the dynamic character of object. Hypergraph class and object have many relations, such as hierarchical structure and non-hierarchical structure. The hierarchical structure among hypergraph class shows class inheritance, association, and aggregation very clearly. The non-hierarchical structure is the base of distributed calculating and object generalization.  

One of the major advantages of HBDS is the generalization of graph theory[ Rongxing LI,1995]. The vertices may be complicated objects themselves (they may even be graph), and the edges of a hypergraph represent relationship among subsets of vertices. Therefore, in a HBDS the connections between objects in the same set and between classes of objects are allowed with both hierarchical and nonhierarchical relationship. When used for modeling, a hypergraph usually has objects with common attributes in the same substructures. Objects in a substructure might have relationship among themselves and relationships with objects outside. At one level, for example, internal relationships are not visible. Relationships with outside objects appear as hyperlinks. Basically, relationships between any objects at any levels can be expressed. Whether an object should be placed at a higher level or a lower level depends on significant factors to be considered, such as efficiency of data retrieval. All of these are only spatial data organizations. 

 4.HOOM[Jin ZHANG,1998a,1998b]
HOOM stands for Hypergraph-based GIS spatial data model(in Fig.1). HOOM has similar semantics with Object-Oriented model. To define hypergraph spatial data model, first, we must define the class and object of hypergraph spatial data model. According to Object-oriented model and the characteristics of hypergraph, complex and composite spatial world can be defined as follow:

4.1 Geometrical object model
Geometrical object model only describes the geometrical characteristics of spatial entity and feature. It describes the shape of feature, spatial location relation, spatial topologic relation, and geometrical measure information. Geometrical object can be divided to node, arc, polygon or pixel, and voxel.

                                                         GIS spatial model

       Geometrical object model       Feature Object model          Represent model      Temporal model 

                                             Point                        Line                        polygon                     complex

         Point            Arc segment         Polygon                Raster coding geometrical object

                                                                                                   Quadrtree polygon
                                                  
 Arc             Line            Polyline        Triangle        Quadrangle        Quadrtree node  quadrtree Arc
                                 Fig. 1  hypergraph Object spatial data model

4.2 Feature object model
Feature object model is used to explain the geometrical object model. In other words, Feature object model is defined by adding attributive values to geometrical object. So the same geometrical object may have different geographical attribution because different attributive value is added to the geometrical object. Feature object class is divided into point feature, line feature, polygon feature, and complex feature. The spatial relation of feature object is derived from its relevant geometrical object.

4.3 Spatial representative object model
GIS spatial representative object model is divided to physical and logical representation.   Physical representative model represents GIS distributed characteristics and operating, and physical storage. GIS distributed operating may produce many problems, such as concurrence control and consistence handle. To solve GIS distributed operating, we must add distributed ID label to geometrical and geographical object. 
GIS logic representation means that we usually need to calculate and draw thematic map from GIS spatial database and attributive database according to the certain conditions and formats. Also we need to manage and query GIS spatial data and attributive data according to the demands of applications. The association functions are used to associate the graphic object and geographical object. 

The main goal that we abstract the graphic class is facility in multi-scale map generalization. Main methods are:
Define dynamic association: The simplest rule that defines dynamic association is that from small to great for a given group discrete scales, scale1, scale2,..., scalen defining follow scale rules, when scale pertains to the scale extend (scalei,scalej), geographical objects are associated with the graphical objects according to the association attributes and association functions. It is not displayed when the association graphics are null. The more complex rules that define dynamic association are establishing map generalization rules and multi-scale and multi-resolution rules on feature objects.
Define the display rules: (1) define the display order. Such as first display polygon feature, then line feature, finally point feature, etc. (2) When the extend of graphics is smaller than the given extend, the graphics are not displayed. (3) Symbolization rules. (4) Map generalization rules. 

4.4 Temporal object model   Both GIS spatial data and attributive data have temporal characteristics. Without time stamping GIS data cannot be used efficiently. Stamping version information in a feature object is a good method. 

The typical data abstract technology of Object-oriented is classification, generalization, association, and aggregation. The characteristics of Object-oriented are that they have abstraction, inheritance, and polymorphism. We can use these characteristics to realize our goal [Alfons Kemper, 1994 and R. J. A. Buhr, 1996]. The typical relationship of objects or classes in Object-oriented model are 'is a' , 'part of' , 'member of' and  'instance of'. Also based on feature GIS Object-oriented model we can model the feature relationship, such as: is a ,a kind of, a instance of ,a member of , a part of , composed of, inflow from, outflow to, connected to, vertically related to, bounded by, bounds, within, contains etc; temporal relationship： before , after, at, between etc.
The spatial data in the hypergraph-based Object-Oriented model can link an attributive class of hypergraph, such as, geometrical object links feature object model. This is a very important character for modeling GIS spatial phenomena. We can label hypergraph class according to the feature of class, such as road, road segment, the grade of road, etc. 

5. Hypergrpah theory
Hypergraph [ C. Berge,1989] are the theoretical basis of hypergraph spatial data model. Hypergraph expands the graph theory. In general graph, edge set is defined duality elements of vertex set. But in hypergraph, edge set is defined any of elements of vertex set and is closed by Jordan curve.
 Let X={x1, x2, …, xn} be a finite set, and let =(Ei / iI) be a family of subsets of X. The family  is said a hypergraph on X if Ei   ( represents null set) and Ei=X, iI. The couple H=(X, ) is called a hypergraph. |X|=n is called the order of this hypergraph. The elements x1, x2, …, xn are called the vertices and the sets E1, E2, …, Em are called the edges.

In a hypergraph, an edge Ei with |Ei|>2 is drawn as a curve encircling all the vertices of Ei. An edge Ei with |Ei|=2 is drawn as a curve connecting its two vertices. An edge Ei with |Ei|=1 is drawn as a loop in a graph. Two vertices are said to be adjacent if there is an edge Ei that contains both of these vertices. Two edges are said to be adjacent if their intersection is not empty.

The incidence matrix of hypergraph H=(X, ) is a matrix ((aji )) with m rows that represent the edges of H and n columns that represent the vertices of H, such that
                        aji=1    if  xj  Ei
                        aji=0    if  xj  Ei
Each (0,1)-matrix is the incidence matrix of hypergraph if no row or column contains only zeros.

                                  E1
                                                               x4                                                     x6
                              x1                                                                        E4
 
                                                                          E3                      x5
                     x2       E2
                                                    x3
                                                                                                                        E5
                                                                                                                                 x7     
Fig.2              A hypergraph with 7 vertices and 5 edges
To each hypergraph H=(X; E1, E2, ..., Em) there corresponds a hypergraph H*=(E;X1, X2,..., Xn) whose vertices are points e1,e2,...,em ( that respectively represent E1, E2, ..., Em) and whose edges are sets X1, X2,..., Xn (that respectively represent x1, x2, ..., xn) where, for all j, Xj={ei / im, Ei  xj}. Hypergraph H* is called the dual hypergraph of H.The incidence matrix of hypergraph H* is the transpose of the incidence matrix ((aij)) of hypergraph H.

Hypergraph generates relevant concepts and algorithms, such as K-section, transversal of a hypergraph, representative graph of a hypergraph.

5.1. K-section of hypergraph
Given an integer k>0, the K-section of hypergraph H=(X, ) is defined to be the couple  Hk =(X,k), formed by X and the set:
     k ={F / F X; 1|F|k; F Ei,  for some Ei}
Hk is still a hypergraph. Its vertex set is X, but its edge set changes to not exceed number of k point. The 2-section H2 of a hypergraph H is a graph with the same vertices as H and with a loop attached to each vertex. The 2-section without loops is useful for GIS automatic generalization GIS spatial object. Fig3 is the 2-section without loops of Fig.2
                     x1
             E1                                                  x4                           E7                 x6
                                 E2       E4
             x2                                                              E6
                    E3                  x3                                             x5      
                                                                 E5                                                    x7
Fig.3   2-section without loops of Fig.2             E8

5.2 Transversal of hypergraph
It defined as: For known Hk =(X,k), Let TX, X is original vertex set of hypergraph. If T has TEi(At least it include one point to each edge) to all im, here T is called the transversal of hypergraph. In fact, the transversal of hypergraph is part of vertex set. This represents a spatial transverse relation in GIS model.

5.3 Representative graph of hypergraph
Let H=(E; X1, X2, ...,Xn), be a hypergraph with n edges. The representative graph H is defined to be the simple graph G=L(H) of order n whose vertices x1, x2,... xn respectively represent the edges X1, X2, ...,Xn  of H and with vertices xi and xj joined by an edge if, and only if, Xi Xj . This new graph G is called representative graph of hypergraph H. The graph G represents the edge relationships of H. In GIS model, representative graph of hypergraph gives us good ability to analyze complex spatial relations.

G=L(H) means that vertices xi and xj are adjacent if , and only if, there exists in H,  a vertex ekxixj. This is also equivalent to saying that there exists an edge Ek in H* that contains both xi and xj, or to saying that G=(H*)2.
According to basic research we can get following conclusions. To analyze and simplify the basic relationships we can use K-section and representative graph of hypergraph. Representative graph of hypergraph represent major dependent relationship between edges of hypergraph. K-section make us analyzing the relationships hierarchically. The dual hypergraph algorithm is important for analyzing dependent relationships between the vertices and edges. That is if in hypergraph vertices represent spatial geometrical objects and attributes and edges represent the relationship between objects, then the hypergraph represents the objects and attributes of the relationship dependence and association. But the dual hypergrpah reverses these associations. It represents the relationships of objects and attributes of dependence and association. In whether or not display spatial object depending on constrain conditions we can fully utilize this dual hypergraph algorithm.
6. Applying Hypergraph Theory in HOOM
No references introduced how to transform between hypergraph and HBDS or HOOM. Ostensibly, Hypergraph is different from HOOM in visualizing. But it is only different in vision. In Fig.2, if we take E3 as the root of HOOM, then in HOOM visualizing mode, Fig.2 can visualize as Fig.4 (Hypergraph edge as class of HOOM, vertices as member of class. Link relationship exists among vertices.
                                                         Hypergraph E3
                                                           x3   x4    x5  
                                                                                               link relationship
                  Hypergraph E2          Hypergraph E4         Hypergraph E5
                         x1                                                                
                                            Constrained Relationship between Vertices
                    Hypergraph E1
•	                                    
Fig.4  The HOOM mode of Hypergraph
Also we can take the vertices of hypergraph as the class of HOOM and edges as constrained relationship. 
Once we established the transformation relationship between hypergraph and HBDS or HOOM, we can use the algorithm of hypergraph simplify or analyze  the feature relationship. We think it is important for GIS spatial calculation.

7. Attributed Hypergraph(AHG)
The AHG is a representation which groups model components into hyperedges based on various structural or relational properties. The resulting model is flexible and can be easily modified. It can be used to facilitate the interpretation and the search procedures associated with knowledge synthesis[12]. The AHG knowledge representation has several important advantages. While being a local representation, it handles various levels of relationships and abstractions.
Definition 1: An attributed graph (AG) is a graph Ga = (Va;Aa) where Va ={ v1; …; vp;… ; vq;…; vm} is an attributed vertex set and Aa = {…; apq;…} is an attributed edge set. The edge apq connects vertices vp and vq. Directed edges are called arcs.
Definition 2: An attributed hypergraph (AHG) Ha = (Xa;Ea) consists of a set of attributed vertices Xa and a set of attributed hyperedges Ea. The attributes of the vertices are similar to those of attributed graphs. The attributes of a hyperedge are mappings from its set of vertices into a range which provides a description of the set. The range can be (i) an AG defined on the vertex set, (ii) a set of nominal or ordinal values or (iii) a geometrical configuration of that set.
Definition 3: An edge in an attributed hypergraph is called an attributed hyperedge. The attributes of the hyperedge are mappings that maps the set of vertices of the hyperedge into a range which provides a description of the set. The range can be: (i) an attributed graph defined on the vertex set (ii) a set of nominal or ordinal values (iii) a geometrical configuration of the set or (iv) any other desirable representation.
A  AHG can be efficiently used to find a subgraph of all traversable regions. Fig5 to Fig.7 represents the traversable of DEM. This feature may not be represented in other models. The terrain features, such as, peak, pit, saddle etc.  are very important for constructing the DEM. But when we use DEM, terrain feature relation, such as, traversable and connection are also important. We use AHG represent these relations.. 

8.An example
    Here give an example of using hypergraph to describe the terrain feature.

Fig.5   DEM and its Contour Map[Fayek and Wong,1996]
Fig.6     Terrain Feature 

                                       Fig.7 Hypergraph Representation of Terrain Feature

8. Conclusion and suggestion

Using hypergraph model people can design many GIS application systems such as, Urban integrated information system, Decision support system of region sustainable development [Weihong CUI, 1995]; etc. But we didn’t pay enough attention to hypergraph theory. Hypergraph theory can be used in data organization of multi-scale or multi-resolutions. Because the lack of studying hypergraph theory, we only used the characteristics of Object-Oriented. Of course this is one of our primary studying direction next step. 
9. Acknowledgements
This paper is Funded By WKL(98)0301 Open Research Fund Program of LIESMARS and Shanxi Nature Science Foundation under the grant No. 991027.

10. Reference
[1]	Alfons Kemper & Guido Moerkotte. Object-Oriented Database Management. Prentice-Hall press, 1994
[2]	Berge C, Hypergraphs. North—Holland, 1989
[3]	BOUILLE, F., 1977 Structuring cartographic data and spatial processes with the Hypergraph-Based Data Structure, Adcnaced Study Symposium on Topological Data Structures in Geographic Information system. MIT, Oct. 17-21, 22p, in Proceedings, Pp.1222-1227.
[4]	BOUILLE, F., 1994 Methodology of building a class-based integrated platform for GIS design and development, EGIS/MARI'94 Int.Conf., Paris, Proceed., Vol.1, pp.909-918. 
[5]	BOUILLE, F., 1994 Fuzziness structuring and processing in an object-oriented GIS, AGIT'94 Symposium, Salzburg, Proceed. Salzburger Geographische Materialien, Heft 21, pp.113-122. 
[6]	BOUILLE, F., 1994 Integration of advanced object-oriented tools in neural knowledge-based GIS, 3rd Int.Colloquium of LIESMARS-IAI'94 on Integration, Automation and Intelligence in Photogrammetry, Remote Sensing and GIS, Wuhan, Proceed. , pp.16. 
[7]	E. Lynn Usery. A feature-based Geographical Information System Model. PE&RS, Vol. 6, 1996, pp.833-838.
[8]	Jin ZHANG, The Integrated model of Object-Oriented and Hypergraph model. In: Geomatics’98 conference proceedings, 71-77,1998a
[9]	Jin ZHANG, The technology and relevant problems of WEB GIS. Surveying Bulletin, 1998b(1):33-35
[10]	Jin, ZHANG et al, A Hypergraph-Based Object-Oriented Geographical Information System Model, In: Proceeding of DL-HKICC’98, Dalian, 279-282,1998c
[11]	Rongxing LI et al, A hypergraph-based conceptual model for bathymetric and related data management, Marine Geodesy, Vol. 18, 1995, pp. 173-182.
[12]	Reda E. Fayek, Andrew K. C. Wong  Using Hypergraph Knowledge Representation for Nature Terrian Robot Navigation and Path Planning. In Research Report of System Design Engineering of University of Waterloo, Canada, 1996
[13]	Weihong, Cui. Research on spatial data structure. China science & technology press, 1995