C++开源算法库OpenSAL1.1(Open Standardized Algorithm Library)——动态链接库

#ifndef graphConst #define graphConst /*//Copyright Statements: This source code file is completed as part of the Open SAL(Open Standardized Algorithm Library) by Ming Li during the summer vocation of 2013 at College of Information Science and Engineering, Central South University. All rights reserved. No part of these files may be reproduced or transmitted in any form or by any means without permission from the author. While, you are permitted to download this Library and its instruction manual freely at http://www.oschina.net/code/snippet_1259068_24335# and use it by yourself. If you find some bugs or problems of this Library,you are welcomed to email me(limingcsu @foxmail.com). If you want to know any details or updates about this Library or would like to discuss issues about algorithms with enthusiasts,you can apply to join the QQ group(222576709). */// #include <vector> #include <list> #include <queue> #include "mySort.h" #include "nonIntersectSet.h" #include "fibonacciHeap.h" #include "hash.h" #include "numberTheory.h" #include "myException.h" #include "array.h" /*图论中通用数据结构和图处理的通用算法*/ namespace lmtc{ //边的类模板，一般指有向边。 template<typename T> class Edge{ public: unsigned int vSt; unsigned int vEd; T data; public: Edge(unsigned int v_st,unsigned int v_ed,const T &t):vSt(v_st),vEd(v_ed),data(t){} Edge(unsigned int v_st,unsigned int v_ed):vSt(v_st),vEd(v_ed),data(){} bool operator==(const Edge<T> &e)const{return vSt==e.vSt&&vEd==e.vEd;} }; /*图论类，包含图论中常用算法，都以静态接口形式呈现 邻接矩阵（有向图或无向图，无向图的边出现两次）用lmtc::Array<T>(2,vN,vN)表示,T表示权类型，vN表示顶点数。值为零表示不连接，否则元素值表示权重 邻接表类型（有向图或无向图，无向图的边出现两次）std::vector<std::list<Edge<T>>>*/ class Graph{ public: //由邻接矩阵ajacencyMatrix转换成邻接表，结果存至ajacencyList。如果ajacencyMatrix不符合邻接矩阵要求，将置空ajacencyList。 //O(V*V) template<typename T> static void ajacencyMatrixToList(const Array<T> &ajacencyMatrix,std::vector<std::list<Edge<T>>> &ajacencyList); //转置邻接表ajacencyList，结果存至transposedAjacencyList。必须保证ajacencyList为正确的邻接表。 //O(V+E) template<typename T> static void transposeAjacencyList(const std::vector<std::list<Edge<T>>> &ajacencyList,std::vector<std::list<Edge<T>>> &transposedAjacencyList); /*广度和深度优先遍历及基于此的基本图算法*/ //通用广度优先遍历（整个广度优先森林），需保证邻接表正确，该接口没有任何实际功能，仅作为待重用代码。 template<typename T> static void bfs(const std::vector<std::list<Edge<T>>> &ajacencyList,const unsigned int s=0); //通用深度优先遍历（整个深度优先森林），需保证邻接表正确，该接口没有任何实际功能，仅作为待重用代码。 template<typename T> static void dfs(const std::vector<std::list<Edge<T>>> &ajacencyList,const unsigned int s=0); //利用深度优先遍历确定有向图或者无向图是否存在回路，需保证邻接表正确。需要利用参数isDirectedGraph区分有向图或者无向图。 //O(E) template<typename T> static bool hasLoop(const std::vector<std::list<Edge<T>>> &ajacencyList,bool isDirectedGraph=true); //通用深度优先遍历进行有向图拓扑排序，需保证邻接表正确。返回拓扑有序序列向量，如果是有环图，则返回空向量。 //O(E+V) template<typename T> static std::vector<unsigned int> topologicalSort(const std::vector<std::list<Edge<T>>> &ajacencyList); //利用深度优先遍历找出有向图（无向图亦可）所有强连通分支，需保证邻接表ajacencyList正确。结果存在strongConnectComponents //O(E+VlgV)，VlgV时间主要花在第二次深度优先遍历时按时间戳排序。 template<typename T> static void computeStrngConctComps(const std::vector<std::list<Edge<T>>> &ajacencyList,std::vector<std::vector<unsigned int>> &strongConnectComponents); //利用变形的深度优先遍历计算有向图或无向图的欧拉环，需保证邻接表ajacencyList正确。存在欧拉环返回true（结果存于EulerCircuit），否则返回false（EulerCircuit置空）。 //O(V+E)，需要利用参数isDirectedGraph区分有向图或者无向图，当为无向图时利用散列进行边的逻辑删除，因此时间复杂度与有向图的是相同的。 template<typename T> static bool computeEulerCircuit(const std::vector<std::list<Edge<T>>> &ajacencyList,std::list<Edge<T>> &EulerCircuit,bool isDirectedGraph=true); /*最小生成树问题*/ //Kruskal计算无向图最小生成树，不连通则计算最小生成森林，允许图中有自环。采用不相交集合实现。 //O(ElgE) template<typename T> static T mstKruskal(const std::vector<std::list<Edge<T>>> &ajacencyList,std::vector<std::list<Edge<T>>> &mstAjacencyList); //Prim计算无向图最小生成树，不连通则计算最小生成森林，允许图中有自环。采用斐波那契堆实现。 //O(E+VlgV) template<typename T> static T mstPrim(const std::vector<std::list<Edge<T>>> &ajacencyList,std::vector<std::list<Edge<T>>> &mstAjacencyList); /*最短路径问题*/ //Bellman-Ford算法，s表示原顶点序号，可判断是否有负回路（有向图或者无向图），允许图中有负权边。 //最短路径树结果存于父节点向量p和距离向量d，如果有负回路则p和d向量表示找到的树并非最短路径树且返回false，否则返回true。 //O(V*E) template<typename T> static bool shortestPathBellmanFord(const std::vector<std::list<Edge<T>>> &ajacencyList,const unsigned int s,std::vector<unsigned int> &p,std::vector<T> &d); //有向无回路图的单源最短路径，s表示原顶点序号，如果有回路则返回false且置空p、d向量，否则返回true。 //最短路径树结果存于父节点向量p和距离向量d，如果有回路则返回false，否则返回true。 //O(V+E) template<typename T> static bool shortestPathOfDag(const std::vector<std::list<Edge<T>>> &ajacencyList,const unsigned int s,std::vector<unsigned int> &p,std::vector<T> &d); //dijkstra算法（要求无负边），s表示原顶点序号，如果有负边则返回false且置空p、d向量，否则返回true。 //最短路径树结果存于父节点向量p和距离向量d。如果非源顶点的父节点为自身，则不存在其到源顶点的路径。 //O(E+VlgV) template<typename T> static bool shortestPathDijkstra(const std::vector<std::list<Edge<T>>> &ajacencyList,const unsigned int s,std::vector<unsigned int> &p,std::vector<T> &d); //利用快速矩阵乘法实现每对顶点间的最短路径，O(V^e*lgV),e<3。参见《算法导论p385》，略。 //Floyd-Warshall算法，假设输入图不存在负回路。 //最短路径森林结果存于父节点矩阵p和距离矩阵d。如果非源顶点的父节点为自身，则不存在其到源顶点的路径。 //O(V^3)。参见《算法导论p387》 template<typename T> static void shortestPathAllFloydWarshall(const std::vector<std::list<Edge<T>>> &ajacencyList,Array<unsigned int> &p,Array<T> &d); //Johnson算法，能够判断是否存在负回路。 //最短路径森林结果存于父节点矩阵p和距离矩阵d。如果非源顶点的父节点为自身，则不存在其到源顶点的路径。 //如果存在负回路，则置空p，d并返回false，否则返回true //O(V^2*lgV+VE)。参见《算法导论p391》 template<typename T> static bool shortestPathAllJohnson(const std::vector<std::list<Edge<T>>> &ajacencyList,Array<unsigned int> &p,Array<T> &d); /*最大流问题*/ //FordFulkerson_EdmondsKarp算法。思路为不断利用广度优先搜索寻找残余网络中的增广路径来增加流。 //要求ajacencyList无负边(负边可事先转成反向正边，但本算法不负责此转换），起点s和汇点t，算法将自动忽略自环和s的入边以及t的出边，最大流网络存于flow之中，返回最大流的值。 //O(V*E^2)。参见《算法导论p397-408》 template<typename T> static T maximumFlowFordFulkerson_EdmondsKarp(const std::vector<std::list<Edge<T>>> &ajacencyList,const unsigned int s,const unsigned int t,std::vector<std::list<Edge<T>>> &flow); //Relabel_To_Front算法。思路为不断对容许网络拓扑排序中第一个溢出节点进行压入和重标记操作以使之不再溢出。 //要求ajacencyList无负边(负边可事先转成反向正边，但本算法不负责此转换），起点s和汇点t，算法将自动忽略自环和s的入边以及t的出边，最大流网络存于flow之中，返回最大流的值。 //O(V^3)。参见《算法导论p411-425》 template<typename T> static T maximumFlowPushRelabelToFront(const std::vector<std::list<Edge<T>>> &ajacencyList,const unsigned int s,const unsigned int t,std::vector<std::list<Edge<T>>> &flow); //多源点多汇点网络流问题《算法导论p399》，最