%* 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.

 \subsubsection*{Returns}

 If the graph is acyclic and therefore all the vertices have been

 assigned numbers, the routine \verb|glp_top_sort| returns zero.

 Otherwise, if the graph is not acyclic, the routine returns the number

 of vertices which have not been numbered, i.e. for which $num(i)=0$.

 \subsubsection*{Example}

 The following program reads a digraph from a plain text file

 `\verb|graph.txt|' and performs topological sorting of its vertices.

 \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, cnt;

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

       glp_read_graph(G, "graph.txt");

       cnt = glp_top_sort(G, offsetof(v_data, num));

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

       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 @=20pt

 {

 1\ar[rrr]&&&2\ar[r]\ar[rddd]&3\ar[rd]&&&&\\

 &&&4\ar[ru]&&5\ar[r]&6\ar[rd]\ar[dd]&&\\

 7\ar[r]&8\ar[r]&9\ar[ruu]\ar[ru]\ar[r]\ar[rd]&10\ar[rr]\ar[rru]&&

 11\ar[ru]&&12\ar[r]&13\\

 &&&14\ar[r]&15\ar[rrru]\ar[rr]&&16\ar[rru]\ar[rr]&&17\\

 }

 \bigskip\bigskip

 \noindent

 the program output may look like follows:

 \begin{footnotesize}

 \begin{verbatim}

 Reading graph from `graph.txt'...

 Graph has 17 vertices and 23 arcs

 24 lines were read

 cnt = 0

 num[1] = 8

 num[2] = 9

 num[3] = 10

 num[4] = 4

 num[5] = 11

 num[6] = 12

 num[7] = 1

 num[8] = 2

 num[9] = 3

 num[10] = 5

 num[11] = 6

 num[12] = 14

 num[13] = 16

 num[14] = 7

 num[15] = 13

 num[16] = 15

 num[17] = 17

 \end{verbatim}

 \end{footnotesize}

 \noindent

 The output corresponds to the following vertex numbering:

 \bigskip

 \noindent\hfil

 \xymatrix @=20pt

 {

 8\ar[rrr]&&&9\ar[r]\ar[rddd]&10\ar[rd]&&&&\\

 &&&4\ar[ru]&&11\ar[r]&12\ar[rd]\ar[dd]&&\\

 1\ar[r]&2\ar[r]&3\ar[ruu]\ar[ru]\ar[r]\ar[rd]&5\ar[rr]\ar[rru]&&

 6\ar[ru]&&14\ar[r]&16\\

 &&&7\ar[r]&13\ar[rrru]\ar[rr]&&15\ar[rru]\ar[rr]&&17\\

 }

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

 \chapter{Network optimization API routines}

 \section{Minimum cost flow problem}

 \subsection{Background}

 The {\it minimum cost flow problem} (MCFP) is stated as follows. Let

 there be given a directed graph (flow network) $G=(V,A)$, where $V$ is

 a set of vertices (nodes), and $A\subseteq V\times V$ is a set of arcs.

 Let for each node $i\in V$ there be given a quantity $b_i$ having the

 following meaning:

 if $b_i>0$, then $|b_i|$ is a {\it supply} at node $i$, which shows

 how many flow units are {\it generated} at node $i$ (or, equivalently,

 entering the network through node $i$ from the outside);

 if $b_i<0$, then $|b_i|$ is a {\it demand} at node $i$, which shows how

 many flow units are {\it lost} at node $i$ (or, equivalently, leaving

 the network through node $i$ to the outside);

 if $b_i=0$, then $i$ is a {\it transshipment} node, at which the flow

 is conserved, i.e. neither generated nor lost.

 Let also for each arc $a=(i,j)\in A$ there be given the following three

 quantities:

 $l_{ij}$, a (non-negative) lower bound to the flow through arc $(i,j)$;

 $u_{ij}$, an upper bound to the flow through arc $(i,j)$, which is the

 {\it arc capacity};

 $c_{ij}$, a per-unit cost of the flow through arc $(i,j)$.

 The problem is to find flows $x_{ij}$ through every arc of the network,

 which satisfy the specified bounds and the conservation constraints at

 all nodes, and minimize the total flow cost. Here the conservation

 constraint at a node means that the total flow entering this node

 through its incoming arcs plus the supply at this node must be equal to

 the total flow leaving this node through its outgoing arcs plus the

 demand at this node.