Graph Basics

The Idea

A graph is nodes joined by edges. That is the whole definition — arrays and linked lists just add rules on top of it. Edges can be undirected (a two-way bond) or directed (one-way). A node's degree is simply how many edges touch it.

Real-World Example

A molecule is a graph you can hold. Atoms are the nodes, chemical bonds are the edges, and an atom's valence is its degree: carbon accepts four bonds, hydrogen exactly one. Chemists draw structures rather than formulas because the connections, not the atom counts, decide what the substance does.

The Code

molecule = {                     # methanol, CH3OH
    "C": ["H1", "H2", "H3", "O"],
    "H1": ["C"], "H2": ["C"], "H3": ["C"],
    "O": ["C", "H4"],
    "H4": ["O"],
}
bonds = sum(len(v) for v in molecule.values()) // 2   # each bond seen twice
print("atoms:", len(molecule))
print("bonds:", bonds)
print("degree of C:", len(molecule["C"]))
# atoms: 6
# bonds: 5
# degree of C: 4

g = {"A": ["B", "C"], "B": ["A"], "C": ["A"]}
print(len(g), sum(len(v) for v in g.values()) // 2)