NetworkX - start

https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg

https://networkx.github.io/
NetworkX. Software for complex networks.

https://networkx.org/documentation/stable/reference/drawing.html

https://networkx.org/documentation/stable/reference/algorithms/traversal.html
Traversal (DFS, BFS, Beam search).

INSTALLING NETWORKX

PIP (in a virtual environment)
pip install networkx[default]   # suggested by documentation
pip install networkx   # no dependencies (limited functionality)
pip install networkx[default,extra]   # with pygraphviz, pydot, lxml

APT (for the entire computer)
Debian packages: python-networkx (Py2.7), python3-networkx, and dependencies.

INTRODUCTION

NetworkX is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks.

A graph is a pair G = (V,E), where V is a set of vertices and E is a set of edges.
An undirected graph is a graph that has undirected edges (unordered pairs of vertices).
A directed graph (or digraph) is a graph that has directed edges (ordered pairs of vertices).

There are four classes in NetworkX for different graphs:
(1) Graph - simple undirected graphs (no self loops and parallel edges),
(2) DiGraph - simple directed graphs (no self loops and parallel edges),
(3) MultiGraph - undirected multigraphs,
(4) MultiDiGraph - directed multigraphs.

Warning! There are no exceptions when self loops and parallel edges are inserted to Graph and DiGraph instances.

import networkx as nx

print(nx.__version__)
# 2.2 in Debian 10
# 3.2.1 in Debian 13

G = nx.Graph()   # an empty undirected graph

# https://mathworld.wolfram.com/LollipopGraph.html
# 1---2   (3,1)-lollipop graph
# | /
# 3---4

vertex_list = [1, 2, 3, 4]
edge_list = [(1, 2), (1, 3), (2, 3), (3, 4)]
for v in vertex_list:
    G.add_node(v)
for (u, v) in edge_list:
    G.add_edge(u, v)

G.number_of_nodes()   # 4
G.number_of_edges()   # 4

G.nodes     # NodeView((1, 2, 3, 4))
G.nodes()   # NodeView((1, 2, 3, 4))
list(G.nodes)   # [1, 2, 3, 4]

G.nodes(data=True)   # NodeDataView({1: {}, 2: {}, 3: {}, 4: {}})
G.nodes.data()       # NodeDataView({1: {}, 2: {}, 3: {}, 4: {}})
list(G.nodes.data())   # [(1, {}), (2, {}), (3, {}), (4, {})]

G.edges     # EdgeView([(1, 2), (1, 3), (2, 3), (3, 4)])
G.edges()   # EdgeView([(1, 2), (1, 3), (2, 3), (3, 4)])
list(G.edges)   # [(1, 2), (1, 3), (2, 3), (3, 4)]

G.edges(data=True)   # EdgeDataView([(1, 2, {}), (1, 3, {}), (2, 3, {}), (3, 4, {})])
G.edges.data()       # EdgeDataView([(1, 2, {}), (1, 3, {}), (2, 3, {}), (3, 4, {})])
list(G.edges.data())   # [(1, 2, {}), (1, 3, {}), (2, 3, {}), (3, 4, {})]

G[3]   # AtlasView({1: {}, 2: {}, 4: {}})
list(G[3])   # [1, 2, 4]

G.degree     # DegreeView({1: 2, 2: 2, 3: 3, 4: 1})
G.degree()   # DegreeView({1: 2, 2: 2, 3: 3, 4: 1})
list(G.degree)   # [(1, 2), (2, 2), (3, 3), (4, 1)]
G.degree[3]   # 3
deg_max = max(deg for (node, deg) in G.degree())   # 3
deg_max_list = [node for (node, deg) in G.degree() if deg == deg_max]   # [3]

import matplotlib.pyplot as plt

nx.draw(G)
#nx.draw(G, with_labels=True, font_weight='bold')
#nx.draw_circular(G)
#nx.draw_planar(G)
#nx.draw_random(G)
#nx.draw_spring(G)
#nx.draw_shell(G)

# Selected keywords:
# with_labels=True - draw labels on the nodes
# node_size=300 - size of nodes (scalar or array)
# node_shape='o' - the shape of the node (string), one of ‘so^>v<dph8’
# node_color='r' - color or array of colors [node_color=(0.5,0.5,0.5)]
# edge_color='k' - color or array of colors
# width=1.0 - line width of edges (float)
# style='solid' - edge line style (solid|dashed|dotted|dashdot)
# cmap=None - colormap for mapping intensities of nodes
# edge_cmap=None - colormap for mapping intensities of edges
# font_size=12 - font size for text labels (int)
# font_color='k' - font color (string)
# font_weight='normal' - font weight (string)
# font_family='sans-serif' - font family (string)

plt.show()

# path graph  1--2--3--4
G = nx.Graph()
vertex_list = [(1, 0, 0), (2, 1, 1), (3, 2, 2), (4, 3, 3)]
edge_list = [(1, 2, 1.5), (2, 3, 2.5), (3, 4, 3.5)]
for (v, x, y) in vertex_list:
    G.add_node(v, pos=(x,y))
for (u, v, w) in edge_list:
    G.add_edge(u, v, weight=w)
    #G.add_edge(u, v, weight=w, color=('green' if w < 3 else 'red'))
#G.add_weighted_edges_from(edge_list)   # for weights

pos = nx.get_node_attributes(G, 'pos')
#{1: (0, 0), 2: (1, 1), 3: (2, 2), 4: (3, 3)}
# pos = nx.circular_layout(G)
# pos = nx.planar_layout(G)
# pos = nx.random_layout(G)
# pos = nx.spring_layout(G)
# pos = nx.shell_layout(G)

weight = nx.get_edge_attributes(G, 'weight')
#{(1, 2): 1.5, (2, 3): 2.5, (3, 4): 3.5}

#color = nx.get_edge_attributes(G, 'color')
# now we can use option edge_color=color.values()

nx.draw(G, pos, with_labels=True, font_weight='bold', width=list(weight.values()))

plt.show()

GRAPH GENERATORS

https://networkx.org/documentation/stable/reference/generators.html

P_6 = nx.path_graph(6)
C_7 = nx.cycle_graph(7)
K_5 = nx.complete_graph(5)
K_3_5 = nx.complete_bipartite_graph(3, 5)
W_5 = nx.wheel_graph(5)
barbell = nx.barbell_graph(10, 10)
lollipop = nx.lollipop_graph(10, 20)
gnm = nx.gnm_random_graph(n=10, m=20)   # n nodes, m edges
regular = nx.random_regular_graph(d=5, n=10)   # random d-regular graph on n nodes
ergraph = nx.erdos_renyi_graph(n=10, p=0.5)   # p - probability for edge creation

petersen = nx.petersen_graph()
tutte = nx.tutte_graph()
maze = nx.sedgewick_maze_graph()
tetra = nx.tetrahedral_graph()