<?xml version="1.0"?>

<xs:schema   
             targetNamespace="http://graphml.graphdrawing.org/xmlns/graphml"

             xmlns="http://graphml.graphdrawing.org/xmlns/graphml"
             xmlns:g="http://graphml.graphdrawing.org/xmlns/graphml"
             xmlns:xs="http://www.w3.org/2001/XMLSchema"
             xmlns:xlink="http://www.w3.org/1999/xlink" 

             elementFormDefault="qualified"
             attributeFormDefault="unqualified"
>

<xs:import namespace="http://www.w3.org/1999/xlink" 
           schemaLocation="xlink.xsd"
/>



<!--======================================================-->
<!--=========user-defined extra attributes================-->
<!--======================================================-->

<!--extra attributes common to all GraphML elements-->

<xs:attributeGroup name="common.extra.attrib"/>

<!--specific extra attributes-->

<xs:attributeGroup name="graphml.extra.attrib">
  <xs:attributeGroup ref="common.extra.attrib"/>
</xs:attributeGroup>

<xs:attributeGroup name="data.extra.attrib">
  <xs:attributeGroup ref="common.extra.attrib"/>
</xs:attributeGroup>

<xs:attributeGroup name="key.extra.attrib">
  <xs:attributeGroup ref="common.extra.attrib"/>
</xs:attributeGroup>

<xs:attributeGroup name="default.extra.attrib">
  <xs:attributeGroup ref="common.extra.attrib"/>
</xs:attributeGroup>

<xs:attributeGroup name="graph.extra.attrib">
  <xs:attributeGroup ref="common.extra.attrib"/>
</xs:attributeGroup>

<xs:attributeGroup name="node.extra.attrib">
  <xs:attributeGroup ref="common.extra.attrib"/>
</xs:attributeGroup>

<xs:attributeGroup name="edge.extra.attrib">
  <xs:attributeGroup ref="common.extra.attrib"/>
</xs:attributeGroup>

<xs:attributeGroup name="port.extra.attrib">
  <xs:attributeGroup ref="common.extra.attrib"/>
</xs:attributeGroup>

<xs:attributeGroup name="hyperedge.extra.attrib">
  <xs:attributeGroup ref="common.extra.attrib"/>
</xs:attributeGroup>

<xs:attributeGroup name="endpoint.extra.attrib">
  <xs:attributeGroup ref="common.extra.attrib"/>
</xs:attributeGroup>

<xs:attributeGroup name="locator.extra.attrib">
  <xs:attributeGroup ref="common.extra.attrib"/>
</xs:attributeGroup>




<!--======================================================-->
<!--=============element type definitions=================-->
<!--======================================================-->

<!--=============data type================================-->

<!--extension mechanism for the content of data and default-->
<xs:complexType name="data-extension.type"/>

<xs:complexType name="data.type" final="#all">
  <xs:complexContent mixed="true">
    <xs:extension base="data-extension.type">
      <xs:attribute name="key" type="xs:NMTOKEN" use="required"/>
      <xs:attribute name="id" type="xs:NMTOKEN" use="optional"/>
      <xs:attributeGroup ref="data.extra.attrib"/>
    </xs:extension>
  </xs:complexContent>
</xs:complexType>


<!--=============key type=================================-->
<xs:simpleType name="key.for.type" final="#all">
  <xs:restriction base="xs:NMTOKEN">
    <xs:enumeration value="all"/>
    <xs:enumeration value="graph"/>
    <xs:enumeration value="node"/>
    <xs:enumeration value="edge"/>
    <xs:enumeration value="hyperedge"/>
    <xs:enumeration value="port"/>
    <xs:enumeration value="endpoint"/>
  </xs:restriction>
</xs:simpleType>


<xs:complexType name="key.type" final="#all">
  <xs:sequence>
    <xs:element ref="desc" minOccurs="0"/>    
    <xs:element ref="default" minOccurs="0"/>
  </xs:sequence>
  <xs:attribute name="id" type="xs:NMTOKEN" use="required"/>
  <xs:attribute name="for" type="key.for.type" default="all"/>
  <xs:attributeGroup ref="key.extra.attrib"/>
</xs:complexType>

<!--=============default type=============================-->
<xs:complexType name="default.type" final="#all">
  <xs:complexContent mixed="true">
    <xs:extension base="data-extension.type">
      <xs:attributeGroup ref="default.extra.attrib"/>
    </xs:extension>
  </xs:complexContent>
</xs:complexType>


<!--=============graphml type=============================-->

<xs:complexType name="graphml.type" final="#all">
  <xs:sequence>
    <xs:element ref="desc" minOccurs="0"/>    
    <xs:element ref="key" minOccurs="0" maxOccurs="unbounded"/>
    <xs:sequence>
      <xs:choice minOccurs="0" maxOccurs="unbounded">
        <xs:element ref="graph"/>
        <xs:element ref="data"/>
      </xs:choice>
    </xs:sequence>
  </xs:sequence>
  <xs:attributeGroup ref="graphml.extra.attrib"/>
</xs:complexType>


<!--=============graph type===============================-->

<xs:simpleType name="graph.edgedefault.type" final="#all">
  <xs:restriction base="xs:NMTOKEN">
    <xs:enumeration value="directed"/>
    <xs:enumeration value="undirected"/>
  </xs:restriction>
</xs:simpleType>


<xs:complexType name="graph.type" final="#all">
  <xs:sequence>
    <xs:element ref="desc" minOccurs="0"/>
    <xs:choice>
      <xs:sequence>
        <xs:choice minOccurs="0" maxOccurs="unbounded">
          <xs:element ref="data"/>
          <xs:element ref="node"/>
          <xs:element ref="edge"/>
          <xs:element ref="hyperedge"/>
        </xs:choice>
      </xs:sequence>
      <xs:element ref="locator"/>
    </xs:choice>
  </xs:sequence>
  <xs:attributeGroup ref="graph.extra.attrib"/>
  <xs:attribute name="id" type="xs:NMTOKEN"  />
  <xs:attribute name="edgedefault" 
                type="graph.edgedefault.type" use="required"/>
</xs:complexType>

<!--=============node type================================-->

<xs:complexType name="node.type" final="#all">
  <xs:sequence>
    <xs:element ref="desc" minOccurs="0"/>
    <xs:choice>
      <xs:sequence>
        <xs:choice minOccurs="0" maxOccurs="unbounded">
          <xs:element ref="data"/>
          <xs:element ref="port"/>
        </xs:choice>
        <xs:element ref="graph" minOccurs="0"/>
      </xs:sequence>
      <xs:element ref="locator"/>
    </xs:choice>
  </xs:sequence>
  <xs:attributeGroup ref="node.extra.attrib"/>
  <xs:attribute name="id" type="xs:NMTOKEN" use="required"/>
</xs:complexType>

<!--=============port type================================-->

<xs:complexType name="port.type" final="#all">
  <xs:sequence>
    <xs:element ref="desc" minOccurs="0" />
    <xs:choice minOccurs="0" maxOccurs="unbounded">
      <xs:element ref="data" />
      <xs:element ref="port" />
    </xs:choice>
  </xs:sequence>
  <xs:attributeGroup ref="port.extra.attrib"/> 
  <xs:attribute name="name" type="xs:NMTOKEN" use="required"/>
</xs:complexType>
  
<!--=============edge type================================-->

<xs:complexType name="edge.type" final="#all">
  <xs:sequence>
    <xs:element ref="desc" minOccurs="0"/>
    <xs:element ref="data" minOccurs="0" maxOccurs="unbounded"/>
    <xs:element ref="graph" minOccurs="0"/>
  </xs:sequence>
  <xs:attributeGroup ref="edge.extra.attrib"/>
  <xs:attribute name="id" type="xs:NMTOKEN" />
  <xs:attribute name="directed" type="xs:boolean"/>
  <xs:attribute name="source" type="xs:NMTOKEN" use="required"/>
  <xs:attribute name="target" type="xs:NMTOKEN" use="required"/>
  <xs:attribute name="sourceport" type="xs:NMTOKEN"/>
  <xs:attribute name="targetport" type="xs:NMTOKEN"/>
</xs:complexType>

<!--=============hyperedge type===========================-->

<xs:complexType name="hyperedge.type" final="#all">
  <xs:sequence>
    <xs:element ref="desc" minOccurs="0" />
    <xs:choice minOccurs="0" maxOccurs="unbounded">
      <xs:element ref="data" />
      <xs:element ref="endpoint" />
    </xs:choice>
    <xs:element ref="graph" minOccurs="0" />
  </xs:sequence>
  <xs:attributeGroup ref="hyperedge.extra.attrib"/> 
  <xs:attribute name="id" type="xs:NMTOKEN" />
</xs:complexType>
  
<!--=============endpoint type============================-->

<xs:simpleType name="endpoint.type.type" final="#all">
  <xs:restriction base="xs:NMTOKEN">
    <xs:enumeration value="in"/>
    <xs:enumeration value="out"/>
    <xs:enumeration value="undir"/>
  </xs:restriction>
</xs:simpleType>

<xs:complexType name="endpoint.type" final="#all">
  <xs:sequence>
    <xs:element ref="desc" minOccurs="0" />
  </xs:sequence>
  <xs:attributeGroup ref="endpoint.extra.attrib"/> 
  <xs:attribute name="id" type="xs:NMTOKEN"/>
  <xs:attribute name="port" type="xs:NMTOKEN" />
  <xs:attribute name="node" type="xs:NMTOKEN" use="required"/>
  <xs:attribute name="type" type="endpoint.type.type" default="undir"/>
</xs:complexType>

<!--=============locator type=============================-->

<xs:complexType name="locator.type" final="#all">
  <xs:attributeGroup ref="locator.extra.attrib"/>
  <xs:attribute ref="xlink:href" use="required"/>
  <xs:attribute ref="xlink:type" fixed="simple"/>
</xs:complexType>


<!--======================================================-->
<!--============element declarations======================-->
<!--======================================================-->

<!--=============element: desc============================-->
<xs:element name="desc" type="xs:string" block="#all"/>

<!--=============element: locator=========================-->
<xs:element name="locator" type="locator.type" block="#all"/>

<!--=============element: data============================-->
<xs:element name="data" type="data.type" block="#all">

  <xs:unique name="data_data_key_unique">
    <xs:selector xpath="./g:data"/>
    <xs:field xpath="@key"/>
  </xs:unique>

</xs:element>

<!--=============element: key=============================-->
<xs:element name="key" type="key.type" block="#all"/>

<!--=============element: default=========================-->
<xs:element name="default" type="default.type" block="#all"/>

<!--=============element: graphml=========================-->
<xs:element name="graphml" type="graphml.type" block="#all">

  <xs:unique name="all_id_unique">
    <xs:selector xpath=".//g:*"/>
    <xs:field xpath="@id"/>
  </xs:unique>

  <xs:unique name="graphml_data_key_unique">
    <xs:selector xpath="./g:data"/>
    <xs:field xpath="@key"/>
  </xs:unique>

  <xs:key name="key_id_key"> 
    <xs:selector xpath=".//g:key"/>
    <xs:field xpath="@id"/>
  </xs:key>

  <xs:key name="node_id_key"> 
    <xs:selector xpath=".//g:node"/>
    <xs:field xpath="@id"/>
  </xs:key>

  <xs:unique name="edge_id_unique"> 
    <xs:selector xpath=".//g:edge"/>
    <xs:field xpath="@id"/>
  </xs:unique>

  <xs:unique name="hyperedge_id_unique"> 
    <xs:selector xpath=".//g:hyperedge"/>
    <xs:field xpath="@id"/>
  </xs:unique>

  <xs:unique name="endpoint_id_unique"> 
    <xs:selector xpath=".//g:endpoint"/>
    <xs:field xpath="@id"/>
  </xs:unique>

  <xs:unique name="graph_id_unique"> 
    <xs:selector xpath=".//g:graph"/>
    <xs:field xpath="@id"/>
  </xs:unique>

  <xs:keyref name="data_key_ref" refer="key_id_key">
    <xs:selector xpath=".//g:data"/>
    <xs:field xpath="@key"/>
  </xs:keyref> 

  <xs:keyref name="edge_source_ref" refer="node_id_key">
    <xs:selector xpath=".//g:edge"/>
    <xs:field xpath="@source"/>
  </xs:keyref> 

  <xs:keyref name="edge_target_ref" refer="node_id_key">
    <xs:selector xpath=".//g:edge"/>
    <xs:field xpath="@target"/>
  </xs:keyref>

  <xs:keyref name="endpoint_node_ref" refer="node_id_key">
    <xs:selector xpath=".//g:endpoint"/>
    <xs:field xpath="@node"/>
  </xs:keyref>

</xs:element>


<!--=============element: graph===========================-->
<xs:element name="graph" type="graph.type" block="#all">

  <xs:unique name="graph_data_key_unique">
    <xs:selector xpath="./g:data"/>
    <xs:field xpath="@key"/>
  </xs:unique>

</xs:element>

<!--=============element: node============================-->
<xs:element name="node" type="node.type" block="#all">

  <xs:key name="port_name_key"> 
    <xs:selector xpath=".//g:port"/>
    <xs:field xpath="@name"/>
  </xs:key>

  <xs:unique name="node_data_key_unique">
    <xs:selector xpath="./g:data"/>
    <xs:field xpath="@key"/>
  </xs:unique>

</xs:element>

<!--=============element: port============================-->
<xs:element name="port" type="port.type" block="#all">

  <xs:unique name="port_data_key_unique">
    <xs:selector xpath="./g:data"/>
    <xs:field xpath="@key"/>
  </xs:unique>

</xs:element>

<!--=============element: edge============================-->
<xs:element name="edge" type="edge.type" block="#all">

  <xs:unique name="edge_data_key_unique">
    <xs:selector xpath="./g:data"/>
    <xs:field xpath="@key"/>
  </xs:unique>

</xs:element>

<!--=============element: hyperedge=======================-->
<xs:element name="hyperedge" type="hyperedge.type" block="#all">

  <xs:unique name="hyperedge_data_key_unique">
    <xs:selector xpath="./g:data"/>
    <xs:field xpath="@key"/>
  </xs:unique>

</xs:element>

<!--=============element: endpoint========================-->
<xs:element name="endpoint" type="endpoint.type" block="#all"/>

</xs:schema>

<!--======================================================-->
<!--      end of file: graphml-struct-0.1.xsd             -->
<!--======================================================-->
