representing a directed graph versus undirected graph

[rozick1]

Hi

As a learning exercise, I am writing a library for graphs. As I understand it, graphs can be represented as an adjacency list (i.e. for each node, a list of its adjacent nodes). I would like for my library to represent directed and undirected graphs - am I correct in thinking that for an undirected graph that you would keep a mirror image of adjacency lists?

So, for example, if you have an undirected graph where A and B are adjacent then A's adjacency list would include B and B's adjacency list would include A?

Thanks

[lastchance]

So, for example, if you have an undirected graph where A and B are adjacent then A's adjacency list would include B and B's adjacency list would include A?

Yes.

[Duthomhas]

Note that a directed graph and an undirected graph are easily representable by the very same structure.

A common representation is as a 2D array, but you can use other structures in the same way. My preferred method is often something like:

using graph = std::unordered_map <name, std::unordered_set <name> > ;

where name is the ID of the node.

If the ID is a simple integer in 0..N, then a bitset is a good choice too.