c++ - Digraph arc list implementation -

i'm trying implement graph arc list, , while implementation works efficiency horrible, missed that's making slow ? time measured average of looking arcs from/to each node.

struct arc  {     int start;     int end;     arc(int start,int end)       : start(start),         end(end)     { } };  typedef vector<arc> arclist;  class alistgraph { public:     alistgraph(imatrix* in); //fills data incidence matrix     bool ise(int va,int vb); //checks if arc exists a->b     int countedges(); //counts arcs     int countnext(int v); //counts outgoing arcs v     int countprev(int v); //counts arcs incoming v  private:     arclist l;     int vcount; };  //cut out constructor clarity  int alistgraph::countedges()  {     return l.size(); }  int alistgraph::countnext(int v) {     int result=0;     for(arclist::iterator =l.begin();it!=l.end();it++)     {         if(it->end==v)result++;     }     return result; }  int alistgraph::countprev(int v) {     int result=0;     for(arclist::iterator =l.begin();it!=l.end();it++)     {         if(it->start==v)result++;     }     return result; } 

well, implemention worst possible : in order find in/out edges have go across whole graph.

do need arc list? adjacency list more efficient.

a naïve implementation of adjacency list keep vector > arcs size of arc number of nodes.

given node u, arcs[u] gives out edges. can figure out how optimize in edges also.