Блог о математике, программировании, алгоритмах. И немного о работе операционной системы Linux.

четверг, 27 октября 2011 г.

graphviz, dot2tex, tikz: вставка графов прямо в тело LaTeX документа (TeXLive, Ubuntu 10.04).

Изветсно, что LaTeX является de-facto стандартом оформления научной (особенно математической, физической и химической) документации. В случае с математикой (особенно дискретной), возникает острая потребность вставки изображений графов в текст документа. Обычно, для визуализации графов используется набор утилит graphviz, который использует для описания графа свой, простой в изучении, язык DOT, но для того, чтобы вставить в LaTeX документ граф, нужно сначала создать файл с описанием графа, потом скомпилировать его, а потом только вставить картинку в документ. Для автоматизации этого процесса создан пакет dot2texi, который использует утилиту dot2tex.

Положим, что у нас есть LaTeX документ, со стандартной преамбулой:
% Задает класс документа, размер шрифта, и двустороннюю разметку
\documentclass[12pt,a4paper,twoside]{book}
% Указывает на то, что будет использована кодировка UTF-8
\usepackage[utf8x]{inputenc}
% Включает пакет babel с поддержкой русского и английского языков
\usepackage[english,russian]{babel}
% Добавляет пакет asmmath (Ameriacn Mathematical Society)
\usepackage{amsmath}
% Дает возможность включать в документ графику
\usepackage[dvips]{graphicx}

\begin{document}
 
\end{document}
Прямо перед \begin{document} мы вставляем следующие строки:
\usepackage{dot2texi}[dot,mathmode]
\usepackage{tikz}
\usetikzlibrary{shapes,arrows}
После чего в документе, то есть между \begin{document} и \end{document} можем вставлять следующее:
\begin{dot2tex}
    digraph G {
        x_1 -> x_2;
        x_1 -> x_3;
    }
\end{dot2tex}
То что стоит между \begin{document} и \end{document} является записью структуры графа на языке DOT. Теперь давайте разберемся. dot2texi — пакет, который переводит запись на языке DOT в TeX представление, а tikz — пакет все это отрисовывающий. Я пользовался пакетом texlive на Ubuntu 10.04. При установке всего этого я столкнулся со следующими проблемами:
  1. Пакет dot2texi не установлен (LaTeX предлагал мне указать где лежит файл стиля *.sty). Для устранения этой ошибки нужно поставить пакет texlive-pictures
    sudo apt-get install texlive-pictures
  2. Также нужно поставить пакет texlive-pstricks.
  3. При попытке компиляции файла выдавалась ошибка: Package dot2texi Warning: Conversion of latex-dot2tex-fig1.dot failed... Я точно не знаю почему возникает эта ошибка (почему-то при запуске из TeX-скриптов не получается найти утилиту dot2tex), но она решается добавлением аттрибута --shell-escape к команде latex, то есть результирующая строка будет выглядеть так:
    latex --shell-escape your_filename.tex
    
  4. Я не помню зачем, но мне понадобилось установить пакет texlive-latex-extras. Но если вы постоянно пользуетесь LaTeX для верстки документов, то у вас он, скорее всего уже стоит.
  5. Были обнаружены проблемы при работе с утилитой dvipdfm. Вместо нее нужно использовать dvipdf.
Для правильной работы пакета dot2texi нужно, чтобы была установлена утилиты dot2tex и graphviz. Они присутствуют в стандартном репозитории. dot2tex-у можно задать параметры, например, каким визуализатором графов из набора graphviz пользоваться. В нашем случае это dot. Подробнее о работе пакета dot2texi можно почитать в официальном руководстве.

суббота, 22 октября 2011 г.

Tips & Tricks #5. Создание анимации. Соединение кадров в видеопоток.

Для того, чтобы соединить отдельные кадры (например кадры вашего собственного мультика :) в видеопоток (с заданым FPS) можно использовать грандиозную по своей мощности утилиту mencoder. Предполагается, что все кадры уже лежат в отдельной папке и названы «по порядку» Зайдите в папку из командной строки и скажите:
mencoder "mf://*.jpg" -mf fps=30 -o output.avi -ovc lavc -lavcopts vcodec=mpeg4
Строкой "mf://*.jpg" вы задаете маску файлов, которые будут соединяться в видео, -mf fps=30, задает количество кадров в секунду, -o output.avi говорит утилите, что результат нужно положить в файл output.avi. Остальные параметры расшифровываются следующим образом: -ovc lavc, устанавливает, что для кодирования будет использоваться кодек libavcodec, а -lavcopts vcodec=mpeg4 говорит, что видео будет кодироваться в MPEG-4. Под Ubuntu Linux утилита устанавливается стандартно:
sudo apt-get install mencoder
Под Windows можно скачать MPlayer, в составе которого она идет.

Утечки памяти, malloc и valgrind.

Утечки памяти — это ситуации, при которых выделенная в процессе выполнения программы память не освобождается, а указатель на эту память затирается. Вообще говоря, существует два базовых способа отладки как таковой. Отладка с исползованием сторонних средств (таких, например, как GDB) и отладка с использованием отладочных выводов (MessageBox-ами или выводом в консоль).

Способ первый.
Для локализации утечек памяти под Linux-ом (для программ скомпилированных GCC) есть прекрасное средство valgrind. Для того, чтобы проанализировать приложение нужно сделать следующее:
valgrind --tool=memcheck --leak-check=full --log-file=<log file name> <program name>
Здесь <log file name> имя файла в который будет записан вывод анализатора, а <program name> — название вашего приложения (и путь к нему). Стоит отметить, что для того, чтобы valgrind смог произвести анализ, нужно, чтобы ваше приложение было собрано с отладочной информацией для отладчика GDB (ключ -g компилятора). Так же стоит заметить, что valgrind запускает приложение в собственной виртуальной среде, что позволяет отследить все ошибки сегментации (приложение не вылетит, и закончит свое выполнение). Вывод valgrind-а имеет примерно следующий вид:
==5454== Memcheck, a memory error detector
==5454== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
==5454== Using Valgrind-3.6.0.SVN-Debian and LibVEX; rerun with -h for copyright info
==5454== Command: ./calc
==5454== Parent PID: 3856
==5454== 
==5454== 
==5454== HEAP SUMMARY:
==5454==     in use at exit: 252 bytes in 24 blocks
==5454==   total heap usage: 60,776 allocs, 60,752 frees, 269,156 bytes allocated
==5454== 
==5454== 126 (16 direct, 110 indirect) bytes in 1 blocks are definitely lost in loss record 7 of 8
==5454==    at 0x402425F: calloc (vg_replace_malloc.c:467)
==5454==    by 0x80498CA: allocateMatrix (calc.c:476)
==5454==    by 0x804981E: loadMatrix (calc.c:454)
==5454==    by 0x8049F15: main (calc.c:669)
==5454== 
==5454== 126 (16 direct, 110 indirect) bytes in 1 blocks are definitely lost in loss record 8 of 8
==5454==    at 0x402425F: calloc (vg_replace_malloc.c:467)
==5454==    by 0x80498CA: allocateMatrix (calc.c:476)
==5454==    by 0x804981E: loadMatrix (calc.c:454)
==5454==    by 0x8049F25: main (calc.c:670)
==5454== 
==5454== LEAK SUMMARY:
==5454==    definitely lost: 32 bytes in 2 blocks
==5454==    indirectly lost: 220 bytes in 22 blocks
==5454==      possibly lost: 0 bytes in 0 blocks
==5454==    still reachable: 0 bytes in 0 blocks
==5454==         suppressed: 0 bytes in 0 blocks
==5454== 
==5454== For counts of detected and suppressed errors, rerun with: -v
==5454== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 20 from 7) 
Здесь число стоящее между символами «==» — это PID потока, а блоки которые начинаются с числа 126 — сообщения о найденых утечках памяти. 126 здесь — это число утеряных байт, а ниже приведен стек вызовов, который привел к утечке. В каждой строчке стека вызовов есть информация о том, в каком файле и в какой строке был сделан данный вызов. Ниже приводится ссумарная информация об ошибках и утечках. Подробнее про valgrind можно прочитать на официальном сайте (англ.).

Способ второй.
Однако, если программа мала или нет возможности использовать valgrind, можно воспользоваться более «низкоуровневым» способом отладки. Если ваша программа написана на C, с использованием стандартного malloc, тогда вы в любой момент времени, можете спросить сколько памяти уже выделено malloc-ом. Для этого используется структура mallinfo. Работу с ней можно организовать, например, таким образом:
#include <malloc.h>

int
main()
{
    struct mallinfo info;
    info = mallinfo();
    printf("%d\n", info.uordblks);
    /**
     * Здесь происходит что-то, через что течет память.
     */
    printf("%d\n", info.uordblks);
    return 0;
}
Функция mallinfo возвращает информацию о работе менеджера памяти в структуру mallinfo. Эта структура содержит поле uordblks, которое хранит количество байт, которое было выделено malloc.

вторник, 18 октября 2011 г.

CSS, HTML, vertical-align и все точки над i.

HTML-верстка окутана туманом путаницы и тайны. Мне очень долго не давал покоя вопрос: «Почему, в некоторых случаях выравнивание по вертикали работает, а в некоторых нет». Начнем с того, что выравнивание по вертикали можно задать двумя способами. Указав атрибут элемента valign элемента, которому вы задаете выравнивание, или указать свойство CSS vertical-align. Оба этих параметра могут принимать значения 'baseline|bottom|middle|sub|super|text-bottom|text-top|top|inherit'. Не буду вдаваться в подробности относительно каждого из них, тут все итак понятно. Важнее то, что выравнивание по высоте работает не всегда. В качестве разъяснения привожу перевод одной коротенькой статейки. HTML элементы бывают блочными (block) и строчными (inline). Блочные элементы характеризуются тем, что:
  • Они всегда переносятся на новую строку.
  • У них можно задать высоту, высоту линии, а также верхнюю и нижнюю границы.
  • Ширина равна 100% ширины родительского элемента, если не задана отдельно.
Примерами блочных элементов могут служить <div>, <p>, <h1>, <form>, <ul> и <li>. Строчные элементы, с другой стороны, являются противоположностью блочным:
  • Они начинаются на той же строке. 
  • У них невозможно задать высоту, высоту строки, а также верхнюю и нижнюю границы.
  • Ширина равна ширине текста/картинки и не может быть изменена.
Примерами строчных элементов могут являться <span>, <a>, <label>, <input>, <img>, <strong> и <em>. Для того, чтобы сменить тип элемента, вы можете использовать CSS-свойство display: inline или display: block. Но какой смысл делать блочный элемент строчным или наоборот? Ну, поначалу сложно представить, зачем использовать этот прием, но на самом деле это очень мощная техника, которая может быть использована когда вы хотите:
  • Заставить строчный элемент начинаться с новой строки.
  • Заставить блочный элемент оставаться на той же строке.
  • Менять ширину строчных элементов (иногда полезно для навигационных ссылок).
  • Менять высоту строчных элементов.
  • Установить фоновый цвет на всю ширину текста для блочных элементов, не без необходимости задавать ширину.

Tips & Tricks #4. Функция переводящая координаты Excel ячейки во внутренний адрес

Недавно, волею судеб, мне пришлось писать Excel-приложение. В процессе работы с таблицей, очень часто возникает необходимость обращаться к ячейкам или диапазонам по их адресу. Иногда удобнее обращаться к ячейкам по координатам. Почему-то мне не удалось использовать формат адресов "R1C1". При попытке сказать:
    Worksheets(1).Range("R1C1").Value = "Hello, World"
вылезала ошибка номер 1004 "Application-defined or object-defined error". В голову пришла идея написать функцию для преобразования координат ячейки или диапазона в его классическое Excel пердставление (знаменитые "A1:B2"). В общем-то вот она. Может быть кому-нибудь пригодится.
' Возвращает Excel адрес ячейки по её координатам, если правый нижний угол не задан,
' возвращает адрес ячейки, если задан - адрес диапазона
Function Addr(nLeft As Long, nTop As Long, _
                     Optional nRight As Long = -1, _
                     Optional nBottom As Long = -1) As String
    Dim sCol As String
    Dim nK1 As Integer, nK2 As Integer
    If (nLeft > 256 Or nRight > 256) Then
        Addr = ""
        Exit Function
    End If
    If (nTop > 65536 Or nBottom > 65536) Then
        Addr = ""
        Exit Function
    End If
    If (nLeft <= 26) Then
        sCol = Chr(Asc("A") + ((nLeft - 1) Mod 26))
    Else
        sCol = Chr(Asc("A") + ((nLeft - 27) \ 26)) + Chr(Asc("A") + ((nLeft - 1) Mod 26))
    End If
    Addr = sCol + CStr(nTop)
    If (nRight > 0 And nBottom > 0) Then
        If (nRight <= 26) Then
            sCol = Chr(Asc("A") + ((nRight - 1) Mod 26))
        Else
            sCol = Chr(Asc("A") + ((nRight - 27) \ 26)) + Chr(Asc("A") + ((nRight - 1) Mod 26))
        End If
        Addr = Addr + ":" + sCol + CStr(nBottom)
    End If
End Function