summaryrefslogtreecommitdiff
path: root/dviware/dvisvgm/src/optimizer/DependencyGraph.hpp
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /dviware/dvisvgm/src/optimizer/DependencyGraph.hpp
Initial commit
Diffstat (limited to 'dviware/dvisvgm/src/optimizer/DependencyGraph.hpp')
-rw-r--r--dviware/dvisvgm/src/optimizer/DependencyGraph.hpp133
1 files changed, 133 insertions, 0 deletions
diff --git a/dviware/dvisvgm/src/optimizer/DependencyGraph.hpp b/dviware/dvisvgm/src/optimizer/DependencyGraph.hpp
new file mode 100644
index 0000000000..c9111b43d5
--- /dev/null
+++ b/dviware/dvisvgm/src/optimizer/DependencyGraph.hpp
@@ -0,0 +1,133 @@
+/*************************************************************************
+** DependencyGraph.hpp **
+** **
+** This file is part of dvisvgm -- a fast DVI to SVG converter **
+** Copyright (C) 2005-2019 Martin Gieseking <martin.gieseking@uos.de> **
+** **
+** 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 (at your option) 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/>. **
+*************************************************************************/
+
+#ifndef DEPENDENCYGRAPH_HPP
+#define DEPENDENCYGRAPH_HPP
+
+#include <map>
+#include <memory>
+#include <set>
+#include <vector>
+#include "../utility.hpp"
+
+template <typename T>
+class DependencyGraph {
+ struct GraphNode {
+ explicit GraphNode (const T &k) : key(k), dependent() {}
+
+ void addDependee (GraphNode *node) {
+ if (node) {
+ node->dependent = this;
+ dependees.insert(node);
+ }
+ }
+
+ void unlinkDependees () {
+ for (GraphNode *dependee : dependees)
+ dependee->dependent = nullptr;
+ dependees.clear();
+ }
+
+ void unlinkDependee (GraphNode *dependee) {
+ auto it = dependees.find(dependee);
+ if (it != dependees.end()) {
+ (*it)->dependent = nullptr;
+ dependees.erase(it);
+ }
+ }
+
+ T key;
+ GraphNode *dependent;
+ std::set<GraphNode*> dependees;
+ };
+
+ using NodeMap = std::map<T, std::unique_ptr<GraphNode>>;
+
+ public:
+ /** Inserts a new isolated node into the dependency graph. */
+ void insert (const T &key) {
+ if (!contains(key))
+ _nodeMap.emplace(key, util::make_unique<GraphNode>(key));
+ }
+
+ /** Inserts a new node to the graph and adds a dependency on an existing one to it.
+ * @param[in] key ID of new node to insert
+ * @param[in] dependantKey ID of node the new node should depend on */
+ void insert (const T &dependentKey, const T &key) {
+ if (!contains(key)) {
+ auto dependentIter = _nodeMap.find(dependentKey);
+ if (dependentIter != _nodeMap.end()) {
+ auto node = util::make_unique<GraphNode>(key);
+ dependentIter->second->addDependee(node.get());
+ _nodeMap.emplace(key, std::move(node));
+ }
+ }
+ }
+
+ /** Removes a node and all its dependents from the graph. */
+ void removeDependencyPath (const T &key) {
+ auto it = _nodeMap.find(key);
+ if (it != _nodeMap.end()) {
+ for (GraphNode *node = it->second.get(); node;) {
+ GraphNode *dependent = node->dependent;
+ node->unlinkDependees();
+ if (dependent)
+ dependent->unlinkDependee(node);
+ _nodeMap.erase(node->key);
+ node = dependent;
+ }
+ }
+ }
+
+ /** Returns the IDs of all nodes present in the graph. */
+ std::vector<T> getKeys () const {
+ std::vector<T> keys;
+ for (auto &entry : _nodeMap)
+ keys.emplace_back(entry.first);
+ return keys;
+ }
+
+ bool contains (const T &value) const {
+ return _nodeMap.find(value) != _nodeMap.end();
+ }
+
+ bool empty () const {
+ return _nodeMap.empty();
+ }
+
+#if 0
+ void writeDOT (std::ostream &os) const {
+ os << "digraph {\n";
+ for (auto it=_nodeMap.begin(); it != _nodeMap.end(); ++it) {
+ GraphNode *node = it->second;
+ if (node->dependent)
+ os << (node->key) << " -> " << (node->dependent->key) << ";\n";
+ else if (node->dependees.empty())
+ os << (node->key) << ";\n";
+ }
+ os << "}\n";
+ }
+#endif
+
+ private:
+ NodeMap _nodeMap;
+};
+
+#endif