XML schema for lattices and graphs - graphs on lattices

XML Schema for Lattices and Graphs

XML Schema for Graphs on Lattices

A simple graph

The graphs in most physics simulations are not irregular graphs, but built up regularly, like a lattice: A 5-site chaiin

We can capture the regularity of this graph by putting it down onto a lattice:

A 6-site chain shown on a lattice

This lattice can be described by a unit cell, and the graph built up from a "unit cell graph" on the unit cell:
A unit cell for a chain graph

The "unit cell graph" consists of a single vertex, and there is a edge to the same vertex in the neighboring cell. We can describe such a graph on a lattice in XML, by combining a LATTICE or FINITELATTICE with a UNITCELL element describing the graph on the unit cell from which the full graph is created:

  <LATTICEGRAPH>
    <FINITELATTICE>
      <LATTICE dimension="1"/>
      <EXTENT size="6"/>
      <BOUNDARY type="open"/>
    </FINITELATTICE>
    <UNITCELL dimension="1" vertices="1">
      <VERTEX/>
      <EDGE>
        <SOURCE vertex="1"/>
        <TARGET vertex="1" offset="1"/>
      </EDGE>
    </UNITCELL>
  </LATTICEGRAPH>

The edge in the unit cell goes from vertex 1 in the cell to vertex 1 in the cell to the right (with an offset +1), as described in the EDGE element. The offet of 0 in the SOURCE element was omitted, as 0 is the default value for the offet.

To describe an infinite chain we would use a LATTICE element instead of the FINITELATTICE one.

A complex example

Like in the schema for graphs , we can describe graphs with colored edges and vertices, or add other attributes like coordinates to the vertices. Also, for the description of the lattice the full machinery described for the lattice schema is available. We will show one example for a complex periodic graph on an L x W rectangular lattice:
A 6-site chain shown on a lattice

This graph on a lattice can be built from this complex unit cell graph deorating the rectangular lattice:
A unit cell for a complex 2D graph

The XML description is:

  <LATTICE name="square" dimension="2">
    <BASIS>
      <VECTOR> 1 0 </VECTOR>
      <VECTOR> 0 1 </VECTOR>
    </BASIS>
  </LATTICE>

  <FINITELATTICE name="rectangular periodic" dimension="2">
    <LATTICE ref="square"/>
    <PARAMETER name="L" />
    <PARAMETER name="W" default="L" />
    <EXTENT dimension="1" size="L"/>
    <EXTENT dimension="2" size="W"/>
    <BOUNDARY type="periodic"/>
  </FINITELATTICE>

  <UNITCELL name="complex example" dimension="2" vertices="2">
    <VERTEX id="1" type="0"><COORDINATE> 0.3 0.7 </COORDINATE></VERTEX>
    <VERTEX id="2" type="1"><COORDINATE> 0.6 0.3 </COORDINATE></VERTEX>
    <EDGE><SOURCE vertex="1"/><TARGET vertex="1" offset="1 0"/></EDGE>
    <EDGE><SOURCE vertex="1"/><TARGET vertex="1" offset="0 1"/></EDGE>
    <EDGE><SOURCE vertex="1"/><TARGET vertex="2"/></EDGE>
  </UNITCELL>

  <LATTICEGRAPH>
    <FINITELATTICE ref="rectangular periodic"/>
    <UNITCELL ref="complex example"/>
  </LATTICEGRAPH>

Here we made use of the predefinition of named lattices and unit cells (e.g. in a library), which we can then combine be referencing them in the LATTICEGRAPH element. Alternatively we could have defined everything in the LATTICEGRAPH element:

  <LATTICEGRAPH>
    <FINITELATTICE dimension="2">
      <LATTICE dimension="2">
        <BASIS>
          <VECTOR> 1 0 </VECTOR>
          <VECTOR> 0 1 </VECTOR>
        </BASIS>
      <PARAMETER name="L" />
      <PARAMETER name="W" default="L" />
      <EXTENT dimension="1" size="L"/>
      <EXTENT dimension="2" size="W"/>
      <BOUNDARY type="periodic"/>
    </FINITELATTICE>
    <UNITCELL dimension="2" vertices="2">
      <VERTEX id="1" type="0"><COORDINATE> 0.3 0.7 </COORDINATE></VERTEX>
      <VERTEX id="2" type="1"><COORDINATE> 0.6 0.3 </COORDINATE></VERTEX>
      <EDGE><SOURCE vertex="1"/><TARGET vertex="1" offset="1 0"/></EDGE>
      <EDGE><SOURCE vertex="1"/><TARGET vertex="1" offset="0 1"/></EDGE>
      <EDGE><SOURCE vertex="1"/><TARGET vertex="2"/></EDGE>
    </UNITCELL>
  </LATTICEGRAPH>

Since both coordinates for the vertices in the unit cell, as well as basis vectors for the lattice are given, the coordinates of all vertices can be calculated.

Various

Schemas and sources:

For the lattice-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 the ALPS library at alps.comp-phys.org

Topics to be discussed, and possible extensions include:

for the graphs we had an <EDGE source=... target=.../> tag. Here in the unitcells we specify not only the source and target vertex, but also the cell offsets. Thus we defined an EDGE element, which contain a SOURCE and TARGET element each with a vertex and offset attribute. Alternatively we could stay with a single EDGE element with additional sourceoffset and targetoffset attributes. This means more and longer attributes, but would be closer to the conventions used in the GRAPH element.
additional properties of edges and vertices?
should the vertex and edge labels start from 0 or 1?
extension to directed graphs by specifying a directed attribute.

We encourage your comments and ideas .

Back to XML in Compuational Physics