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
|