While writing a C++ implementation for weighed, labeled graphs, I started to doubt the effectiveness/correctness of my chosen structure and I would like to hear some reviews.
I tried to implement the graph as follows:
template <typename T, typename K> struct graph {
unordered_map< T, list< pair<T, K> > > adjList;
bool directed = 1;
};
This allowed me to store a list of pairs (where first is the destination vertex, and second is the weight) for every vertex, and the adjacency list can be indexed by the vertex content.
So far, I was able to implement the basic operations successfully:
insertEdge()
removeEdge()
searchEdge()
printGraph()
(prints all edges)
These operations behave correctly for both directed and undirected graphs.
template <typename T, typename K> struct graph {
unordered_map< T, list< pair<T, K> > > adjList;
bool directed = 1;
};
template <typename T, typename K> void reinit(graph<T, K>& g, bool directed)
{
g.directed = directed;
g.adjList.clear();
}
template <typename T, typename K> void insertEdge(graph<T, K>& g, T v1, T v2, K weight)
{
g.adjList[v1].push_front(std::make_pair(v2, weight));
if (!g.directed)
g.adjList[v2].push_front(std::make_pair(v1, weight));
}
template <typename T, typename K> void printGraph(graph<T, K>& g)
{
cout << "Graph is " << (g.directed ? "directed" : "undirected") << endl;
for (const auto& v : g.adjList) //for every vertex
for (const auto& e : v.second)
cout << v.first << "---" << e.second << "---" << e.first << endl;
}
template <typename T, typename K> K searchEdge(graph<T, K>& g, T v1, T v2)
{ //test if edge(v1,v2) is graph
auto l = g.adjList.find(v1);
if (l != g.adjList.end())
for (auto e : l->second)
if (e.first == v2)
return e.second;
return numeric_limits<K>::min();
}
template <typename T, typename K> void removeEdge(graph<T, K>& g, T v1, T v2)
{
if (GRAPH::searchEdge(g, v1, v2) != numeric_limits<K>::min())
{
auto l = g.adjList.find(v1);
for (auto e = l->second.begin(); e != l->second.end(); e++)
if (e->first == v2)
{
l->second.erase(e);
return;
}
}
}
For the most part, I found trouble implementing breadth-first search and depth-first search algorithms. If the current structure is not that great, please suggest any changes/reformulations. If it's passable, please suggest how I can approach those mentioned algorithms.