-1

I have to model an unweighted graph in C++ and do BFS and DFS. But, I have to create two separate classes: node and edge which would contain the two extremities of type node. I do not understand how would I be able to do any search in the graph using the edge class. If it were me, I would only create the node class and have the neighbours of node X in a list/array inside the class. Is there something I am missing? How could I take advantege of the class edge? Is there any way to do the searches without using an adjacency matrix or list? Thank you!

Toma Radu-Petrescu
  • 2,152
  • 2
  • 23
  • 57

2 Answers2

2

You can still use adjacency lists. But they will contain not references to other nodes, but rather references to edge instances, which in turn contain both endpoints as node references, as you mention. Of course, that seems kind of redundant because if you have, say source and target nodes in each edge and then you access some edge of a given node using something like node.edges[i].source, then you instantly know that this source is the node itself, otherwise this edge wouldn't even be in this node's adjacency list. But source may still be useful if you pass a reference to edge alone somewhere, where you don't have the source node at hand.

That aside, for the simplest graph this kind of approach seems like an overkill, because edges only store source and destination edges, the former being mostly redundant. But you may need to extend your edge class later with something like weights, labels, auxiliary data like residual flow or something like that. So having such class is a nice idea after all.

Moreover, some algorithms work directly on edges. For example, you may need to search for an edge satisfying some criterion. Having a separate class gives you freedom to create lists of edges without ad-hoc approaches like pair<Node, Node> or something.

Sergei Tachenov
  • 24,345
  • 8
  • 57
  • 73
  • Thanks a lot for your help! – Toma Radu-Petrescu Feb 28 '16 at 17:09
  • I am encountering a problem, though. The edge class won't be able to see the node class and vice versa. I saw that this can be solved with forward declaration and pointers like [here](http://stackoverflow.com/questions/4964482/how-to-create-two-classes-in-c-which-use-each-other-as-data), but I don't completely understand. Can you help me, please? – Toma Radu-Petrescu Feb 29 '16 at 14:23
  • @rptoma, this is a completely different question. I suggest you study the subject first, then ask a new question if something is still not clear. – Sergei Tachenov Feb 29 '16 at 15:11
1

You miss the constant of space complexity in storing the edges. When you store the edges in adjacency matrix/list, you have to store both (node1, node2) and (node2, node1) for each edge. You double the space, although the big-O complexity stays the same. However, there're times when such space constant has to be considered.

You can take advantage of the class edge when you would like to save as much space as possible, and you would like to prioritize space over time.

Linear search on all the edge instances is a way. Linear search is slow but you prioritize space over time. Maybe parallel search when you have a distributed system is another way, but you have to verify.

Your homework question may have an artificial constraint of the design of the edge class. Artificial constraint idea comes from https://meta.stackexchange.com/questions/10811/how-do-i-ask-and-answer-homework-questions

Community
  • 1
  • 1
Patrick Chan
  • 76
  • 8