Python Class Example: Breadth First Search Search, Depth First Search: Exercises in tree data search efficiency and optimization in Python

Python Class Example that follows the above example is provided in the same code link below: Puzzles with BFS and DFS, Max Clique Subgraphs and Power Sets: Exercises in tree data search efficiency and optimization in Python

Links to Python Class Example: Breadth First Search Search, Depth First Search, Puzzles, Max Clique Subgraphs, Tree and Graph Algorithms, and Power Sets : Exercises in tree data search efficiency and optmization in Python. We explored graphs to find paths that represent physical networks. They are used for communication networks, circuits, genes, social networks, disease populations, etc.

Comparing the Breadth First Search, Depth First Search, in a class example

Some rules to set up the example and terminology that follows.

A graph: set of nodes connected by edges.

Edges: unidirectional if directed, or a digraph.

If weight or cost added to an edge, then it is a weighted graph.

Graph optimizations: shortest path (SP): shortest set of edges from node A to B

Shortest weighted path: same as SP but with a minimum function on weights of edges

in sequence cliques - set of nodes such that there is a path with maximum length in graph between each pair of nodes in set

Minimum Cut: 2 sets of nodes, a cut is a set of edges whose removal eliminates all paths from every node in one set to each node in the other. The minimum cut is the smallest set of cuts.

DFS (Depth First Search) starts at root and if not goal node, you extend the current path by adding each child of current node to path, unless already in path.

New paths added to set of paths at front (a stack - last in, first out).

Select next path: recursively repeat. If no children, go to next node, and stop when goal node is reached or there are no more paths.

SP: track best path found so far: when you find a new path, keep going if path still shorter than best.

BFS (Breadth First First): do not go down first branch of existing tree. Instead, examine all children of current node first before going deeper in tree.

BFS, no weights, stop when you find solution, guaranteed SP.

BFS starts at root node, and if not goal, extends current path unless child already in path.

Add new paths to potential set of paths: put at end of set (uses a queue - First In, First Out, push to end, pop at front).

Select next path and recursively repeat. If no children, go to next, and stop at goal node or when no more paths.

Things we observed from this example:

Weighted graphs: DFS can sum weights rather than just check length of path.

BFS: 1st found solution may not be best.

Python Class Example: Puzzles with BFS and DFS, Max Clique Subgraphs and Power Sets: Exercises in tree data search efficiency and optimization in Python

We explored graphs to find paths that represent physical networks.

We used graphs to search and explore changes to the state of a physical system, with nodes representing states of the system, edges the actions that cause the change of state, and found a sequence of actions to convert the system to the desired state.

We did an 8-puzzle example and kept track of legal shifts in a dictionary (graph edges), and the puzzle used BFS and DFS, checking for loops. BFS was quicker for this, with DFS taking a long time and running out of memory.

We then explored Max Cliques: making subgraphs, such as all people connected to each other in social network, infected populations that had contact, and you make collections of cliques.

They are used for communication networks, circuits, genes, social networks, disease populations, etc.

The max clique can use brute force for small problems, and find all subgraphs, test if complete (all connected), keep track of largest clique, and extend to recursively find other large cliques by removing nodes of largest cliques and repeating.

The last example was a power set, the set of all subsets.

To find cliques, generate power sets, all subgraphs, test if all connected and complete, and keep track of largest found.