This source file includes following definitions.
- AddNode
- RemoveNode
- AddEdge
- GetConstructionOrder
- GetDestructionOrder
- BuildConstructionOrder
- DumpAsGraphviz
#include "components/keyed_service/core/dependency_graph.h"
#include <algorithm>
#include <deque>
#include <iterator>
DependencyGraph::DependencyGraph() {}
DependencyGraph::~DependencyGraph() {}
void DependencyGraph::AddNode(DependencyNode* node) {
all_nodes_.push_back(node);
construction_order_.clear();
}
void DependencyGraph::RemoveNode(DependencyNode* node) {
all_nodes_.erase(std::remove(all_nodes_.begin(), all_nodes_.end(), node),
all_nodes_.end());
EdgeMap::iterator it = edges_.begin();
while (it != edges_.end()) {
EdgeMap::iterator temp = it;
++it;
if (temp->first == node || temp->second == node)
edges_.erase(temp);
}
construction_order_.clear();
}
void DependencyGraph::AddEdge(DependencyNode* depended,
DependencyNode* dependee) {
edges_.insert(std::make_pair(depended, dependee));
construction_order_.clear();
}
bool DependencyGraph::GetConstructionOrder(
std::vector<DependencyNode*>* order) {
if (construction_order_.empty() && !BuildConstructionOrder())
return false;
*order = construction_order_;
return true;
}
bool DependencyGraph::GetDestructionOrder(std::vector<DependencyNode*>* order) {
if (construction_order_.empty() && !BuildConstructionOrder())
return false;
*order = construction_order_;
std::reverse(order->begin(), order->end());
return true;
}
bool DependencyGraph::BuildConstructionOrder() {
std::deque<DependencyNode*> queue;
std::copy(all_nodes_.begin(), all_nodes_.end(), std::back_inserter(queue));
std::deque<DependencyNode*>::iterator queue_end = queue.end();
for (EdgeMap::const_iterator it = edges_.begin(); it != edges_.end(); ++it) {
queue_end = std::remove(queue.begin(), queue_end, it->second);
}
queue.erase(queue_end, queue.end());
std::vector<DependencyNode*> output;
EdgeMap edges(edges_);
while (!queue.empty()) {
DependencyNode* node = queue.front();
queue.pop_front();
output.push_back(node);
std::pair<EdgeMap::iterator, EdgeMap::iterator> range =
edges.equal_range(node);
EdgeMap::iterator it = range.first;
while (it != range.second) {
DependencyNode* dest = it->second;
EdgeMap::iterator temp = it;
it++;
edges.erase(temp);
bool has_incoming_edges = false;
for (EdgeMap::iterator jt = edges.begin(); jt != edges.end(); ++jt) {
if (jt->second == dest) {
has_incoming_edges = true;
break;
}
}
if (!has_incoming_edges)
queue.push_back(dest);
}
}
if (!edges.empty()) {
return false;
}
construction_order_ = output;
return true;
}
std::string DependencyGraph::DumpAsGraphviz(
const std::string& toplevel_name,
const base::Callback<std::string(DependencyNode*)>& node_name_callback)
const {
std::string result("digraph {\n");
std::deque<DependencyNode*> nodes;
std::copy(all_nodes_.begin(), all_nodes_.end(), std::back_inserter(nodes));
std::deque<DependencyNode*>::iterator nodes_end(nodes.end());
result.append(" /* Dependencies */\n");
for (EdgeMap::const_iterator it = edges_.begin(); it != edges_.end(); ++it) {
result.append(" ");
result.append(node_name_callback.Run(it->second));
result.append(" -> ");
result.append(node_name_callback.Run(it->first));
result.append(";\n");
nodes_end = std::remove(nodes.begin(), nodes_end, it->second);
}
nodes.erase(nodes_end, nodes.end());
result.append("\n /* Toplevel attachments */\n");
for (std::deque<DependencyNode*>::const_iterator it = nodes.begin();
it != nodes.end();
++it) {
result.append(" ");
result.append(node_name_callback.Run(*it));
result.append(" -> ");
result.append(toplevel_name);
result.append(";\n");
}
result.append("\n /* Toplevel node */\n");
result.append(" ");
result.append(toplevel_name);
result.append(" [shape=box];\n");
result.append("}\n");
return result;
}