Network Example

This example showcases graph traversal and shortest path algorithms in an undirected graph network. As such, it demonstrates the usage of the following classes and algorithms:

• The undirected_graph implemented in graaf::undirected_graph
• The shortest path algorithm implemented in graaf::algorithm::get_shortest_path
• The graph traversal implemented in graaf::algorithm::graph_traversal

Using the following graph:

Custom vertex and edge. In order to use Dijkstra, we should provide the get_weight() function for the edge.

struct station {
  std::string name{};
};

struct railroad : public graaf::weighted_edge<double> {
  double kilometers{};
  [[nodiscard]] double get_weight() const noexcept override {
    return kilometers;
  }
  railroad(double distance) : kilometers(distance) {}
  ~railroad() {}
};

Initializing graph, start and end vertecies

First, we create data structure and initializing graph with vertices and edges

struct graph_with_start_and_target {
    graaf::undirected_graph<station, road> graph{};
    graaf::vertex_id_t start{};
    graaf::vertex_id_t target{};
};

graph_with_start_and_target create_graph_with_start_and_target() {
...
}

Visualizing graph traversal result

For shortest path, colouring edges with red to indicate the shortest path for both weighted and unweighted graph We need to specify the start and end vertices in order to find the shortest path between the start and end vertices.

Result of unweighted shortest path, chosen edges are coloured red

Result of weighted shortest path, chosen edges are coloured red

void print_shortest_path(const graaf::undirected_graph<station, road>& graph,
                const std::optional<graaf::algorithm::graph_path<int>>& path, const std::string & filepath) {
...
}

void print_visited_vertices(const graaf::undirected_graph<station, road>& graph,
                            seen_vertices_t& seen,
                            const std::string& filepath) {
...
}

Creating an edge callback structure that will be passed as an argument in the graph traverse function The function is needed in order to be called inside the traverse function; see graph.tpp for context.

using seen_edges_t = std::unordered_set<graaf::edge_id_t, graaf::edge_id_hash>;
struct record_edges_callback {
  seen_edges_t& seen_edges;

  record_edges_callback(seen_edges_t& seen_edges)
      : seen_edges{seen_edges} {}

  void operator()(const graaf::edge_id_t& edge) const {
    seen_edges.insert(edge);
  }
};

Result of shortest path BFS, visited edges are coloured red

Graph example usage

First code block: traversing a weighted graph for the shortest path (Dijkstra) and printing the result to *.dot file. Second code block: traversing an unweighted graph for the shortest path and printing the result to *.dot file. The last one is traversing the graph from a given vertex and printing the result to *.dot file.

  const auto [graph, start, target]{create_graph_with_start_and_target()};

  const auto weighted_shortest_path{
      graaf::algorithm::dijkstra_shortest_path(graph, start, target)};
  print_shortest_path(graph, weighted_shortest_path,
                      "example_weighted_graph.dot");

  const auto unweighted_shortest_path{
      graaf::algorithm::bfs_shortest_path(graph, start, target)};
  print_shortest_path(graph, unweighted_shortest_path,
                      "example_unwieghted_graph.dot");

  seen_edges_t seen_edges{};
  graaf::algorithm::breadth_first_traverse(
      graph, start, record_edges_callback{seen_edges});
  print_visited_vertices(graph, seen_edges,
                         "example_traverse_BFS_graph.dot");