48 template <typename Vertex>
51   explicit VertexTotalOrdering(const Graph<Vertex>& graph)  in VertexTotalOrdering()
54   bool operator()(const Vertex& lhs, const Vertex& rhs) const {  in operator()
62   const Graph<Vertex>& graph_;
65 template <typename Vertex>
68   explicit VertexDegreeLessThan(const Graph<Vertex>& graph)  in VertexDegreeLessThan()
71   bool operator()(const Vertex& lhs, const Vertex& rhs) const {  in operator()
76   const Graph<Vertex>& graph_;
95 template <typename Vertex>
96 int IndependentSetOrdering(const Graph<Vertex>& graph,  in IndependentSetOrdering()
97                            vector<Vertex>* ordering) {  in IndependentSetOrdering()
98   const HashSet<Vertex>& vertices = graph.vertices();  in IndependentSetOrdering()
111   HashMap<Vertex, char> vertex_color;  in IndependentSetOrdering()
112   vector<Vertex> vertex_queue;  in IndependentSetOrdering()
113   for (typename HashSet<Vertex>::const_iterator it = vertices.begin();  in IndependentSetOrdering()
122        VertexTotalOrdering<Vertex>(graph));  in IndependentSetOrdering()
127     const Vertex& vertex = vertex_queue[i];  in IndependentSetOrdering()
134     const HashSet<Vertex>& neighbors = graph.Neighbors(vertex);  in IndependentSetOrdering()
135     for (typename HashSet<Vertex>::const_iterator it = neighbors.begin();  in IndependentSetOrdering()
147   for (typename vector<Vertex>::const_iterator it = vertex_queue.begin();  in IndependentSetOrdering()
150     const Vertex vertex = *it;  in IndependentSetOrdering()
171 template <typename Vertex>
172 int StableIndependentSetOrdering(const Graph<Vertex>& graph,  in StableIndependentSetOrdering()
173                                  vector<Vertex>* ordering) {  in StableIndependentSetOrdering()
175   const HashSet<Vertex>& vertices = graph.vertices();  in StableIndependentSetOrdering()
184   vector<Vertex> vertex_queue(*ordering);  in StableIndependentSetOrdering()
187               VertexDegreeLessThan<Vertex>(graph));  in StableIndependentSetOrdering()
190   HashMap<Vertex, char> vertex_color;  in StableIndependentSetOrdering()
191   for (typename HashSet<Vertex>::const_iterator it = vertices.begin();  in StableIndependentSetOrdering()
202     const Vertex& vertex = vertex_queue[i];  in StableIndependentSetOrdering()
209     const HashSet<Vertex>& neighbors = graph.Neighbors(vertex);  in StableIndependentSetOrdering()
210     for (typename HashSet<Vertex>::const_iterator it = neighbors.begin();  in StableIndependentSetOrdering()
222   for (typename vector<Vertex>::const_iterator it = vertex_queue.begin();  in StableIndependentSetOrdering()
225     const Vertex vertex = *it;  in StableIndependentSetOrdering()
242 template <typename Vertex>
243 Vertex FindConnectedComponent(const Vertex& vertex,  in FindConnectedComponent()
244                               HashMap<Vertex, Vertex>* union_find) {  in FindConnectedComponent()  argument
245   typename HashMap<Vertex, Vertex>::iterator it = union_find->find(vertex);  in FindConnectedComponent()
272 template <typename Vertex>
273 Graph<Vertex>*
274 Degree2MaximumSpanningForest(const Graph<Vertex>& graph) {  in Degree2MaximumSpanningForest()
276   vector<pair<double, pair<Vertex, Vertex> > > weighted_edges;  in Degree2MaximumSpanningForest()
277   Graph<Vertex>* forest = new Graph<Vertex>();  in Degree2MaximumSpanningForest()
281   HashMap<Vertex, Vertex> disjoint_set;  in Degree2MaximumSpanningForest()
287   const HashSet<Vertex>& vertices = graph.vertices();  in Degree2MaximumSpanningForest()
288   for (typename HashSet<Vertex>::const_iterator it = vertices.begin();  in Degree2MaximumSpanningForest()
291     const Vertex vertex1 = *it;  in Degree2MaximumSpanningForest()
295     const HashSet<Vertex>& neighbors = graph.Neighbors(vertex1);  in Degree2MaximumSpanningForest()
296     for (typename HashSet<Vertex>::const_iterator it2 = neighbors.begin();  in Degree2MaximumSpanningForest()
299       const Vertex vertex2 = *it2;  in Degree2MaximumSpanningForest()
316     const pair<Vertex, Vertex>& edge = weighted_edges[i].second;  in Degree2MaximumSpanningForest()
317     const Vertex vertex1 = edge.first;  in Degree2MaximumSpanningForest()
318     const Vertex vertex2 = edge.second;  in Degree2MaximumSpanningForest()
332     Vertex root1 = FindConnectedComponent(vertex1, &disjoint_set);  in Degree2MaximumSpanningForest()
333     Vertex root2 = FindConnectedComponent(vertex2, &disjoint_set);  in Degree2MaximumSpanningForest()