一种求有向图中任意两顶点之间的有向子图算法

本文给出了求有向图中任意两顶大、之间的有向子图算法．该算法改善了求任意两顶．大之间的最短路径的时间复杂度．且有利于有向阁的局部优化。     

一种求有向图中任意两项点之间的有向子图算法

本文给出了求有向图中任意两项之间的有向子图算法。该算法改善了求任意两顶点之 间的最短路径的时间复杂度，且有利于有向图的局部优化。     

一种表示有向图的表方法及其应用

图的表示方法很多,各有其优缺点.采用不同的表示方法,可获得图的不同的时空性能.本文阐述了图的一种新表示方法,该方法用一种命名规则将有向图表示为节点标签表,给出了由节点标签表产生节点链的算法.并用这种称为表方法研究了有向图的回路性质,特别地将它应用于研究de Bruijn回路、欧拉回路和哈密顿回路,给出了计算欧拉回路和哈密顿回路的新方法.本研究表明该方法具有较好的理论和实用价值.     

有向图k顶点导出子图的DNA粘贴算法

在经典的电子计算中,有向图k顶点导出子图是一个高度复杂的问题。DNA计算是近年来发展的以DNA为载体求解计算问题的非经典计算技术。文中研究了使用DNA计算解决有向图k顶点导出子图的问题,从而提出了一种在粘贴机上运行的子图生成算法。首先,以粘贴机的标准生化元操作作为算法调用的基本算子;其次,使用顺序与循环等程序结构,把上述基本算子按照一定的逻辑方式组织起来;最后,读取生化反应结果,即可获得给定有向图的所有k顶点导出子图。仿真实验结果表明,与经典算法相比,新算法在理想条件下大幅缩短了子图生成时间。     

基于出租车轨迹数据的最优路径规划方法

针对传统的路径规划算法并不一定能计算得到现实中最优路径的问题,提出一种融合了出租车驾驶经验并以时间为度量的路径规划算法。该算法的实现是将路径规划这个以计算为中心的技术变为以数据为中心的数据驱动挖掘技术。首先,从大量的出租车轨迹数据中提取真实的载人轨迹数据,并将载人轨迹数据匹配到路网数据中;然后,根据地图匹配结果计算路段的访问频次,选取前Top-k个路段作为热点路段;其次,计算热点路段间行车轨迹的相似度,对轨迹进行聚类分析,在路网的基础上构建该k个路段的热点路段图;最后,使用一种改进的A^*算法实现路径规划。实验结果表明,与传统的最短路径规划算法和基于驾驶经验路网分层的路径规划算法相比,所提出的基于热点路段图的路径规划方法有效地缩短规划路径的长度及路径行驶时间,提高路径规划的用时效率。     

求有向图的所有Hamilton回路的新方法

引入了单源单汇线性有向k-部图，设计了该结构上的删除算法、合并算法和输出算法，在此基础上给出了判断有向图是否含有H回路的多项式时间算法和计算H回路数的多项式时间算法，给出了求解有向图的所有H回路算法，并通过实例验证了算法的有效性，解决了H回路的判定、计数和求解问题。     

大规模路网图下关键词覆盖最优路径查询优化

游客倾向于采用个性化的旅游路线,规划这样的路线需要综合考量路径长度、路径开销和路径覆盖的兴趣点.关键词覆盖最优路径查询（KOR）就是用于规划这样的路线的一类查询,其处理过程通常包括预处理和路径拓展.由于路网图规模的不断扩大,现有算法预处理所需内存开销急剧上升,由于内存不足,导致较大规模的路网不能处理;路径拓展搜索空间快速膨胀,应用场景可扩展性与查询实时性难以保证.针对这些问题,提出一种大规模路网图下关键词覆盖最优路径查询算法KORL.KORL在预处理阶段将路网划分为若干子图,仅保存子图内路径和子图之间路径的信息,以减小预处理所需内存.在路径拓展阶段,综合运用最小代价剪枝、近似支配剪枝、全局优先拓展和关键词顶点拓展等策略对现有算法进行优化,以高效地搜索近似最优解.采用美国各地区的路网图,在16G内存环境下进行实验,突破了现有算法只能处理顶点数不超过25K路网图的限制.实验结果表明,KORL算法具有良好的可扩展性.     

车辆行驶最优路径优化算法设计

针对实际交通路网的特点,对道路网络模型、路网数据库的结构建设、最优路径优化算法等问题进行了研究.建立了体现城市道路交通的方向性及交叉口延误和限制的新城市路网模型,该模型利用交叉口、路段等基本构成要素描述道路网络,利用节点--弧段联合结构描述路段特性,再用图论中的有向图思想将路网抽象成数学模型描述;基于经典高效的狄杰斯特拉(Dijkstra)算法,设计了一种可应用于实际道路网络中的最优路径算法--改进的狄杰斯特拉算法,采用该算法可求解带有转向延误和限制的最优路径问题.     

制服调换问题中的路圈子图与圈包装研究

利用制服型号数有限这一特征,对制服调换(UE)问题和以物易物的制服调换(BUE)问题各给出一个快速的线性时间算法.在常量阶有向图上,将BUE转化为一个顶点容量约束的整值最大环流问题,提出其整数线性规划表示,论证其可行域的整性.证明BUE的最优解必为对应UE的一个最优解子图.实验结果表明,UE和BUE的渐进最优值相同.     

一种新的基于递归分解的图可达性查询算法

针对现实中许多超大规模图可达性查询的问题,提出了一种新的基于递归分解的算法,即将原图递归分解成一系列生成树和剩余图两类子图,并通过分别查询这两类子图来减少查询开销.相比于区间标记、链分解、2-hop标签和路径树等传统算法,该算法不仅空间开销更小,且时间复杂度更低.仿真实验表明,该算法对处理大规模有向图可达性问题上存储规模更小且查询效率更高.     

图论在网络的可靠性分析中的应用——对基于 1-critical-Path subset网络的性能分析

本文对一种网络流模型的可靠性进行分析 .在这个模型中 ,我们考虑一对源节点和汇节点的图 ,它的弧是随机失效的 .当网络最大流大于正常工作流 ,我们就说系统是正常工作的 .考虑正常工作流的一种特殊情况 ,这里 ,所有的弧都具有相同的容量 .在这种特殊的情况中 ,潜在的系统是 1- critical的 ,也就是说 ,所有的弧的最小截大小为 2 .此时 ,问题转化为在有向图中 ,求所有的失效弧都在同一条路径上的概率 ,而这个问题可以用多项式算法来解决     

Aesthetics-based Graph Layout for Human Consumption

Automatic graph layout is an important and long-studied problem. The basic straight-edge graph layout problem is to find spatial positions for the nodes of an input graph that maximize some measure of desirability. When graph layout is intended for human consumption, we call this measure of desirability an aesthetic. We seek an algorithm that produces graph layouts of high aesthetic quality not only for general graphs, but also for specific classes of graphs, such as trees and directed acyclic graphs. The Aesthetic Graph Layout (AGLO) approach described in this paper models graph layout as a multiobjective optimization problem, where the value of a layout is determined by multiple user-controlled layout aesthetics. The current AGLO algorithm combines the power and flexibility of the simulated annealing approach of Davidson and Harel (1989) with the relative speed of the method of Fruchterman and Reingold (1991). In addition, it is more general, and incorporates several new layout aesthetics to support new layout styles. Using these aesthetics, we are able to produce pleasing displays for graphs on which these other methods flounder.     

Partitioning road networks using density peak graphs: Efficiency vs. accuracy

Road traffic networks are rapidly growing in size with increasing complexities. To simplify their analysis in order to maintain smooth traffic, a large urban road network can be considered as a set of small sub-networks, which exhibit distinctive traffic flow patterns. In this paper, we propose a robust framework for spatial partitioning of large urban road networks based on traffic measures. For a given urban road network, we aim to identify the different sub-networks or partitions that exhibit homogeneous traffic patterns internally, but heterogeneous patterns to others externally. To this end, we develop a two-stage algorithm (referred as FaDSPa) within our framework. It first transforms the large road graph into a well-structured and condensed density peak graph (DPG) via density based clustering and link aggregation using traffic density and adjacency connectivity, respectively. Thereafter we apply our spectral theory based graph cut (referred as α-Cut) to partition the DPG and obtain the different sub-networks. Thus the framework applies the locally distributed computations of density based clustering to improve efficiency and the centralized global computations of spectral clustering to improve accuracy. We perform extensive experiments on real as well as synthetic datasets, and compare its performance with that of an existing road network partitioning method. Our results show that the proposed method outperforms the existing normalized cut based method for small road networks and provides impressive results for much larger networks, where other methods may face serious problems of time and space complexities.     

结合因子图的多目的地地图布局优化

目的提出一种结合因子图的多目的地地图生成方法。方法首先,由用户选择多个感兴趣的目的地,系统根据相应规则自动地选择与目的地最相关的路线。然后,通过定义一组衡量布局质量的约束规则,采用因子图方法将定义的每条规则编码成因子,并采用Metropolis Hastings算法对由因子图构建得到的目标分布函数进行采样得到符合约束规则的多目的地地图。结果实验结果表明,使用这种方法得到的多目的地地图,可以在同一显示空间中显示多个目的地之间的道路信息,同时又保留了各目的地区域之间的拓扑和空间关系。结论提出的多目的地地图能有效地为用户提供导航,解决了当前在线地图无法在同一视野中为用户提供空间距离较远的区域道路信息的问题。     

多视角融合的时空动态图卷积网络城市交通流量预测

城市交通流量预测是构建绿色低碳、安全高效的智能交通系统的重要组成部分.时空图神经网络由于具有强大的时空数据表征能力,被广泛应用于城市交通流量预测.当前时空图神经网络在城市交通流量预测中仍存在以下两方面局限性:1)直接构建静态路网拓扑图对城市空间相关性进行表示,忽略了节点的动态交通模式,难以表达节点流量之间的时序相似性,无法捕获路网节点之间在时序上的动态关联.2)只考虑路网节点的局部空间相关性,忽略节点的全局空间相关性,无法建模交通路网中局部区域和全局空间之间的依赖关系.为打破上述局限性,本文提出了一种多视角融合的时空动态图卷积模型用于预测交通流量.首先,从静态空间拓扑和动态流量模式视角出发,构建路网空间结构图和动态流量关联图,并使用动态图卷积学习节点在两种视角下的特征,全面捕获城市路网中多元的空间相关性.其次,从局部视角和全局视角出发,计算路网的全局表示,将全局特征与局部特征融合,增强路网节点特征的表现力,发掘城市交通流量的整体结构特征.接下来,设计了局部卷积多头自注意力机制来获取交通数据的动态时间相关性,实现在多种时间窗口下的准确流量预测.最后,在四种真实交通数据上的实验结果证明了本文模型的有效性和准确性.     

构建贝叶斯网络本质图的新方法

等价类学习是贝叶斯网络结构学习的一个重要分支,而本质图是贝叶斯网络等价类的图形表示,是进行等价类学习的有力工具。针对求解贝叶斯网络结构本质图存在的繁琐问题,提出了一种构建贝叶斯网络本质图的组合算法。该算法从初始非循环有向图开始,对所有有向边进行排序,保持V-结构中的边不变,将不参与V-结构的有向边转化为无向边,依次根据三条规则判定各条无向边在本质图中的方向。给出了算法的理论证明,通过具体案例分析验证了算法的有效性。     

级连层次图的网络最大流算法研究

给出一种通过构造网络级连层次图的方法,来间接求出最大网络流的算法。对于给定的有n个顶点,e条边的网络N=G,s,t,C,该算法可在On2时间内快速求出流经网络N的最大网络流及达最大流时的网络流。     

基于自适应门控图神经网络的交通流预测

交通流预测是智能交通系统中的重要组成部分,由于交通数据的复杂性,长期而又准确的交通流预测一直是时间序列预测中最具挑战性的任务之一。近年来,研究人员将基于图神经网络的时空图建模方法应用于交通流预测任务,并取得了良好的预测性能。然而,现有的图建模方法仅通过预定义的邻接结构反映道路网络中的空间依赖关系,忽略了各节点之间的序列关联关系对预测的重要性。针对这一局限性,提出了一种自适应门控图神经网络（Ada-GGNN）,其核心为通过空间传递模块同时捕获道路网络的空间结构及自适应的时序相关性,并通过门控机制学习节点上的时间序列特征。在两个真实交通网络数据集PeMSD7和Los-loop上的实验结果证明了该模型具有更优越的性能。     

Automating the Detection and Simplification of Junctions in Road Networks

A road network is cartographically drawn in varying levels of detail depending on the resolution or scale of the output graphic. In automated generalization, the challenge is in deriving generalized forms of a road network, appropriate for the intended target scale and to achieve this with minimum intervention from the user. This paper presents a method for the detection and simplification of road junctions as part of that process. Road junctions within the network are identified using a combination of spatial clustering and graph theory. The junctions are simplified using a combination of contractions and restrictions of the graph. Consideration is given to ways in which attribute and cartometric information can be used both to modify the behavior of the algorithm, and to influence the choice of other generalization algorithms. This algorithm is considered to be part of a growing number of generalization algorithms that can be used to derive generalized products from single detailed database. The success and limitations are discussed and future developments are proposed.     

大图上跳数受限的可达查询算法研究与优化

判断有向图上两个顶点之间是否存在一条路径是一个经典问题,而对于一些路由规划和图分析等实际应用,要求查找是否存在跳数受限的可达路径,这是一个变种的图可达查询问题.对于大图上跳数受限的查询算法,不仅仅要对大图查询的时间效率和空间效率进行权衡,而且还要利用跳数受限的特性进行优化.普通的可达查询算法存在小度数顶点索引项占用空间过多的问题,造成空间浪费严重.为此我们提出了一种面向跳数受限的2-hop部分索引方法,采用改进的索引方法并结合局部搜索,实现跳数受限的有效可达性查询.实验结果表明,在Orkut社交网络数据集上与已有算法相比,该算法索引空间节省了32％,同时查询时间略微增加,使得我们算法可以计算更大规模图的跳数受限可达问题.