Scribd
Upload
102 views10 pages

Graph Theory Basics in Python

The document discusses graph theory and its implementation in Python using the NetworkX library. It introduces basic graph concepts like nodes, edges, and adjacency lists. Examples show how to create a graph from pairwise relationships, find the nodes and edges of a graph, and visualize the graph. It then demonstrates how to build a flight network graph from data and calculate the degree centrality of airports. Finally, it shows how to find all paths and the shortest path between nodes using Dijkstra's algorithm.

Uploaded by

ante mitar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
102 views10 pages

Graph Theory Basics in Python

The document discusses graph theory and its implementation in Python using the NetworkX library. It introduces basic graph concepts like nodes, edges, and adjacency lists. Examples show how to create a graph from pairwise relationships, find the nodes and edges of a graph, and visualize the graph. It then demonstrates how to build a flight network graph from data and calculate the degree centrality of airports. Finally, it shows how to find all paths and the shortest path between nodes using Dijkstra's algorithm.

Uploaded by

ante mitar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

The Graph Theory — An Introduction In Python | by Sofiyan Sheikh | A... [Link]

1 of 10 4/25/2021, 3:21 PM
The Graph Theory — An Introduction In Python | by Sofiyan Sheikh | A... [Link]

2 of 10 4/25/2021, 3:21 PM
The Graph Theory — An Introduction In Python | by Sofiyan Sheikh | A... [Link]

3 of 10 4/25/2021, 3:21 PM
The Graph Theory — An Introduction In Python | by Sofiyan Sheikh | A... [Link]

# Initiating an empty Graph object


P = [Link]() # create an empty object

4 of 10 4/25/2021, 3:21 PM
The Graph Theory — An Introduction In Python | by Sofiyan Sheikh | A... [Link]

# You can add nodes using add_nodes_from()


P.add_nodes_from(['A','B','C','D', 'E'])

# Use add_edges_from to add pairwise relationships


P.add_edges_from ([('B','C'), ('A','C'), ('B','D'), ('D','A'),
('D','E'), ('B','E')])

<object>.nodes() <object>.edges()

print([Link]())

print([Link]())

[Link]

%matplotlib inline
import [Link] as plt
[Link](P, with_labels = True)

5 of 10 4/25/2021, 3:21 PM
The Graph Theory — An Introduction In Python | by Sofiyan Sheikh | A... [Link]

#import packages
import pandas as pd
import numpy as np

#import data file (subset of original file)


path = "INSERT YOUR PATH"
file = pd.read_csv(path + "[Link]", low_memory = False)

#review dataframe structure


[Link]

#review data
[Link]()

6 of 10 4/25/2021, 3:21 PM
The Graph Theory — An Introduction In Python | by Sofiyan Sheikh | A... [Link]

<object>.edges() [Link]

import networkx as nx
FG = nx.from_pandas_edgelist(file2, source='ORIGIN_AIRPORT',
target='DESTINATION_AIRPORT', edge_attr=True)
[Link]()

[Link]()

[Link](FG, with_labels = True)

7 of 10 4/25/2021, 3:21 PM
The Graph Theory — An Introduction In Python | by Sofiyan Sheikh | A... [Link]

[Link].degree_centrality(<object>)

# Calculating the centrality of each of the airports


[Link].degree_centrality(FG)

# What options are available to fly from San Bernardino County to


Newark, NJ?
for path in nx.all_simple_paths(FG, source='ONT', target='EWR'):
print(path)

8 of 10 4/25/2021, 3:21 PM
The Graph Theory — An Introduction In Python | by Sofiyan Sheikh | A... [Link]

nx.dijkstra_path

#Finding the dijkstra path


djk_path = nx.dijkstra_path(FG, source='ONT', target='EWR')
djk_path

[Link]()

#Exercise Solution Code

9 of 10 4/25/2021, 3:21 PM
The Graph Theory — An Introduction In Python | by Sofiyan Sheikh | A... [Link]

# Add a node
NG.add_nodes_from(['A','B','C','D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L'])
# Add a list of nodes by passing a list argument

# Add edges
NG.add_edges_from([('A', 'B'),('C','E'),('D','E'), ('F','G'), ('F','H'),
('G', 'J'), ('H', 'J'), ('H', 'M'), ('H','L'), ('M', 'L'), ('J', 'K'), ('J',
'G'), ('K', 'I'), ('I', 'G'), ('L', 'K')])

#show nodes
NG = nx.from_pandas_edgelist(ntwrk, source='source', target='target',
edge_attr=True)
[Link]()

#show edges
[Link]()

#draw graph
[Link](NG, with_labels = True)

#shortest path
djk_path = nx.dijkstra_path(NG, source='L', target='F')
djk_path

10 of 10 4/25/2021, 3:21 PM

You might also like