OLD | NEW |
---|---|
(Empty) | |
1 // Copyright (c) 2009 The Chromium Authors. All rights reserved. | |
2 // Use of this source code is governed by a BSD-style license that can be | |
3 // found in the LICENSE file. | |
4 | |
5 #ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_GRAPH_TYPES_H__ | |
6 #define CHROMEOS_PLATFORM_UPDATE_ENGINE_GRAPH_TYPES_H__ | |
7 | |
8 #include <map> | |
9 #include <set> | |
10 #include <utility> | |
11 #include <vector> | |
12 #include "base/basictypes.h" | |
13 #include "update_engine/update_metadata.pb.h" | |
14 | |
15 // A few classes that help in generating delta images use these types | |
16 // for the graph work. | |
17 | |
18 namespace chromeos_update_engine { | |
19 | |
20 struct EdgeProperties { | |
21 std::vector<Extent> extents; // filesystem extents represented | |
22 }; | |
23 | |
24 struct Vertex { | |
25 Vertex() : index(-1), lowlink(-1), op(NULL) {} | |
26 typedef std::map<std::vector<Vertex>::size_type, EdgeProperties> EdgeMap; | |
27 EdgeMap out_edges; | |
28 | |
29 // We sometimes wish to consider a subgraph of a graph. A subgraph would have | |
30 // a subset of the vertices from the graph and a subset of the edges. | |
31 // When considering this vertex within a subgraph, subgraph_edges stores | |
32 // the out-edges. | |
33 typedef std::set<std::vector<Vertex>::size_type> SubgraphEdgeMap; | |
34 SubgraphEdgeMap subgraph_edges; | |
35 | |
36 // For Tarjan's algorithm: | |
37 std::vector<Vertex>::size_type index; | |
38 std::vector<Vertex>::size_type lowlink; | |
39 | |
40 // Other Vertex properties: | |
41 DeltaArchiveManifest_InstallOperation* op; | |
42 }; | |
43 | |
44 typedef std::vector<Vertex> Graph; | |
45 typedef std::vector<Vertex>::size_type VertexIndex; | |
46 | |
47 const VertexIndex kInvalidVertexIndex = -1; | |
Daniel Erat
2010/02/05 17:55:19
can you move this into Vertex, i.e. Vertex::kInval
adlr
2010/02/22 23:27:31
Done.
| |
48 | |
49 typedef std::pair<VertexIndex, VertexIndex> Edge; | |
50 | |
51 } // namespace chromeos_update_engine | |
52 | |
53 #endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_GRAPH_TYPES_H__ | |
OLD | NEW |