% Default to the notebook output style
% Inherit from the specified cell style.
\documentclass[11pt]{article}
\usepackage{tcolorbox}
\usepackage[T1]{fontenc}
% Nicer default font (+ math font) than Computer Modern for most use cases
\usepackage{mathpazo}
% Basic figure setup, for now with no caption control since it's done
% automatically by Pandoc (which extracts  syntax from Markdown).
\usepackage{graphicx}
\graphicspath{ {Figs/} }
% We will generate all images so they have a width \maxwidth. This means
% that they will get their normal width if they fit onto the page, but
% are scaled down if they would overflow the margins.
\makeatletter
\def\maxwidth{\ifdim\Gin@nat@width>\linewidth\linewidth
\else\Gin@nat@width\fi}
\makeatother
\let\Oldincludegraphics\includegraphics
% Set max figure width to be 80% of text width, for now hardcoded.
\renewcommand{\includegraphics}[1]{\Oldincludegraphics[width=.8\maxwidth]{#1}}
% Ensure that by default, figures have no caption (until we provide a
% proper Figure object with a Caption API and a way to capture that
% in the conversion process - todo).
\usepackage{caption}
\DeclareCaptionLabelFormat{nolabel}{}
\captionsetup{labelformat=nolabel}
\usepackage{adjustbox} % Used to constrain images to a maximum size
\usepackage{xcolor} % Allow colors to be defined
\usepackage{enumerate} % Needed for markdown enumerations to work
\usepackage{geometry} % Used to adjust the document margins
\usepackage{amsmath} % Equations
\usepackage{amssymb} % Equations
\usepackage{textcomp} % defines textquotesingle
% Hack from http://tex.stackexchange.com/a/47451/13684:
\AtBeginDocument{%
\def\PYZsq{\textquotesingle}% Upright quotes in Pygmentized code
}
\usepackage{upquote} % Upright quotes for verbatim code
\usepackage{eurosym} % defines \euro
\usepackage[mathletters]{ucs} % Extended unicode (utf-8) support
\usepackage[utf8x]{inputenc} % Allow utf-8 characters in the tex document
\usepackage{fancyvrb} % verbatim replacement that allows latex
\usepackage{grffile} % extends the file name processing of package graphics
% to support a larger range
% The hyperref package gives us a pdf with properly built
% internal navigation ('pdf bookmarks' for the table of contents,
% internal cross-reference links, web links for URLs, etc.)
\usepackage{hyperref}
\usepackage{longtable} % longtable support required by pandoc >1.10
\usepackage{booktabs} % table support for pandoc > 1.12.2
\usepackage[inline]{enumitem} % IRkernel/repr support (it uses the enumerate* environment)
\usepackage[normalem]{ulem} % ulem is needed to support strikethroughs (\sout)
% normalem makes italics be italics, not underlines
% Colors for the hyperref package
\definecolor{urlcolor}{rgb}{0,.145,.698}
\definecolor{linkcolor}{rgb}{.71,0.21,0.01}
\definecolor{citecolor}{rgb}{.12,.54,.11}
% ANSI colors
\definecolor{ansi-black}{HTML}{3E424D}
\definecolor{ansi-black-intense}{HTML}{282C36}
\definecolor{ansi-red}{HTML}{E75C58}
\definecolor{ansi-red-intense}{HTML}{B22B31}
\definecolor{ansi-green}{HTML}{00A250}
\definecolor{ansi-green-intense}{HTML}{007427}
\definecolor{ansi-yellow}{HTML}{DDB62B}
\definecolor{ansi-yellow-intense}{HTML}{B27D12}
\definecolor{ansi-blue}{HTML}{208FFB}
\definecolor{ansi-blue-intense}{HTML}{0065CA}
\definecolor{ansi-magenta}{HTML}{D160C4}
\definecolor{ansi-magenta-intense}{HTML}{A03196}
\definecolor{ansi-cyan}{HTML}{60C6C8}
\definecolor{ansi-cyan-intense}{HTML}{258F8F}
\definecolor{ansi-white}{HTML}{C5C1B4}
\definecolor{ansi-white-intense}{HTML}{A1A6B2}
% commands and environments needed by pandoc snippets
% extracted from the output of `pandoc -s`
\providecommand{\tightlist}{%
\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
% Add ',fontsize=\small' for more characters per line
\newenvironment{Shaded}{}{}
\newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{{#1}}}}
\newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{{#1}}}
\newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{{#1}}}
\newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{{#1}}}
\newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{{#1}}}
\newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{{#1}}}
\newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{{#1}}}
\newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{{#1}}}}
\newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{{#1}}}
\newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{{#1}}}}
\newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{{#1}}}
\newcommand{\RegionMarkerTok}[1]{{#1}}
\newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{{#1}}}}
\newcommand{\NormalTok}[1]{{#1}}
% Additional commands for more recent versions of Pandoc
\newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{{#1}}}
\newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{{#1}}}
\newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{{#1}}}
\newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{{#1}}}
\newcommand{\ImportTok}[1]{{#1}}
\newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{{#1}}}}
\newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{{#1}}}}}
\newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{{#1}}}}}
\newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{{#1}}}
\newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{{#1}}}}
\newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{{#1}}}
\newcommand{\BuiltInTok}[1]{{#1}}
\newcommand{\ExtensionTok}[1]{{#1}}
\newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{{#1}}}
\newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{{#1}}}
\newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{{#1}}}}}
\newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{{#1}}}}}
% Define a nice break command that doesn't care if a line doesn't already
% exist.
\def\br{\hspace*{\fill} \\* }
% Math Jax compatability definitions
\def\gt{>}
\def\lt{<}
% Document parameters
\title{Introduction to python-igraph}
% Pygments definitions
\makeatletter
\def\PY@reset{\let\PY@it=\relax \let\PY@bf=\relax%
\let\PY@ul=\relax \let\PY@tc=\relax%
\let\PY@bc=\relax \let\PY@ff=\relax}
\def\PY@tok#1{\csname PY@tok@#1\endcsname}
\def\PY@toks#1+{\ifx\relax#1\empty\else%
\PY@tok{#1}\expandafter\PY@toks\fi}
\def\PY@do#1{\PY@bc{\PY@tc{\PY@ul{%
\PY@it{\PY@bf{\PY@ff{#1}}}}}}}
\def\PY#1#2{\PY@reset\PY@toks#1+\relax+\PY@do{#2}}
\expandafter\def\csname PY@tok@gd\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.63,0.00,0.00}{##1}}}
\expandafter\def\csname PY@tok@gu\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.50,0.00,0.50}{##1}}}
\expandafter\def\csname PY@tok@gt\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.27,0.87}{##1}}}
\expandafter\def\csname PY@tok@gs\endcsname{\let\PY@bf=\textbf}
\expandafter\def\csname PY@tok@gr\endcsname{\def\PY@tc##1{\textcolor[rgb]{1.00,0.00,0.00}{##1}}}
\expandafter\def\csname PY@tok@cm\endcsname{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.25,0.50,0.50}{##1}}}
\expandafter\def\csname PY@tok@vg\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.10,0.09,0.49}{##1}}}
\expandafter\def\csname PY@tok@vi\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.10,0.09,0.49}{##1}}}
\expandafter\def\csname PY@tok@vm\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.10,0.09,0.49}{##1}}}
\expandafter\def\csname PY@tok@mh\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}}
\expandafter\def\csname PY@tok@cs\endcsname{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.25,0.50,0.50}{##1}}}
\expandafter\def\csname PY@tok@ge\endcsname{\let\PY@it=\textit}
\expandafter\def\csname PY@tok@vc\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.10,0.09,0.49}{##1}}}
\expandafter\def\csname PY@tok@il\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}}
\expandafter\def\csname PY@tok@go\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.53,0.53,0.53}{##1}}}
\expandafter\def\csname PY@tok@cp\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.74,0.48,0.00}{##1}}}
\expandafter\def\csname PY@tok@gi\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.63,0.00}{##1}}}
\expandafter\def\csname PY@tok@gh\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.00,0.50}{##1}}}
\expandafter\def\csname PY@tok@ni\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.60,0.60,0.60}{##1}}}
\expandafter\def\csname PY@tok@nl\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.63,0.63,0.00}{##1}}}
\expandafter\def\csname PY@tok@nn\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.00,1.00}{##1}}}
\expandafter\def\csname PY@tok@no\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.53,0.00,0.00}{##1}}}
\expandafter\def\csname PY@tok@na\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.49,0.56,0.16}{##1}}}
\expandafter\def\csname PY@tok@nb\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}}
\expandafter\def\csname PY@tok@nc\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.00,1.00}{##1}}}
\expandafter\def\csname PY@tok@nd\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.67,0.13,1.00}{##1}}}
\expandafter\def\csname PY@tok@ne\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.82,0.25,0.23}{##1}}}
\expandafter\def\csname PY@tok@nf\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.00,1.00}{##1}}}
\expandafter\def\csname PY@tok@si\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.73,0.40,0.53}{##1}}}
\expandafter\def\csname PY@tok@s2\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}}
\expandafter\def\csname PY@tok@nt\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}}
\expandafter\def\csname PY@tok@nv\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.10,0.09,0.49}{##1}}}
\expandafter\def\csname PY@tok@s1\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}}
\expandafter\def\csname PY@tok@dl\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}}
\expandafter\def\csname PY@tok@ch\endcsname{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.25,0.50,0.50}{##1}}}
\expandafter\def\csname PY@tok@m\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}}
\expandafter\def\csname PY@tok@gp\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.00,0.50}{##1}}}
\expandafter\def\csname PY@tok@sh\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}}
\expandafter\def\csname PY@tok@ow\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.67,0.13,1.00}{##1}}}
\expandafter\def\csname PY@tok@sx\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}}
\expandafter\def\csname PY@tok@bp\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}}
\expandafter\def\csname PY@tok@c1\endcsname{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.25,0.50,0.50}{##1}}}
\expandafter\def\csname PY@tok@fm\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.00,1.00}{##1}}}
\expandafter\def\csname PY@tok@o\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}}
\expandafter\def\csname PY@tok@kc\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}}
\expandafter\def\csname PY@tok@c\endcsname{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.25,0.50,0.50}{##1}}}
\expandafter\def\csname PY@tok@mf\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}}
\expandafter\def\csname PY@tok@err\endcsname{\def\PY@bc##1{\setlength{\fboxsep}{0pt}\fcolorbox[rgb]{1.00,0.00,0.00}{1,1,1}{\strut ##1}}}
\expandafter\def\csname PY@tok@mb\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}}
\expandafter\def\csname PY@tok@ss\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.10,0.09,0.49}{##1}}}
\expandafter\def\csname PY@tok@sr\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.40,0.53}{##1}}}
\expandafter\def\csname PY@tok@mo\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}}
\expandafter\def\csname PY@tok@kd\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}}
\expandafter\def\csname PY@tok@mi\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.40,0.40,0.40}{##1}}}
\expandafter\def\csname PY@tok@kn\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}}
\expandafter\def\csname PY@tok@cpf\endcsname{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.25,0.50,0.50}{##1}}}
\expandafter\def\csname PY@tok@kr\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}}
\expandafter\def\csname PY@tok@s\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}}
\expandafter\def\csname PY@tok@kp\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}}
\expandafter\def\csname PY@tok@w\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.73,0.73}{##1}}}
\expandafter\def\csname PY@tok@kt\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.69,0.00,0.25}{##1}}}
\expandafter\def\csname PY@tok@sc\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}}
\expandafter\def\csname PY@tok@sb\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}}
\expandafter\def\csname PY@tok@sa\endcsname{\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}}
\expandafter\def\csname PY@tok@k\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.00,0.50,0.00}{##1}}}
\expandafter\def\csname PY@tok@se\endcsname{\let\PY@bf=\textbf\def\PY@tc##1{\textcolor[rgb]{0.73,0.40,0.13}{##1}}}
\expandafter\def\csname PY@tok@sd\endcsname{\let\PY@it=\textit\def\PY@tc##1{\textcolor[rgb]{0.73,0.13,0.13}{##1}}}
\def\PYZbs{\char`\\}
\def\PYZus{\char`\_}
\def\PYZob{\char`\{}
\def\PYZcb{\char`\}}
\def\PYZca{\char`\^}
\def\PYZam{\char`\&}
\def\PYZlt{\char`\<}
\def\PYZgt{\char`\>}
\def\PYZsh{\char`\#}
\def\PYZpc{\char`\%}
\def\PYZdl{\char`\$}
\def\PYZhy{\char`\-}
\def\PYZsq{\char`\'}
\def\PYZdq{\char`\"}
\def\PYZti{\char`\~}
% for compatibility with earlier versions
\def\PYZat{@}
\def\PYZlb{[}
\def\PYZrb{]}
\makeatother
% Exact colors from NB
\definecolor{incolor}{rgb}{0.0, 0.0, 0.5}
\definecolor{outcolor}{rgb}{0.545, 0.0, 0.0}
% Prevent overflowing lines due to hard-to-break entities
\sloppy
% Setup hyperref package
\hypersetup{
breaklinks=true, % so long urls are correctly broken across lines
colorlinks=true,
urlcolor=urlcolor,
linkcolor=linkcolor,
citecolor=citecolor,
}
% Slightly bigger margins than the latex defaults
\geometry{verbose,tmargin=1in,bmargin=1in,lmargin=1in,rmargin=1in}
\usepackage{pstricks}
\begin{document}
\author{Soroosh Nazem}
\maketitle
In this tutorial, we are going to introduce python-igraph that is packages for network analysis. igraph provides a huge amount of facilities for those who want to do any analysis on networks, from elementary aspects to advanced ones like shortest path, community detection and clustering, network traffic analysis and so forth. In this tutorial, we are going to introduce igraph by a real-life example which is finding a route in Australian road network between two Australian cities with minimum duration.
\tableofcontents
\section{The Problem}\label{the-problem}
In figure \ref{AustralianCities}, a road network between major Australian cities are shown. The numbers written on the roads are the amount of hours between the two cities. Here for each city, we are going to find a path that minimize the spent hours between any two cities. In graph theory, this problem is called \textbf{shortest path problem}.
For finding the shortest paths in a graph, there are different algorithms. Depending on the type of graph and our objective, one algorithm may work better than others. For example, some algorithms work better on weighted graph, some others on unweighted, some work better on directed graphs, some on undirected and so forth. Some well-known algorithms are Dijkstra algorithm, Bellman-Ford, Breadth first search. In order to see the list of algorithm and their comparison with respect to complexity and application, see
\href{https://en.wikipedia.org/wiki/Shortest_path_problem#Algorithms}{here}.
Here we are not going to explain the algorithms in detail, we just want to use the built-in methods in igraph.
\begin{center}
\begin{figure}
\includegraphics{AustralianCities.png}
\caption{Logical presentation of road network among major cities in Australia}\label{AustralianCities}
\end{figure}
\end{center}
\section{Introduction to
python-igraph}\label{introduction-to-python-igraph}
For solving the shortest path problem in igraph, at first we should import igraph package:
\vspace{0.15cm}
\begin{tcolorbox}[colback=red!5!white,colframe=red!75!black,title=Input:]
\begin{Verbatim}[commandchars=\\\{\}]
\PY{k}{import} \PY{n+nn}{igraph} \PY{k+kn}{as} \PY{n+nn}{ig}
\end{Verbatim}
\end{tcolorbox}
Now, by \texttt{Graph()} method, we initiate a graph that here we call it \texttt{g}.
\vspace{0.15cm}
\begin{tcolorbox}[colback=red!5!white,colframe=red!75!black,title=Input:]
\begin{Verbatim}[commandchars=\\\{\}]
\PY{n}{g} \PY{o}{=} \PY{n}{ig}\PY{o}{.}\PY{n}{Graph}\PY{p}{(}\PY{p}{)}
\PY{k}{print} \PY{n}{g}
\end{Verbatim}
\end{tcolorbox}
\begin{tcolorbox}[colframe=blue!50!black,colback=white,title=Output:]
\begin{Verbatim}[commandchars=\\\{\}]
IGRAPH U--- 0 0 --
\end{Verbatim}
\end{tcolorbox}
By \texttt{ \color{green} {print}} \texttt{g}, we can get some general information about \texttt{g}. As you see above, graph \texttt{g} is undirected with no vertex and no edge.
Then, by \texttt{add\_vertices()} method, we can request to add vertices to the graph. Here, since the number of cities is 9, we add 9 vertices to the \texttt{g}.
\begin{tcolorbox}[colback=red!5!white,colframe=red!75!black,title=Input:]
\begin{Verbatim}[commandchars=\\\{\}]
\PY{n}{g}\PY{o}{.}\PY{n}{add\PYZus{}vertices}\PY{p}{(}\PY{l+m+mi}{9}\PY{p}{)}
\PY{k}{print} \PY{n}{g}
\end{Verbatim}
\end{tcolorbox}
\begin{tcolorbox}[colframe=blue!50!black,colback=white,title=Output:]
\begin{Verbatim}[commandchars=\\\{\}]
IGRAPH U--- 9 0 --
\end{Verbatim}
\end{tcolorbox}
As you see, right now \texttt{g} has 9 vertices and 0 edge. now, it is time to add some edges to \texttt{g}. Here, we could have a more concise solution which was giving the number of vertices when initiating the graph:
\vspace{0.15cm}
\begin{tcolorbox}[colback=red!5!white,colframe=red!75!black,title=Input:]
\begin{Verbatim}[commandchars=\\\{\}]
\PY{n}{g} \PY{o}{=} \PY{n}{ig}\PY{o}{.}\PY{n}{Graph}\PY{p}{(}\PY{l+m+mi}{9}\PY{p}{)}
\end{Verbatim}
\end{tcolorbox}
In the next step, we want to give label to the edges
\begin{tcolorbox}[colback=red!5!white,colframe=red!75!black,title=Input:]
\begin{Verbatim}[commandchars=\\\{\}]
\PY{n}{g}\PY{o}{.}\PY{n}{vs}\PY{p}{[}\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{label}\PY{l+s+s2}{\PYZdq{}}\PY{p}{]}\PY{o}{=}\PY{p}{[}\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{Sydney}\PY{l+s+s2}{\PYZdq{}}\PY{p}{,}\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{Melbourne}\PY{l+s+s2}{\PYZdq{}}\PY{p}{,}\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{Canberra}\PY{l+s+s2}{\PYZdq{}}\PY{p}{,}\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{Brisbane}\PY{l+s+s2}{\PYZdq{}}\PY{p}{,}\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{Adelaide}\PY{l+s+s2}{\PYZdq{}}\PY{p}{,}
\PY{l+m+mi}{Alice Springs}\PY{l+s+s2}{\PYZdq{}}\PY{p}{,}\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{Cairns}\PY{l+s+s2}{\PYZdq{}}\PY{p}{,}\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{Darwin}\PY{l+s+s2}{\PYZdq{}}\PY{p}{,}\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{Perth}\PY{l+s+s2}{\PYZdq{}}\PY{p}{]}
\end{Verbatim}
\end{tcolorbox}
Now, we have to add the edges to \texttt{g}. By \texttt{add\_edge()}, we just add one edge to the graph. By \texttt{add\_edges()}, we add a list of edges to the graph. Edges are defined by their end-points indices.
\vspace{0.15cm}
\begin{tcolorbox}[colback=red!5!white,colframe=red!75!black,title=Input:]
\begin{Verbatim}[commandchars=\\\{\}]
\PY{n}{g}\PY{o}{.}\PY{n}{add\PYZus{}edge}\PY{p}{(}\PY{l+m+mi}{0}\PY{p}{,}\PY{l+m+mi}{1}\PY{p}{)}
\PY{n}{g}\PY{o}{.}\PY{n}{add\PYZus{}edges}\PY{p}{(}\PY{p}{[}\PY{p}{(}\PY{l+m+mi}{0}\PY{p}{,}\PY{l+m+mi}{2}\PY{p}{)}\PY{p}{,}\PY{p}{(}\PY{l+m+mi}{0}\PY{p}{,}\PY{l+m+mi}{3}\PY{p}{)}\PY{p}{,}\PY{p}{(}\PY{l+m+mi}{1}\PY{p}{,}\PY{l+m+mi}{2}\PY{p}{)}\PY{p}{,}\PY{p}{(}\PY{l+m+mi}{1}\PY{p}{,}\PY{l+m+mi}{4}\PY{p}{)}\PY{p}{,}\PY{p}{(}\PY{l+m+mi}{2}\PY{p}{,}\PY{l+m+mi}{5}\PY{p}{)}\PY{p}{,}\PY{p}{(}\PY{l+m+mi}{3}\PY{p}{,}\PY{l+m+mi}{5}\PY{p}{)}\PY{p}{,}\PY{p}{(}\PY{l+m+mi}{3}\PY{p}{,}\PY{l+m+mi}{6}\PY{p}{)}\PY{p}{,}\PY{p}{(}\PY{l+m+mi}{4}\PY{p}{,}\PY{l+m+mi}{5}\PY{p}{)}\PY{p}{,}\PY{p}{(}\PY{l+m+mi}{4}\PY{p}{,}\PY{l+m+mi}{8}\PY{p}{)}\PY{p}{,}
\PY{p}{(}\PY{l+m+mi}{5}\PY{p}{,}\PY{l+m+mi}{6}\PY{p}{)}\PY{p}{,}\PY{p}{(}\PY{l+m+mi}{5}\PY{p}{,}\PY{l+m+mi}{7}\PY{p}{)}\PY{p}{,}\PY{p}{(}\PY{l+m+mi}{6}\PY{p}{,}\PY{l+m+mi}{7}\PY{p}{)}\PY{p}{,}\PY{p}{(}\PY{l+m+mi}{7}\PY{p}{,}\PY{l+m+mi}{8}\PY{p}{)}\PY{p}{]}\PY{p}{)}
\PY{k}{print} \PY{n}{g}
\end{Verbatim}
\end{tcolorbox}
\begin{tcolorbox}[colframe=blue!50!black,colback=white,title=Output:]
\begin{Verbatim}[commandchars=\\\{\}]
IGRAPH U--- 9 14 --
+ edges:
0 -- 1 2 3 3 -- 0 5 6 6 -- 3 5 7
1 -- 0 2 4 4 -- 1 5 8 7 -- 5 6 8
2 -- 0 1 5 5 -- 2 3 4 6 7 8 -- 4 7
\end{Verbatim}
\end{tcolorbox}
Right now, we introduce \texttt{summary()} method. As you
see in the following, the difference between \texttt{
\color{green} {print}} \texttt{g.summary()} is that in the \texttt{summary()} the list of edges are not shown anymore. This method can be useful when the graph is very big with a lot of edges.
\vspace{0.15cm}
\begin{tcolorbox}[colback=red!5!white,colframe=red!75!black,title=Input:]
\begin{Verbatim}[commandchars=\\\{\}]
\PY{k}{print} \PY{n}{g}\PY{o}{.}\PY{n}{summary}\PY{p}{(}\PY{p}{)}
\end{Verbatim}
\end{tcolorbox}
\begin{tcolorbox}[colframe=blue!50!black,colback=white,title=Output:]
\begin{Verbatim}[commandchars=\\\{\}]
IGRAPH U--- 9 14 --
\end{Verbatim}
\end{tcolorbox}
Now, we have to add the weights of edges to the graph:
\begin{tcolorbox}[colback=red!5!white,colframe=red!75!black,title=Input:]
\begin{Verbatim}[commandchars=\\\{\}]
\PY{n}{g}\PY{o}{.}\PY{n}{es}\PY{p}{[}\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{weight}\PY{l+s+s2}{\PYZdq{}}\PY{p}{]}\PY{o}{=}\PY{p}{[}\PY{l+m+mi}{12}\PY{p}{,} \PY{l+m+mi}{4}\PY{p}{,} \PY{l+m+mi}{9}\PY{p}{,} \PY{l+m+mi}{6}\PY{p}{,} \PY{l+m+mi}{1}\PY{p}{,} \PY{l+m+mi}{8}\PY{p}{,} \PY{l+m+mi}{15}\PY{p}{,} \PY{l+m+mi}{31}\PY{p}{,} \PY{l+m+mi}{22}\PY{p}{,} \PY{l+m+mi}{8}\PY{p}{,} \PY{l+m+mi}{15}\PY{p}{,} \PY{l+m+mi}{32}\PY{p}{,}
\PY{l+m+mi}{24}\PY{p}{,} \PY{l+m+mi}{15}\PY{p}{,} \PY{l+m+mi}{30}\PY{p}{,} \PY{l+m+mi}{48}\PY{p}{]}
\end{Verbatim}
\end{tcolorbox}
There are three useful methods for checking is the graph is directed,
weighted and connected. The result is a boolean value. Besides by
\texttt{degree()} method, we can have the degrees of vertices.
\vspace{0.15cm}
\begin{tcolorbox}[colback=red!5!white,colframe=red!75!black,title=Input:]
\begin{Verbatim}[commandchars=\\\{\}]
\PY{k}{print} \PY{n}{g}\PY{o}{.}\PY{n}{degree}\PY{p}{(}\PY{p}{)}
\PY{k}{print} \PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{Number of vertices and edges in g are }\PY{l+s+s2}{\PYZdq{}}\PY{p}{,}\PY{n}{g}\PY{o}{.}\PY{n}{vcount}\PY{p}{(}\PY{p}{)}\PY{p}{,} \PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{ and }\PY{l+s+s2}{\PYZdq{}}\PY{p}{,} \PY{n}{g}\PY{o}{.}\PY{n}{ecount}\PY{p}{(}\PY{p}{)}
\PY{k}{print} \PY{n}{g}\PY{o}{.}\PY{n}{is\PYZus{}directed}\PY{p}{(}\PY{p}{)}
\PY{k}{print} \PY{n}{g}\PY{o}{.}\PY{n}{is\PYZus{}weighted}\PY{p}{(}\PY{p}{)}
\PY{k}{print} \PY{n}{g}\PY{o}{.}\PY{n}{is\PYZus{}connected}\PY{p}{(}\PY{p}{)}
\end{Verbatim}
\end{tcolorbox}
\begin{tcolorbox}[colframe=blue!50!black,colback=white,title=Output:]
\begin{Verbatim}[commandchars=\\\{\}]
[3, 3, 3, 3, 3, 5, 3, 3, 2]
Number of vertices and edges in g are 9 and 14
False
True
True
\end{Verbatim}
\end{tcolorbox}
At this point, all data are imported into igraph and we can start to do our analysis
\section{Network Analysis}
We are going to find the shortest path between all these cities, for this, we use \texttt{shortest\_paths\_dijkstra()} method in the following way:
\vspace{0.15cm}
\begin{tcolorbox}[colback=red!5!white,colframe=red!75!black,title=Input:]
\begin{Verbatim}[commandchars=\\\{\}]
\PY{n}{shortestLength=}\PY{n}{g}\PY{o}{.}\PY{n}{shortest\_paths\_dijkstra}\PY{p}{(}\PY{n}{weights=}\PY{n}{g}\PY{o}{.}\PY{n}{es}\PY{p}{[}\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{weight}\PY{l+s+s2}{\PYZdq{}}\PY{p}{]}\PY{p}{)}
\PY{k}{print} \PY{n}{shortestLength}
\end{Verbatim}
\end{tcolorbox}
\begin{tcolorbox}[colframe=blue!50!black,colback=white,title=Output:]
\begin{Verbatim}[commandchars=\\\{\}]
[[0.0, 10.0, 4.0, 9.0, 18.0, 19.0, 31.0, 34.0, 50.0], [10.0, 0.0, 6.0, 19.0,
8.0, 21.0, 41.0, 36.0, 40.0], [4.0, 6.0, 0.0, 13.0, 14.0, 15.0, 35.0, 30.0, 46.0
], [9.0, 19.0, 13.0, 0.0, 27.0, 28.0, 22.0, 43.0, 59.0], [18.0, 8.0, 14.0, 27.0,
0.0, 15.0, 39.0, 30.0, 32.0], [19.0, 21.0, 15.0, 28.0, 15.0, 0.0, 24.0, 15.0,
47.0], [31.0, 41.0, 35.0, 22.0, 39.0, 24.0, 0.0, 30.0, 71.0], [34.0, 36.0, 30.0
, 43.0, 30.0, 15.0, 30.0, 0.0, 48.0], [50.0, 40.0, 46.0, 59.0, 32.0, 47.0, 71.0
, 48.0, 0.0]]
\end{Verbatim}
\end{tcolorbox}
In the output, we have a list of lists that shows the length of shortest distance between cities. The minimum distance of each city from itself is correctly zero. But we are interested as well to find the routes that lead us to the shortest paths. Let us find the shortest paths from Sydney to other cities. In graph \texttt{g}, the index of Sydney is 0:
\vspace{0.15cm}
\begin{tcolorbox}[colback=red!5!white,colframe=red!75!black,title=Input:]
\begin{Verbatim}[commandchars=\\\{\}]
\PY{n}{shortestPaths=}\PY{n}{g}\PY{o}{.}\PY{n}{get\_shortest\_paths}\PY{p}{(}\PY{l+m+mi}{0}\PY{n}{,}\PY{n}{weights=}\PY{n}{g}\PY{o}{.}\PY{n}{es}\PY{p}{[}\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{weight}\PY{l+s+s2}{\PYZdq{}}\PY{p}{]}\PY{n}{,}\PY{n}{output=}\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{vpath}\PY{l+s+s2}{\PYZdq{}}\PY{p}{)}\PY{p}{[}\PY{l+m+mi}{1}\PY{p}{:}\PY{p}{]}
\PY{k}{print} \PY{n}{shortestPaths}
\end{Verbatim}
\end{tcolorbox}
\begin{tcolorbox}[colframe=blue!50!black,colback=white,title=Output:]
\begin{Verbatim}[commandchars=\\\{\}]
[[0, 2, 1], [0, 2], [0, 3], [0, 2, 1, 4], [0, 2, 5], [0, 3, 6], [0, 2, 5, 7],
[0, 2, 1, 4, 8]]
\end{Verbatim}
\end{tcolorbox}
For Sydney we could find the shortest paths to other Australian cities. Here, \texttt{output="vpath"} means that we are interested in having the list of paths by vertices not by edges. If we want to have the path by edges we have to put \texttt{output="epath"}. We are interested more in the name of cities instead of their indices, so we can get the names by the following code:
\vspace{0.15cm}
\begin{tcolorbox}[colback=red!5!white,colframe=red!75!black,title=Input:]
\begin{Verbatim}[commandchars=\\\{\}]
[g.vs[i][\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{label}\PY{l+s+s2}{\PYZdq{}}] \PY{k}{for} i \PY{k}{in} shortestPaths]
\end{Verbatim}
\end{tcolorbox}
\begin{tcolorbox}[colframe=blue!50!black,colback=white,title=Output:]
\begin{Verbatim}[commandchars=\\\{\}]
[['Sydney', 'Canberra', 'Melbourne'],
['Sydney', 'Canberra'],
['Sydney', 'Brisbane'],
['Sydney', 'Canberra', 'Melbourne', 'Adelaide'],
['Sydney', 'Canberra', 'Alice Springs'],
['Sydney', 'Brisbane', 'Cairns'],
['Sydney', 'Canberra', 'Alice Springs', 'Darwin'],
['Sydney', 'Canberra', 'Melbourne', 'Adelaide', 'Perth']]
\end{Verbatim}
\end{tcolorbox}
\section{Some More Points}
In this section we introduce a concept that can be very informative about the paths in the network. This concept is called \texttt{betweenness centrality}. Betweenness centrality can be defined for both vertices and edges. The betweenness centrality of a vertex $v$ is given by the following formula:
\[
g(v)= \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}
\]
where $\sigma_{st}$ is the total number of shortest paths from node $s$ to node $t$ and $\sigma _{st}(v)$ is the number of those paths that pass through $v$, while the betweenness centrality for an edge $e$ is:
$$
g(e)= \sum_{s \neq t \in V} \frac{\sigma_{st}(e)}{\sigma_{st}}
$$
where $\sigma_{st}$ is the total number of shortest paths from node $s$ to node $t$ and $\sigma_{st}(e)$ is the number of those paths that pass through $e$.In fact, betweenness centrality tells us in what percentage of shortest paths a vertex or an edge is present. Let us return to our example and see the betweenness centrality of all cities and roads. For cities, we have:
\vspace{0.15cm}
\begin{tcolorbox}[colback=red!5!white,colframe=red!75!black,title=Input:]
\begin{Verbatim}[commandchars=\\\{\}]
g.vs.betweenness(weights=g.es[\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{weight}\PY{l+s+s2}{\PYZdq{}}])
\end{Verbatim}
\end{tcolorbox}
\begin{tcolorbox}[colframe=blue!50!black,colback=white,title=Output:]
\begin{Verbatim}[commandchars=\\\{\}]
[8.0, 6.0, 13.0, 3.0, 6.0, 7.0, 0.0, 0.0, 0.0]
\end{Verbatim}
\end{tcolorbox}
As you see, Canberra has the maximum presence in the shortest paths, while Cairns, Darwin and Perth do not exist in any shortest path among the cities. On the other hand, for roads the centralities are:
\vspace{0.15cm}
\begin{tcolorbox}[colback=red!5!white,colframe=red!75!black,title=Input:]
\begin{Verbatim}[commandchars=\\\{\}]
g.es.edge\_betweenness(weights=g.es[\PY{l+s+s2}{\PYZdq{}}\PY{l+s+s2}{weight}\PY{l+s+s2}{\PYZdq{}}])
\end{Verbatim}
\end{tcolorbox}
\begin{tcolorbox}[colframe=blue!50!black,colback=white,title=Output:]
\begin{Verbatim}[commandchars=\\\{\}]
[0.0, 14.0, 10.0, 12.0, 8.0, 8.0, 0.0, 4.0, 5.0, 7.0, 3.0, 6.0, 1.0, 1.0]
\end{Verbatim}
\end{tcolorbox}
There are two roads that are absent in all shortest path, even the cities that are connected directly by that road. These two roads are "Sydney-Melbourne" and "Brisbane-Alice Springs" roads. In fact, we can claim these two direct roads are useless.
\section{Conclusion}
igraph is a very powerful package for network analysis. You can find the complete documentation of python-igraph in its \href{http://igraph.org/python/}{webpage}.Here; I tried to give you an introduction to igraph by a simple practical example.
There are much more complicated examples on network analysis that can be imported to igraph like social networks, networks of diseases and so forth.
\end{document}
