Using XML-Topic Map on a PDA

Graph

adjacent  edges  endpoints  graph  incident with  neighbors  vertices  A graph G is a couple (V,E), where V is the set of vertices and E the set of edges. An edge e is a pair of vertices {x,y}. We usually say that x and y are incident with e, or that they are the endpoints of e. x and y are said to be adjacent or neighbors.

In this paper we will consider that all the graphs are simple, meaning there exist neither multiple edges nor self-loops, ie each pair {x,y} in E is unique and with x different of y.

degree  order  size  The order of a graph, that we will note n, is its number of vertices, and its size, that we usually note m, is its number of edges. The degree of a vertex v, denoted by deg(v), is the number of edges that are incident with it.

Example

The simple graph in figure fig06 is of order 6, and size 8. The degree of the vertex labeled 1 is 2, while its neighbors are the vertices 2 and 6 and its incident edges are a = {1,2}and f = {1,6}.

Hypergraphs

Hypergraphs  hyperedges   Hypergraphs are a generalization of graph concepts, where an edge is incident with an unspecified number of vertices. In this case, we will use the term hyperedges. The representing graph of a hypergraph, is a graph G where the set of vertices is the union of the set of vertices and the edges of the hypergraph, and there exists an edge between two vertices if and only if one of the vertices is a hyperedge incident with the other vertex : .

bipartiteAn important property of the representative graph of hypergraph is that the vertices can be decomposed into two sets such that there exist no edges between any couple of vertices belonging to the same set. These types of graphs are therefore named bipartite graphs.

Graph Coding

To represent the Topic Map on the PDA, we use its graph representation. A graph is mainly represented using two arrays of integers. Each vertex is represented by an integer from 0 to n - 1. Because the graph is simple, we only have to code the list of neighbors for each vertex. This is done in a first array a1, of size 2m where the adjacency lists are given in a contiguous order. The second array a2 is of size n+1 and contains at each index v the starting index of the neighborhood of vertex v. The last index n contains 2m. In that way, the degree of each vertex v may be easily obtained because it is equal to a2[v+1] - a2[v].

Note that if each neighborhood is sorted, knowing if two vertices are adjacent or not may be obtained in a logarithmic time, using dichotomy.

Example The graph in figure fig06 is coded by the two following arrays:

Technical specifications

Both PC's XML parser and Palm navigator were written using Java.

The XML parser uses the Sun's Java APIs for XML processing : JAXP 1.1  . It is implemented as a HotSync Manager's plug-in, using CDKJ 4.0  . Our DTD for the Topic Map on the Palm is a subset of the ISO DTD, which is itself a subset of the DTD used by Mondeca Navigator (palmdtd).

Palm Navigator were written using WabaSDK   and runs using the Waba virtual machine WabaVM. The IHM was written using Waba Extras v1.30.

The software was tested on a Palm emulator and on a Palm V with 3Mo of RAM, and a processor at 20Mhz. It runs well on the emulator. On the Palm, the number of topics and associations available is too small to have a real use. Moreover, drawing a screen takes too much time.

Furtherwork

A new version of Palm Navigator is planned for February 2002. The following improvements have been defined for this version :

• specify screens more similar than those proposed in Mondeca Navigator;

• rewrite Palm Navigator in C or C++ to improve the number of topics and associations and the speed;

• improve the XTM Parser.