理论计算机科学电子笔记264（5）（2011）23-45www.elsevier.com/locate/entcsLEMONBal'azsDezsBázoa，2 AlparJüttnerb，3P'eter Kov'acsa，4a算法与应用匈牙利布达佩斯b埃奥特维奥斯大学运筹学系匈牙利布达佩斯摘要本文介绍了LEMON，一个通用的开放源代码的C++库提供了易于使用和高效的实现图和网络算法和相关的数据结构。LEMON的基本设计思想、特点和性能与同类软件包BGL（Boost）进行了比较图形库）和LEDA。事实证明，LEMON是这些广泛使用的库的可行替代品，我们的基准测试表明，它通常在效率上优于它们关键词：C++，库，设计，图形，网络，模板1引言LEMON [29]是一个C++模板库，专注于主要与图形和网络相关的组合优化任务。它 的 名 字 是 网 络 中 的 有 效 建 模 和 优 化 的 缩 写 。 LEMON 是Egerv′aryResearchchGrouponCombinatorialOptimization（EGRES）[14]的一个开源软件，位于布达佩斯的Eetv′osLor′andUniv-它也是COIN-OR倡议的成员[9]，这是一个与运筹学相关的开源项目其清晰的设计和许可证计划使LEMON有利于商业和非商业软件开发，以及研究活动。1 LEMON项目得到EGRES的支持[14]。2电子邮件：deba@inf.elte.hu3电子邮件：alpar@cs.elte.hu4电子邮件：kpeter@inf.elte.hu1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2011.06.00324B. Dezs oBogaetal. /《理论与计算科学》选编264（5）（2011）23该库的目标是提供高效、易用和良好协作的软件组件，以帮助解决复杂的现实优化问题。这些组件包括图形实现和相关数据结构、基本图形算法（如图形搜索、最短路径、生成树、匹配和网络流算法）以及各种辅助工具（例如，图形和相关数据的灵活输入输出支持）。此外，该库为几个线性规划（LP）和混合整数规划（MIP）[10，12]求解器提供了一个通用的高级接口。LEMON被设计为跨平台的，并支持广泛的操作系统和编译器。到目前为止，它已经在Linux，Windows，OSX和AIX系统上进行了测试，使用以下编译器：GCC3.3-4.4，Intel C++，IBM xlC，Visual C++2005，2008和2010，MinGW。由于基于 CMake [8] 的 构建 环 境，LEMON 可 以很 好 地与 各 种IDE 集 成， 例 如 VisualStudio，CodeBlocks或Eclipse。开发LEMON的基本动机是通过建立一个比市场上其他替代品更适合他们的开源库来支持在图论和网络优化领域工作的LEMON除了提供更广泛的复杂算法和实现尽可能高的整体性能外，还致力于更简单的设计和界面。目前，LEMON被广泛用于研究目的，包括网络设计、传输路由和一般图论[2，6，25，37]，以及教育、技术和经济学。此外，它也用于商业应用，例如[13]。在2003年到2007年之间，发布了一系列LEMON的开发版本，这些版本具有越来越多的功能，但没有稳定的API。自2008年以来，稳定版本已开发为1.x版本。它们确保了完全的向后兼容性，并具有更小但更成熟的工具集，这些工具集在界面和效率方面都得到了改进。本文基于LEMON 1.2，这是撰写本文时的最新主要版本本文的其余部分组织如下。第2节概述了LEMON与类似的C++图形库相比的主要特性。第3节描述了选定的实施细节。第4节通过基本算法的基准测试比较了所讨论的库的性能。第5节概述了开发LEMON的主要进一步计划最后，在第6节中得出结论。2概述Boost Graph Library（BGL）可能是最著名的C++图形库，这就是为什么读者通过使用这两个库的简单和等效的示例代码来介绍LEMON。这两个程序都构造一个有向图，为弧分配长度，并从源节点开始运行Dijkstra算法。图1和图2简要地演示了图形库的基本工具的B. Dezs oBogaetal. /《理论与计算科学》选编264（5）（2011）2325typedef adjacency_list listS，vecS，bidirectionalS，no_property，int> graph_t;graph_t g;graph_t：：vertex_descriptor s= add_vertex（g）;graph_t：：vertex_descriptort= add_vertex（g）;... //添加更多顶点graph_t：：edge_descriptor e= add_edge（s，t，g）.first;g[e]= 8;... //添加更多边vector int> dist（num_vertices（g））;dijkstra_shortest_paths（g，s，weight_map（get（edge_bundle，g））.distance_map（dist[0]））;std：：cout“dist[t]=“ dist[t] std：：endl;<<<<图1.一、演示BGL用法的示例代码ListDegraph g; ListDegraph：：ArcMap int> length（g）;ListDigraph：：Node s=g.addNode（）; ListDigraph：：Nodet= g.addNode（）;... //添加更多节点ListDigraph：：Arc a= g.addArc（s，t）;length[a]= 8;... //添加更多弧ListDivraph：：NodeMap int> dist（g）; dijkstra（g，length）.distMap（dist）.run（s）;std：：cout“dist[t]=“ dist[t] std：：endl;<<<<图二、演示LEMON用法的示例代码本节的后续部分将详细讨论LEMON的所有基本特性，并在用户界面、主要概念和设计决策方面将该库与其两个主要竞争对手BGL [4，32]和LEDA [28，30]进行请注意，BGL是一个开源软件，而LEDA是一个商业库。2.1图形数据结构虽然LEMON是一个通用库，但它的主要图形类型不是模板类，这是由一个重要的设计决策实现的也就是说，分配给节点和弧的所有数据都与图形数据结构分开存储（参见第2.3节）。图2中的示例使用了ListDigraph，这是一个基于双向链接邻接列表的通用有向图实现。另一个重要的有向图类型是SmartDigraph，它将节点和弧连续存储在向量中，并使用简单链表来跟踪每个节点的关联弧（参见3.1节）。因此，它比ListDigraph占用的内存更少，速度也更快，但代价是不能从中删除节点和弧。ListGraph和SmartGraph是这些数据结构的无向版本。LEMON遵循BGL和LEDA的泛型编程范式，通过概念描述泛型组件的需求。这些概念的作用与STL中的相同：它们定义了数据类型，以及它们的用户界面和语义。LEMON定义了两个图的概念，有向图和图，分别描述了有向图和无向图的要求。无向图26B. Dezs oBogaetal. /《理论与计算科学》选编264（5）（2011）23概念被设计为也满足有向图概念的要求，使得无向图的每条边也可以被视为一对相反方向的弧。因此，每一个无向图，没有任何变换，可以被认为是一个有向图。这种设计的主要好处是，所有有向图算法也自动适用于无向图。在大多数情况下，这也意味着不需要单独的算法实现。然而，特定的算法可能需要专门化无向图。这种特殊的方法是检查欧拉性质，这将在3.4节中详细讨论。uv边缘u弧v电弧图三. LEMON的无向图概念的说明。也可以查看每个无向边两个方向相反的弧。无向图为无向边提供边类型，为弧提供弧类型。这种分离使得一些算法的实现更简单（例如，平面图算法），因为我们可以将无向边与它们的有向变体区分开。另一方面，无向图的Arc类型可以转换为Edge类型，从而可以方便地得到弧的相应边，而不需要调用任何函数。因此，所有为边设计的方法和数据结构都可以直接用于边和弧。 这在几种情况下可能是非常实用的。 比如说，将数据分配给边的属性映射（参见第2.3节）可以用于边和弧，但弧映射只能用于弧。BGL实现了一个基于邻接表的图形类，但它可以完全定制的模板参数，指定内部存储数据结构的节点和弧。此外，可以使用另一个模板参数将图设置为有向、双向或无向双向图的概念相当于LEMON这些图形类型支持遍历每个节点的传出和传入弧。BGL的有向图只存储输出弧列表，因此它们比双向图需要更少的存储空间。请注意，LEMON中缺少此类别BGL的邻接表类模板通过广泛使用模板专门化实现了有向图和无向图。因此，在BGL中，有向图和无向图具有相同的接口，但具有不同的语义。无向图的边通常被认为是无向的，但它们在某些情况下具有方向，例如，在迭代中。 这种不一致可能会造成混乱。此外，这种设计不可能定义其键是边的有向变体的属性映射，尽管它在某些算法中也很重要。LEDA主要区别是LEDA在同一个类中实现有向图和无向图，并提供成员函数在两种模式之间切换这种设计当然方便，B. Dezs oBogaetal. /《理论与计算科学》选编264（5）（2011）2327但它没有LEMON的概念那么独特库中还实现了各种特殊用途的图形类型，例如全图、网格图或邻接矩阵图。此外，这三个库都为有向图提供了优化的静态数据结构，它将节点和弧存储在数组或向量中，按其源节点排序。由于大多数有向图算法的关键操作都是在节点的输出弧上进行的，因此使用这些静态实现通常会运行得更快。2.2迭代器大多数图形库提供用于遍历图形数据结构的元素的迭代器类（即，节点和弧）。LEMON定义了一个特殊的迭代器接口，它不符合C++标准模板库（STL）的迭代器概念。LEMON的迭代器由其构造函数初始化为遍历范围中的第一个元素，并通过将其与特殊常量INVALID进行比较来检查其有效性。此外，每个迭代器类都可以转换为cor-响应图形元素类型，而不必使用运算符 *（）。 此功能将LEMON迭代器与标准C++迭代器区分开来，并使它们的使用稍微简单一些。回想一下图2所示的示例。每个节点的计算距离可以打印到标准输出，如下所示。for（ListDigraph：：NodeIt v（g）; v！=INVALID;++v）{ std：：cout g.id（v）“：“dist[v]std：：endl;<<<<<<<<}在第一行中，所有出现的v都指向迭代器本身，而对应的- ing节点对象在循环中被引用两次请注意，这个概念不能应用于一般迭代器。例如，STL为任意项的容器定义迭代器 这意味着容器的迭代器类型和项类型可以具有连接功能，例如，它们都可以支持operator++（）。因此，迭代器对象和被引用对象必须区分开：it++ a选择迭代器it，而（*it）++ a选择被引用对象 *it。然而，LEMON迭代器概念利用了图的特殊性，图可以被视为特定元素的容器。节点和弧本身提供了一组非常有限的特性，这与迭代器的功能不一致。因此，程序上下文总是指示我们引用的是迭代器还是图形元素，正如我们在上面的例子中已经看到的与 此 相反 ， BGL 迭 代 器遵 循 输 入 迭代 器 的 STL 要 求 。这 意 味 着 必须 使 用operator*（）函数对它们进行解引用，以获得相应的项描述符。回想一下图1所示的BGL代码。运行Dijkstra算法后graph_t：：vertex_iterator vi，vend;for（tie（vi， vend）=顶点（g）; vi！=vend;++vi）{28B. Dezs oBogaetal. /《理论与计算科学》选编264（5）（2011）23std：：cout *vi“：“dist[*vi] std：：endl;<<<<<<<<}tie（）函数用于使代码更紧凑，并避免程序员的简单错误。上述解决方案的一个缺点是迭代器对象定义在比循环本身的范围更广。然而，BGL还提供了几个迭代宏，这些宏简化了遍历图元素的过程，并仅在循环范围BGL_FORALL_VERTICES（v，g，graph_t）{std：：cout< label（g）;ListDegraph：：ArcMap int> length（g）;映射值可以使用operator[]（）的相应重载版本获得和修改。B. Dezs oBogaetal. /《理论与计算科学》选编264（5）（2011）2329label[v] =“source”;length[e] = 2 * length[f];除了标准的图形映射，LEMON还包含几个它们不是独立的地图，拥有自己的数据存储，但它们适应一个或多个其他地图对象，并“在后台”更改其数据。当调用映射适配器的访问操作时，它从底层映射中读取相应的数据并对其执行某种操作，但实际上并不这些适配器类也符合映射概念，因此它们可以像标准LEMON映射一样使用假设我们有一个存储在LEMON图对象中的交通网络，其中有两个弧映射长度和速度，它们存储每个弧的物理长度。以及在该路段上可以达到的最大（或平均）速度。如果我们对最优旅行时间感兴趣，那么我们可以如下调用Dijkstradijkstra（g，divMap（length，speed））.distMap（dist）.run（s）;divMap（）函数返回一个map适配器对象，该对象提供两个原始map的值的这意味着Dijkstra算法为每个弧接收相应路段的表达行驶时间与LEMON相反，有几个库直接将相关数据存储在图的节点和弧对象中。例如，只有有限数量的固定类型的内部映射可以在Stanford GraphBase库中使用[27，31]。这种设计允许更容易的实现，但强烈限制了库的通用性BGL支持图形相关数据的内部和外部存储。 节点和边的内部属性可以指定为捆绑属性或属性列表。捆绑的属性提供了一个更简单的接口，并且它们的使用是首选，而后一种解决方案与旧编译器和旧版本的Boost库兼容图1显示了一个使用捆绑属性（边的长度）的简单示例。如果节点和边需要更多的赋值，则必须将它们收集到特定的数据类型中，然后将其作为模板参数传递给图形类。struct NodeData {. };struct EdgeData {. }的情况;typedef adjacency_list listS，vecS，bidirectionalS，NodeData，EdgeData>GraphType;内部存储的主要优点是，如果图被修改，它的容量会自动调整，但它是不灵活的，因为它的生命周期严格限制在图对象上。通过包装标准容器数据结构，BGL也支持外部属性映射。它们比内部性质更灵活，因为它们的生命期不受关联图的约束然而，如果我们将这些映射与变化的图结合使用，我们必须在效率和方便之间做出选择我们可以应用包装随机访问容器的映射（例如，std：：vector）确保快速的数据访问，但每次图形变化或者，我们也可以使用基于as的外部映射30B. Dezs oBogaetal. /《理论与计算科学》选编264（5）（2011）23关联容器（例如， std：：map）。 这种解决方案自然地适应图的任何变化，而无需显式更新，但以效率为代价。请注意，LEMONLEDA实现了两种外部数据结构来处理与图形相关的数据。数组是静态数据结构，但它们的访问操作需要恒定的时间。映射类型更加灵活，因为当关联的图改变时，它们不会失效。然而，它们是通过哈希表实现的，因此效率较低。因此，我们遇到了与BGL的外部映射虽然这些数据结构是外部的，但LEDA可以在图形对象中为它们分配额外的存储空间新创建的数组和映射可以分配给这些插槽，因此可以优化内存使用。除了这些解决方案，LEDA还提供了参数化的图形数据结构，其节点和边对象可以包含任意附加数据，就像BGL中的绑定属性一样。2.4算法不可避免地，图形库之间最重要的区别因素是实现算法的范围和质量用于特定用途的简单图数据结构可以快速实现，但复杂的算法需要精心设计和熟练程序员的大量工作，特别是当效率具有高度优先级时。LEMON为图论和组合优化的众多算法提供了高效的实现。这些算法包括基本方法，例如广度优先搜索（BFS）、深度优先搜索（DFS）、Dijkstra算法、Bellman-Ford算法、Kruskal算法，以及用于发现各种图属性（连通性、二分性、欧拉属性等）的方法，以及复杂的算法，用于发现最大的最小割，可行的循环，最大匹配，最小平均圈，最小成本最小割，和平面嵌入图。BGL和LEDA具有类似的算法，但具有不同的接口。在LEMON中，算法被实现为类模板，但为了方便起见，函数类型接口也可用于其中一些。例如，Dijkstra算法的函数接口相当简单，但由于广泛使用的命名参数技术，它们适用于大多数实际情况。该技术支持多个具有默认值的函数参数，并且可以以任意顺序指定这些参数的任意集合通过为每个所需参数调用专用函数。这意味着参数是通过名称引用的，而不是标准的基于位置的引用。LEMON实现命名参数与Boost库非常相似[32]。图2中的示例代码也可以使用类接口，如下所示。B. Dezs oBogaetal. /《理论与计算科学》选编264（5）（2011）2331Dijkstra ListDigraph> alg（g，length）; alg.distMap（dist）;网址：alg.run;这段代码比前一段代码长，但是使用这个接口可以在更高的程度上控制执行。例如，可以指定更多的源节点，也可以逐步执行算法，如以下代码所示。alg.init（）;alg.addSource（s）;同时（！public void run（）{ListDigraph：：Nodevint n. getString（）;std：：cout g.id（v）“：“alg.dist（v）std：：endl;<<<<<<<<}算法的基本功能可以使用特殊用途的映射类型作为其内部数据结构来大大扩展例如，Dijkstra类存储ProcessedMap，它应该是bool值类型的可写节点映射。当节点被处理时，节点的赋值被设置为true，也就是说，它的实际距离被找到。应用一个特殊的映射，LoggerBoolMap，节点的处理顺序可以很容易地记录在标准容器中这种特定的映射类型可以使用以下技术传递给算法：命名的模板参数。与命名函数参数类似，它们允许以任意顺序指定参数的任何子集typedef vector ListDigraph：：Node> Container;typedef back_insert_iterator Container>InsIterator;typedef LoggerBoolMap InsIterator>MyProcessedMap;集装箱;InsIterator iterator（container）;MyProcessedMap map（iterator）; Dijkstra ListDigraph>：：SetProcessedMap MyProcessedMap>* 创建alg（g，length）;alg.processedMap（map）;alg.run（s）;令人惊讶的是，即使是上面的例子也可以使用dijkstra（）实现函数和命名参数如下。vector ListDimraph：：Node>container;dijkstra（g，length）.processedMap（loggerBoolMap（back_insert（container）.run（s）;请注意，函数接口的主要优点是临时对象可以作为引用参数传递。在这个例子中，插入迭代器对象和映射对象都只是临时创建BGL使用基于访问者的接口实现了几种算法，而不是使用特殊用途的图形映射。访问者类是函数对象的泛化：它们通过定义几个回调函数而具有更多的入口点。基于访问者的算法在其执行期间发出不同的事件，并调用相关联的访问者的相应入口函数。在某些情况下，这种技术可能比使用自定义映射更方便，因为所有事件处理程序操作都在同一个类中实现。出于这个原因，LEMON也提供了基于访问者的解决方案，但仅适用于基本的图搜索算法BFS和DFS。32B. Dezs oBogaetal. /《理论与计算科学》选编264（5）（2011）23LEDA在使用算法方面提供的灵活性比其他两个库要少。它为每个算法实现了一些紧凑的函数接口，但没有命名参数。这些函数是为最典型的用例而设计的，仅支持有限的配置选项。2.5图形适配器在典型的图算法和应用中，我们通常需要对图进行特定的例如，应删除某些节点或弧，或者应使用反向图形。然而，物理存储的实际修改或制作数据结构的副本以及所需的映射与应在更改的图上执行的操作相比可能相当昂贵（在时间或内存使用方面）。在这种情况下，可以使用LEMON图适配器是特殊的类模板，用于以不同的方式考虑其他图数据结构它们基于与前面讨论的map adaptor相同的思想（见2.3节），但它们更复杂。图形适配器只能与提供图形实际存储的另一个图形对象结合使用。它们并不修改底层的数据结构，只是通过利用原始操作来提供另一种视图。图适配器符合图的概念，因此它们可以像“真实”图一样使用下面的示例显示了如何使用ReverseDigraphdijkstra（reverseDigraph（g），length）.distMap（dist）.run（s）;请注意，原始图的映射（length和dist）也可以与适配器一起使用，因为所有适配器的节点和弧类型都会转换为原始项类型。正如这个例子所展示的，图适配器有助于编写紧凑而优雅的代码，并使基于可靠的标准组件实现复杂算法变得更容易另一个基本的图形修改是隐藏节点和弧，这可以使用LEMON中的一个子图适配器来实现这些类存储迭代器用来跳过当前隐藏项的过滤器映射。因此，子图适配器的效率明显低于原始图对象。由于适配器类符合图形概念，我们甚至可以将一个适配器应用于另一个适配器。图4示出了当将子有向图适配器应用于有向图并且使用Undirector来使所获得的子图无向时的情形。组合优化方法通常基于更复杂的图变换。例如，残差网络是一个特别重要的模型，用于搜索和匹配算法。ResidualDigraph通过适配有向图以及容量图和流量图来实现该网络。SplitNodes是另一个实用的适配器，它将每个节点拆分为一个in-nodeB. Dezs oBogaetal. /《理论与计算科学》选编264（5）（2011）2333非导向器适配器SubDigraph适配器原有向图图四、LEMON中图形适配器的插图和有向图中的出节点。形式上，适配器用两个节点vin和vout替换每个节点v。原始图的每个弧（u，v）将对应于一个弧（uout，vin）。适配器还为原始图的每个节点v添加额外的绑定弧（vin，vout）。这种构造的目的是在使用仅考虑弧成本或容量的算法时将成本或容量分配给图的节点。BGL也有图形适配器，但只有几个基本的，如反向图或过滤图。 另一方面，LEDA不提供类似的工具。2.6LP接口线性规划是运筹学中最重要的通用方法之一。无数的优化问题可以用LP技术来公式化和解决如今，有各种高效的LP求解器可用，包括开源和商业软件。因此，LEMON不实现自己的求解器，而是为几个LP库提供了一个通用的高级接口。这种设计的优点是双重的。首先，LEMON应用了一种面向对象的方法，这与BLOG Concert技术[11]非常相似。这种方法使LEMON的接口比几个LP库的本地接口更灵活，对于那些熟悉面向对象编程的人来说，它可能更舒适。其次，在使用这种通用语法的应用程序中更改底层求解器不需要进行排序。因此，人们可以很容易地在她的特定应用中试验各种LP解算器，并在开发的任何阶段比较它们的图5演示了在LEMON中形式化和解决LP问题是多么简单Lp：：Col表示LP问题的变量，而Lp：：Row表示约束。数值运算符用于从列形成表达式，从行形成对偶表达式由于适当的算子过载，LP问题可以方便地直接描述为数学34B. Dezs oBogaetal. /《理论与计算科学》选编264（5）（2011）23ΣΣLplp;Lp：：Col x1 = lp.addCol（）; Lp：：Col x2 =lp.addCol（）;int max（）;lp.obj（10 *x1+ 6 * x2）;lp.addRow（0 = x1 + x2 = 100）;lp.addRow（2 * x1 = x2 + 32）;int n = nums（nums，0）;int n = nums（n，n）;sort（）;std：：cout“Solution：“lp.primal（）std：：endl;std：：cout“x1=“lp.primal（x1）std：：endl; std：：cout“x2=“lp.primal（x2）std：：endl;<<<<<<<<<<<<<<<<<<图五、演示LEMON的LP接口用法的示例代码线性规划求解器是求解各种复杂优化问题的强大通用工具。让我们以著名的最大流问题为例。它是在一个具有容量约束的网络中，寻找一个在源节点和目标节点之间的最大值流。设G=（V，A）表示一个有向图，c：A→R+表示一个容量函数，s，t∈V表示源节点和目标节点，re-k。一个最大最小流是以下优化问题的f：A→R解。最大v：（s，v）∈A受制于v：（u，v）∈Af（s，v）−v：（v，s）∈Af（u，v）=0f（v，s）f（v，u）<$u∈V\{s，t}0≤f（u，v）≤c（u，v）<$（u，v）∈A图6中的示例代码使用LEMON的LP接口解决了这个问题。请注意，表达式是使用简单的循环构建的，这些循环遍历节点的传出和传入弧。其他各种图优化问题也可以表示为线性规划和接口提供的LEMON方便解决他们很容易（虽然通常不那么有效，因为通过直接组合方法，如果存在）。目前，LEMON支持以下线性和混合整数规划包：GLPK [16]，Clp [7]，Cbc[5]，CNOG CPLEX [11]和SoCron [34]。新求解器的附加包装类也可以很容易地实现。2.7输入输出处理LEMON提供了一种通用的文件格式，用于存储图形和相关的节点和弧映射。这种格式应该是通用的，也就是说，它应该支持存储任意数量的任意值类型的映射。此外，文件大小和易于处理对于支持处理大型图也至关重要，这是LEMON的主要目标。因此，设计了一种可扩展的文本文件格式，而不是使用结构化的分层格式，如GraphML [21]，GXL [22]或GML [17]。最大10x1+6x2，0≤x1+x2≤1002x1≤x2+32x1≥0x2≤10v：（v，u）∈AB. Dezs oBogaetal. /《理论与计算科学》选编264（5）（2011）2335Lplp; GR：：ArcMapLp：：Col>f（g）;lp.addColSet（f）;//目标函数Lp：：Expr obj;for （ GR ： ： OutArcIt a （ g ， src ） ; a ！ = 无 效 ;++a ）obj+=f[a]; for（GR：：InArcIt a（g，src）; a！= int [a];int [b]; int [a];lp.obj（）;//流量守恒约束for（GR：：NodeIt v（g）; v！= ++v）{if（v == s ||v ==t）continue;Lp：：Expr expr;for（GR：：OutArcIt a（g，v）; a！=无效; ++a）expr +=f[a]; for（GR：：InArcIt a（g，v）; a！= ++a）expr -= f[a];lp.addRow（expr == 0）;}//容量限制for（GR：：ArcIt a（g）; a！= ++a）{int n = nums（f[a]，n）;int n = nums（f[a]，n）;}//求出LP.solve（）;图第六章使用LEMON的LP接口解决最大流问题的示例代码LEMON图形格式（LGF）包括不同的部分，例如，有向图存储在@nodes和@arcs部分中。这些部分使用面向列的各节的第一行将名称与这些地图相关联，这些地图可用于指代它们。请注意，这个简单的想法使得在任何位置使用新映射（列）扩展文件成为可能，而无需修改处理代码。标签映射扮演着一个特殊的角色，它们必须存储唯一的值，这些值反过来可以用来引用文件中的节点和弧。 前两列是匿名的，它们分别表示源节点和目标节点。@nodes标签坐标0（20，100）1...(40，120）41@arcs(600 100）标签长度0 10 160 21122 12...36 4121232021@属性源% 0靶标41标题“最短路径问题”这个LGF文件可以使用digraphReader（）函数和几个命名参数来处理，如下所示。ListDigraph g;ListDigraph：：NodeMap dim2：：Point int> > coord（g）; ListDigraph：：ArcMapint> length（g）; ListDigraph：：Node src;std：：String title;digraphReader（g，“input.lgf”）.nodeMap（“coord”，coord）.arcMap（“length”，length）36B. Dezs oBogaetal. /《理论与计算科学》选编264（5）（2011）23.attribute（“caption”，title）.node（“source”，src）return（）;3实现细节本节介绍LEMON的部分实现细节，以及演示所应用技术的特定代码示例3.1向量中的邻接列表LEMON的一般图类型在内部将邻接列表存储在std：：vectors中，并使用向量索引作为节点和弧的标识符。Node和Arc对象存储这些索引，因此对于它们中的每一个，可以在恒定时间内查找为 举例来说，的 以下 代码 片段 来 从 的 来源智能方向图。构造Node T{int first_in;//第一个传入弧的索引int first_out;//第一个传出弧的索引};构造ArcT {int target，source;//结束节点的索引intnext_in;//下一个传入弧的索引intnext_out;//下一个传出弧的索引};std：：vector NodeT>nodes;std：：vector ArcT>arcs;给定节点的传出弧上的迭代开始于查找相应的NodeT项，其第一个传出成员存储第一个弧的索引。之后，每个步骤从当前ArcT对象读取下一个输出值以获得下一个弧的索引，如果当前弧是最后一个弧，则为-1。传入的弧以相同的方式使用成员firstin和next in进行处理。这意味着事件弧是使用简单链表记录的，这些链表实际上存储在一个向量中。ListDigraph的实现方式类似，但它使用双向链表来维护节点和弧，以支持有效删除它们以及添加新元素。这些数据结构的一个主要优点是，每个节点和弧都与一个唯一的整数标识符相关联，这是实现有效外部映射的关键要求（见第2.3节）。另一方面，这种设计限制了图形数据结构的定制可能性，因为节点和弧必须存储在随机访问容器中。BGL应用另一种方法：它的主图类型，邻接列表类 是高度可定制的。容器类型可以通过模板参数分别指定节点列表和节点的关联边列表。在某些情况下，使用例如，将入射边存储在std：：set中允许对数时间查找给定目标节点的传出边。然而，由于缺乏自然分配的唯一整数标识符，因此很难使用外部映射，而外部映射通常B. Dezs oBogaetal. /《理论与计算科学》选编264（5）（2011）2337在图形算法中需要临时存储。3.2使用混合扩展图形接口设计通用图形概念的一个基本问题是，一个易于实现的概念应该需要最少数量的重叠功能，但这种方法强烈限制了接口的多功能性。这个矛盾是克服发展两级图的概念。在LEMON中，用户级图概念定义了广泛的成员函数和嵌套类，因此它们支持方便和灵活的使用。 对 另一方面，低级图概念仅定义了非常基本的功能性，例如，简化的基于功能的迭代。使用模板Mixin策略[33]将这些简单的接口扩展到用户级概念。 具体地说，如果一个类DigraphBase实现了低级接口，然后 DigraphExtender DigraphBase将 满足 的 要求 的 使用者─水平有向图概念。public class：//Node和Arc类classNode{. }的情况;class Arc {. } 的情况;//基本迭代void first（Node node）const;void next（Node node）const;...};扩展器将嵌套迭代器和映射类添加到图类型，以及观察变更所需的成员变量（参见第3.3节）。如果底层图类也定义了节点和弧添加或删除的函数，那么它们也会被重写以处理更改观察模板类型DigraphBase>public class： public String {//迭代器类publicNode { public：publicvoid run（const）{_graph.first（*this）;}public void run（）{_graph.next（*this）; return*this;}...私人：const DigraphExtender_graph;};...};3.3信令图变更回想一下2.3节，LEMON图映射是外部的、自动更新的数据结构。它们使用数组或std：：vector来实现，以确保高效的数据访问，这是地图最重要的设计目标。然而，当新的节点或弧被添加到相关联的图时，这些数据结构被扩展。38B. Dezs oBogaetal. /《理论与计算科学》选编264（5）（2011）23图和映射类型实现了观察者设计模式[15]，它们表示节点和弧集的变化。观察到的事件仅限于添加和删除一个或多个项，从头开始构建图，以及从中删除所有项。观察者从相应的AlterationNotifier Graph，Item>：：ObserverBase类继承，并且它们必须重写事件处理程序函数。图表包含每个项类型的AlterationNotifier C，I>public
我的内容管理
展开
