Lines Matching refs:Vertex
45 template <typename Vertex>
48 explicit VertexDegreeLessThan(const Graph<Vertex>& graph)
51 bool operator()(const Vertex& lhs, const Vertex& rhs) const {
59 const Graph<Vertex>& graph_;
78 template <typename Vertex>
79 int IndependentSetOrdering(const Graph<Vertex>& graph,
80 vector<Vertex>* ordering) {
81 const HashSet<Vertex>& vertices = graph.vertices();
94 HashMap<Vertex, char> vertex_color;
95 vector<Vertex> vertex_queue;
96 for (typename HashSet<Vertex>::const_iterator it = vertices.begin();
105 VertexDegreeLessThan<Vertex>(graph));
107 // Iterate over vertex_queue. Pick the first white vertex, add it
110 const Vertex& vertex = vertex_queue[i];
111 if (vertex_color[vertex] != kWhite) {
115 ordering->push_back(vertex);
116 vertex_color[vertex] = kBlack;
117 const HashSet<Vertex>& neighbors = graph.Neighbors(vertex);
118 for (typename HashSet<Vertex>::const_iterator it = neighbors.begin();
130 for (typename vector<Vertex>::const_iterator it = vertex_queue.begin();
133 const Vertex vertex = *it;
134 DCHECK(vertex_color[vertex] != kWhite);
135 if (vertex_color[vertex] != kBlack) {
136 ordering->push_back(vertex);
144 // Find the connected component for a vertex implemented using the
146 // the disjoint set structure till you reach a vertex whose connected
147 // component has the same id as the vertex itself. Along the way
150 template <typename Vertex>
151 Vertex FindConnectedComponent(const Vertex& vertex,
152 HashMap<Vertex, Vertex>* union_find) {
153 typename HashMap<Vertex, Vertex>::iterator it = union_find->find(vertex);
155 if (it->second != vertex) {
173 // G_T with the same vertex set V as the input graph G(V,E) but an
180 template <typename Vertex>
181 Graph<Vertex>*
182 Degree2MaximumSpanningForest(const Graph<Vertex>& graph) {
184 vector<pair<double, pair<Vertex, Vertex> > > weighted_edges;
185 Graph<Vertex>* forest = new Graph<Vertex>();
189 HashMap<Vertex, Vertex> disjoint_set;
193 // Spanning Tree graph and set each vertex to be its own connected
195 const HashSet<Vertex>& vertices = graph.vertices();
196 for (typename HashSet<Vertex>::const_iterator it = vertices.begin();
199 const Vertex vertex1 = *it;
203 const HashSet<Vertex>& neighbors = graph.Neighbors(vertex1);
204 for (typename HashSet<Vertex>::const_iterator it2 = neighbors.begin();
207 const Vertex vertex2 = *it2;
224 const pair<Vertex, Vertex>& edge = weighted_edges[i].second;
225 const Vertex vertex1 = edge.first;
226 const Vertex vertex2 = edge.second;
239 // vertex, and adding this edge will create a cycle.
240 Vertex root1 = FindConnectedComponent(vertex1, &disjoint_set);
241 Vertex root2 = FindConnectedComponent(vertex2, &disjoint_set);
