%* graphs.tex *%

%***********************************************************************

%  This code is part of GLPK (GNU Linear Programming Kit).

%

%  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,

%  2009, 2010 Andrew Makhorin, Department for Applied Informatics,

%  Moscow Aviation Institute, Moscow, Russia. All rights reserved.

%  E-mail: <mao@gnu.org>.

%

%  GLPK is free software: you can redistribute it and/or modify it

%  under the terms of the GNU General Public License as published by

%  the Free Software Foundation, either version 3 of the License, or

%  (at your option) any later version.

%

%  GLPK is distributed in the hope that it will be useful, but WITHOUT

%  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY

%  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public

%  License for more details.

%

%  You should have received a copy of the GNU General Public License

%  along with GLPK. If not, see <http://www.gnu.org/licenses/>.

%***********************************************************************

\documentclass[11pt]{report}

\usepackage{amssymb}

\usepackage[dvipdfm,linktocpage,colorlinks,linkcolor=blue,

urlcolor=blue]{hyperref}

\usepackage[all]{xy}

\renewcommand\contentsname{\sf\bfseries Contents}

\renewcommand\chaptername{\sf\bfseries Chapter}

\renewcommand\appendixname{\sf\bfseries Appendix}

\begin{document}

\thispagestyle{empty}

\begin{center}

\vspace*{1in}

\begin{huge}

\sf\bfseries GNU Linear Programming Kit

\end{huge}

\vspace{0.5in}

\begin{LARGE}

\sf Graph and Network Routines

\end{LARGE}

\vspace{0.5in}

\begin{LARGE}

\sf for GLPK Version 4.45

\end{LARGE}

\vspace{0.5in}

\begin{Large}

\sf (DRAFT, December 2010)

\end{Large}

\end{center}

\newpage

\vspace*{1in}

\vfill

\noindent

The GLPK package is part of the GNU Project released under the aegis of

GNU.

\medskip \noindent

Copyright \copyright{} 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,

2008, 2009, 2010 Andrew Makhorin, Department for Applied Informatics,

Moscow Aviation Institute, Moscow, Russia. All rights reserved.

\medskip \noindent

Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA

02110-1301, USA.

\medskip \noindent

Permission is granted to make and distribute verbatim copies of this

manual provided the copyright notice and this permission notice are

preserved on all copies.

\medskip \noindent

Permission is granted to copy and distribute modified versions of this

manual under the conditions for verbatim copying, provided also that the

entire resulting derived work is distributed under the terms of

a permission notice identical to this one.

\medskip \noindent

Permission is granted to copy and distribute translations of this manual

into another language, under the above conditions for modified versions.

\tableofcontents

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Basic Graph API Routines}

\section{Graph program object}

In GLPK the base program object used to represent graphs and networks

is a directed graph (digraph).

Formally, {\it digraph} (or simply, {\it graph}) is a pair $G=(V,A)$,

where $V$ is a set of {\it vertices}, and $A$ is a set

{\it arcs}.\footnote{$A$ may be a multiset.} Each arc $a\in A$ is an

ordered pair of vertices $a=(x,y)$, where $x\in V$ is called {\it tail

vertex} of arc $a$, and $y\in V$ is called its {\it head vertex}.

Representation of a graph in the program includes three structs defined

by typedef in the header \verb|glpk.h|:

\medskip

$\bullet$ \verb|glp_graph|, which represents the graph in a whole,

$\bullet$ \verb|glp_vertex|, which represents a vertex of the graph, and

$\bullet$ \verb|glp_arc|, which represents an arc of the graph.

\medskip

All these three structs are ``semi-opaque'', i.e. the application

program can directly access their fields through pointers, however,

changing the fields directly is not allowed---all changes should be

performed only with appropriate GLPK API routines.

\newpage

\newenvironment{comment}

{\addtolength{\leftskip}{17pt}\noindent}

{\par\addtolength{\leftskip}{-17pt}}

\noindent

{\bf glp\_graph.} The struct \verb|glp_graph| has the following

fields available to the application program:

\medskip

\noindent

\verb|char *name;|

\begin{comment}Symbolic name assigned to the graph. It is a pointer to

a null terminated character string of length from 1 to 255 characters.

If no name is assigned to the graph, this field contains \verb|NULL|.

\end{comment}

\medskip

\noindent

\verb|int nv;|

\begin{comment}The number of vertices in the graph, $nv\geq 0$.

\end{comment}

\medskip

\noindent

\verb|int na;|

\begin{comment}The number of arcs in the graph, $na\geq 0$.

\end{comment}

\medskip

\noindent

\verb|glp_vertex **v;|

\begin{comment}Pointer to an array containing the list of vertices.

Element $v[0]$ is not used. Element $v[i]$, $1\leq i\leq nv$, is a

pointer to $i$-th vertex of the graph. Note that on adding new vertices

to the graph the field $v$ may be altered due to reallocation. However,

pointers $v[i]$ are not changed while corresponding vertices exist in

the graph.

\end{comment}

\medskip

\noindent

\verb|int v_size;|

\begin{comment}Size of vertex data blocks, in bytes,

$0\leq v\_size\leq 256$. (See also the field \verb|data| in the struct

\verb|glp_vertex|.)

\end{comment}

\medskip

\noindent

\verb|int a_size;|

\begin{comment}Size of arc data blocks, in bytes,

$0\leq v\_size\leq 256$. (See also the field \verb|data| in the struct

\verb|glp_arc|.)

\end{comment}

\bigskip

\noindent

{\bf glp\_vertex.} The struct \verb|glp_vertex| has the following

fields available to the application program:

\medskip

\noindent

\verb|int i;|

\begin{comment}Ordinal number of the vertex, $1\leq i\leq nv$. Note

that element $v[i]$ in the struct \verb|glp_graph| points to the vertex,

whose ordinal number is $i$.

\end{comment}

\medskip

\noindent

\verb|char *name;|

\begin{comment}Symbolic name assigned to the vertex. It is a pointer to

a null terminated character string of length from 1 to 255 characters.

If no name is assigned to the vertex, this field contains \verb|NULL|.

\end{comment}

\medskip

\noindent

\verb|void *data;|

\begin{comment}Pointer to a data block associated with the vertex. This

data block is automatically allocated on creating a new vertex and freed

on deleting the vertex. If $v\_size=0$, the block is not allocated, and

this field contains \verb|NULL|.

\end{comment}

\medskip

\noindent

\verb|void *temp;|

\begin{comment}Working pointer, which may be used freely for any

purposes. The application program can change this field directly.

\end{comment}

\medskip

\noindent

\verb|glp_arc *in;|

\begin{comment}Pointer to the (unordered) list of incoming arcs. If the

vertex has no incoming arcs, this field contains \verb|NULL|.

\end{comment}

\medskip

\noindent

\verb|glp_arc *out;|

\begin{comment}Pointer to the (unordered) list of outgoing arcs. If the

vertex has no outgoing arcs, this field contains \verb|NULL|.

\end{comment}

\bigskip

\noindent

{\bf glp\_arc.} The struct \verb|glp_arc| has the following fields

available to the application program:

\medskip

\noindent

\verb|glp_vertex *tail;|

\begin{comment}Pointer to a vertex, which is tail endpoint of the arc.

\end{comment}

\medskip

\noindent

\verb|glp_vertex *head;|

\begin{comment}Pointer to a vertex, which is head endpoint of the arc.

\end{comment}

\medskip

\noindent

\verb|void *data;|

\begin{comment}Pointer to a data block associated with the arc. This

data block is automatically allocated on creating a new arc and freed on

deleting the arc. If $v\_size=0$, the block is not allocated, and this

field contains \verb|NULL|.

\end{comment}

\medskip

\noindent

\verb|void *temp;|

\begin{comment}Working pointer, which may be used freely for any

purposes. The application program can change this field directly.

\end{comment}

\medskip

\noindent

\verb|glp_arc *t_next;|

\begin{comment}Pointer to another arc, which has the same tail endpoint

as this one. \verb|NULL| in this field indicates the end of the list of

outgoing arcs.

\end{comment}

\medskip

\noindent

\verb|glp_arc *h_next;|

\begin{comment}Pointer to another arc, which has the same head endpoint

as this one. \verb|NULL| in this field indicates the end of the list of

incoming arcs.

\end{comment}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\section{Graph creating and modifying routines}

\subsection{glp\_create\_graph---create graph}

\subsubsection*{Synopsis}

\begin{verbatim}

glp_graph *glp_create_graph(int v_size, int a_size);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_create_graph| creates a new graph, which

initially is\linebreak empty, i.e. has no vertices and arcs.

The parameter \verb|v_size| specifies the size of vertex data blocks,

in bytes, $0\leq v\_size\leq 256$.

The parameter \verb|a_size| specifies the size of arc data blocks, in

bytes, $0\leq a\_size\leq 256$.

\subsubsection*{Returns}

The routine returns a pointer to the graph created.

\subsection{glp\_set\_graph\_name---assign (change) graph name}

\subsubsection*{Synopsis}

\begin{verbatim}

void glp_set_graph_name(glp_graph *G, const char *name);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_graph_name| assigns a symbolic name specified

by the character string \verb|name| (1 to 255 chars) to the graph.

If the parameter \verb|name| is \verb|NULL| or an empty string, the

routine erases the existing symbolic name of the graph.

\newpage

\subsection{glp\_add\_vertices---add new vertices to graph}

\subsubsection*{Synopsis}

\begin{verbatim}

int glp_add_vertices(glp_graph *G, int nadd);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_add_vertices| adds \verb|nadd| vertices to the

specified graph. New vertices are always added to the end of the vertex

list, so ordinal numbers of existing vertices remain unchanged. Note

that this operation may change the field \verb|v| in the struct

\verb|glp_graph| (pointer to the vertex array) due to reallocation.

Being added each new vertex is isolated, i.e. has no incident arcs.

If the size of vertex data blocks specified on creating the graph is

non-zero, the routine also allocates a memory block of that size for

each new vertex added, fills it by binary zeros, and stores a pointer to

it in the field \verb|data| of the struct \verb|glp_vertex|. Otherwise,

if the block size is zero, the field \verb|data| is set to \verb|NULL|.

\subsubsection*{Returns}

The routine \verb|glp_add_vertices| returns the ordinal number of the

first new vertex added to the graph.

\subsection{glp\_set\_vertex\_name---assign (change) vertex name}

\subsubsection*{Synopsis}

\begin{verbatim}

void glp_set_vertex_name(glp_graph *G, int i, const char *name);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_set_vertex_name| assigns a given symbolic name

(1 up to 255 characters) to \verb|i|-th vertex of the specified graph.

If the parameter \verb|name| is \verb|NULL| or empty string, the

routine erases an existing name of \verb|i|-th vertex.

\newpage

\subsection{glp\_add\_arc---add new arc to graph}

\subsubsection*{Synopsis}

\begin{verbatim}

glp_arc *glp_add_arc(glp_graph *G, int i, int j);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_add_arc| adds one new arc to the specified graph.

The parameters \verb|i| and \verb|j| specify the ordinal numbers of,

resp., tail and head endpoints (vertices) of the arc. Note that

self-loops and multiple arcs are allowed.

If the size of arc data blocks specified on creating the graph is

non-zero, the routine also allocates a memory block of that size, fills

it by binary zeros, and stores a pointer to it in the field \verb|data|

of the struct \verb|glp_arc|. Otherwise, if the block size is zero, the

field \verb|data| is set to \verb|NULL|.

\subsection{glp\_del\_vertices---delete vertices from graph}

\subsubsection*{Synopsis}

\begin{verbatim}

void glp_del_vertices(glp_graph *G, int ndel, const int num[]);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_del_vertices| deletes vertices along with all

incident arcs from the specified graph. Ordinal numbers of vertices to

be deleted should be placed in locations \verb|num[1]|, \dots,

\verb|num[ndel]|, \verb|ndel| $>0$.

Note that deleting vertices involves changing ordinal numbers of other

vertices remaining in the graph. New ordinal numbers of the remaining

vertices are assigned under the assumption that the original order of

vertices is not changed.

\subsection{glp\_del\_arc---delete arc from graph}

\subsubsection*{Synopsis}

\begin{verbatim}

void glp_del_arc(glp_graph *G, glp_arc *a);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_del_arc| deletes an arc from the specified graph.

The arc to be deleted must exist.

\subsection{glp\_erase\_graph---erase graph content}

\subsubsection*{Synopsis}

\begin{verbatim}

void glp_erase_graph(glp_graph *G, int v_size, int a_size);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_erase_graph| erases the content of the specified

graph. The effect of this operation is the same as if the graph would be

deleted with the routine \verb|glp_delete_graph| and then created anew

with the routine \verb|glp_create_graph|, with exception that the handle

(pointer) to the graph remains valid.

The parameters \verb|v_size| and \verb|a_size| have the same meaning as

for the routine \verb|glp_create_graph|.

\subsection{glp\_delete\_graph---delete graph}

\subsubsection*{Synopsis}

\begin{verbatim}

void glp_delete_graph(glp_graph *G);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_delete_graph| deletes the specified graph and

frees all the memory allocated to this program object.

\newpage

\section{Graph searching routines}

\subsection{glp\_create\_v\_index---create vertex name index}

\subsubsection*{Synopsis}

\begin{verbatim}

void glp_create_v_index(glp_graph *G);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_create_v_index| creates the name index for the

specified graph. The name index is an auxiliary data structure, which

is intended to quickly (i.e. for logarithmic time) find vertices by

their names.

This routine can be called at any time. If the name index already

exists, the routine does nothing.

\subsection{glp\_find\_vertex---find vertex by its name}

\subsubsection*{Synopsis}

\begin{verbatim}

int glp_find_vertex(glp_graph *G, const char *name);

\end{verbatim}

\subsubsection*{Returns}

The routine \verb|glp_find_vertex| returns the ordinal number of

a vertex, which is assigned (by the routine \verb|glp_set_vertex_name|)

the specified symbolic \verb|name|. If no such vertex exists, the

routine returns 0.

\subsection{glp\_delete\_v\_index---delete vertex name index}

\subsubsection*{Synopsis}

\begin{verbatim}

void glp_delete_v_index(glp_graph *G);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_delete_v_index| deletes the name index previously

created by the routine \verb|glp_create_v_index| and frees the memory

allocated to this auxiliary data structure.

This routine can be called at any time. If the name index does not

exist, the routine does nothing.

\newpage

\section{Graph reading/writing routines}

\subsection{glp\_read\_graph---read graph from plain text file}

\subsubsection*{Synopsis}

\begin{verbatim}

int glp_read_graph(glp_graph *G, const char *fname);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_read_graph| reads a graph from a plain text file,

whose name is specified by the parameter \verb|fname|. Note that before

reading data the current content of the graph object is completely

erased with the routine \verb|glp_erase_graph|.

For the file format see description of the routine

\verb|glp_write_graph|.

\subsubsection*{Returns}

If the operation was successful, the routine returns zero. Otherwise

it prints an error message and returns non-zero.

\subsection{glp\_write\_graph---write graph to plain text file}

\subsubsection*{Synopsis}

\begin{verbatim}

int glp_write_graph(glp_graph *G, const char *fname);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_write_graph| writes the graph to a plain text

file, whose name is specified by the parameter \verb|fname|.

\subsubsection*{Returns}

If the operation was successful, the routine returns zero. Otherwise

it prints an error message and returns non-zero.

\subsubsection*{File format}

The file created by the routine \verb|glp_write_graph| is a plain text

file, which contains the following information:

\begin{verbatim}

   nv na

   i[1] j[1]

   i[2] j[2]

   . . .

   i[na] j[na]

\end{verbatim}

\noindent

where:

\noindent

\verb|nv| is the number of vertices (nodes);

\noindent

\verb|na| is the number of arcs;

\noindent

\verb|i[k]|, $k=1,\dots,na$, is the index of tail vertex of arc $k$;

\noindent

\verb|j[k]|, $k=1,\dots,na$, is the index of head vertex of arc $k$.

\subsection{glp\_read\_ccdata---read graph from text file in DIMACS

clique/coloring format}

\subsubsection*{Synopsis}

\begin{verbatim}

int glp_read_ccdata(glp_graph *G, int v_wgt,

      const char *fname);

\end{verbatim}

\subsubsection*{Description}

The routine {\it glp\_read\_ccdata} reads a graph from a text file in

DIMACS clique/coloring format. (Though this format is originally

designed to represent data for the minimal vertex coloring and maximal

clique problems, it may be used to represent general undirected and

directed graphs, because the routine allows reading self-loops and

multiple edges/arcs keeping the order of vertices specified for each

edge/arc of the graph.)

The parameter $G$ specifies the graph object to be read in. Note that

before reading data the current content of the graph object is

completely erased with the routine {\it glp\_erase\_graph}.

The parameter {\it v\_wgt} specifies an offset of the field of type

{\bf double} in the vertex data block, to which the routine stores the

vertex weight. If {\it v\_wgt} $<0$, the vertex weights are not stored.

The character string {\it fname} specifies the name of a text file to

be read in. (If the file name ends with the suffix `\verb|.gz|', the

file is assumed to be compressed, in which case the routine decompresses

it ``on the fly''.)

\subsubsection*{Returns}

If the operation was successful, the routine returns zero. Otherwise,

it prints an error message and returns non-zero.

\subsubsection*{DIMACS clique/coloring format\footnote{This material is

based on the paper ``Clique and Coloring Problems Graph Format'', which

is publically available at

{\tt http://dimacs.rutgers.edu/Challenges/}.}}

The DIMACS input file is a plain ASCII text file. It contains

{\it lines} of several types described below. A line is terminated with

an end-of-line character. Fields in each line are separated by at least

one blank space. Each line begins with a one-character designator to

identify the line type.

Note that DIMACS requires all numerical quantities to be integers in

the range $[-2^{31},2^{31}-1]$ while GLPK allows the quantities to be

floating-point numbers.

\paragraph{Comment lines.} Comment lines give human-readable information

about the file and are ignored by programs. Comment lines can appear

anywhere in the file. Each comment line begins with a lower-case

character \verb|c|.

\begin{verbatim}

   c This is a comment line

\end{verbatim}

\paragraph{Problem line.} There is one problem line per data file. The

problem line must appear before any node or edge descriptor lines. It

has the following format:

\begin{verbatim}

   p edge NODES EDGES

\end{verbatim}

\noindent

The lower-case letter \verb|p| signifies that this is a problem line.

The four-character problem designator \verb|edge| identifies the file

as containing data for the minimal vertex coloring or maximal clique

problem. The \verb|NODES| field contains an integer value specifying

the number of vertices in the graph. The \verb|EDGES| field contains an

integer value specifying the number of edges (arcs) in the graph.

\paragraph{Vertex descriptors.} These lines give the weight assigned to

a vertex of the graph. There is one vertex descriptor line for each

vertex, with the following format. Vertices without a descriptor take on

a default value of 1.

\begin{verbatim}

   n ID VALUE

\end{verbatim}

\noindent

The lower-case character \verb|n| signifies that this is a vertex

descriptor line. The \verb|ID| field gives a vertex identification

number, an integer between 1 and $n$, where $n$ is the number of

vertices in the graph. The \verb|VALUE| field gives a vertex weight,

which can either positive or negative (or zero).

\paragraph{Edge descriptors.} There is one edge descriptor line for

each edge (arc) of the graph, each with the following format:

\begin{verbatim}

   e I J

\end{verbatim}

\noindent

The lower-case character \verb|e| signifies that this is an edge

descriptor line. For an edge (arc) $(i,j)$ the fields \verb|I| and

\verb|J| specify its endpoints.

\paragraph{Example.} The following example of an undirected graph:

\bigskip

\noindent\hfil

\xymatrix %@C=32pt

{&{v_1}\ar@{-}[ldd]\ar@{-}[dd]\ar@{-}[rd]\ar@{-}[rr]&&{v_2}\ar@{-}[ld]

\ar@{-}[dd]\ar@{-}[rdd]&\\

&&{v_7}\ar@{-}[ld]\ar@{-}[rd]&&\\

{v_6}\ar@{-}[r]\ar@{-}[rdd]&{v_{10}}\ar@{-}[rr]\ar@{-}[rd]\ar@{-}[dd]&&

{v_8}\ar@{-}[ld]\ar@{-}[dd]\ar@{-}[r]&{v_3}\ar@{-}[ldd]\\

&&{v_9}\ar@{-}[ld]\ar@{-}[rd]&&\\

&{v_5}\ar@{-}[rr]&&{v_4}&\\

}

\bigskip

\noindent

might be coded in DIMACS clique/coloring format as follows:

\begin{footnotesize}

\begin{verbatim}

c sample.col

c

c This is an example of the vertex coloring problem data

c in DIMACS format.

c

p edge 10 21

c

e 1 2

e 1 6

e 1 7

e 1 10

e 2 3

e 2 7

e 2 8

e 3 4

e 3 8

e 4 5

e 4 8

e 4 9

e 5 6

e 5 9

e 5 10

e 6 10

e 7 8

e 7 10

e 8 9

e 8 10

e 9 10

c

c eof

\end{verbatim}

\end{footnotesize}

\subsection{glp\_write\_ccdata---write graph to text file in DIMACS

clique/coloring format}

\subsubsection*{Synopsis}

\begin{verbatim}

int glp_write_ccdata(glp_graph *G, int v_wgt,

      const char *fname);

\end{verbatim}

\subsection*{Description}

The routine {\it glp\_write\_ccdata} writes the graph object specified

by the parameter $G$ to a text file in DIMACS clique/coloring format.

(Though this format is originally designed to represent data for the

minimal vertex coloring and maximal clique problems, it may be used to

represent general undirected and directed graphs, because the routine

allows writing self-loops and multiple edges/arcs keeping the order of

vertices specified for each edge/arc of the graph.)

The parameter {\it v\_wgt} specifies an offset of the field of type

{\bf double} in the vertex data block, which contains the vertex weight.

If {\it v\_wgt} $<0$, it is assumed that the weight of each vertex is 1.

The character string {\it fname} specifies a name of the text file to be

written out. (If the file name ends with suffix `\verb|.gz|', the file

is assumed to be compressed, in which case the routine performs

automatic compression on writing it.)

\subsubsection*{Returns}

If the operation was successful, the routine returns zero. Otherwise,

it prints an error message and returns non-zero.

\newpage

\section{Graph analysis routines}

\subsection{glp\_weak\_comp---find all weakly connected components of

graph}

\subsubsection*{Synopsis}

\begin{verbatim}

int glp_weak_comp(glp_graph *G, int v_num);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_weak_comp| finds all weakly connected components

of the specified graph.

The parameter \verb|v_num| specifies an offset of the field of type

\verb|int| in the vertex data block, to which the routine stores the

number of a weakly connected component containing that vertex. If

\verb|v_num| $<0$, no component numbers are stored.

The components are numbered in arbitrary order from 1 to \verb|nc|,

where \verb|nc| is the total number of components found,

$0\leq$ \verb|nc| $\leq|V|$.

\subsubsection*{Returns}

The routine returns \verb|nc|, the total number of components found.

\subsection{glp\_strong\_comp---find all strongly connected components

of graph}

\subsubsection*{Synopsis}

\begin{verbatim}

int glp_strong_comp(glp_graph *G, int v_num);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_strong_comp| finds all strongly connected

components of the specified graph.

The parameter \verb|v_num| specifies an offset of the field of type

\verb|int| in the vertex data block, to which the routine stores the

number of a strongly connected component containing that vertex. If

\verb|v_num| $<0$, no component numbers are stored.

The components are numbered in arbitrary order from 1 to \verb|nc|,

where \verb|nc| is the total number of components found,

$0\leq$ \verb|nc| $\leq|V|$. However, the component numbering has the

property that for every arc $(i\rightarrow j)$ in the graph the

condition $num(i)\geq num(j)$ holds.

\subsubsection*{Returns}

The routine returns \verb|nc|, the total number of components found.

\subsubsection*{References}

I.~S.~Duff, J.~K.~Reid, Algorithm 529: Permutations to block triangular

form, ACM Trans. on Math. Softw. 4 (1978), 189-92.

\subsubsection*{Example}

The following program reads a graph from a plain text file

`\verb|graph.txt|' and finds all its strongly connected components.

\begin{footnotesize}

\begin{verbatim}

#include <stddef.h>

#include <stdio.h>

#include <stdlib.h>

#include <glpk.h>

typedef struct { int num; } v_data;

#define vertex(v) ((v_data *)((v)->data))

int main(void)

{     glp_graph *G;

      int i, nc;

      G = glp_create_graph(sizeof(v_data), 0);

      glp_read_graph(G, "graph.txt");

      nc = glp_strong_comp(G, offsetof(v_data, num));

      printf("nc = %d\n", nc);

      for (i = 1; i <= G->nv; i++)

         printf("num[%d] = %d\n", i, vertex(G->v[i])->num);

      glp_delete_graph(G);

      return 0;

}

\end{verbatim}

\end{footnotesize}

\noindent

If the file `\verb|graph.txt|' contains the graph shown below:

\bigskip

\noindent\hfil

\xymatrix

{1\ar[r]&2\ar[r]&3\ar[r]\ar[dd]&4\ar[dd]\\

5\ar[u]&6\ar[l]\\

7\ar[u]&&8\ar[lu]\ar[ll]\ar[r]&9\ar[r]&10\ar[r]\ar[d]&11\ar[d]\\

12\ar[u]\ar[rru]\ar@/_/[rr]&&13\ar[ll]\ar[u]\ar[rr]&&14\ar[lu]&15\ar[l]

\\

}

\bigskip\bigskip

\noindent

the program output may look like follows:

\begin{footnotesize}

\begin{verbatim}

Reading graph from `graph.txt'...

Graph has 15 vertices and 30 arcs

31 lines were read

nc = 4

num[1] = 3

num[2] = 3

num[3] = 3

num[4] = 2

num[5] = 3

num[6] = 3

num[7] = 3

num[8] = 3

num[9] = 1

num[10] = 1

num[11] = 1

num[12] = 4

num[13] = 4

num[14] = 1

num[15] = 1

\end{verbatim}

\end{footnotesize}

\subsection{glp\_top\_sort---topological sorting of acyclic digraph}

\subsubsection*{Synopsis}

\begin{verbatim}

int glp_top_sort(glp_graph *G, int v_num);

\end{verbatim}

\subsubsection*{Description}

The routine \verb|glp_top_sort| performs topological sorting of

vertices of the specified acyclic digraph.

The parameter \verb|v_num| specifies an offset of the field of type

\verb|int| in the vertex data block, to which the routine stores the

vertex number assigned. If \verb|v_num| $<0$, vertex numbers are not

stored.

The vertices are numbered from 1 to $n$, where $n$ is the total number

of vertices in the graph. The vertex numbering has the property that

for every arc $(i\rightarrow j)$ in the graph the condition

$num(i)<num(j)$ holds. Special case $num(i)=0$ means that vertex $i$ is

not assigned a number, because the graph is {\it not} acyclic.