NetworkX - algorithms

VERTEX COLORING

https://networkx.org/documentation/stable/reference/algorithms/coloring.html

import networkx as nx

G = nx.petersen_graph()

d = nx.coloring.greedy_color(G, strategy="largest_first") # default
#d = nx.coloring.greedy_color(G, strategy='random_sequential')
#d = nx.coloring.greedy_color(G, strategy='smallest_last')
#d = nx.coloring.greedy_color(G, strategy='connected_sequential_bfs')
#d = nx.coloring.greedy_color(G, strategy='connected_sequential_dfs')
#d = nx.coloring.greedy_color(G, strategy='saturation_largest_first')

print(d)   # a dict with pairs (node, int), colors are 0, 1, 2, ...
n_colors = len(set(d.values()))

Exercise. Create an undirected graph G. Color nodes from G using a greedy algorithm.

def trivial_node_coloring(graph):
    """Trivial node coloring."""
    counter = 0
    for node in graph.nodes:
        graph.nodes[node]['color'] = counter
        counter += 1

Exercise. Create an undirected graph G. Color edges from G using a greedy algorithm.

def trivial_edge_coloring(graph):
    """Trivial edge coloring."""
    counter = 0
    for edge in graph.edges:   # edge is a 2-tuple
        graph.edges[edge]['color'] = counter
        counter += 1

MINIMUM SPANNING TREE

https://networkx.org/documentation/stable/reference/algorithms/tree.html

import networkx as nx
from networkx.algorithms import tree

# tree.minimum_spanning_tree(G, weight='weight', algorithm='kruskal',
# ignore_nan=False)
# Returns a minimum spanning tree or forest on an undirected graph G.
# [Jeżeli graf nie ma atrybutu 'weight', to domyślnie jest 1]
# G : an undirected graph
# weight (string) : data key to use for edge weights [can be weight='length']
# algorithm (string) : ‘kruskal’ (default), ‘prim’, ‘boruvka’ (distinct weights)

mst = tree.minimum_spanning_tree(G, algorithm="kruskal") # nx.Graph

mst_e = tree.minimum_spanning_edges(G, algorithm="kruskal") # generator object
T = nx.Graph()
T.add_edges_from(mst_e)

SHORTEST PATHS

https://networkx.org/documentation/stable/reference/algorithms/shortest_paths.html

import networkx as nx

# Create an undirected weighted graph
G = nx.Graph()
G.add_edge("A", "B", weight=4)
G.add_edge("A", "C", weight=2)
G.add_edge("B", "C", weight=5)
G.add_edge("B", "D", weight=10)
G.add_edge("C", "E", weight=3)
G.add_edge("E", "D", weight=4)
G.add_edge("D", "F", weight=11)

# Compute shortest path from A to F considering weights
weighted_path = nx.shortest_path(G, source="A", target="F", weight="weight")
print(weighted_path)   # ['A', 'C', 'E', 'D', 'F']

# Compute shortest path length from A to F ignoring weights
unweighted_path = nx.shortest_path(G, source="A", target="F")
print(unweighted_path)   # ['A', 'B', 'D', 'F']