Extract DependencyGraph from ProfileDependencyManager.

chrome/browser/profiles/dependency_graph.h

Index: chrome/browser/profiles/dependency_graph.h
diff --git a/chrome/browser/profiles/dependency_graph.h b/chrome/browser/profiles/dependency_graph.h
new file mode 100644
index 0000000000000000000000000000000000000000..a5ab35f006dfd3b003a321a8a4497870565e8d79
--- /dev/null
+++ b/chrome/browser/profiles/dependency_graph.h
@@ -0,0 +1,70 @@
+// Copyright 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CHROME_BROWSER_PROFILES_DEPENDENCY_GRAPH_H_
+#define CHROME_BROWSER_PROFILES_DEPENDENCY_GRAPH_H_
+
+#include <map>
+#include <string>
+#include <vector>
+
+#include "base/callback.h"
+#include "base/compiler_specific.h"
+
+class DependencyNode;
+
+// Dynamic graph of dependencies between nodes.
+class DependencyGraph {
+ public:
+  typedef base::Callback<std::string(DependencyNode*)> GetNodeNameCallback;
+
+  // Constructor. The name callback is used for debugging.

[Jói, 2013/04/14 23:13:20]

Clarify the documentation: Is a non-is_null() callback optional?

[Paweł Hajdan Jr., 2013/04/15 19:07:40]

Done.

+  explicit DependencyGraph(const GetNodeNameCallback& callback);
+  ~DependencyGraph();
+
+  // Adds/Removes a node from our list of live nodes. Removing will
+  // also remove live dependency links.
+  void AddNode(DependencyNode* node);
+  void RemoveNode(DependencyNode* node);
+
+  // Adds a dependency between two nodes.
+  void AddEdge(DependencyNode* depended, DependencyNode* dependee);
+
+  // Topologically sorts nodes to produce a safe construction order
+  // (all nodes after their dependees).
+  bool GetConstructionOrder(
+      std::vector<DependencyNode*>* order) WARN_UNUSED_RESULT;
+
+  // Topologically sorts nodes to produce a safe destruction order
+  // (all nodes before their dependees).
+  bool GetDestructionOrder(
+      std::vector<DependencyNode*>* order) WARN_UNUSED_RESULT;
+
+  // Returns representation of the dependency graph in graphviz format.
+  std::string DumpAsGraphviz(const std::string& toplevel_name);
+
+ private:
+  typedef std::multimap<DependencyNode*, DependencyNode*> EdgeMap;
+
+  // Populates |construction_order_| with computed construction order.
+  // Returns true on success.
+  bool BuildConstructionOrder() WARN_UNUSED_RESULT;
+
+  // Keeps track of all live nodes (see AddNode, RemoveNode).
+  std::vector<DependencyNode*> all_nodes_;
+
+  // Keeps track of edges of the dependency graph.
+  EdgeMap edges_;
+
+  // Cached construction order (needs rebuild with BuildConstructionOrder
+  // when empty).
+  std::vector<DependencyNode*> construction_order_;
+
+  // Callback to get name of a node (for debugging).
+  GetNodeNameCallback get_node_name_callback_;
+
+  DISALLOW_COPY_AND_ASSIGN(DependencyGraph);
+};
+
+#endif  // CHROME_BROWSER_PROFILES_DEPENDENCY_GRAPH_H_