Lines Matching full:vertex
48 template <typename Vertex>
51 explicit VertexTotalOrdering(const Graph<Vertex>& graph)
54 bool operator()(const Vertex& lhs, const Vertex& rhs) const {
62 const Graph<Vertex>& graph_;
65 template <typename Vertex>
68 explicit VertexDegreeLessThan(const Graph<Vertex>& graph)
71 bool operator()(const Vertex& lhs, const Vertex& rhs) const {
76 const Graph<Vertex>& graph_;
95 template <typename Vertex>
96 int IndependentSetOrdering(const Graph<Vertex>& graph,
97 vector<Vertex>* ordering) {
98 const HashSet<Vertex>& vertices = graph.vertices();
111 HashMap<Vertex, char> vertex_color;
112 vector<Vertex> vertex_queue;
113 for (typename HashSet<Vertex>::const_iterator it = vertices.begin();
122 VertexTotalOrdering<Vertex>(graph));
124 // Iterate over vertex_queue. Pick the first white vertex, add it
127 const Vertex& vertex = vertex_queue[i];
128 if (vertex_color[vertex] != kWhite) {
132 ordering->push_back(vertex);
133 vertex_color[vertex] = kBlack;
134 const HashSet<Vertex>& neighbors = graph.Neighbors(vertex);
135 for (typename HashSet<Vertex>::const_iterator it = neighbors.begin();
147 for (typename vector<Vertex>::const_iterator it = vertex_queue.begin();
150 const Vertex vertex = *it;
151 DCHECK(vertex_color[vertex] != kWhite);
152 if (vertex_color[vertex] != kBlack) {
153 ordering->push_back(vertex);
171 template <typename Vertex>
172 int StableIndependentSetOrdering(const Graph<Vertex>& graph,
173 vector<Vertex>* ordering) {
175 const HashSet<Vertex>& vertices = graph.vertices();
184 vector<Vertex> vertex_queue(*ordering);
187 VertexDegreeLessThan<Vertex>(graph));
190 HashMap<Vertex, char> vertex_color;
191 for (typename HashSet<Vertex>::const_iterator it = vertices.begin();
199 // Iterate over vertex_queue. Pick the first white vertex, add it
202 const Vertex& vertex = vertex_queue[i];
203 if (vertex_color[vertex] != kWhite) {
207 ordering->push_back(vertex);
208 vertex_color[vertex] = kBlack;
209 const HashSet<Vertex>& neighbors = graph.Neighbors(vertex);
210 for (typename HashSet<Vertex>::const_iterator it = neighbors.begin();
222 for (typename vector<Vertex>::const_iterator it = vertex_queue.begin();
225 const Vertex vertex = *it;
226 DCHECK(vertex_color[vertex] != kWhite);
227 if (vertex_color[vertex] != kBlack) {
228 ordering->push_back(vertex);
236 // Find the connected component for a vertex implemented using the
238 // the disjoint set structure till you reach a vertex whose connected
239 // component has the same id as the vertex itself. Along the way
242 template <typename Vertex>
243 Vertex FindConnectedComponent(const Vertex& vertex,
244 HashMap<Vertex, Vertex>* union_find) {
245 typename HashMap<Vertex, Vertex>::iterator it = union_find->find(vertex);
247 if (it->second != vertex) {
265 // G_T with the same vertex set V as the input graph G(V,E) but an
272 template <typename Vertex>
273 Graph<Vertex>*
274 Degree2MaximumSpanningForest(const Graph<Vertex>& graph) {
276 vector<pair<double, pair<Vertex, Vertex> > > weighted_edges;
277 Graph<Vertex>* forest = new Graph<Vertex>();
281 HashMap<Vertex, Vertex> disjoint_set;
285 // Spanning Tree graph and set each vertex to be its own connected
287 const HashSet<Vertex>& vertices = graph.vertices();
288 for (typename HashSet<Vertex>::const_iterator it = vertices.begin();
291 const Vertex vertex1 = *it;
295 const HashSet<Vertex>& neighbors = graph.Neighbors(vertex1);
296 for (typename HashSet<Vertex>::const_iterator it2 = neighbors.begin();
299 const Vertex vertex2 = *it2;
316 const pair<Vertex, Vertex>& edge = weighted_edges[i].second;
317 const Vertex vertex1 = edge.first;
318 const Vertex vertex2 = edge.second;
331 // vertex, and adding this edge will create a cycle.
332 Vertex root1 = FindConnectedComponent(vertex1, &disjoint_set);
333 Vertex root2 = FindConnectedComponent(vertex2, &disjoint_set);
