基本信息
- 项目名称：
- 无向关系图结点定位软件
- 来源：
- 第十二届“挑战杯”省赛作品
- 小类：
- 信息技术
- 大类：
- 科技发明制作A类
- 简介：
- 《无向关系图结点定位软件》是将描述结点及其关系的无向关系图的文本文件或数据库文件读入，再经过软件确定结点在某个二维矩形区域内的坐标位置，最后按照这些坐标在屏幕上输出结点并按关系连线，得到连线清晰化的无向关系图的图形化显示结果，或者将这些坐标依照文本文件或数据库文件的形式保存输出，供下游软件使用。
- 详细介绍：
- 在计算机科学与技术中，描述一组对象之间的关系经常用无向图表示，而此类关系信息的获取形式往往是无向图的逻辑表示，如表格、数据库、邻接矩阵，这种逻辑表示很不直观，所以人们喜欢用平面上的图重新表示，将表示对象的结点用一个圆点或小圆圈表示，再将对象间的关系用一条条连接两个结点的线表示。这种图形化表示固然直观，但存在一个问题：如果一开始结点的位置摆放得不好，画连线时会产生纵横交错的结果，画出来的图关系不清晰，连线产生交叉、远跨或重叠。所以结点的定位很重要，如果有一种能保证连线清晰的结点自动定位方法，那么在结点位置确定之后，根据无向关系将一对对的结点用直线段连接起来就行了。这就是我们项目所要研究的无向关系图结点定位技术。 无向关系图结点定位软件主要用于基于无向图的关系模型如产品关联图、文档抄袭关系图、数据引用图、路由分布图、知识点依赖图、软件工程PERT图、组织关系图、模块关系图等的图形化输出，通过结点坐标的合理确定，使关系连线清晰美观，连通分支分离易辨。 我们可以将无向关系图结点定位技术植入软件工程、识别系统、Visio、Cisco Packet Tracer等应用技术、系统或软件中去，使这些应用技术、系统或软件更加自动化、智能化、高效率、实用化和人性化。
作品图片
作品专业信息
设计、发明的目的和基本思路、创新点、技术关键和主要技术指标
- 目的：在计算机科学与技术中，表示对象之间的关系通常用无向图表示。这种图形化表示固然直观，但存在一个问题：如果一开始结点的位置摆放得不好，画出来的图关系就会不清晰。如果有一个能保证连线清晰化的无向关系图结点定位软件，对一副关系混乱的无向图重新确定结点位置后能使关系图变得清晰美观，将很大程度上便于我们分析和理解无向关系图。而设计这款无向关系图结点定位软件就是本项目的目的。 基本思路：无向关系图结点定位软件采用图内割边、团内割点的识别技术，并基于树型结构实现区域划分，采用逐步清晰的方法，最终使无向关系图达到视觉上清晰的目的。 创新点：（1）采用割边割点识别技术，将连通图分解为团与子团后再定位。 （2）非迭代方法，直接定位，比遗传算法、模拟退火等进化算法要直接、快速得多。 技术关键和主要技术指标：软件采用割边割点识别技术，将连通图分解为团与子团后再定位，可以使最终显示的无向关系图的关系连线尽量不交叉、不远跨、不重叠，关系结点组汇聚成团，能清晰地看出结点间的连接关系和分组情况。定位结果既可以直接显示，又可以通过文件接口输出，支持文本文件和Access数据库两种格式。
科学性、先进性
- 本软件采用的无向关系图结点定位方法首先将无向关系图去除孤立点、分离连通分支，并通过识别割边将每个连通分支分解成一系列的团，每个团内无割边，这些团以树型结构连接，然后通过识别割点和虚连线将每个团分解成子团，每个子团内无割点，最后将子团内顶点均匀分布在一个圆环上。该方法具有实现方便，方法简单，运行高效，输出结果美观，易于并行化等优点。
获奖情况及鉴定结果
- 本项目是2009年度浙江省大学生科技创新活动计划（新苗人才计划）立项（项目编号：2009R424008）成果，该大学生科技创新活动计划项目已于2010年12月通过温州大学大学生科技评审委员会评审，并同意结题。 2011年3月在浙江省科技信息研究院做科技查新报告，查新结论：无向关系图结点定位软件在检索到的相关国内文献中未见具体述及。 2011年3月在浙江省电子产品检验所做软件鉴定评测。 2011年3月向中国版权保护中心申请软件著作权登记，流水号：2011R11L015531。 2011年4月向国家知识产权局专利局申请发明专利。
作品所处阶段
- 中试阶段
技术转让方式
- 软件销售，专利转让。
作品可展示的形式
- 实物、产品；现场演示。
使用说明,技术特点和优势,适应范围,推广前景的技术性说明,市场分析,经济效益预测
- 使用说明：本软件的功能是将一副无向关系图读入，通过结点坐标的合理定位使无向图关系连线清晰可辨，或者将定位后的无向图保存，供下游软件使用。 技术特点和优势：（1）定位方法模型简单，效率高，且属于确定性方法。（2）支持多种格式的无向关系图的数据文件。 适用范围及推广情景：我们可以将无向关系图结点定位软件植入软件工程、识别系统、Visio、Cisco Packet Tracer等应用技术、系统或软件中去，使这些应用技术、系统或软件更加自动化、智能化、高效率、实用化和人性化。我们也可以将本软件应用于数据挖掘、模式识别等领域。 市场分析和经济效益预测：一方面，Cisco Packet Tracer软件和Visio软件是应用很广泛的软件，但这两款软件没有提供关系清晰化的技术，而我们的软件弥补了这两款软件的不足，能使这两款软件使用起来更加方便。 另一方面，本软件能用于超市等机构的产品间数据挖掘，使产品间的关系直观、清晰，便于决策者做出正确的商业决策。
同类课题研究水平概述
- 目前，现有的无向关系图结点定位方法各有所长，也各有所短。他们主要分为两类，一类是基于最优化方法的结点定位方法，该方法的特点是将无向关系图结点定位问题转发为函数优化问题，用基于某种算法或模型求目标函数最优解的近似解，从而改变结点位置。该方法的的优点在于方法简单，易于实现，普遍适用于不同特点的无向图，缺点在于计算量大，最终结果不确定，且收敛性差。其中，基于遗传算法实现无向关系图结点定位的方法是该类方法中一种主流的方法。基于遗传算法实现无向关系图结点定位是将无向图结点定位问题转化为约束优化问题，即转化为计算某个带有约束条件的函数的最小值或最大值。不同的结点定位方法其实质在于设计不同的目标函数。但遗传算法属于概率算法，算法执行结果具有不确定性，同时，想要得到好的输出结果，需要经过相当长的时间演化，因此算法收敛性较差。 另一类方法是基于某类确定算法实现无向图结点定位的方法。该方法的特点是经过一个算法，最终确定结点的最后位置。相比于前者，该类方法的一个显著优点在于，计算量明显减小，且最终结点位置确定，不会随着执行的次数不同而不同。但设计一个算法适用于不同特点的无向图并非易事，这样的结点定位方法往往对满足某些特点的无向图才能达到很好的效果。其中，该类方法中，比较有代表性的是将无向图显示在环上，根据每个结点的加权值确定其所占有的扇形区域，并将每个结点布局在其扇区的中心线上的方法。
