Searched refs:graph (Results 1 - 16 of 16) sorted by relevance

/system/update_engine/payload_generator/
H A Dtarjan.cc35 Graph* graph,
40 for (Graph::iterator it = graph->begin(); it != graph->end(); ++it)
44 Tarjan(vertex, graph);
49 void TarjanAlgorithm::Tarjan(Vertex::Index vertex, Graph* graph) { argument
50 CHECK_EQ((*graph)[vertex].index, kInvalidIndex);
51 (*graph)[vertex].index = index_;
52 (*graph)[vertex].lowlink = index_;
55 for (Vertex::EdgeMap::iterator it = (*graph)[vertex].out_edges.begin();
56 it != (*graph)[verte
34 Execute(Vertex::Index vertex, Graph* graph, vector<Vertex::Index>* out) argument
[all...]
H A Dgraph_utils_unittest.cc36 Graph graph(2);
38 graph[0].out_edges.insert(make_pair(1, EdgeProperties()));
40 vector<Extent>& extents = graph[0].out_edges[1].extents;
56 EXPECT_EQ(4U, graph_utils::EdgeWeight(graph, make_pair(0, 1)));
61 Graph graph(3);
63 graph_utils::AddReadBeforeDep(&graph[0], 1, 3);
64 EXPECT_EQ(1U, graph[0].out_edges.size());
66 Extent& extent = graph[0].out_edges[1].extents[0];
70 graph_utils::AddReadBeforeDep(&graph[0], 1, 4);
71 EXPECT_EQ(1U, graph[
[all...]
H A Dtopological_sort.cc30 void TopologicalSortVisit(const Graph& graph, argument
39 for (Vertex::EdgeMap::const_iterator it = graph[node].out_edges.begin();
40 it != graph[node].out_edges.end(); ++it) {
41 TopologicalSortVisit(graph, visited_nodes, nodes, it->first);
48 void TopologicalSort(const Graph& graph, vector<Vertex::Index>* out) { argument
51 for (Vertex::Index i = 0; i < graph.size(); i++) {
52 TopologicalSortVisit(graph, &visited_nodes, out, i);
H A Dtopological_sort.h26 // Performs a topological sort on the directed graph 'graph' and stores
28 // For example, this graph:
37 // Note: results are undefined if there is a cycle in the graph.
38 void TopologicalSort(const Graph& graph, std::vector<Vertex::Index>* out);
H A Dtopological_sort_unittest.cc66 Graph graph(kNodeCount);
68 graph[n_i].out_edges.insert(make_pair(n_j, EdgeProperties()));
69 graph[n_i].out_edges.insert(make_pair(n_c, EdgeProperties()));
70 graph[n_i].out_edges.insert(make_pair(n_e, EdgeProperties()));
71 graph[n_i].out_edges.insert(make_pair(n_h, EdgeProperties()));
72 graph[n_c].out_edges.insert(make_pair(n_b, EdgeProperties()));
73 graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties()));
74 graph[n_e].out_edges.insert(make_pair(n_d, EdgeProperties()));
75 graph[n_e].out_edges.insert(make_pair(n_g, EdgeProperties()));
76 graph[n_
[all...]
H A Dcycle_breaker_unittest.cc39 void SetOpForNodes(Graph* graph) { argument
40 for (Vertex& vertex : *graph) {
60 Graph graph(kNodeCount);
61 SetOpForNodes(&graph);
63 graph[n_a].out_edges.insert(make_pair(n_e, EdgeProperties()));
64 graph[n_a].out_edges.insert(make_pair(n_f, EdgeProperties()));
65 graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties()));
66 graph[n_c].out_edges.insert(make_pair(n_d, EdgeProperties()));
67 graph[n_d].out_edges.insert(make_pair(n_e, EdgeProperties()));
68 graph[n_
[all...]
H A Dinplace_generator_unittest.cc184 Graph graph; local
187 // Create nodes in graph
189 graph.resize(graph.size() + 1);
190 graph.back().aop.op.set_type(InstallOperation::MOVE);
196 StoreExtents(extents, graph.back().aop.op.mutable_src_extents());
197 blocks[3].reader = graph.size() - 1;
198 blocks[5].reader = graph.size() - 1;
199 blocks[7].reader = graph.size() - 1;
206 StoreExtents(extents, graph
[all...]
H A Dgraph_utils.h34 uint64_t EdgeWeight(const Graph& graph, const Edge& edge);
36 // These add a read-before dependency from graph[src] -> graph[dst]. If the dep
47 // For each node N in graph, drop all edges N->|index|.
48 void DropIncomingEdgesTo(Graph* graph, Vertex::Index index);
50 void DumpGraph(const Graph& graph);
H A Dinplace_generator.cc83 // their destination extents given the index of the operations in the graph.
86 explicit IndexedInstallOperationsDstComparator(Graph* graph) argument
87 : graph_(graph) {}
101 void InplaceGenerator::CheckGraph(const Graph& graph) { argument
102 for (const Vertex& v : graph) {
139 bool InplaceGenerator::CutEdges(Graph* graph, argument
150 (*graph)[edge.first].out_edges[edge.second].extents;
152 scratch_blocks_used += graph_utils::EdgeWeight(*graph, edge);
154 scratch_allocator.Allocate(graph_utils::EdgeWeight(*graph, edge));
156 cuts.back().new_vertex = graph
207 CreateEdges( Graph* graph, const vector<Block>& blocks) argument
274 MoveAndSortFullOpsToBack( Graph* graph, vector<Vertex::Index>* op_indexes) argument
323 ConvertCutsToFull( Graph* graph, const string& new_part, BlobFileWriter* blob_file, vector<Vertex::Index>* op_indexes, vector<vector<Vertex::Index>::size_type>* reverse_op_indexes, const vector<CutEdgeVertexes>& cuts) argument
361 AssignBlockForAdjoiningCuts( Graph* graph, const string& new_part, BlobFileWriter* blob_file, vector<Vertex::Index>* op_indexes, vector<vector<Vertex::Index>::size_type>* reverse_op_indexes, const vector<CutEdgeVertexes>& cuts) argument
477 AssignTempBlocks( Graph* graph, const string& new_part, BlobFileWriter* blob_file, vector<Vertex::Index>* op_indexes, vector<vector<Vertex::Index>::size_type>* reverse_op_indexes, const vector<CutEdgeVertexes>& cuts) argument
525 NoTempBlocksRemain(const Graph& graph) argument
552 ConvertCutToFullOp(Graph* graph, const CutEdgeVertexes& cut, const string& new_part, BlobFileWriter* blob_file) argument
600 ConvertGraphToDag(Graph* graph, const string& new_part, BlobFileWriter* blob_file, vector<Vertex::Index>* final_order, Vertex::Index scratch_vertex) argument
670 AddInstallOpToBlocksVector( const InstallOperation& operation, const Graph& graph, Vertex::Index vertex, vector<Block>* blocks) argument
704 AddInstallOpToGraph(Graph* graph, Vertex::Index existing_vertex, vector<Block>* blocks, const InstallOperation operation, const string& op_name) argument
744 Graph graph; local
[all...]
H A Dtarjan_unittest.cc47 Graph graph(kNodeCount);
49 graph[n_a].out_edges.insert(make_pair(n_e, EdgeProperties()));
50 graph[n_a].out_edges.insert(make_pair(n_f, EdgeProperties()));
51 graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties()));
52 graph[n_c].out_edges.insert(make_pair(n_d, EdgeProperties()));
53 graph[n_d].out_edges.insert(make_pair(n_e, EdgeProperties()));
54 graph[n_d].out_edges.insert(make_pair(n_f, EdgeProperties()));
55 graph[n_e].out_edges.insert(make_pair(n_b, EdgeProperties()));
56 graph[n_e].out_edges.insert(make_pair(n_c, EdgeProperties()));
57 graph[n_
[all...]
H A Dgraph_utils.cc38 uint64_t EdgeWeight(const Graph& graph, const Edge& edge) { argument
41 graph[edge.first].out_edges.find(edge.second)->second.extents;
94 // For each node N in graph, drop all edges N->|index|.
95 void DropIncomingEdgesTo(Graph* graph, Vertex::Index index) { argument
97 // edges in the graph.
98 for (Graph::iterator it = graph->begin(), e = graph->end(); it != e; ++it) {
124 void DumpGraph(const Graph& graph) { argument
125 LOG(INFO) << "Graph length: " << graph.size();
126 for (Graph::size_type i = 0, e = graph
[all...]
H A Dtarjan.h21 // Strongly Connected Components in a graph.
24 // in the graph. This implementation will only find the strongly connected
39 Graph* graph,
42 void Tarjan(Vertex::Index vertex, Graph* graph);
H A Dinplace_generator.h59 // each of which has a corresponding vertex in a graph.
71 // Checks all the operations in the graph have a type assigned.
72 static void CheckGraph(const Graph& graph);
86 // Cuts 'edges' from 'graph' according to the AU algorithm. This means
93 static bool CutEdges(Graph* graph,
97 // Creates all the edges for the graph. Writers of a block point to
100 static void CreateEdges(Graph* graph,
104 // which the op is performed -> graph vertex index, and produces the
105 // reverse: a mapping from graph vertex index -> op_indexes index.
116 // Given a topologically sorted graph |op_indexe
[all...]
H A Dcycle_breaker.h21 // finding all elementary cycles (a.k.a. circuits) in a directed graph.
32 // In a sample graph representative of a typical workload, I found over
46 void BreakCycles(const Graph& graph, std::set<Edge>* out_cut_edges);
H A Dcycle_breaker.cc39 void CycleBreaker::BreakCycles(const Graph& graph, set<Edge>* out_cut_edges) { argument
45 subgraph_ = graph;
47 // The paper calls for the "adjacency structure (i.e., graph) of
50 // We arbitrarily order each vertex by its index in the graph. Thus,
58 InstallOperation_Type op_type = graph[i].aop.op.type();
84 // If there's a link from *it -> *jt in the graph,
/system/core/libmemunreachable/
H A DTarjan.h68 void Execute(Graph<T>& graph, SCCList<T>& out);
71 void Tarjan(Node<T>* vertex, Graph<T>& graph);
79 void TarjanAlgorithm<T>::Execute(Graph<T>& graph, SCCList<T>& out) { argument
83 for (auto& it: graph) {
88 for (auto& it: graph) {
90 Tarjan(it, graph);
97 void TarjanAlgorithm<T>::Tarjan(Node<T>* vertex, Graph<T>& graph) { argument
106 Tarjan(vertex_next, graph);
126 void Tarjan(Graph<T>& graph, SCCList<T>& out) { argument
127 TarjanAlgorithm<T> tarjan{graph
[all...]

Completed in 159 milliseconds