liveBook · Manning

Graph

As explained in Optimization Algorithms: AI techniques for design, planning, and control problems

A graph is a nonlinear data structure consisting of vertices and edges that represent entities and relationships.

A graph is a nonlinear data structure that represents entities as vertices (or nodes) and relationships as edges (or links). Formally, G = (V, E), with optional edge attributes such as length, capacity, or material. section 3.1

Choose a graph form that matches the relationships being represented:

  • Use an undirected graph for bidirectional relationships such as mutual connections. section 3.1
  • Use a directed graph for one-way streets, causal relationships, or task dependencies. section 3.1
  • Use a multigraph when multiple edges connect the same vertices, such as parallel roads or different social relationships. section 3.1
  • Use acyclic graphs when paths must not cycle back to a starting node, or hypergraphs when one edge connects more than two nodes. section 3.1
  • Add weights when edges carry measurable costs, distances, capacities, or other values. section 3.1

Graphs model networked systems that tabular structures handle poorly: social interactions, road networks, web links, user–item preferences, factual knowledge, and molecular bonds. Their structure makes relationships explicit and supports analysis of interconnected entities. section 11.3

Representing a road network

Treat locations as nodes and roads as edges. Directed edges can encode one-way streets, while edge weights can represent distance or travel cost. Search algorithms can then calculate routes, update traffic information, or estimate arrival times. section 3.1 section 3.6

Listing 3.1 Creating an undirected graph using NetworkX
import networkx as nx
import matplotlib.pyplot as plt
 
graph = nx.Graph()
 
nodes = list(range(5))                        #1
graph.add_nodes_from(nodes)
 
edges = [(0,1),(1,2), (1,3), (2,3),(3,4)]     #2
graph.add_edges_from(edges)
 
nx.draw_networkx(graph, font_color="white")

Create and visualize a five-node undirected graph in NetworkX by adding nodes, adding edges, and drawing the resulting structure. section 3.1

Listing 11.1 Converting tabular data to a graph
import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt
  
data={'Player':['L. Messi','R. Lewandowski','C. Ronaldo','Neymar Jr','K. 
 Mbappé','E.Haaland','H. Kane','Luka Modrić','L. Goretzka','M. Salah'],
    'Age':[36,34,38,22,24,35,29,37,28,31],
    'Nationality':['Argentina','Poland','Portugal','Brazil','France','Norway',
    'England','Croatia','Germany','Egypt'],
    'Club':['Inter Miami','Barcelona','Al-Nassr','Al-Hilal ','PSG','Manchester
    City','Tottenham Hotspur','Real Madrid','Bayern Munich','Liverpool'],
    'League':['Major League Soccer ','Spain Primera Division','Saudi Arabia
 League','Saudi Arabia League','French Ligue 1','English Premier
 League','English Premier League','Spain Primera Division','German 1.
 Bundesliga','English Premier League']}
df=pd.DataFrame.from_dict(data)

Convert tabular soccer-player data into a graph whose edges represent player–club and player–nationality relationships. section 11.3

How Optimization Algorithms: AI techniques for design, planning, and control problems covers it

How deep it goes
Defines graph structure, classifications, weighted edges, and Python construction, then connects graphs to search and real-world datasets.
Examples
Uses social networks, road networks, soccer-player data, weighted devices, and NetworkX diagrams as concrete representations.
What it assumes
Assumes basic data-structure familiarity while defining vertices, edges, graph notation, and major graph classifications.
What you can do after
Builds and visualizes graph structures with NetworkX and selects representations suited to relationships, weights, direction, and multiplicity.
How it connects
Connects graphs with graph search, BFS, DFS, shortest-path algorithms, graph-structured data, knowledge graphs, and recommender systems.
Cover of Optimization Algorithms: AI techniques for design, planning, and control problems
liveBookmanning.com
Read Optimization Algorithms: AI techniques for design, planning, and control problems on liveBook Get the book at manning.com

Also explained in

Compare how 21 books explain graph →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Optimization Algorithms: AI techniques for design, planning, and control problems. The section links point to the parts of the book it draws on.