QuickGraph：一个100% C# 图形库，支持 Graphviz

Jonathan de Halleux

4.86/5 (72投票s)

2003年12月8日

Zlib

9分钟阅读

1208065

32643

一个通用有向图库，附带 Graphviz Web 控件奖励！

Screenshot - dfs_graph.gif

自2020年12月8日首次提交以来，源代码和下面的文章已经发生了许多变化。

引言

本文介绍了一个 **通用图库**，100% C#。该库旨在将 Boost Graph Library (BGL) 从 C++ 移植到 C#。

图问题出现在许多情况下（比你想象的更频繁）：文件编译顺序、网络带宽、最短路径等。该库提供了表示顶点、边和图的基本数据结构，还提供了各种图算法的 **通用** 实现，例如深度优先搜索、Dijkstra 最短路径等。

由于该库附带了完整的 NDoc 参考手册，本文将不深入探讨编码细节。

关于图论

这是关于图论的快速回顾

Screenshot - vertexedgeexplanation.gif

有向 **图** *G=(VxE)* 由一个有限的 **顶点** 集合 *V=V(G)* 和一个有限的包含在 *VxV = {(u,v)| u,v in V}* 中的 **边** 多重集合 *E* 组成，这些边是顶点的有序对。

如果 *e=(u,v)*，那么 *e* 是 *u* 的 **出边** 和 *v* 的 **入边**。*indegree(v)* 表示 *v* 的 **入** 边数量，*outdegree(u)* 表示 *u* 的 **出** 边数量。

经典图示例有

交通网络
- 顶点 = 路口
- 边 = 道路
互联网
- 顶点 = 计算机
- 边 = 电话线
源代码文件
- 顶点 = 文件
- 边 = 依赖

什么是 BoostGraphLibrary？

本节讨论将 C++ 的 `BoostGraphLibrary` 移植到 C# 的方面。`BoostGraphLibrary` 是一个 C++ 通用图库，它这样介绍自己：

"图是数学抽象，在计算机科学中对于解决许多类型的问题非常有用。因此，这些抽象也必须在计算机程序中表示。一个用于遍历图的标准化通用接口至关重要，以鼓励图算法和数据结构的重用。**Boost Graph Library 的一部分是一个接口，用于如何使用一个通用接口来访问图的结构，该接口隐藏了图数据结构实现的细节。** 这是一个“开放”接口，任何实现此接口的图库都将与 BGL 通用算法以及使用此接口的其他算法互操作。BGL 提供了一些符合此接口的通用图类，但它们并非“唯一”的图类；对于某些情况，肯定会有更好的图类。我们相信 BGL 的主要贡献在于此接口的制定。"

引言摘自 BGL 介绍页面。

`QuickGraphLibrary` 受 BGL 实现的影响很大，事实上，该库的概念和结构很大一部分直接来源于 BGL。下面讨论将 BGL 移植到 C# 的一些主要问题。

C# 中没有模板

这无疑是最大的问题：C# 不支持模板…… **目前（.NET 2.0 中的泛型）**。因此，类模板、函数模板和偏模板特化都无法使用。起初，没有模板，库的通用性受到了严重损害。

概念和 C# 接口：天然的朋友

C# 接口前来救援。事实上，它们是 **抽象概念** 的天然 C# 等效物。实际上，将 BGL 概念转换为 C# 接口只是编写有效表达式到接口中……

例如，`VertexList` 概念定义了 `add_vertex` 和 `remove_vertex` 方法，并完善了图概念。相应的接口是

public interface IVertexListGraph : 
    IGraph // this interface defines the Graph conecpt
{
    IVertex AddVertex();
    void RemoveVertex(IVertex u);
}

`VertexList` 概念的一个模型必须实现 `IVertexListGraph` 接口。例如，`AdjacencyGraph` 类将派生自 `IVertexListGraph`，这将迫使它实现所需的方法。

public class AdjacencyGraph : ..., IVertexListGraph

所有 `QuickGraph` 概念都集中在 `QuickGraph.Concepts` 命名空间中（在 *QuickGraph.Concepts.dll* 程序集中），该命名空间实际上只包含接口。

概念检查和 C# 接口：天然的朋友

C# 接口有很多优点。事实上，它们强制实现了其定义的方法，这隐式地是一种 `ConceptChecking` 形式。

访问者……没有事件！

BGL 通过使用访问者（参见 GoF 的 `VisitorPattern`）为其算法增加了极大的灵活性和可重用性。

在 BGL 中，要定义访问者，您必须首先创建一个定义许多方法的 `visitor` 类。例如，在 `depth_firsts_search` 算法中，访问者必须实现五个方法：`discover_vertex`、`tree_edge`、`back_egde`、`forward_or_cross_edge` 和 `finish_vertex`。这些事件将在下面的实际示例中进行说明。

在 `QuickGraph` 中，可以决定重用 BGL 访问者模式，但结果是 C# 提供了一个非常灵活的解决方案：**事件**。在 C# 中，事件是 **委托**，即函数调用分派器，`static` 函数或实例绑定方法（**处理程序**）可以附加到它。当此事件触发时，处理程序将被调用。因此，BGL 访问者方法自然地转换为事件，访问者可以将其处理程序附加到这些事件。

关于委托的另一个有趣优点是它们是多播的。因此，多个访问者可以开箱即用地附加到同一个算法。

顶点、边描述符……提供者

在 BGL 中，顶点和边描述符的选择是通过使用模板开箱即用的。为了解决这个问题，`QuickGraph` 要求用户提供 `VertexAndEdgeProvider` 类，这些类按需生成顶点和边。因此，只要对象派生自 `IVertex` 或 `IEdge`，您就可以将任何对象用作顶点或边。提供者在 `ProviderConcepts` 部分详细介绍。

库的简要描述

与 BGL 一样，概念在 `QuickGraph` 中扮演着至关重要的角色。它们通过 `QuickGraph.Concepts` 命名空间中的接口实现。这些概念分为以下几类：

核心概念：定义顶点（`IVertex`）、边（`IEdge`）、图（`IGraph`）
图遍历概念：定义如何迭代图、边和顶点。（`IVertexListGraph`、`IIncidenceGraph` 等）
图修改概念：定义如何通过添加或删除边和顶点来修改图（`IEdgeMutableGraph`、`IMutableIncidenceGraph` 等）
...

AdjacencyGraph 类

`AdjacencyGraph` 类实现了许多遍历概念和修改概念，它相当于 BGL 的 `adjacency_list` 模板。它可以用于创建和填充图

// Create a new graph
AdjacencyGraph g = new AdjacencyGraph(
    new VertexAndEdgeProvider(), // vertex and edge provider 
    true // directed graph
    );

// adding vertices u,v
IVertex u = g.AddVertex();    // IVertexMutableGraph
IVertex v = g.AddVertex();    

// adding the edge (u,v)
IEdge e = g.AddEdge(u,v);     // IEdgeMutableGraph

由于顶点和边是集合，因此在这些集合上索引和排序没有意义。但是，它们可以很容易地迭代

//iterating vertices
foreach(IVertex v in g.Vertices) // IVertexListGraph
{
   ...
}

// iterating edges
foeach(IEdge e in g.Edges)       // IEdgeListGraph
{
   ...
}

顶点和边也可以从图中移除

//this will automatically remove the in and out edges of u
g.Remove(u); // IVertexMutableGraph
g.Remove(e);

将数据附加到顶点和边

类似于 BGL 属性映射，创建和维护数据映射以将数据关联到顶点和边是用户的工作。`Collections` 命名空间包含许多类型化的字典来帮助您完成此任务。

以下示例显示了如何创建顶点名称映射

using QuickGraph.Collections;
...
VertexStringDictionary names = new VertexStringDictionary();

IVertex u = g.AddVertex();
names[u] = "u";

算法

算法是库的问题解决者。没有算法，这个库就没有多大意义。

类似于 BGL，算法以通用方式使用访问者模式实现。算法在特定事件处调用用户定义的操作：当第一次发现顶点时，当第一次发现边时等等……在 `QuickGraph` 中，访问者模式通过事件实现。

快速示例

Screenshot - dfs_graph.gif

让我们用一个例子来说明，即深度优先搜索算法。如果可能，深度优先遍历会选择一个与当前顶点相邻的顶点进行下一次访问。如果所有相邻顶点都已被发现，或者没有相邻顶点，则算法回溯到最后一个具有未发现邻居的顶点。一旦所有可达顶点都被访问，算法会从任何剩余的未发现顶点中选择并继续遍历。当所有顶点都被访问时，算法结束。深度优先搜索对于对图中的边进行分类以及对顶点施加排序非常有用。为了实现这一点，算法使用颜色：顶点颜色标记

白色顶点：尚未发现的顶点
灰色顶点：已发现顶点，正在探索子树
黑色顶点：已发现顶点，子树遍历完成

在 `QuickGraph` 中，深度优先搜索由 `DepthFirstSearchAlgorithm` 类实现。此类公开了许多事件（此处未全部详细介绍）

`DiscoverVertex`，当首次遇到顶点时调用
`ExamineEdge`，在每个顶点被发现后，对其每个出边调用
`TreeEdge`，当每条边成为构成搜索树的边的一部分时调用
`FinishVertex`，在顶点的所有出边都已添加到搜索树中且所有相邻顶点都已发现（但在检查它们的出边之前）时调用

深度优先搜索在简单图中的应用在下面的图中详细说明。实现此目的的代码（或多或少）如下所示

// A graph that implements the IVertexListGraph interface
IVertexListGraph g = ...;
// create algorithm
DepthFirstSearchAlgorithm dfs = new DepthFirstSearchAlgorithm(g);
// do the search
dfs.Compute();

InitializeVertex 事件
访问 u 顶点
访问 v 顶点
访问 y 顶点
访问 x 顶点
完成 u 顶点
访问 w 顶点
完成图

上图显示了事件何时被调用。用户可以使用事件来实现自定义操作。例如，假设您想要记录顶点的先行者（这将创建一个排序），首先您需要创建一个类，该类为 `TreeEdge` 事件提供一个委托

class PredecessorRecorder
{
    private VertexEdgeDictionary m_Predecessors;
    
    public PredecessorRecorder()
    {
        m_Predecessors = new VertexEdgeDictionary();
    }

    // the delegate
    public void RecordPredecessor(object sender, EdgeEventArgs args)
    {
        m_Predecessors[ args.Edge.Target ] = args.Edge;
    }
}

`PredecessorRecorder` 类可以随后插入到深度优先搜索算法中。

PredecessorRecorder p = new PredecessorRecorder();

// adding handler
dfs.TreeEdge += new EdgeHandler( p.RecordPredecessor );

因此，将自定义操作插入到算法中非常容易，并且充分利用了 C# 的事件多委托功能。

其他算法在 NDoc 文档中提供并详细介绍。

GraphViz 渲染器和 Web 控件

可以使用 Graphviz 渲染器和 Web 控件对图进行可视化。Graphviz 是一个开源 C 应用程序，用于绘制有向图和无向图。

非常感谢 Leppie，他花时间和精力将 Graphviz 应用程序移植到 .NET。

Graphviz 渲染器

`QuickGraph` 提供了许多辅助类，用于使用 Graphviz 输出您的图

`DotRenderer` 封装了 `Dot` 调用，允许您选择输出路径、图像类型等。
`GraphvizAlgorithm` 是一个遍历图并创建点输出的算法。该算法提供了三个事件，可用于自定义顶点和边的外观
- `WriteGraph` 用于设置全局属性
- `WriteVertex` 在每个顶点上调用
- `WriteEdge` 在每条边上调用
`GraphvizGraph` 是一个用于设置全局设置的类助手
`GraphvizVertex` 是一个用于设置顶点外观属性的类助手
`GraphvizEdge` 是一个用于设置边外观属性的类助手

以下示例将图渲染为 SVG，并使用顶点名称映射来渲染顶点的名称

public class MyRenderer
{
   private VertexStringDictionary m_Names; // name map
   private GraphvizVertex m_Vertex; // helper
   ...

   // vertex delegate
   public WriteVertex(Object sender, VertexEventArgs args)
   {
      // sender is of type GraphvizWriterAlgorithm
      GraphvizWriterAlgorithm algo = (GraphvizWriterAlgorithm)sender;
      // setting name
      m_Vertex.Label = m_Names[args.Vertex];

      // outputing
      algo.Output.Write( m_Vertex.ToDot() );      
   }

   // rendering method
   public void Render(Graph g, VerteStringDictionary names)
   {
      m_Names =names;
      GraphvizWriterAlgorithm algo = new GraphvizWriterAlgorithm(g);

      algo.WriteVertex += new VertexHandler( this.WriteVertex );

      algo.Renderer.ImageType = GraphvizImageType.Svg;
      algo.Compute();
   }
}

Graphviz Web 控件

提供了一个服务器 Web 控件 `QuickGraph.Web.Controls.GraphvizControl`：它具有设计时支持，因此您可以将其插入到工具箱中。

以下示例展示了如何使用该控件

.aspx

<%@ Register TagPrefix="quickgraph" 
  Namespace="QuickGraph.Web.Controls" Assembly="QuickGraph.Web" %>
...
<quickgraph:GraphvizControl RunAt="server" id="Dot" />

代码隐藏

GraphvizControl Dot;
...

// PageLoad method
IVertexAndEdgeListGraph g = ...;

// output file path
Dot.RelativePath = "./temp";
Dot.Algo.VisitedGraph = g;
        
Dot.Algo.Renderer.Prefix="customprefix";
Dot.TimeOut = new TimeSpan(0,0,1,0,0); // files are cached
Dot.Algo.Renderer.ImageType = 
  QuickGraph.Algorithms.Graphviz.GraphvizImageType.Svgz;

历史

2.1：库几乎完全重写。主要变化是
- BGL 概念到接口的完整映射
- 图实现和算法的完全分离
- 算法的单元测试
- 改进了 Graphviz 控件
v1.0：首次发布

参考文献

BoostGraphLibrary
Graphviz 主页
用于 .NET 的离散有限自动机，来自 Leppie。这是 .NET Dot DLL 的来源。