Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Typedefs | Functions
bfs_dfs_example.C File Reference

Graph traversal in Aleph-w: BFS vs DFS demos (comparison, paths, degrees, early stop, components). More...

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <tpl_graph.H>
#include <graph-traverse.H>
#include <tpl_components.H>
#include <tpl_find_path.H>
#include <tclap/CmdLine.h>
Include dependency graph for bfs_dfs_example.C:

Go to the source code of this file.

Typedefs

using Node = Graph_Node< string >
 
using Arc = Graph_Arc< int >
 
using Graph = List_Graph< Node, Arc >
 

Functions

Graph build_social_network ()
 Build a sample social network graph.
 
Graph build_tree_graph ()
 Build a tree-like graph for clear traversal comparison.
 
Graph::Node * find_node (Graph &g, const string &name)
 Find a node by name.
 
void print_graph (Graph &g, const string &title)
 Print graph structure.
 
void demo_bfs (Graph &g, Graph::Node *start)
 Demonstrate BFS traversal.
 
void demo_dfs (Graph &g, Graph::Node *start)
 Demonstrate DFS traversal.
 
void demo_comparison ()
 Compare BFS and DFS on the same graph.
 
void demo_degrees_of_separation ()
 Practical example: Finding degrees of separation.
 
void demo_any_path ()
 Practical example: Finding any path (DFS)
 
void demo_early_termination ()
 Demonstrate early termination.
 
void demo_connected_components ()
 Demonstrate finding connected components.
 
int main (int argc, char *argv[])
 

Detailed Description

Graph traversal in Aleph-w: BFS vs DFS demos (comparison, paths, degrees, early stop, components).

Overview

This example contrasts the two fundamental graph traversal strategies:

  • BFS (breadth-first search): explores level by level using a queue.
  • DFS (depth-first search): explores deep-first using a stack/recursion.

The file includes several small demos that show typical use cases:

  • comparing visitation order and properties
  • degrees-of-separation (BFS)
  • finding any path (DFS)
  • early termination patterns
  • connected components

Data model used by this example

This program builds small graphs with Aleph-w containers (nodes/arcs stored in tpl_graph.H graph types) and traverses them with BFS/DFS style routines.

Usage / CLI

This example uses TCLAP. Options:

  • --compare / -c: compare BFS and DFS on the same graph.
  • --degrees / -d: degrees-of-separation demo (BFS).
  • --path / -p: find any path demo (DFS).
  • --early / -e: early termination demo.
  • --components / -o: connected components demo.
  • --all / -a: run all demos.
  • --help: show help.

Behavior:

  • If no demo-selection flags are provided, the program defaults to running all demos.
./bfs_dfs_example
./bfs_dfs_example --compare
./bfs_dfs_example --degrees
./bfs_dfs_example --path
./bfs_dfs_example --early
./bfs_dfs_example --components
./bfs_dfs_example --help

Algorithms

  • BFS discovers nodes in nondecreasing distance (in number of edges) from the source. On unweighted graphs, BFS yields shortest paths in edge count.
  • DFS explores as far as possible before backtracking; it is the basis for many algorithms (topological sorting, SCCs, articulation points, etc.).

Complexity

Let V be the number of vertices and E the number of edges.

  • Time: O(V + E)
  • Extra space: O(V) (visited set + queue/stack)

Pitfalls and edge cases

  • BFS memory can grow with the frontier (graph "width").
  • DFS recursion can overflow for very deep graphs; an explicit stack avoids that.
  • Traversal order depends on adjacency iteration order.

References / see also

Author
Leandro Rabindranath León

Definition in file bfs_dfs_example.C.

Typedef Documentation

◆ Arc

using Arc = Graph_Arc<int>

Definition at line 127 of file bfs_dfs_example.C.

◆ Graph

using Graph = List_Graph<Node, Arc>

Definition at line 128 of file bfs_dfs_example.C.

◆ Node

using Node = Graph_Node<string>

Definition at line 126 of file bfs_dfs_example.C.

Function Documentation

◆ build_social_network()

Graph build_social_network ( )

Build a sample social network graph. 

    Alice
   /     \
Bob --- Charlie
 |         |

Diana — Eve | Frank — Grace | Henry

Definition at line 143 of file bfs_dfs_example.C.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

Referenced by demo_any_path(), demo_degrees_of_separation(), and demo_early_termination().

◆ build_tree_graph()

Graph build_tree_graph ( )

Build a tree-like graph for clear traversal comparison. 

         1
       / | \
      2  3  4
     /|     |
    5 6     7
   /|\
  8 9 10

Definition at line 181 of file bfs_dfs_example.C.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), nodes, and Aleph::to_string().

Referenced by demo_comparison().

◆ demo_any_path()

void demo_any_path ( )

Practical example: Finding any path (DFS)

Definition at line 366 of file bfs_dfs_example.C.

References build_social_network(), find_node(), Aleph::Path< GT >::get_it(), Aleph::Dlink::Iterator::has_curr(), Aleph::maps(), and Aleph::Path< GT >::size().

Referenced by main().

◆ demo_bfs()

void demo_bfs ( Graph &  g,
Graph::Node *  start 
)

Demonstrate BFS traversal.

Definition at line 245 of file bfs_dfs_example.C.

References Aleph::maps().

Referenced by demo_comparison().

◆ demo_comparison()

void demo_comparison ( )

Compare BFS and DFS on the same graph.

Definition at line 301 of file bfs_dfs_example.C.

References build_tree_graph(), demo_bfs(), demo_dfs(), find_node(), Aleph::maps(), print_graph(), and root().

Referenced by main().

◆ demo_connected_components()

void demo_connected_components ( )

Demonstrate finding connected components.

Definition at line 453 of file bfs_dfs_example.C.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::maps(), print_graph(), and Aleph::HTList::size().

Referenced by main().

◆ demo_degrees_of_separation()

void demo_degrees_of_separation ( )

Practical example: Finding degrees of separation.

Definition at line 323 of file bfs_dfs_example.C.

References build_social_network(), find_node(), Aleph::Path< GT >::get_it(), Aleph::Dlink::Iterator::has_curr(), Aleph::maps(), print_graph(), and Aleph::Path< GT >::size().

Referenced by main().

◆ demo_dfs()

void demo_dfs ( Graph &  g,
Graph::Node *  start 
)

Demonstrate DFS traversal.

Definition at line 273 of file bfs_dfs_example.C.

References Aleph::maps().

Referenced by demo_comparison().

◆ demo_early_termination()

void demo_early_termination ( )

Demonstrate early termination.

Definition at line 405 of file bfs_dfs_example.C.

References build_social_network(), find_node(), and Aleph::maps().

Referenced by main().

◆ find_node()

Graph::Node * find_node ( Graph &  g,
const string &  name 
)

Find a node by name.

Definition at line 206 of file bfs_dfs_example.C.

References GraphCommon< GT, Node, Arc >::get_node_it().

Referenced by demo_any_path(), demo_comparison(), demo_degrees_of_separation(), and demo_early_termination().

◆ main()

int main ( int  argc,
char *  argv[] 
)

Definition at line 503 of file bfs_dfs_example.C.

References demo_any_path(), demo_comparison(), demo_connected_components(), demo_degrees_of_separation(), demo_early_termination(), and Aleph::maps().

◆ print_graph()

void print_graph ( Graph &  g,
const string &  title 
)

Print graph structure.

Definition at line 217 of file bfs_dfs_example.C.

References GraphCommon< GT, Node, Arc >::get_connected_node(), GraphCommon< GT, Node, Arc >::get_node_it(), GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), and Aleph::maps().

Referenced by demo_comparison(), demo_connected_components(), and demo_degrees_of_separation().