visual studio 2010 - Adjacency list implementation in C++ -

i looking concise , precise adjacency list representation of graph in c++. nodes node ids. here how did it. want know experts think it. there better way?

this class implementation (nothing fancy, right don't care public/private methods)

#include <iostream> #include <vector> #include <fstream> #include <sstream>  using namespace std;  class adjlist { public:     int head;     vector<int> listofnodes;     void print(); };  void adjlist :: print() {     (int i=0; i<listofnodes.size(); ++i) {         cout << head << "-->" << listofnodes.at(i) << endl;     } }  class graph { public:     vector<adjlist> list;     void print(); };  void graph :: print() {     (int i=0; i<list.size(); ++i) {         list.at(i).print();         cout << endl;     } } 

my main function parses input file line line. each line interpreted following:

<source_node> <node1_connected_to_source_node> <node2_connected_to_source_node <node3_connected_to_source_node> <...> 

here main:

int main()     {         fstream file("graph.txt", ios::in);         string line;         graph g;         while (getline(file, line)) {             int source;             stringstream str(line);             str >> source;             int node2;             adjlist l;             l.head = source;             while (str >> node2) {                 l.listofnodes.push_back(node2);             }             g.list.push_back(l);         }         file.close();         g.print();         getchar();         return 0;     } 

i know should add addedge() function inside adjlist class instead of directly modifying variable main() however, right wonder best structure.

edit: there 1 shortcoming in approach. complicated graph large number of nodes, node indeed struct/class , in case duplicating values storing whole object. in case think should use pointers. example undirected graph, storing copies of node objects in adjlist (connection between node 1 , 2 means 1's adjacency list have 2 , vice versa). can avoid storing pointers of node objects in adjlist instead of whole object. check dfs implementation benefited approach. there need insure each node gets visited once. having multiple copies of same node make life harder. no?

in case class definitions change this:

#include <iostream> #include <vector> #include <fstream> #include <sstream> #include <map>  using namespace std;  class node { public:     node() {}     node(int id, bool _dirty): node_id(id), dirty(_dirty) {}     int node_id;     bool dirty; };  class adjlist { public:     node *head;     vector<node*> listofnodes;     void print();     ~adjlist() { delete head;} };  void adjlist :: print() {     (int i=0; i<listofnodes.size(); ++i) {         cout << head->node_id << "-->" << listofnodes.at(i)->node_id << endl;     } }  class graph { public:     vector<adjlist> list;     void print();     void dfs(node *startnode); };  void graph::dfs(node *startnode) {     startnode->dirty = true;     for(int i=0; i<list.size(); ++i) {         node *stnode = list.at(i).head;         if (stnode->node_id != startnode->node_id) { continue;}         (int j=0; j<list.at(i).listofnodes.size(); ++j) {             if (!list.at(i).listofnodes.at(j)->dirty) {                 dfs(list.at(i).listofnodes.at(j));             }         }     }     cout << "node: "<<startnode->node_id << endl; }  void graph :: print() {     (int i=0; i<list.size(); ++i) {         list.at(i).print();         cout << endl;     } } 

and how implemented main() function. using map<> avoid duplication of objects. creating new object when not defined earlier. checking existence of object id.

int main() {     fstream file("graph.txt", ios::in);     string line;     graph g;     node *startnode;     map<int, node*> nodemap;     while (getline(file, line)) {         int source;         stringstream str(line);         str >> source;         int node2;         node *sourcenode;         // create new node if node not exist         if (nodemap.find(source) == nodemap.end()) {                 sourcenode = new node(source, false);                 nodemap[source] = sourcenode;         } else {                 sourcenode = nodemap[source];         }         adjlist l;         l.head = sourcenode;         nodemap[source] = sourcenode;         while (str >> node2) {             // create new node if node not exist             node *secnode;             if (nodemap.find(node2) == nodemap.end()) {                 secnode = new node(node2, false);                 nodemap[node2] = secnode;             } else {                 secnode = nodemap[node2];             }             l.listofnodes.push_back(secnode);         }         g.list.push_back(l);         startnode = sourcenode;     }     file.close();     g.print();     g.dfs(startnode);     getchar();     return 0; } 

second edit after ulrich eckhardt suggestion put adjacency list in node class, here think better data structure store graph , perform dfs(), dijkstra() kind of operations. please note adjacency list merged in node class.

#include <iostream> #include <vector> #include <fstream> #include <sstream> #include <map>  using namespace std;  class node { public:     node() {     }     node(int id, bool _dirty): node_id(id), dirty(_dirty) {         //cout << "in overloaded const\n";     }     int node_id;     bool dirty;     vector<node*> listofnodes; };  class graph { public:     vector<node*> mygraph;     void dfs(node* startnode); };  void graph::dfs(node* startnode) {     startnode->dirty = true;     (int j=0; j<startnode->listofnodes.size(); ++j) {             if (!startnode->listofnodes.at(j)->dirty) {                 dfs(startnode->listofnodes.at(j));             }         }      cout << "node: "<<startnode->node_id << endl; } 

can better this?

there few things improved, in general approach reasonable. notes:

• you using int index container, give warning compilers, because size of container exceed size representable int. instead, use size_t.
• rewrite for (int i=0; i<list.size(); ++i) for(size_t i=0, size=list.size(); i!=size; ++i). using != instead of < work iterators. reading , storing size once makes easier debug , possibly more efficient.
• inside loop print, have list.at(i).print();. list.at(i) verify index valid , raise exception when not. in simple case, sure index valid, using list[i] instead faster. also, implicitly documents index valid , not expect invalid.
• the print() functions should constant.
• i don't understand int head is. kind of id node? , isn't id index inside graph::list? if index, compute on demand using address of element minus address of first element, there's no need store redundantly. also, consider validating index when reading, don't have edges going vertex doesn't exist.
• if don't care encapsulation on node-level (which reasonable!), make struct, saves typing.
• storing pointers instead of indices tricky improve speed. problem reading, might need pointer vertex doesn't exist yet. there hack allows doing without using additional storage, requires first storing indices in pointer values (using reinterpret_cast) , after reading, making second pass on data adjust these values actual addresses. of course, can use second pass validate don't have edges going vertices don't exist @ (which place at(i) function becomes useful) second pass verify guarantees thing anyway.

on explicit request, here's example how store index in pointer:

// read file for(...) {     size_t id = read_id_from_file();     node* node_ptr = reinterpret_cast<node*>(id);     adjacency_list.push_back(node_ptr); }  /* note @ point, have node* don't contain valid addresses ids of nodes should point to, must not use these pointers! */  // make pass on nodes after reading file for(size_t i=0, size=adjacency_list.size(); i!=size; ++i) {     // read id adjacency list     node* node_ptr = adjacency_list[i];     size_t id = reinterpret_cast<size_t>(node_ptr);     // convert id actual address     node_ptr = lookup_node_by_id(id);     if(!node_ptr)         throw std::runtime_error("unknown node id in adjacency list");     // store actual node address in adjacency list     adjacency_list[i] = node_ptr; } 

i'm pretty sure works in general, though i'm not 100% sure if guaranteed work, why i'm reluctant post here. however, hope makes clear why i'm asking "head" is. if index in container, there little need it, neither inside file nor in memory. if kind of name or identifier node retrieved file, absolutely need it, can't use index, values there start ids 1 or 1000, should catch , handle without crashing!