🧭 QUICK TIP #13 – “Connections and Paths - (Python Graph)”

📰 Edição #14 — QUICK TIP #13 – “Connections and Paths - (Python Graph)”

1) The metaphor of a connected world

Imagine looking down at a bustling city — streets, crossroads, and infinite possible routes.

Each intersection is a node (vertex) and each road is an edge (connection). That’s what a graph represents: how things are linked and how they move between one another.

From social networks to delivery routes, graphs are the invisible architecture of modern life.

2) The core idea

A graph is a mathematical structure made of vertices (nodes) connected by edges (links).

Connections can be directed (one-way streets) or undirected (two-way). Edges may also have weights — numbers that represent distance, cost, or intensity. This simple abstraction allows us to model almost any kind of relationship: physical, digital, or logical.

3) Elegance behind simplicity

What seems like a web of lines and dots hides a world of insight. Graphs help discover shortest paths, influential connections, data flows, and hidden clusters.

They describe not just where things are, but how they interact — making them a bridge between structure and intelligence.

4) How we represent them in code

There’s more than one way to describe a graph programmatically:

• Adjacency Matrix → best for dense graphs with many connections.
• Adjacency List → efficient for sparse networks.
• Dictionary of lists → the Pythonic favorite, offering clarity and flexibility. Each format determines how quickly algorithms can explore the graph’s relationships.

5) Algorithms that bring graphs to life

A graph without algorithms is just geometry.

• BFS (Breadth-First Search) explores neighbors level by level — ideal for finding minimal hops.
• DFS (Depth-First Search) dives deep through every branch — great for discovering cycles or traversing hierarchies.
• Dijkstra and Floyd–Warshall compute the shortest weighted paths, powering GPS systems and routing engines. These algorithms transform connections into intelligence.

6) Python — the perfect tool for graphs

Python makes graph manipulation both elegant and readable:

• NetworkX: ideal for building, drawing, and analyzing graphs.
• igraph: optimized for large social and scientific networks.
• Or simply use a dict of lists for full control and clarity. Python turns complex graph theory into practical visual experimentation.

7) A small example that says a lot

# ================================================
# Script: Connections & Paths — Graphs with NetworkX (EN)
# Author: Izairton Oliveira de Vasconcelos
# Description: BFS, DFS, Dijkstra, and Floyd–Warshall with NetworkX.
#              Prints to terminal and (optionally) draws/saves the graph.
# Compatible with Python 3.8+ | Tested on VSCode
# ================================================
# Tips to see the plot in VSCode:
# 1) Install matplotlib:    pip install matplotlib
# 2) Run from VSCode Integrated Terminal (not a headless debugger).
# 3) On WSL/headless, set SHOW_PLOT=False and SAVE_PNG=True to save 'graph_networkx.png'.
# Plot note:
# - The script automatically prefers the "Agg" backend when no display is available,
#   avoiding messages like "Unable to open monitor interface". With a GUI, it tries to show the window.
# ================================================


from __future__ import annotations

import math
from typing import Dict, List, Tuple
import networkx as nx

# Toggle interactive window
SHOW_PLOT = True
# Save PNG regardless of SHOW_PLOT
SAVE_PNG = True  # outputs 'graph_networkx.png' in the current folder

def build_graph() -> nx.DiGraph:
    """
    Builds the same directed, weighted graph used in the manual example.

    A: B(2), C(5)
    B: C(1), D(2)
    C: D(3), E(2)
    D: E(1), F(4)
    E: F(1)
    F: -
    """
    G = nx.DiGraph()
    edges = [
        ("A", "B", 2), ("A", "C", 5),
        ("B", "C", 1), ("B", "D", 2),
        ("C", "D", 3), ("C", "E", 2),
        ("D", "E", 1), ("D", "F", 4),
        ("E", "F", 1),
    ]
    G.add_weighted_edges_from(edges)
    return G

def bfs_order(G: nx.DiGraph, start: str) -> List[str]:
    """Breadth-first visit order (layers)."""
    return list(nx.bfs_tree(G, source=start).nodes())

def dfs_order(G: nx.DiGraph, start: str) -> List[str]:
    """Depth-first visit order (preorder)."""
    return list(nx.dfs_preorder_nodes(G, source=start))

def dijkstra_single_source(G: nx.DiGraph, source: str) -> Tuple[Dict[str, float], Dict[str, List[str]]]:
    """Single-source shortest path distances and paths from 'source'."""
    dist = nx.single_source_dijkstra_path_length(G, source=source, weight="weight")
    paths = nx.single_source_dijkstra_path(G, source=source, weight="weight")
    return dist, paths

def floyd_warshall_all_pairs(G: nx.DiGraph) -> Dict[str, Dict[str, float]]:
    """All-pairs shortest path distances (Floyd–Warshall)."""
    return dict(nx.floyd_warshall(G, weight="weight"))

def print_matrix(dist: Dict[str, Dict[str, float]]) -> None:
    """Pretty-prints an all-pairs distance matrix."""
    nodes = sorted(dist.keys())
    header = "     " + "  ".join(f"{v:>3}" for v in nodes)
    print(header)
    for u in nodes:
        row = [f"{u:>3}"]
        for v in nodes:
            d = dist[u][v]
            val = "∞" if d == math.inf else f"{int(d):d}" if abs(d - int(d)) < 1e-9 else f"{d:.1f}"
            row.append(f"{val:>3}")
        print("  ".join(row))

# --- Backend helper: choose GUI when SHOW_PLOT=True, otherwise use Agg ---
def _setup_matplotlib_backend(show_plot: bool) -> bool:
    """
    Tries to configure an interactive backend (QtAgg/Qt5Agg/TkAgg/MacOSX) if show_plot=True.
    Returns True if a GUI backend was successfully set; otherwise forces 'Agg' and returns False.
    """
    import matplotlib

    # If we don't want a window, force a headless backend and exit early.
    if not show_plot:
        matplotlib.use("Agg", force=True)
        return False

    # Try a list of interactive backends, in order of preference.
    candidates = ["QtAgg", "Qt5Agg", "TkAgg", "MacOSX"]
    for cand in candidates:
        try:
            matplotlib.use(cand, force=True)
            return True  # GUI backend set → windows can be shown
        except Exception:
            continue

    # No GUI available → fall back to Agg (saves PNG, no window)
    matplotlib.use("Agg", force=True)
    return False

def maybe_plot(G: nx.DiGraph, title: str = "Directed, weighted graph (NetworkX)") -> None:
    """
    Draws the graph with edge weights.
    - If a GUI is available and SHOW_PLOT=True, opens a window (plt.show()).
    - It can always save a PNG when SAVE_PNG=True.
    - When no GUI is available, it silently falls back to 'Agg' (no window).
    """
    # Nothing to do if both showing and saving are disabled.
    if not SHOW_PLOT and not SAVE_PNG:
        return

    try:
        # Decide backend (interactive if possible, otherwise Agg)
        gui = _setup_matplotlib_backend(SHOW_PLOT)
        # Import pyplot only AFTER the backend has been chosen
        import matplotlib.pyplot as plt
    except Exception as e:
        print(f"[Plot] matplotlib not available: {e}")
        return

    # Compute node positions and draw nodes/edges
    pos = nx.spring_layout(G, seed=2701)
    nx.draw(G, pos, with_labels=True, node_size=1200, font_size=10)
    edge_labels = nx.get_edge_attributes(G, "weight")
    nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=9)
    plt.title(title)
    plt.tight_layout()

    # Save PNG regardless of GUI
    if SAVE_PNG:
        fname = "graph_networkx.png"
        plt.savefig(fname, dpi=150)
        print(f"[Plot] Saved figure to {fname}")

    # Show window only if GUI backend is active
    if SHOW_PLOT and gui:
        plt.show()
    else:
        plt.close()

def main() -> None:
    G = build_graph()
    start, goal = "A", "F"

    print("=== BFS (layers) from A ===")
    print(bfs_order(G, start))

    print("\n=== DFS (preorder) from A ===")
    print(dfs_order(G, start))

    print("\n=== Dijkstra (min cost) from A ===")
    dist, paths = dijkstra_single_source(G, start)
    print("Min distances (A→*):", {k: float(v) for k, v in dist.items()})
    print(f"Shortest path A→{goal}:", paths[goal])
    print(f"Total cost A→{goal}: {dist[goal]}")

    print("\n=== Floyd–Warshall (all-pairs) ===")
    allpairs = floyd_warshall_all_pairs(G)
    print_matrix(allpairs)

    # Optional visualization
    maybe_plot(G)

if __name__ == "__main__":
    main()        

8) Terminal Analysis (text output)

When you run the script graph_networkx_demo_eng.py, the terminal prints the logical results from each algorithm step implemented in NetworkX. Let’s interpret what every section means.

🔹 1. BFS (Breadth-First Search)

=== BFS (layers) from A ===
['A', 'B', 'C', 'D', 'E', 'F']        

👉 The BFS explores the graph level by level, visiting all neighbors of a node before moving deeper.

Starting from A, it reaches B and C, then continues to D, E, and finally F.

This sequence represents the structural reachability of the network — it ignores edge weights and focuses only on connectivity.

🔹 2. DFS (Depth-First Search)

=== DFS (preorder) from A ===
['A', 'B', 'C', 'D', 'E', 'F']        

👉 The DFS dives as deep as possible along each path before backtracking.

Even though it shows the same order here, its logic differs: DFS descends sequentially A→B→C→D→E→F before returning.

In this particular graph, the structure happens to form a linear directional flow, so both traversals yield the same sequence.

🔹 3. Dijkstra (Shortest Path)

=== Dijkstra (min cost) from A ===
Min distances (A→*): {'A': 0.0, 'B': 2.0, 'C': 3.0, 'D': 4.0, 'E': 5.0, 'F': 6.0}
Shortest path A→F: ['A', 'B', 'C', 'E', 'F']
Total cost A→F: 6        

👉 The Dijkstra algorithm now considers the weights of the edges.

It calculates the minimum cumulative cost to reach each node from A:

• Cost 0 → A (origin)
• Cost 2 → B
• Cost 3 → C
• Cost 4 → D
• Cost 5 → E
• Cost 6 → F

The optimal route from A to F is A → B → C → E → F, totaling 6 units of cost.

This confirms the correctness of the graph’s weighted structure.

🔹 4. Floyd–Warshall (All-Pairs Shortest Paths)

=== Floyd–Warshall (all-pairs) ===
     A   B   C   D   E   F

A    0   2   3   4   5   6

B  ∞   0   1   2   3   4

C  ∞  ∞   0   3   2   3

D  ∞  ∞  ∞   0   1   2

E  ∞  ∞  ∞  ∞   0   1

F  ∞  ∞  ∞  ∞  ∞   0        

👉 This table is the matrix of all-pairs shortest distances.

Each cell shows the minimum travel cost between the node on that row and the node on that column.

The symbol ∞ (infinity) means no path exists from that node to the other.

💡 Examples of reading:

• From A to D → cost 4
• From D to F → cost 2
• From E to F → cost 1
• From F to A → ∞ (no connection backwards)

 🧾 Terminal Summary

The terminal output reveals the full logical and mathematical behavior of the graph:

• BFS shows structural connectivity (breadth view).
• DFS shows path depth (exploration order).
• Dijkstra shows the cheapest route and its total cost.
• Floyd–Warshall provides the complete shortest-distance matrix between every node pair.

Together, these outputs confirm that the directed, weighted graph behaves correctly and models a network of optimized, directional paths.

9) GRAPH ANALYSIS (visual output)

The graphical output rendered by Matplotlib + NetworkX is the visual counterpart of the terminal data:

• Blue circles: represent the nodes (A through F).
• Black arrows: indicate directed edges.
• Numbers on arrows: are the weights (costs) assigned to each connection.
• Layout: generated by spring_layout(), producing a balanced, natural diagram that simulates forces between nodes.

💡 Visual interpretation:

• The main route A → B → C → E → F follows a left-to-right flow, perfectly matching Dijkstra’s optimal path.
• Alternative routes such as A → C or D → F illustrate redundant or backup connections in the network.
• The overall symmetry shows how cost and connectivity coexist: more arrows mean flexibility, higher weights mean longer “distances.”

🎯 Graphical Summary

The plot acts as a visual mirror of the algorithms. The terminal expresses logic and cost numerically; the figure reveals it spatially. Together, they provide a complete understanding of how paths, directions, and weights interact to form an optimized network of connections and dependencies.

10) From code to the real world

Graphs are everywhere — powering decisions, connections, and predictions:

• Waze and Google Maps use graph algorithms for real-time routing.
• LinkedIn builds connection networks using shortest-path logic.
• Power grids, neural networks, and transport systems depend on graph theory to stay optimized. To understand graphs is to understand the nervous system of the modern world.

11) Challenges and curiosities

Real-world graphs can be massive, dynamic, and unpredictable. Finding optimal paths can quickly become computationally expensive.

Concepts like connected components, minimum spanning trees, and directed acyclic graphs (DAGs) expand the horizon of what graphs can model.

Each one brings a new way of visualizing how systems evolve and depend on one another.

12) ✨ The Aha Moment (a.k.a. The Cat’s Meow)

Graphs are the mathematical poetry of relationships.

They describe how data breathes, how ideas travel, and how systems depend on each other.

Mastering graphs means learning to see the invisible — to map not only positions, but the meaning of every connection.

In a world built on links, graphs are the language of logic and motion.

13) Closing with CTA:

💼 LinkedIn & Newsletters: 🔹 Personal Profile – Izairton Oliveira de Vasconcelos (Feed) 🔹 Reason & Code – Subscribe on LinkedIn 🔹 Python Tips for Productivity – Subscribe on LinkedIn 🔹 Scripts in Python – Productivity and Decision-Making – Subscribe on LinkedIn

🏢 Company Page: 🔹 Izairton Vascon | Python Projects for Strategy and Finance

💻 GitHub: 🔹 Python + Finance Projects

14) Hashtags

#Python #NetworkX #Graphs #Dijkstra #FloydWarshall #DataStructures #BreadthFirstSearch #DepthFirstSearch #NetworkAnalysis #DataScience #Algorithms #AppliedComputing