c++ - 计算图中节点的出度

Question

我已经为 Graph 实现了以下代码。为了计算任何节点的出度，outDegree 函数就在那里。它将采用需要计算其 outDegree 的节点的名称。我想知道在计算任何节点的 outDegree 时，我可以使用 vector.h 中提供的 find() 函数吗？如果是，如何？

    #include<iostream>
    #include<iterator>
    #include<vector>
    #include<list>
    using namespace std;
    template<class T1,class T2>
    class Edge{
            public:
            T1 d_vertex;
            T2 d_weight;
            Edge(T1,T2);
            T1 vertex();
            T2 weight();
    };
    template<class T1,class T2>
    Edge<T1,T2>::Edge(T1 v,T2 w):d_vertex(v),d_weight(w){
    }
    template<class T1,class T2>
    T1 Edge<T1,T2>:: vertex(){
            return d_vertex;
    }
    template<class T1,class T2>
    T2 Edge<T1,T2>::weight(){
            return d_weight;
    }
    template<class T,class T2>
    class Graph{
            vector<pair<T, list<T2> > > node;
            public:
            void addNode(T data,const list<T2>&);
            void show();
            int outDegree(T);
    };
   ////////////////////////////////////////////////////////////////////
    template<class T,class T2>
    int Graph<T,T2>::outDegree(T node_name){
            for(int i=0;i<node.size();i++){
                    if(node[i].first==node_name)
                            break;
  }
        if(i==node.size())
                return -1;
        else
        return(node[i].second.size());
}
template<class T,class T2>
void Graph<T,T2>:: addNode(T data, const list<T2>& lst){
        node.push_back(pair<T, list<T2> >(data,lst));
}
template<class T,class T2>
void Graph<T,T2>:: show(){
        for(int i=0;i<node.size();i++){
                cout<<node[i].first<<"------ ";
                for(typename list<T2> :: iterator it=node[i].second.begin();it!=node[i].second.end();it++)
                        cout<<(*it).d_vertex<<" ";
                cout<<endl;
        }
}
int main(){
        Graph<int,Edge<int,float> > g;
        list<Edge<int,float> > x;
        x.push_back(Edge<int,float>(4,float(3.5)));
        x.push_back(Edge<int,float>(5,float(4.0)));
        g.addNode(3,x);
        list<Edge<int,float> > y;
        y.push_back(Edge<int,float>(4,float(6.3)));
        y.push_back(Edge<int,float>(2,float(12.0)));
        y.push_back(Edge<int,float>(1,float(2.1)));
        g.addNode(6,y);
        g.show();
        cout<<g.outDegree(6);
}

Answer 1

好吧，如果你使用 C++11，你可以使用带有 lambda 的 find_if:

#include <algorithm>

template<class T,class T2>
int Graph<T,T2>::outDegree(T node_name)
{
  typename vector<pair<T, list<T2> > >::const_iterator it
    = std::find_if(node.begin(), node.end(),
                   [&node_name](const pair<T, list<T2> > &n) 
                   {
                     return n.first ==node_name;
                   });

  if(it != node.end())
    return it->second.size();

  return -1;
}

作为侧边栏:如果您想高效地使用图表，请使用柠檬 (http://lemon.cs.elte.hu/trac/lemon) 或类似的东西。