directed.hpp 7.21 KB
Newer Older
Steffen Vogel's avatar
Steffen Vogel committed
1
2
3
4
/** A directed graph.
 *
 * @file
 * @author Daniel Krebs <github@daniel-krebs.net>
Steffen Vogel's avatar
Steffen Vogel committed
5
 * @copyright 2014-2020, Institute for Automation of Complex Power Systems, EONERC
Steffen Vogel's avatar
Steffen Vogel committed
6
7
 * @license GNU General Public License (version 3)
 *
8
 * VILLAScommon
Steffen Vogel's avatar
Steffen Vogel committed
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *********************************************************************************/

#pragma once

#include <map>
#include <list>
#include <memory>
#include <sstream>
#include <string>
#include <fstream>
#include <stdexcept>
#include <algorithm>

#include <villas/log.hpp>
#include <villas/graph/vertex.hpp>
#include <villas/graph/edge.hpp>


namespace villas {
namespace graph {


template<typename VertexType = Vertex, typename EdgeType = Edge>
class DirectedGraph {
public:

	using VertexIdentifier = Vertex::Identifier;
	using EdgeIdentifier = Edge::Identifier;
	using Path = std::list<EdgeIdentifier>;

	DirectedGraph(const std::string& name = "DirectedGraph") :
	    lastVertexId(0), lastEdgeId(0)
	{
55
		logger = logging.get(name);
Steffen Vogel's avatar
Steffen Vogel committed
56
57
58
59
	}

	std::shared_ptr<VertexType> getVertex(VertexIdentifier vertexId) const
	{
Steffen Vogel's avatar
Steffen Vogel committed
60
		if (vertexId >= lastVertexId)
Steffen Vogel's avatar
Steffen Vogel committed
61
62
63
64
65
66
67
68
69
70
			throw std::invalid_argument("vertex doesn't exist");

		// cannot use [] operator, because creates non-existing elements
		// at() will throw std::out_of_range if element does not exist
		return vertices.at(vertexId);
	}

	template<class UnaryPredicate>
	VertexIdentifier findVertex(UnaryPredicate p)
	{
Steffen Vogel's avatar
Steffen Vogel committed
71
		for (auto& v : vertices) {
Steffen Vogel's avatar
Steffen Vogel committed
72
73
74
			auto& vertexId = v.first;
			auto& vertex = v.second;

Steffen Vogel's avatar
Steffen Vogel committed
75
			if (p(vertex)) {
Steffen Vogel's avatar
Steffen Vogel committed
76
77
78
79
80
81
82
83
84
				return vertexId;
			}
		}

		throw std::out_of_range("vertex not found");
	}

	std::shared_ptr<EdgeType> getEdge(EdgeIdentifier edgeId) const
	{
Steffen Vogel's avatar
Steffen Vogel committed
85
		if (edgeId >= lastEdgeId)
Steffen Vogel's avatar
Steffen Vogel committed
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
			throw std::invalid_argument("edge doesn't exist");

		// cannot use [] operator, because creates non-existing elements
		// at() will throw std::out_of_range if element does not exist
		return edges.at(edgeId);
	}

	std::size_t getEdgeCount() const
	{ return edges.size(); }

	std::size_t getVertexCount() const
	{ return vertices.size(); }

	VertexIdentifier addVertex(std::shared_ptr<VertexType> vertex)
	{
		vertex->id = lastVertexId++;

		logger->debug("New vertex: {}", *vertex);
		vertices[vertex->id] = vertex;

		return vertex->id;
	}

	EdgeIdentifier addEdge(std::shared_ptr<EdgeType> edge,
	                       VertexIdentifier fromVertexId,
	                       VertexIdentifier toVertexId)
	{
		// allocate edge id
		edge->id = lastEdgeId++;

		// connect it
		edge->from = fromVertexId;
		edge->to = toVertexId;

		logger->debug("New edge {}: {} -> {}", *edge, edge->from, edge->to);

		// this is a directed graph, so only push edge to starting vertex
		getVertex(edge->from)->edges.push_back(edge->id);

		// add new edge to graph
		edges[edge->id] = edge;

		return edge->id;
	}


	EdgeIdentifier addDefaultEdge(VertexIdentifier fromVertexId,
	                              VertexIdentifier toVertexId)
	{
		// create a new edge
		std::shared_ptr<EdgeType> edge(new EdgeType);

		return addEdge(edge, fromVertexId, toVertexId);
	}

	void removeEdge(EdgeIdentifier edgeId)
	{
		auto edge = getEdge(edgeId);
		auto startVertex = getVertex(edge->from);

		// remove edge only from starting vertex (this is a directed graph)
		logger->debug("Remove edge {} from vertex {}", edgeId, edge->from);
		startVertex->edges.remove(edgeId);

		logger->debug("Remove edge {}", edgeId);
		edges.erase(edgeId);
	}

	void removeVertex(VertexIdentifier vertexId)
	{
		// delete every edge that start or ends at this vertex
		auto it = edges.begin();
Steffen Vogel's avatar
Steffen Vogel committed
158
		while (it != edges.end()) {
Steffen Vogel's avatar
Steffen Vogel committed
159
160
161
162
163
			auto& edgeId = it->first;
			auto& edge = it->second;

			bool removeEdge = false;

Steffen Vogel's avatar
Steffen Vogel committed
164
			if (edge->to == vertexId) {
Steffen Vogel's avatar
Steffen Vogel committed
165
166
167
168
169
170
171
172
173
				logger->debug("Remove edge {} from vertex {}'s edge list",
				              edgeId, edge->from);

				removeEdge = true;

				auto startVertex = getVertex(edge->from);
				startVertex->edges.remove(edge->id);
			}

Steffen Vogel's avatar
Steffen Vogel committed
174
			if ((edge->from == vertexId) or removeEdge) {
Steffen Vogel's avatar
Steffen Vogel committed
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
				logger->debug("Remove edge {}", edgeId);
				// remove edge from global edge list
				it = edges.erase(it);
			} else {
				++it;
			}
		}

		logger->debug("Remove vertex {}", vertexId);
		vertices.erase(vertexId);
	}

	const std::list<EdgeIdentifier>&
	vertexGetEdges(VertexIdentifier vertexId) const
	{ return getVertex(vertexId)->edges; }


	using check_path_fn = std::function<bool(const Path&)>;

	static bool
	checkPath(const Path&)
	{ return true; }

	bool getPath(VertexIdentifier fromVertexId,
	             VertexIdentifier toVertexId,
	             Path& path,
	             check_path_fn pathCheckFunc = checkPath)
	{
Steffen Vogel's avatar
Steffen Vogel committed
203
		if (fromVertexId == toVertexId) {
Steffen Vogel's avatar
Steffen Vogel committed
204
205
206
207
208
			// arrived at the destination
			return true;
		} else {
			auto fromVertex = getVertex(fromVertexId);

Steffen Vogel's avatar
Steffen Vogel committed
209
			for (auto& edgeId : fromVertex->edges) {
Steffen Vogel's avatar
Steffen Vogel committed
210
211
212
213
				auto edgeOfFromVertex = getEdge(edgeId);

				// loop detection
				bool loop = false;
Steffen Vogel's avatar
Steffen Vogel committed
214
				for (auto& edgeIdInPath : path) {
Steffen Vogel's avatar
Steffen Vogel committed
215
					auto edgeInPath = getEdge(edgeIdInPath);
Steffen Vogel's avatar
Steffen Vogel committed
216
					if (edgeInPath->from == edgeOfFromVertex->to) {
Steffen Vogel's avatar
Steffen Vogel committed
217
218
219
220
221
						loop = true;
						break;
					}
				}

Steffen Vogel's avatar
Steffen Vogel committed
222
				if (loop) {
Steffen Vogel's avatar
Steffen Vogel committed
223
224
225
226
227
228
229
230
					logger->debug("Loop detected via edge {}", edgeId);
					continue;
				}

				// remember the path we're investigating to detect loops
				path.push_back(edgeId);

				// recursive, depth-first search
Steffen Vogel's avatar
Steffen Vogel committed
231
				if (getPath(edgeOfFromVertex->to, toVertexId, path, pathCheckFunc) and
Steffen Vogel's avatar
Steffen Vogel committed
232
233
234
235
236
237
238
239
240
241
242
243
244
				   pathCheckFunc(path)) {
					// path found, we're done
				    return true;
				} else {
					// tear down path that didn't lead to the destination
					path.pop_back();
				}
			}
		}

		return false;
	}

245
	void dump(const std::string& fileName = "") const
Steffen Vogel's avatar
Steffen Vogel committed
246
247
	{
		logger->info("Vertices:");
Steffen Vogel's avatar
Steffen Vogel committed
248
		for (auto& v : vertices) {
Steffen Vogel's avatar
Steffen Vogel committed
249
250
251
252
			auto& vertex = v.second;

			// format connected vertices into a list
			std::stringstream ssEdges;
Steffen Vogel's avatar
Steffen Vogel committed
253
			for (auto& edge : vertex->edges) {
Steffen Vogel's avatar
Steffen Vogel committed
254
255
256
257
258
259
260
				ssEdges << getEdge(edge)->to << " ";
			}

			logger->info("  {} connected to: {}", *vertex, ssEdges.str());
		}

		std::fstream s(fileName, s.out | s.trunc);
Steffen Vogel's avatar
Steffen Vogel committed
261
		if (s.is_open()) {
Steffen Vogel's avatar
Steffen Vogel committed
262
263
264
265
			s << "digraph memgraph {" << std::endl;
		}

		logger->info("Edges:");
Steffen Vogel's avatar
Steffen Vogel committed
266
		for (auto& e : edges) {
Steffen Vogel's avatar
Steffen Vogel committed
267
268
269
			auto& edge = e.second;

			logger->info("  {}: {} -> {}", *edge, edge->from, edge->to);
Steffen Vogel's avatar
Steffen Vogel committed
270
			if (s.is_open()) {
Steffen Vogel's avatar
Steffen Vogel committed
271
272
273
274
275
276
277
278
279
				auto from = getVertex(edge->from);
				auto to = getVertex(edge->to);

				s << std::dec;
				s << "  \"" << *from << "\" -> \"" << *to << "\""
				  << " [label=\"" << *edge << "\"];" << std::endl;
			}
		}

Steffen Vogel's avatar
Steffen Vogel committed
280
		if (s.is_open()) {
Steffen Vogel's avatar
Steffen Vogel committed
281
282
283
284
285
286
287
288
289
290
291
292
			s << "}" << std::endl;
			s.close();
		}
	}

protected:
	VertexIdentifier lastVertexId;
	EdgeIdentifier lastEdgeId;

	std::map<VertexIdentifier, std::shared_ptr<VertexType>> vertices;
	std::map<EdgeIdentifier, std::shared_ptr<EdgeType>> edges;

293
	Logger logger;
Steffen Vogel's avatar
Steffen Vogel committed
294
295
};

Steffen Vogel's avatar
Steffen Vogel committed
296
} /* namespace graph */
297
} /* namespace villas */