350 lines
12 KiB
C++
350 lines
12 KiB
C++
#ifndef GRAPH_H
|
||
#define GRAPH_H
|
||
|
||
#include "Array.h"
|
||
#include "DynamicArray.h"
|
||
#include "DynamicArrayList.h"
|
||
#include "LinkedQueue.h"
|
||
#include "LinkedStack.h"
|
||
#include "Object.h"
|
||
#include "SharedPointer.h"
|
||
#include "Sort.h"
|
||
#include <optional>
|
||
|
||
namespace Kylin {
|
||
|
||
/*ListGraph用*/
|
||
template <typename EdgeType>
|
||
struct Edge : public Object {
|
||
static constexpr size_t npos = static_cast<size_t>(-1);
|
||
Edge(size_t begin = npos, size_t end = npos) : begin(begin), end(end) {}
|
||
|
||
Edge(size_t begin, size_t end, const EdgeType &value) : begin(begin), end(end), value(value) {}
|
||
|
||
bool operator==(const Edge &obj) { return (begin == obj.begin) && (end == obj.end); }
|
||
|
||
bool operator!=(const Edge &obj) { return !(*this == obj); }
|
||
|
||
bool operator<(const Edge &obj) { return (value < obj.value); }
|
||
|
||
bool operator>(const Edge &obj) { return (value > obj.value); }
|
||
|
||
bool operator<=(const Edge &obj) { return !(*this > obj); }
|
||
size_t begin;
|
||
size_t end;
|
||
EdgeType value;
|
||
};
|
||
|
||
template <typename VertexType, typename EdgeType>
|
||
class Graph : public Object {
|
||
public:
|
||
virtual VertexType vertex(size_t index) const = 0;
|
||
virtual bool setVertex(size_t index, const VertexType &value) = 0;
|
||
virtual DynamicArray<size_t> adjacent(size_t index) const = 0;
|
||
virtual std::optional<EdgeType> edge(size_t start, size_t end) const = 0;
|
||
virtual bool setEdge(size_t start, size_t end, const EdgeType &value) = 0;
|
||
virtual bool removeEdge(size_t start, size_t end) = 0;
|
||
virtual size_t vertexCount() const = 0;
|
||
virtual size_t edgeCount() const = 0;
|
||
virtual size_t outDegree(size_t index) const = 0;
|
||
virtual size_t inDegree(size_t index) const = 0;
|
||
|
||
size_t degree(size_t index) const { return outDegree(index) + inDegree(index); }
|
||
|
||
bool asUndirected() {
|
||
bool ret = true;
|
||
auto vertexes = vertexCount();
|
||
for (size_t i = 0; (i < vertexes) && ret; i++) {
|
||
for (size_t j = 0; (j < vertexes) && ret; j++) {
|
||
auto edge1 = edge(i, j);
|
||
if (edge1) {
|
||
auto edge2 = edge(j, i);
|
||
ret = ret && edge2 && (edge1 == edge2);
|
||
}
|
||
}
|
||
}
|
||
return ret;
|
||
}
|
||
|
||
DynamicArrayList<Edge<EdgeType>> prim(const EdgeType &LIMIT) {
|
||
if (!asUndirected()) THROW_EXCEPTION(InvalidOperationException, "Graph must be undirectedgraph.");
|
||
auto vertexSize = vertexCount();
|
||
DynamicArrayList<Edge<EdgeType>> result(vertexSize - 1);
|
||
DynamicArray<size_t> edges(vertexSize);
|
||
DynamicArray<EdgeType> costs(vertexSize, LIMIT);
|
||
DynamicArray<bool> mark(vertexSize, false);
|
||
|
||
//以start为起点，查找邻边，获取权值。如果有最小的，则更新cost数组和edges邻边记录表。
|
||
auto updateCosts = [this, &mark, &costs, &edges](size_t start) {
|
||
auto adjacent = this->adjacent(start);
|
||
for (size_t j = 0; j < adjacent.size(); j++) {
|
||
auto end = adjacent[j];
|
||
auto newCost = *edge(start, end);
|
||
if (mark[end] == false && costs[end] > newCost) {
|
||
costs[end] = newCost;
|
||
edges[end] = start;
|
||
}
|
||
}
|
||
};
|
||
|
||
updateCosts(0);
|
||
mark[0] = true;
|
||
|
||
for (size_t i = 1; i < vertexSize; i++) {
|
||
|
||
//选取最小边，记录其终点
|
||
auto miniCost = LIMIT;
|
||
size_t end = static_cast<size_t>(-1);
|
||
for (size_t j = 0; j < vertexSize; j++) {
|
||
if (mark[j] == false && costs[j] < miniCost) {
|
||
miniCost = costs[j];
|
||
end = j;
|
||
}
|
||
}
|
||
if (end == static_cast<size_t>(-1)) break;
|
||
|
||
result.append(Edge(edges[end], end, miniCost));
|
||
mark[end] = true;
|
||
|
||
updateCosts(end); //已上次的end为start,更新cost数组
|
||
}
|
||
if (result.size() != (vertexSize - 1))
|
||
THROW_EXCEPTION(InvalidOperationException, "No enough edge for prim operation...");
|
||
return result;
|
||
}
|
||
|
||
DynamicArrayList<Edge<EdgeType>> kruskal() {
|
||
DynamicArrayList<Edge<EdgeType>> result(1);
|
||
auto edges = getUndirectedEdges();
|
||
if (edges.empty()) return result;
|
||
auto vertexSize = vertexCount();
|
||
|
||
DynamicArray<size_t> set(vertexSize);
|
||
for (size_t i = 0; i < vertexSize; i++) {
|
||
set[i] = i;
|
||
}
|
||
auto find = [&set](size_t index) {
|
||
while (index != set[index]) {
|
||
index = set[index];
|
||
}
|
||
return index;
|
||
};
|
||
|
||
Sort::quick(&edges[0], edges.size());
|
||
for (size_t i = 0; i < edges.size(); i++) {
|
||
auto beginRoot = find(edges[i].begin);
|
||
auto endRoot = find(edges[i].end);
|
||
if (beginRoot != endRoot) {
|
||
result.append(edges[i]);
|
||
set[endRoot] = beginRoot;
|
||
}
|
||
if (result.size() >= (vertexSize - 1)) break;
|
||
}
|
||
if (result.size() != vertexSize - 1)
|
||
THROW_EXCEPTION(InvalidOperationException, "No enough edge for kruskal operation...");
|
||
return result;
|
||
}
|
||
|
||
DynamicArray<size_t> breadthFirstSearch(size_t index) {
|
||
if (index < 0 || index >= vertexCount()) THROW_EXCEPTION(InvalidParameterException, "Index is invalid...");
|
||
LinkedQueue<size_t> queue;
|
||
LinkedQueue<size_t> ret;
|
||
DynamicArray<bool> visited(vertexCount(), false);
|
||
queue.enqueue(index);
|
||
while (queue.length() > 0) {
|
||
auto v = queue.dequeue();
|
||
if (visited[v]) continue;
|
||
auto aj = adjacent(v);
|
||
for (size_t j = 0; j < aj.length(); j++) {
|
||
queue.enqueue(aj.at(j));
|
||
}
|
||
ret.enqueue(v);
|
||
visited[v] = true;
|
||
}
|
||
return toArray(ret);
|
||
}
|
||
|
||
DynamicArray<size_t> depthFirstSearch(size_t index) {
|
||
if (index >= vertexCount()) THROW_EXCEPTION(InvalidParameterException, "Index is invalid...");
|
||
LinkedStack<size_t> stack;
|
||
LinkedQueue<size_t> ret;
|
||
DynamicArray<bool> visited(vertexCount(), false);
|
||
stack.push(index);
|
||
while (stack.size() > 0) {
|
||
auto v = stack.top();
|
||
stack.pop();
|
||
if (visited[v]) continue;
|
||
auto aj = adjacent(v);
|
||
for (auto value : aj) {
|
||
stack.push(value);
|
||
}
|
||
ret.enqueue(v);
|
||
visited[v] = true;
|
||
}
|
||
return toArray(ret);
|
||
}
|
||
|
||
DynamicArray<size_t> dijkstra(size_t begin, size_t end, const EdgeType &LIMIT) {
|
||
size_t vertexSize = vertexCount();
|
||
if (begin >= vertexSize || end >= vertexSize)
|
||
THROW_EXCEPTION(InvalidParameterException, "Parameter begin or end is invalid.");
|
||
LinkedStack<size_t> result;
|
||
DynamicArray<EdgeType> distance(vertexSize, LIMIT);
|
||
DynamicArray<bool> mark(vertexSize, false);
|
||
DynamicArray<size_t> path(vertexSize, static_cast<size_t>(-1));
|
||
|
||
for (size_t i = 0; i < vertexSize; i++) {
|
||
auto edge = this->edge(begin, i);
|
||
if (edge) {
|
||
distance[i] = *edge;
|
||
path[i] = begin;
|
||
}
|
||
}
|
||
mark[begin] = true;
|
||
|
||
for (size_t i = 1; i < vertexSize; i++) {
|
||
EdgeType mini = LIMIT;
|
||
size_t endIndex = static_cast<size_t>(-1);
|
||
for (size_t j = 0; j < vertexSize; j++) {
|
||
if (mark[j] == false && distance[j] < mini) {
|
||
endIndex = j;
|
||
mini = distance[j];
|
||
}
|
||
}
|
||
if (endIndex == static_cast<size_t>(-1)) break;
|
||
mark[endIndex] = true;
|
||
for (size_t j = 0; j < vertexSize; j++) {
|
||
if (mark[j] == false) {
|
||
auto edge = this->edge(endIndex, j);
|
||
if (edge && (*edge + distance[endIndex] < distance[j])) {
|
||
distance[j] = *edge + distance[endIndex];
|
||
path[j] = endIndex;
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
result.push(end);
|
||
size_t pos = end;
|
||
while (path[pos] != begin) {
|
||
pos = path[pos];
|
||
result.push(pos);
|
||
}
|
||
result.push(begin);
|
||
return toArray(result);
|
||
}
|
||
|
||
DynamicArray<int> floyd(int x, int y, const EdgeType &LIMIT) {
|
||
LinkedQueue<int> ret;
|
||
if ((x >= 0) && (x < vertexCount()) && (y >= 0) && (y < vertexCount())) {
|
||
DynamicArray<DynamicArray<EdgeType>> dist(vertexCount());
|
||
DynamicArray<DynamicArray<int>> path(vertexCount());
|
||
for (int k = 0; k < vertexCount(); k++) {
|
||
dist[k].resize(vertexCount());
|
||
path[k].resize(vertexCount());
|
||
}
|
||
for (int i = 0; i < vertexCount(); i++) { // A -1
|
||
for (int j = 0; j < vertexCount(); j++) {
|
||
auto edge = this->edge(i, j);
|
||
dist[i][j] = edge ? *edge : LIMIT;
|
||
path[i][j] = edge ? j : -1;
|
||
}
|
||
}
|
||
|
||
for (int k = 0; k < vertexCount(); k++) {
|
||
for (int i = 0; i < vertexCount(); i++) {
|
||
for (int j = 0; j < vertexCount(); j++) {
|
||
if (dist[i][k] + dist[k][j] < dist[i][j]) {
|
||
dist[i][j] = dist[i][k] + dist[k][j];
|
||
path[i][j] = path[i][k];
|
||
}
|
||
}
|
||
}
|
||
}
|
||
while ((x != -1) && (x != y)) {
|
||
ret.enqueue(x);
|
||
x = path[x][y];
|
||
}
|
||
|
||
if (x != -1) {
|
||
ret.enqueue(x);
|
||
}
|
||
if (ret.size() < 2) {
|
||
THROW_EXCEPTION(InvalidOperationException, "There is no path form x to y.");
|
||
}
|
||
|
||
} else {
|
||
THROW_EXCEPTION(InvalidParameterException, "Index<x,y> is invalid .");
|
||
}
|
||
return toArray(ret);
|
||
}
|
||
|
||
/* DFS递归版实现
|
||
static void DFS(Graph *graph,size_t index,Kylin::Array<bool> &visited,LinkedQueue<size_t> &ret) {
|
||
if((index>=0)&&(index<graph->vertexCount())) {
|
||
ret.add(index);
|
||
visited[index] = true;
|
||
auto aj = graph->adjacent(index);
|
||
for(size_t i=0;i<aj->length();i++){
|
||
if(visited[aj->at(i)]) continue;
|
||
DFS(graph,aj->at(i),visited,ret);
|
||
}
|
||
} else {
|
||
THROW_EXCEPTION(Kylin::InvalidParameterException,"Index is invalid...");
|
||
}
|
||
}
|
||
|
||
|
||
SharedPointer<Array<size_t>> DFS(size_t index) {
|
||
Kylin::DynamicArray<bool> visited(vertexCount(),false);
|
||
LinkedQueue<size_t> ret;
|
||
DFS(this,index,visited,ret);
|
||
return toArray(ret);
|
||
}
|
||
*/
|
||
protected:
|
||
template <typename T>
|
||
static DynamicArray<T> toArray(LinkedQueue<T> &queue) {
|
||
DynamicArray<T> ret(queue.length());
|
||
for (size_t i = 0; i < ret.length(); i++) {
|
||
ret[i] = queue.dequeue();
|
||
}
|
||
return ret;
|
||
}
|
||
|
||
template <typename T>
|
||
static DynamicArray<T> toArray(LinkedStack<T> &stack) {
|
||
DynamicArray<T> ret(stack.size());
|
||
for (size_t i = 0; i < ret.size(); i++) {
|
||
ret[i] = stack.pop();
|
||
}
|
||
return ret;
|
||
}
|
||
|
||
DynamicArrayList<Edge<EdgeType>> getUndirectedEdges() {
|
||
DynamicArrayList<Edge<EdgeType>> result(1);
|
||
if (!asUndirected()) return result;
|
||
auto vertexes = vertexCount();
|
||
for (size_t i = 0; i < vertexes; i++) {
|
||
for (size_t j = i + 1; j < vertexes; j++) {
|
||
auto e = edge(i, j);
|
||
if (e) {
|
||
result.append(Edge<EdgeType>(i, j, *e));
|
||
}
|
||
}
|
||
}
|
||
|
||
return result;
|
||
}
|
||
|
||
size_t findTerminalVertex(Array<size_t> &p, size_t v) {
|
||
while (p[v] != static_cast<size_t>(-1)) {
|
||
v = p[v];
|
||
}
|
||
return v;
|
||
}
|
||
}; // namespace Kylin
|
||
|
||
} // namespace Kylin
|
||
#endif // GRAPH_H
|