如何使用 XML 模式表示网络图？

Question

我有一个表示网络图的数据模型。所以我得到了主机实体（带有它们的地址，以及许多其他 attributes/elements），我需要以某种方式对 Link 实体（代表源节点和目标之间的网络 link 进行建模节点，具有延迟和吞吐量属性）。

问题是，我无法想象使用 XML 架构设计网络的正确方法。我应该如何以适当的方式设计它？（在 XML 设计之后，我将在 Java 应用程序中使用此模式）。

我想我应该创建一个网络元素作为模式的根元素，但我如何管理主机之间的 Links？不知道我是否必须将 Link 元素放在根元素网络中，所以在主机元素旁边，或者我是否必须将 Link 元素放在主机元素中。

这是一个指导示例

<xsd:element name="network" type="NetworkType"/>
<xsd:complexType name="NetworkType">
       <xsd:sequence>
              <xsd:element name="host" type="HostType"/>
              <!-- don't know if put Link element here or inside HostType-->
       </xsd:sequence>
</complexType>

请忽略缺少模式声明等问题，我只需要一个建模建议，如果可以的话，还有一个如何使用 "host" 或主机属性 "hostName" 的示例（未显示）在上面的示例中）作为键以及如何使 "link" 的 elements/attributes sourceHost 和 destHost 引用前一个。

编辑：我会告诉你更多关于建模问题的信息，我注意到我的问题不是很准确。因为我正在为网络基础设施建模，所以我什至不关心顶点（主机）而不是 "connected" 到其他顶点（主机）。话虽如此，我考虑过仅通过 Links 对图形进行建模，并且由于我不关心源顶点和目标顶点（对于我的用例），我可以对其进行建模只插入一个 Link 对于每对连接的顶点。但事实是，我必须从 Java 通用接口开始建模 XML 应用程序（和 XML 模式）并表示引用它的所有信息。让我们假设接口是

public interface NetworkReader {
        public Set<Host> getHosts();
        public Host getHost(String hostName);
        public Connection getConnectionPerformance(Host h1, Host h2);
}

鉴于这样的接口，我选择在我的根元素网络中也包括主机元素（它可以使接口的第一种和第二种方法所需的主机访问更容易），这就是为什么上面考虑 links-only 网络元素失败（在我看来）。

如您所见，第三种方法需要有关给定两个主机的 link 状态的信息，这就是为什么我还需要 XSD 中的 Link 元素的原因。

Answer 1

您可以在 Link 元素中使用主机类型进行建模：

<?xml version="1.0"?>
<schema targetNamespace="urn:your:domain"
        xmlns:ud="urn:your:domain"
        xmlns="http://www.w3.org/2001/XMLSchema"
        elementFormDefault="qualified"
        attributeFormDefault="unqualified"
        blockDefault="substitution"
        version="2.0">

<complexType name="hostType">
  <sequence>
    <element name="…" type="string" minOccurs="0"/>
    <element name="…" type="string" minOccurs="0"/>
  </sequence>
  <attribute name="…" type="string"/>
</complexType>

<element name="Link">
  <complexType>
    <sequence>
      <element name="Source" type="ud:hostType"/>
      <element name="Destination" type="ud:hostType"/>
    </sequence>
  </complexType>
  <attribute name="…" type="string"/>
</element>

</schema>

Answer 2

既然你说你感兴趣的是建模问题，而不是 XSD 细节，那么让我们考虑一些替代方案。

抽象地说，图是一对 (V, E)，其中 V 是任意集合，E 是 V 上的关系，即一组对 (v1, v2)，其中 (a) v1 和 v2 是当且仅当 (v2, v1) 在 E 中时，(v2, v1) 在 V 和 (b) 中均在 E 中。V 的成员是图的顶点，E 的成员是边。图的某些定义使 E 成为一袋边，而不是一个集合，因此两个顶点可以 link 由零个或多个弧组成；一些定义允许和其他禁止 v1 = v2 的边。

在XML中，有三种相当明显的图形表示方法：

每个顶点的一个元素和每条边的一个元素以任一顺序给出一对端点，两个端点都不包含在另一个中。三个节点 a、b、c 的图，其边从 b 到自身以及从 a 到 be 可能是：
```
<graph>
  <vertex id="a"/>
  <vertex id="b"/>
  <vertex id="c"/>
  <edge endpoints="a b"/>
  <edge endpoints="b b"/>
</graph>
```
一些用户（可能还有一些工具链）更喜欢边的端点由 children 给出，而不是由属性给出；这是你的架构，你根据自己的知识、技能和品味来决定。
每个节点的一个元素，以及指示它与哪些其他元素相邻的从属元素。如果我们允许在任一端记录边缘而不一定在两端记录边缘，我们可能会得到上面描述的图形
```
<graph>
  <vertex id="a">
    <adjacent vertex="b"/>
  </vertex>
  <vertex id="b">
    <adjacent vertex="b"/>
  </vertex>
  <vertex id="c"/>
</graph>
```
根据更新和搜索等操作的相对频率，我们可能更愿意要求每条边都记录在两端，因此每个顶点都有 children 所有相邻节点的完整列表（在XML) 更复杂验证的成本；那么我们可能需要：
```
<graph> 
  <vertex id="a">
    <adjacent vertex="b"/>
  </vertex>
  <vertex id="b">
    <adjacent vertex="b"/>
    <adjacent vertex="a"/>
  </vertex>
  <vertex id="c"/>
</graph>
```
请注意，在此表示中，边集由邻接关系间接表示。出于某些目的，这是个好主意；对于其他人来说，这可能是个坏主意。您的选择。
正如在 XML 中可以将边从属于顶点一样，也可以将顶点从属于边。由于图不一定是连通的，我们还需要一些其他方式来表示不与任何边相连的顶点。我们的示例图可能是：
```
<graph>
  <edge endpoints="a b"/>
  <edge endpoints="b b"/>
  <isolated vertices="c"/>
</graph>
```
这里是隐含的顶点集（distinct-values(for $e in $graph/edge return tokenize(@endpoints,' '), tokenize($graph/isolated/@vertices,' '))）。

在XSD中定义这些中的任何一个都很简单；使 XSD 强制执行必要的参照完整性约束在某些表示中可能比在其他表示中更容易。（特别是，在 XSD 1.0 中要求每条边都在两端表示的第二个变体将很困难。）

请注意，在每种情况下，表达的直接性和冗余之间都有一些折衷。在方法 1 中，我们有一个简单的 XML 表示顶点集和边集。但两者的分离意味着为了检查边是否正确表示，我们必须检查边中的每个端点值以确保它命名为已知顶点。此外，如果我们只对连接到其他顶点的顶点感兴趣——如果，也就是说，一个孤立的顶点是一个编码错误——那么在方法 1 中，我们还需要检查每个顶点以确保它被命名为端点至少一个边缘。方法二保证每条边的一个端点是正确的，因为边只出现children个顶点；然而，我们确实必须检查每条边上其他顶点的每个标识符。方法 2 需要关于每个端点下每个 link 的冗余信息，或者它需要搜索网络中的所有节点，以便找到连接到给定边的所有边。

如果您有 non-trivial 个关于每个节点和每个 link 的信息要存储，那么方法 1 将是最不冗余的。

如何使用 XML 模式表示网络图？

How can I represent a network graph using XML Schema?

xml

xsd

modeling

graph