有向图的特定模式搜索和优化(3)
2.2基于有向图的服务组合及图论
有向图的特定模式搜索和优化在SOA中的应用
那么到底我们的有向图在服务组合中如何应用的，我认为服务组合可以用有向图的方式来建模，而如何优化服务组合，可以转换为对其中特定模式的搜索和优化。众所周知，建模在服务组合中是最重要的环节，服务是以封装为特定功能的实体，以业务作为他的核心理念，通过定义优质的接口，来实现约束以及控制彼此间进行的联系。同时，有向图来建模完全是可以独立于特定的技术和平台。服务具有可重用性，一个定义良好的有向图也可在多个业务流程的组装中使用。也正是因为SOA 中所有应用都是服务，基于SOA 的系统或操作平台可以采用有向图建模技术将中立的、单独的、封装已完善的服务组合成新的、更复杂的服务，从而实现数据共享。而且基于有向图建模的SOA的系统平台可以屏蔽或者忽略由于编程平台、操作系统以及实现代码的语言不同而造成的差异。[9]
基于SOA 服务的有向图图架构建模以一系列执行业务功能的服务为基础，通过服务的形式来表达企业需要在服务之间最优的使用资源。同时，对不同的组合进行策略搜索以及特定优化不仅实现异构环境中的消息、数据的交互和共享，还可以使业务流程变得更加灵活，从而快速，有效地满足生活中不断变化的业务需求。可见，利用有向图在服务组合中建模可以让被搭建的架构开始灵活多变起来。 这也就衍生了我们现在的课题，利用有向图来对服务组合进行建模，然后利用特定模式的识别进行搜索，并优化。
有向图：有向图是一个二元组<V,E>，其中1.V是非空集合，称为顶点集。2.E是V×V的子称为弧集。[10]
完全有向图：有n个顶点的有向图有n(n-1)条边，则此图称为完全有向图。在有 n个顶点的有向图中，每个顶点的度最大可达 2(n-1) [11]
图的遍历：图遍历也可以叫图的遍历，是数据结构中主要的内容。他表示的是从图中的任一顶点出发，开始对图中每一个顶点都访问且仅仅访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面：
1、 在图结构中，没有一个“自然”的首结点，图中任意一个顶点都可作为第一个被访问的结点。
2、在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。
3、在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。
4、在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。[12]
有向无环图：在图论中，如果一个有向图无法从任意顶点出发经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。因为有向图中一个点经过两种路线到达另一个点未必形成环，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。
拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）。 1. 每个顶点出现且只出现一次； 2. 若A在序列中排在B的前面，则在图中不存在从B到A的路径。 也可以定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中B出现在A的后面[13]。