XML schema for lattices and graphs - graphs

XML Schema for Lattices and Graphs

XML Schema for Graphs

For a review of graph theory we refer to this section in the Boost Graph Library .

Simple graphs

Here we want to describe the representation of graphs in XML. Our first graph will be the following simple graph with five verticers and five edges:

A simple graph

We propose to represent this graph in XML in the following way, where the edges attribute to the GRAPH element is optional, since the number of edges can be obtained by counting the number of

 
  EDGE

elements:

  <GRAPH vertices="5" edges="5">
    <EDGE source="1" target="2"/>
    <EDGE source="2" target="3"/>
    <EDGE source="1" target="4"/>
    <EDGE source="2" target="5"/>
    <EDGE source="2" target="3"/>
  </GRAPH>

Colored graphs

Graphs with colored edges and vertices can also be represented:
A colored graph

We represent this graph in XML by introducing additional VERTEX elements to describe the vertices, and type attributes for vertices and edges to specify their type (color). Vertex types 0,1 and 2 refer to the red, green and blue vertices respectively, while edge types 0 and 1 refer to the solid and dashed lines in our example:

  <GRAPH vertices="5" edges="5">
    <VERTEX id="1" type="0"/>
    <VERTEX id="2" type="1"/>
    <VERTEX id="3" type="0"/>
    <VERTEX id="4" type="2"/>
    <VERTEX id="5" type="2"/>
    <EDGE source="1" target="2" type="0"/>
    <EDGE source="2" target="3" type="0"/>
    <EDGE source="1" target="4" type="1"/>
    <EDGE source="2" target="5" type="1"/>
    <EDGE source="2" target="3" type="0"/>
  </GRAPH>

In this example both the vertices and edges attributes are optional, since both can be obtained by counting the respective number of VERTEX and EDGE elements.

The optional id attribute of the VERTEX element specifies the vertex number. If it is omitted a consecutive numbering is assumed. The default for the type attribute is 0.

A shorter but equivalent version is thus:

  <GRAPH>
    <VERTEX/>
    <VERTEX type="1">
    <VERTEX/>
    <VERTEX type="2"/>
    <VERTEX type="2"/>
    <EDGE source="1" target="2"/>
    <EDGE source="2" target="3"/>
    <EDGE source="1" target="4" type="1"/>
    <EDGE source="2" target="5" type="1"/>
    <EDGE source="2" target="3"/>
  </GRAPH>

More properties

Additional vertex and edge properties can be added as elements or attributes. At the moment we only specify a COORDINATE element to specify spatial coordinates for a vertex. Taking the first graph abobe as an example, the coordinates can be specified as:

  <GRAPH vertices="5" edges="5">
    <VERTEX id="1"> <COORDINATE> 1 1 </COORDINATE> </VERTEX>
    <VERTEX id="2"> <COORDINATE> 2 1 </COORDINATE> </VERTEX>
    <VERTEX id="3"> <COORDINATE> 3 1 </COORDINATE> </VERTEX>
    <VERTEX id="4"> <COORDINATE> 1 2 </COORDINATE> </VERTEX>
    <VERTEX id="5"> <COORDINATE> 2 2 </COORDINATE> </VERTEX>
    <EDGE source="1" target="2"/>
    <EDGE source="2" target="3"/>
    <EDGE source="1" target="4"/>
    <EDGE source="2" target="5"/>
    <EDGE source="2" target="3"/>
  </GRAPH>

Additional elements and atrributes can be added if there is demand for them.

Various

Schemas and sources:

For the graph part of the lattice and graph schema see this link
For a library to read such an XML file and to create a Boost graph , see www.comp-phys.org

Topics to be discussed, and possible extensions include:

is there already an XML standard in the graph community?
additional properties of edges and vertices?
should the vertex and edge labels start from 0 or 1?
extension do directed graphs by specifying a directed attribute.
the type attribute for the color is an unsigned integer. Is that sufficient or should we be more flexible.
the egde and vertex numbers are unsigned integers. Is that sufficient or should we allow other enumeration schemes, e.g. letters

We encourage your comments and ideas .

Back to XML in Compuational Physics