Skip to content

Instantly share code, notes, and snippets.

@Arseny-N

Arseny-N/ALL.c

Last active August 29, 2015 14:21
Show Gist options
  • Save Arseny-N/db4d698832d69ba45f01 to your computer and use it in GitHub Desktop.
Save Arseny-N/db4d698832d69ba45f01 to your computer and use it in GitHub Desktop.
Download ZIP
Graphs
Raw
ALL.c
8<------------------------ graphs.c ------------------------
#include <stdlib.h>
#include <string.h>
#include "graphs.h"
struct graph *alloc_graph(size_t num_vertices, storage_t vertices, storage_t edges)
{
struct graph *g = malloc(sizeof(struct graph));
if(!g) {
err_printf("malloc(1)");
goto err_end;
}
g->num_vertices = num_vertices;
g->matrix = malloc(sizeof(storage_t **)*num_vertices);
if(!g->matrix) {
err_printf("malloc(2)");
goto free_graph;
}
size_t i, j;
for(i=0; i < num_vertices; ++i) {
g->matrix[i] = malloc(sizeof(storage_t)*num_vertices);
if(!g->matrix[i]) {
err_printf("malloc(3)");
goto free_matrix_els;
}
for(j=0; j < num_vertices; ++j)
if( i == j ) {
g->matrix[i][j] = vertices;
} else {
g->matrix[i][j] = edges;
}
// dbg_printf("%d number %d", i, (num_vertices-i));
}
return g;
free_matrix_els:
for(i=0; i < num_vertices && g->matrix[i] ; ++i)
free(g->matrix[i]);
// free_matrix:
free(g->matrix);
free_graph:
free(g);
err_end:
return NULL;
}
void free_graph(struct graph *g)
{
int i;
for(i=0; i < g->num_vertices && g->matrix[i] ; ++i)
free(g->matrix[i]);
free(g->matrix);
free(g);
}
8<------------------------ graphs.h ------------------------
#ifndef __GRAPHS_H__
#define __GRAPHS_H__
#include "types.h"
#include "utils.h"
/*
# Графы #
## Метод хранения графов ##
Граф хранится в матричной форме[1]. Указатель на матрицу хранится в структуре
`struct graph` полем `.matrix`. Также в поле `.num_vertices` хранится кол-во
вершин графа. Тип элементов в вдуxмерном массиве `.matrix` - `storage_t`.
*/
#include <limits.h>
#include <stddef.h>
typedef u64 storage_t;
struct graph
{
storage_t **matrix;
size_t num_vertices;
};
/*
## Особенности хранения графов ##
### Побитовое представление ###
Каждая ячейка матрицы в которой хранится граф (graph.matrix) разделена на два поля - в первом
хранится "стоимость" а во втором поле хранится вспомогаельная информация. Доступ к эти
полям абстрагирован при помощи макросов G_DATA_MASK/G_UTIL_MASK и G_DATA_SHIFT/G_UTIL_SHIFT.
Пример доступа к вспомогательному полю некой переменной типа storage_t:
storage_t x = fn();
printf("x's util filed is %x", (x&G_UTIL_MASK)>>G_UTIL_SHIFT);
*/
#define G_DATA_MASK ((storage_t) 0xffffffff)
#define G_UTIL_MASK ((storage_t) 0xffffffff00000000)
#define G_UTIL_SHIFT 32
#define G_DATA_SHIFT 0
/*
## Вспомогательные типы для работы со структурой `struct graph` ##
`cost_t` - тип в котором хранится стоимость ребра/вершины графа при
манипуляции таковой.
`INFINITY` - некое особое значение для переменной типа `cost_t`. Аналог NULL.
`util_t` - тип в котором хранится вспомогательная информация ребра/вершины графа при
манипуляции таковой.
`vertex_t` - тип в котором хранится значение вершины графа при манипуляции такового.
`UNIT` - некое особое значение для переменной типа `vertex_t`. Аналог NULL.
*/
typedef u64 cost_t;
typedef u64 util_t;
#define INFINITY 0xffffffff
typedef u32 vertex_t;
#define UNIT 0xffffffff
#define VERTEX_FMT "%d"
#define EDGE_FMT "%d"
#define COST_FMT "%ld"
/*
## Вспомогательные функции для работы со структурой `struct graph` ##
### Функции возвращающие или ассигнирующие "стоимость" вершины или ребра графа. ###
*/
/*
get_edge_cost(g,s,t):
Аргументы:
g - граф, представляемый структурой `struct graph`.
s - исходная вершина
t - конечная вершина
Описание:
Возвращает "стоимость" ребра между вершинами s и t.
*/
static inline cost_t get_edge_cost(const struct graph *g, vertex_t s, vertex_t t)
{
return (((g)->matrix[s][t]) & G_DATA_MASK) >> G_DATA_SHIFT ;
}
/*
set_edge_cost(g,s,t, cost):
Аргументы:
g - граф, представляемый структурой `struct graph`.
s - исходная вершина
t - конечная вершина
cost - стоимость
Описание:
Ассигнирует "стоимость" `cost` ребру между вершинами `s` и `t`.
*/
static inline void set_edge_cost(struct graph *g, vertex_t s, vertex_t t, cost_t cost)
{
((g)->matrix[s][t]) =
((cost << G_DATA_SHIFT) & G_DATA_MASK) |
(((g)->matrix[s][t]) & G_UTIL_MASK);
}
/*
get_vertex_cost(g,a):
Аргументы:
g - граф, представляемый структурой `struct graph`.
а - некая вершина.
Описание:
Возвращает "стоимость" вершины а.
*/
static inline cost_t get_vertex_cost(const struct graph *g, vertex_t a)
{
return (((g)->matrix[a][a]) & G_DATA_MASK) >> G_DATA_SHIFT ;
}
/*
set_vertex_cost(g,s, cost):
Аргументы:
g - граф, представляемый структурой `struct graph`.
s - некая вершина
cost - стоимость
Описание:
Ассигнирует "стоимость" `cost` вершине `s`.
*/
static inline void set_vertex_cost(struct graph *g, vertex_t a, cost_t cost)
{
g->matrix[a][a] =
((cost << G_DATA_SHIFT) & G_DATA_MASK) |
( g->matrix[a][a] & G_UTIL_MASK );
}
/*
### Функции возвращающие или ассигнирующие спец. поле соответствующие вершине или ребру графа. ###
*/
/*
get_edge_util(g,s,t):
Аргументы:
g - граф, представляемый структурой `struct graph`.
s - исходная вершина
t - конечная вершина
Описание:
Возвращает "служебное поле" ребра между вершинами s и t.
*/
static inline util_t get_edge_util(const struct graph *g, vertex_t s, vertex_t t)
{
return (((g)->matrix[s][t]) & G_UTIL_MASK) >> G_UTIL_SHIFT ;
}
/*
set_edge_cost(g,s,t, cost):
Аргументы:
g - граф, представляемый структурой `struct graph`.
s - исходная вершина
t - конечная вершина
util - значение служебного поля
Описание:
Ассигнирует "значение служебного поля" `util` ребру между вершинами `s` и `t`.
*/
static inline void set_edge_util(struct graph *g, vertex_t s, vertex_t t, util_t cost)
{
((g)->matrix[s][t]) =
((cost << G_UTIL_SHIFT) & G_UTIL_MASK) |
(((g)->matrix[s][t]) & G_DATA_MASK);
}
/*
get_vertex_util(g,a):
Аргументы:
g - граф, представляемый структурой `struct graph`.
а - некая вершина.
Описание:
Возвращает "служебное поле" вершины а.
*/
static inline util_t get_vertex_util(const struct graph *g, vertex_t a)
{
return (((g)->matrix[a][a]) & G_UTIL_MASK) >> G_UTIL_SHIFT ;
}
/*
set_vertex_util(g,s, util):
Аргументы:
g - граф, представляемый структурой `struct graph`.
s - некая вершина
util - значение служебного поля
Описание:
Ассигнирует "значение служебного поля" `util` вершине `s`.
*/
static inline void set_vertex_util(struct graph *g, vertex_t a, util_t cost)
{
g->matrix[a][a] =
((cost << G_UTIL_SHIFT) & G_UTIL_MASK) |
( g->matrix[a][a] & G_DATA_MASK );
}
/*
## Функции аллокирующие или деаллокирующие граф. ##
*/
/*
alloc_graph(num_vertices, iv, ie):
Аргументы:
num_vertices - Кол-во вершин создаваемого графа.
iv - начальное значение вершин
ie - начальное значение ребер
Описание:
Возвращает узазатель на новый граф.
*/
struct graph *alloc_graph(size_t num_vertices, storage_t vertices, storage_t edges);
/*
free_graph(g):
Аргументы:
g - указатель на граф созданный при помощи `alloc_graph()`.
Описание:
Деаллокирует граф g.
*/
void free_graph(struct graph *g);
/*
## Макросы для более удобной работы с графами. ##
### "Макросы со значением цикла" ###
"Макросы со значением цикла" помогают упростить код устранив некие рутинные операции.
Пример:
g - указатель типа struct graph
v - переменная типа vertex_t
for_each_vertex(g, v)
printf("%ld", (long int) v);
аналогично, но более понятно чем
for( v = 0; v < (g)->num_vertices; ++v)
printf("%ld", (long int) v);
*/
/*
for_each_vertex(g, v):
Аргументы:
g - указатель типа struct graph
v - переменная типа vertex_t
Описание:
цикл, который "проходит" через каждую вершину. При каждой итерации цикла
переменная v равна новой верине, т.е. вершине которой она не была ранее.
*/
#define _for_each_vertex(g, i, begin) for( i = begin; i < (g)->num_vertices; ++i)
#define for_each_vertex(g, i) _for_each_vertex(g, i, 0)
/*
for_each_edge(g, v, u) :
Аргументы:
g - указатель типа struct graph
v - переменная типа vertex_t
Описание:
цикл, который "проходит" через каждое ребро. При каждой итерации цикла
переменные v и u равны новому ребру, т.е. ребру которому они не были ранее.
*/
#define for_each_edge(g, i, j) for( i = 0; i < (g)->num_vertices; ++i) \
for(j= i == 0 ? 1 : 0; j<(g)->num_vertices; ++j, j == i ? ++j : 0)
/*
num_vertices(g) :
Аргументы:
g - указатель типа struct graph
Описание:
возвращает кол-вл вершин в графе g
*/
#define num_vertices(g) ((g)->num_vertices)
static inline vertex_t next_neighbor(struct graph *g, vertex_t v, vertex_t prev)
{
int i;
_for_each_vertex(g, i, prev == UNIT ? 0 : (prev+1)) {
if(get_edge_cost(g, i, v) != INFINITY )
return i;
}
return UNIT;
}
/*
for_each_neighbor(g, v, u) :
Аргументы:
g - граф, представляемый структурой `struct graph`.
v - вершина, чьи соседи нам интересны
u - переменная типа `vertex_t`
Описание:
цикл, который "проходит" через все соседние вершины v. При каждой итерации цикла
переменнaz u равны новой соседней вершине v.
*/
#define for_each_neighbor(g, v, a) for(a = next_neighbor(g, v, UNIT); a != UNIT; a = next_neighbor(g, v, a))
char *get_street_name(struct graph *g, vertex_t s, vertex_t t );
#endif /* __GRAPHS_H__ */
8<------------------------ main.c ------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <ncurses.h>
#include "utils.h"
#include "types.h"
#include "graphs.h"
#include "print_graphs.h"
/*
# Имена улиц #
## Реализация ##
Для присвоения имен улицам используются служебные поля ребер графов.
Ниже определен вспомогательный тип `street_id_t` в котором хранися идентификатор
улици при работе с ним. Идентификатор является индексом в массиве имен улиц `street_names`
*/
typedef s32 street_id_t;
/*
UTIL_BITS_GET_FILED(name, num):
Аргументы:
name - имя некого битового "пространства"
num - значение битового "пространства"
Описание:
Макрос UTIL_BITS_GET_FILED облегчает работу с бтовыми пространствами,
первым аргументом ему передаётся имя соответстующего битового пространтсва,
вторым, переменная в которой хранися искомое пространство. Макорс возвращает
значение нужного пространства.
*/
#define UTIL_BITS_GET_FILED(name, num) ( ( (num) >> (name ## _UTIL_SHIFT)) & (name ## _UTIL_MASK) )
/*
UTIL_BITS_ENCODE_FILED(name, num):
Аргументы:
name - имя некого битового "пространства"
num - значение битового "пространства"
Описание:
Макрос UTIL_BITS_ENCODE_FILED облегчает работу с бтовыми пространствами,
первым аргументом ему передаётся имя соответстующего битового пространтсва,
вторым значение соответсвующего пр. Макорс возвращает "закодированное значение"
переменной.
*/
#define UTIL_BITS_ENCODE_FILED(name, num) ( ( (num) & (name ## _UTIL_MASK) ) << (name ## _UTIL_SHIFT) )
/*
Определение битового пространства `STREET_ID`
*/
#define STREET_ID_UTIL_MASK 0xff
#define STREET_ID_UTIL_SHIFT 0
#define STREET_ID_UTIL_WIDTH 8
/*
get_street_id(g, s, t)
Аргументы:
g - граф, представляемый структурой `struct graph`.
s - исходная вершина
t - конечная вершина
Описание:
Функция возвращает идентификатор улици соотв. ребру s -- t.
*/
static inline street_id_t get_street_id(struct graph *g, vertex_t s, vertex_t t)
{
return UTIL_BITS_GET_FILED(STREET_ID, get_edge_util(g, t, s));
}
/*
set_street_id(g, s,t,id )
Аргументы:
g - граф, представляемый структурой `struct graph`.
s - исходная вершина
t - конечная вершина
Описание:
Функция присваивает идентификатор `id` улицие соотв. ребру s -- t.
*/
static inline void set_street_id(struct graph *g, vertex_t s, vertex_t t, street_id_t id )
{
set_edge_util(g, s, t, UTIL_BITS_ENCODE_FILED(STREET_ID, id));
set_edge_util(g, t, s, UTIL_BITS_ENCODE_FILED(STREET_ID, id));
}
/*
get_street_name(g, s, t ):
Аргументы:
g - граф, представляемый структурой `struct graph`.
s - исходная вершина
t - конечная вершина
Описание:
Функция возвращает указатель на имя соотв. улице между s и t.
*/
static char *street_names[];
char *get_street_name(struct graph *g, vertex_t s, vertex_t t )
{
return street_names[get_street_id(g, s, t)];
}
/*
create_road(g, s, t, len, id )
Аргументы:
g - граф, представляемый структурой `struct graph`.
s - исходная вершина
t - конечная вершина
Описание:
Функция создает дорогу между вершинами s и t с длинной len и идентификатором
улици соотв. id.
*/
static inline void create_road(struct graph *g, vertex_t s, vertex_t t, cost_t len, street_id_t id )
{
set_edge_cost(g, s, t, len);
set_edge_cost(g, t, s, len);
set_vertex_cost(g, t, 0);
set_vertex_cost(g, s, 0);
set_street_id(g, t, s, id);
}
/*
=============================================================================
# Карта #
## Реализация ##
Карта хранится в файле "streets.h.inc" и выглядит сл. образом:
declare_street(none, "без названия")
__ds_sep declare_street(none1, "без названия 1")
__ds_sep declare_street(none2, "без названия 2")
так, объявляются улици - сначала их английское название, потом русское (строчной переменной).
Далее к улицам можно обращатся при помощи их ангилйского инени.
declare_crossroad2(belova, stepana_razina)
__dc_sep declare_crossroad2(belova, pugacheva)
__dc_sep declare_crossroad2(belova, ogorodnaya)
__dc_sep declare_crossroad2(belova, sergievskaya)
так, объявляются перекрестки - двух ранее объявленных улиц.
declare_street_pice(belova, stepana_razina, belova, pugacheva, 100)
__dp_sep declare_street_pice(belova, pugacheva, belova, ogorodnaya, 60)
__dp_sep declare_street_pice(belova, ogorodnaya, belova, sergievskaya, 70)
__dp_sep declare_street_pice(belova, sergievskaya, belova, bobilskaya, 530)
так, объявляются участки дорог - первые два аргумента соответствуют первому перекрестку, вторые
соответственно второму, последним аргументом идет расстояние между двумя перекрестками. Название
дороги соответствует названию первой дороги переданной функцие (первого аргумента). Каждый
перекресток должен был быть объявлен ранее.
Ниже мы определяем макросы declare_street(), declare_crossroad2() и declare_street_pice()
и включаем фаил "streets.h.inc".
*/
// Трюк, чтобы компилятор определил макрос __coma__ как макрос содержащий запятую
// Иначе `#define __coma__ , ` не компилируется.
#define __empty__
#define __coma__ __empty__,
#define __ds_sep __coma__
#define __dc_sep
#define __dp_sep
#define declare_crossroad2(a, b)
#define declare_street_pice(a, b,c,d,e)
#define declare_street(name, rus) rus
static char *street_names[] = {
/*
declare_crossroad2(a, b) и declare_street_pice(a, b,c,d,e) определены как макросы
не возвращающие ничего и передоваемые им аргументы отбрасываются.
Тогда как declare_street(name, rus) "оставляет" только свой последний аргумент.
Далее мы включаем "streets.h.inc", заметим, что включение происходит в блоке инициализации
в массива, т.е. оставленные строчные переменные `rus` станут его элементами.
*/
#include "streets.h.inc"
};
#undef declare_street
#define declare_street(name, rus) #name, rus
/*
Используя технику описанную ранее объявляем и этот массив
*/
static char *street_names_eng_rus[] = {
#include "streets.h.inc"
};
#undef declare_street
#define declare_street(name, rus) st_## name
/*
Используя технику описанную ранее объявляем элементы энумерации
соответствующие названию улицы на английском языке и имеющие уникалтное значение
*/
enum streets_e
{
#include "streets.h.inc"
};
#undef __ds_sep
#undef __dc_sep
#undef __dp_sep
#undef declare_street_pice
#undef declare_crossroad2
#undef declare_street
/* -------------------- Build streets crossings -------------------- */
#define __ds_sep
#define __dc_sep __coma__
#define __dp_sep
#define declare_street_pice(a, b,c,d,e)
#define declare_crossroad2(name1, name2) cr_ ## name1## _ ## name2
#define declare_street(a,b)
enum crossroads_e
{
#include "streets.h.inc"
};
#undef declare_crossroad2
#define declare_crossroad2(name1, name2) cr_ ## name2 ## _ ## name1
enum crossroads_e_inv
{
#include "streets.h.inc"
};
#undef declare_crossroad2
#define declare_crossroad2(name1, name2) st_##name1, st_##name2, cr_ ## name1 ## _ ## name2
vertex_t street_ids_to_crossings[] = {
#include "streets.h.inc"
};
#undef __dc_sep
#define __dc_sep +
#undef declare_crossroad2
#define declare_crossroad2(name1, name2) 1
static const size_t num_cross_roads =
#include "streets.h.inc"
;
#undef __ds_sep
#undef __dc_sep
#undef __dp_sep
#undef declare_street_pice
#undef declare_crossroad2
#undef declare_street
/* -------------------- Build map -------------------- */
#define __ds_sep
#define __dc_sep
#define __dp_sep ;
#define declare_street_pice(origin1, name1, origin2, name2, len) \
create_road(g, cr_ ## origin1 ## _ ## name1, cr_ ## origin2 ## _ ## name2, len, st_ ## origin1 )
#define declare_crossroad2(a, b)
#define declare_street(a, b)
static inline void __build_map(struct graph *g)
{
#include "streets.h.inc"
;
}
#undef __ds_sep
#undef __dc_sep
#undef __dp_sep
#undef declare_street_pice
#undef declare_crossroad2
#undef declare_street
#undef __coma__
#undef __empty__
#include "path_search.h"
typedef int (*find_min_path_cb_t)(struct graph *g, vertex_t source, vertex_t target, visitor_cb_t, void*);
u64 rdtsc(void)
{
u32 lo,hi;
__asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi));
return ((u64)hi << 32) | lo;
}
/*
print_stats(g,aname,niter, cb, s, t )
Аргументы:
g - граф, представляемый структурой `struct graph`.
aname - имя алгоритма, котоорое будет выведено на этран
niter - кол-во итераций
cb - указатель на функцию типа <название алгоритма>_find_min_path()
s - исходная вершина
t - конечная вершина
Описание:
Функция выводит кол-во циклов процессора затроченных на прокладывание niter
маршрутов из вершины s в вершину t, алгоритмом cb.
*/
void print_stats(struct graph *g, char *aname, size_t niter, find_min_path_cb_t cb, vertex_t s,vertex_t t )
{
u64 t0, t1, p = 0;
size_t i;
t0 = rdtsc();
for(i = 0; i < niter; ++i) {
ASSERT(cb(g, s, t, void_visitor, NULL),
exit(EXIT_FAILURE), " %s () failed, exitting", aname);
}
t1 = rdtsc();
p = t1 - t0;
printf("executed %30s algorithm %ld times in %10ld cpu cycles, averadge loop time %10ld\n", aname, niter, p, p/niter);
}
#define PRINT_STATS(g, niter, cb, s, t) print_stats(g, #cb, niter, cb, s, t)
/*
print_all_stats(g, nit)
Аргументы:
g - граф, представляемый структурой `struct graph`.
nit - кол-во итераций
Описание:
Функция выводит "статисики" прокладывания nit маршрутов из 0 в 17 вершину
всех реализованных алгоритмов.
*/
void print_all_stats(struct graph *g, size_t nit)
{
PRINT_STATS(g, nit, floyd_warshall_find_min_path, 0,17 );
PRINT_STATS(g, nit, bellman_ford_find_min_path, 0,17 );
PRINT_STATS(g, nit, dijkstra_find_min_path, 0,17 );
}
/*
simply_run(g)
Аргументы:
g - некий граф
Описание:
Функция прокладывает наименший путь из 0 в 17 вершину, каждым алгоритмом и
выводит получившиеся пути.
*/
void simply_run(struct graph *g)
{
struct street_print_visitor_arg arg;
arg.length = 0; arg.g = g;arg.previous = UNIT;
ASSERT(dijkstra_find_min_path(g, 0, 17, street_print_visitor, (void*) &arg),
exit(EXIT_FAILURE), " *_fin_min_path() failed, exitting" );
printf("\n");
arg.length = 0; arg.g = g;arg.previous = UNIT;
ASSERT(bellman_ford_find_min_path(g, 0, 17, street_print_visitor, (void*) &arg),
exit(EXIT_FAILURE), " *_fin_min_path() failed, exitting" );
printf("\n");
arg.length = 0; arg.g = g;arg.previous = UNIT;
ASSERT(floyd_warshall_find_min_path(g, 0, 17, street_print_visitor, (void*) &arg),
exit(EXIT_FAILURE), " *_fin_min_path() failed, exitting" );
printf("\n");
}
/*
print_min_path(g, s, t)
Аргументы:
g - граф, представляемый структурой `struct graph`.
s - исходная вершина
t - конечная вершина
Описание:
Функция выводит наименций путь из вершины s в вершину t.
*/
void print_min_path(struct graph *g, vertex_t s, vertex_t t)
{
struct street_print_visitor_arg arg;
arg.length = 0; arg.g = g;arg.previous = UNIT;
ASSERT(dijkstra_find_min_path(g, s, t, street_print_visitor, (void*) &arg),
exit(EXIT_FAILURE), " *_fin_min_path() failed, exitting" );
printf("\n");
}
#define PRINT_MIN_PATH(g, r00, r01, r10, r11 ) print_min_path(g, cr_ ## r00 ## _ ## r01, cr_ ## r10 ## _ ## r11 )
/*
# Работа с аргументами командной стрки #
*/
#include <stdbool.h>
/*
_get_argument_value_str(this, next, skip_one)
Аргументы:
this - указатель на текущий аргумени командной строки
next - указатель на следующий аргумени командной строки
skip_one - эта переменная истина когда нужно пропустить следующий
аргумени командной строки
Описание:
Функция помогает разбирать аргументы командной строки.
*/
char *_get_argument_value_str(char *this, char *next, bool *skip_one)
{
switch(*this) {
case '=': return this + 1;
case '\0':
*skip_one = true;
return next;
default:
return this;
}
}
/*
street_id_from_name(name)
Аргументы:
name - имя улици
Описание:
Функция возвращает идентификатор улици имея её имя.
*/
street_id_t street_id_from_name(char *name)
{
size_t i = 0;
for(; i<ARRSIZE(street_names_eng_rus); ++i) {
if(strcmp(street_names_eng_rus[i], name) == 0)
return i/2;
}
return -1;
}
/*
crossroad_from_street_ids(s0,s1)
Аргументы:
s0 - идентификатор улици
s1 - идентификатор улици
Описание:
Функция возвращает идентификатор перекрестка (вершину графа) дорог s0 и s1.
*/
vertex_t crossroad_from_street_ids(street_id_t s0, street_id_t s1)
{
size_t i = 0;
for(; i<ARRSIZE(street_ids_to_crossings); i += 3) {
if( (street_ids_to_crossings[i] == s0 && street_ids_to_crossings[i+1] == s1) ||
(street_ids_to_crossings[i] == s1 && street_ids_to_crossings[i+1] == s0) )
return street_ids_to_crossings[i+2];
}
return UNIT;
}
/*
path_from_string(str, s, t)
Аргументы:
str - сторковая переменная
s - указатель на начальную вершину
t - указатель на конечную вершину
Описание:
Функция извлекает из строковой переменной вида 's0,s1+s2,s3' начальную и
конечную точку маршрута (от перекрестка s0,s1 до перекрестка s2,s3).
*/
int path_from_string(char *s, vertex_t *vs, vertex_t *vt)
{
char *p = strchr(s, ',');
if(!p) return -1;
else *p = '\0';
street_id_t s0 = street_id_from_name(s);
*p = ',';
if(s0 == -1) return -1;
s = strchr(p+1, '+');
if(!s) return -1;
else *s = '\0';
street_id_t s1 = street_id_from_name(p+1);
*s = '+';
if(s1 == -1) return -1;
p = strchr(s+1, ',');
if(!p) return -1;
else *p = '\0';
street_id_t s2 = street_id_from_name(s+1);
*p = ',';
if(s2 == -1) return -1;
street_id_t s3 = street_id_from_name(p+1);
if(s3 == -1) return -1;
*vs = crossroad_from_street_ids(s0, s1);
*vt = crossroad_from_street_ids(s2, s3);
return 0;
}
int main(int argc, char *argv[])
{
struct graph *g = alloc_graph(num_cross_roads, INFINITY, UNIT);
if(!g){
err_printf("alloc_graph()");
return 1;
}
__build_map(g);
vertex_t v, s;
size_t i = 1;
bool skip_one;
char def_path[] = "belova,stepana_razina+khalturina,bobilskaya";
char *path = def_path;
for( skip_one = false; argv[i] && argv[i][0] == '-' ; ++i ) {
switch(argv[i][1]) {
case 'j' : simply_run(g); exit(EXIT_SUCCESS); break;
case 's' : print_all_stats(g, 10000); exit(EXIT_SUCCESS); break;
case 'm' : fprint_graph(stdout, g); exit(EXIT_SUCCESS); break;
case 'p' : path = _get_argument_value_str(&argv[i][2], argv[i+1], &skip_one); break;
case 'h' :
printf("Usage %s [ -s | -m | -h | -j | -p s0,s1+s2,s3 ]\n"
"\t -s print algorithm stats\n"
"\t -j simply run algorithms\n"
"\t -m print map graph\n"
"\t -p fing shortest path form 's0,s1' to 's2,s3'\n"
"\t -h output this help\n"
, argv[0]);
exit(EXIT_SUCCESS);
default:
err_printf("bad flag '%s' %ld", argv[i], i);
exit(EXIT_FAILURE);
}
if(skip_one) {
skip_one = false;
++i;
}
}
// PRINT_MIN_PATH(g, belova,stepana_razina,khalturina,bobilskaya);
if(path_from_string(path, &v, &s) ) {
err_printf("path_from_string(%s)", path);
exit(EXIT_FAILURE);
}
print_min_path(g, v, s);
free_graph(g);
return 0;
}
8<------------------------ path_search.c ------------------------
#include "path_search.h"
int dijkstra_find_min_path(struct graph *g, vertex_t source, vertex_t target, visitor_cb_t visit, void *data)
{
cost_t *dist = malloc(g->num_vertices*sizeof(cost_t));
vertex_t *prev = malloc(g->num_vertices*sizeof(vertex_t));
vertex_t u,v;
int r = -1;
enum e_Q { PRESENT, ABSENT };
enum e_Q *Q = malloc(g->num_vertices*sizeof(enum e_Q));
size_t Q_size = 0;
if( !dist || !prev || !Q) {
err_printf("malloc() returned NULL");
goto bulk_free;
}
dbg_printf("Initialization");
dist[source] = 0;
prev[source] = UNIT;
for_each_vertex(g, v) {
if( v != source) {
dist[v] = INFINITY;
prev[v] = UNIT;
}
Q[v] = PRESENT;
Q_size ++;
}
dbg_printf("distance[] & prev[] computrtion");
while(Q_size) {
cost_t min_dist;
dbg_printf("u ← vertex in Q with min dist[u]");
min_dist = INFINITY;
for_each_vertex(g, v)
if(Q[v] == PRESENT && dist[v] <= min_dist) {
u = v;
min_dist = dist[v];
}
if(u == target)
break;
Q[u] = ABSENT;
Q_size --;
for_each_neighbor(g, u, v) {
cost_t alt = dist[u] + get_edge_cost(g, u, v);
if(alt < dist[v]) {
dist[v] = alt;
prev[v] = u;
}
}
}
for(v = target; v != UNIT; v = prev[v] )
visit(v, data);
r = 0;
bulk_free:
if(dist)
free(dist);
if(prev)
free(prev);
if(Q)
free(Q);
return r;
}
/*
function BellmanFord(list vertices, list edges, vertex source)
::distance[],predecessor[]
// This implementation takes in a graph, represented as
// lists of vertices and edges, and fills two arrays
// (distance and predecessor) with shortest-path
// (less cost/distance/metric) information
// Step 1: initialize graph
for each vertex v in vertices:
if v is source then distance[v] := 0
else distance[v] := inf
predecessor[v] := null
// Step 2: relax edges repeatedly
for i from 1 to size(vertices)-1:
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
distance[v] := distance[u] + w
predecessor[v] := u
// Step 3: check for negative-weight cycles
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
error "Graph contains a negative-weight cycle"
return distance[], predecessor[]
*/
int bellman_ford_find_min_path(struct graph *g, vertex_t source, vertex_t target, visitor_cb_t visit, void *data)
{
cost_t *dist = malloc(num_vertices(g)*sizeof(cost_t));
vertex_t *prev = malloc(num_vertices(g)*sizeof(vertex_t));
vertex_t v, u;
size_t i;
int r = -1;
if( !dist || !prev ) {
err_printf("malloc() returned NULL");
goto bulk_free;
}
dbg_printf("Step 1: initialize graph");
for_each_vertex(g, v) {
dist[v] = INFINITY;
prev[v] = UNIT;
}
dist[source] = 0;
dbg_printf("Step 2: relax edges repeatedly");
for(i=1; i < num_vertices(g)-1; ++i )
for_each_edge(g, u, v) {
cost_t w = get_edge_cost(g, v, u);
if(w != INFINITY && dist[u] != INFINITY &&
dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
prev[v] = u;
}
}
for_each_edge(g, u, v)
dbg_printf("(%d %d) -- %ld", u, v, get_edge_cost(g, u, v));
dbg_printf(" %d", INFINITY);
for(i=0; i<num_vertices(g); ++i) {
dbg_printf("%d p-> %d d-> %d",i ,prev[i], dist[i]);
}
dbg_printf("Step 3: filling struct vertex_list");
for(v = target; v != UNIT; v = prev[v] )
visit(v, data);
r = 0;
bulk_free:
if(dist)
free(dist);
if(prev)
free(prev);
return r;
}
void free_matrix(void **m, size_t e_count)
{
size_t i;
for(i=0; i<e_count; ++i)
free(m[i]);
free(m);
}
void **alloc_square_matrix(size_t e_count, size_t e_size, u8 init)
{
u8 **m = malloc(e_count *sizeof(u8*));
if(m) {
size_t i;
for(i=0; i<e_count; ++i) {
m[i] = malloc(e_size*e_count);
if(!m[i]) {
free_matrix((void**)m, e_count);
return NULL;
}
memset(m[i], init,e_size*e_count );
}
}
return (void**) m;
}
/*
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
let next be a |V| × |V| array of vertex indices initialized to null
procedure FloydWarshallWithPathReconstruction ()
for each edge (u,v)
dist[u][v] ← w(u,v) // the weight of the edge (u,v)
next[u][v] ← v
for k from 1 to |V| // standard Floyd-Warshall implementation
for i from 1 to |V|
for j from 1 to |V|
if dist[i][k] + dist[k][j] < dist[i][j] then
dist[i][j] ← dist[i][k] + dist[k][j]
next[i][j] ← next[i][k]
procedure Path(u, v)
if next[u][v] = null then
return []
path = [u]
while u ≠ v
u ← next[u][v]
path.append(u)
return path
*/
int floyd_warshall_find_min_path(struct graph *g, vertex_t source, vertex_t target, visitor_cb_t visit, void *data)
{
cost_t **dist = (cost_t **) alloc_square_matrix(num_vertices(g), sizeof(cost_t), 0xff);
vertex_t **next = (vertex_t **)alloc_square_matrix(num_vertices(g), sizeof(vertex_t), 0xff);
vertex_t i, j, k;
int r = -1;
if( !dist || !next ) {
err_printf("malloc() returned NULL");
goto bulk_free;
}
dbg_printf("Step 1: initialize graph");
for_each_edge(g, i, j) {
dist[i][j] = get_edge_cost(g, i, j);
next[i][j] = j;
}
dbg_printf("Step 2: relax edges repeatedly");
for_each_vertex(g, k)
for_each_vertex(g, i)
for_each_vertex(g, j) {
if( dist[i][k] != INFINITY && dist[k][j] != INFINITY &&
dist[i][k] + dist[k][j] < dist[i][j] ) {
dist[i][j] = dist[i][k] + dist[k][j];
next[i][j] = next[i][k];
}
}
i = target;
j = source;
visit(i, data);
while( i != j ) {
i = next[i][j];
visit(i, data);
}
r = 0;
bulk_free:
if(dist)
free_matrix((void**)dist,num_vertices(g));
if(next)
free_matrix((void**)next,num_vertices(g));
return r;
}
8<------------------------ path_search.h ------------------------
#ifndef __PATH_SEARCH_H__
#define __PATH_SEARCH_H__
#include <stdlib.h>
#include <string.h>
#include "graphs.h"
/*
# Алогоритмы поиска кратчайшего пути #
## Особенности реализации ##
Каждый алгоритм предсавляет собой функцию вида:
<название алгоритма>_find_min_path(g, s, t, cb, a):
Аргументы:
g - граф
s - начальная вершина
t - конечная вершина
cb - функция когорая будет вызыватся при новой вершине в минимальном пути
a - аргумент функции cb
Описание:
<название алгоритма>_find_min_path находит наименший путь между вершинами
s и t. При нахождении такового, <название алгоритма>_find_min_path вызывает
функцию cb(v, a), передавая первым аргументом вершину состоящую в мин. пути,
второй аргумент cb() равен последнму аргументу <название алгоритма>_ find_min_path().
cb() вызывается поочередно для каждой вершины в мин. пути.
*/
typedef void (*visitor_cb_t)(vertex_t, void *);
/*
Функции производящие поиск наименшего пути в графе.
*/
int dijkstra_find_min_path(struct graph *g, vertex_t source, vertex_t target, visitor_cb_t, void*);
int bellman_ford_find_min_path(struct graph *g, vertex_t source, vertex_t target, visitor_cb_t, void*);
int floyd_warshall_find_min_path(struct graph *g, vertex_t source, vertex_t target, visitor_cb_t visit, void *data);
/*
Функции предназначенные для передачи в качестве cb "аргумента", некому алгоритму
поиска кратчайшего пути.
void_visitor() - если эта ф-ция передаётся в качества аргумента cb
<название алгоритма>_find_min_path, то ничего не происходит.
vertex_print_visitor() - если эта ф-ция передаётся в качества аргумента cb
<название алгоритма>_find_min_path, поочередно выводятся вершины
состоящие в мин. пути.
street_print_visitor() - если эта ф-ция передаётся в качества аргумента cb
<название алгоритма>_find_min_path, то выводятся участки дорог
состоящие в мин пути.
*/
static inline void vertex_print_visitor(vertex_t v, void *arg)
{
size_t *cnt = (size_t*) arg;
printf("%s %d ", *cnt == 0 ? "| " : "->", v);
(*cnt) ++;
}
static inline void void_visitor(vertex_t v, void *arg) {}
struct street_print_visitor_arg
{
size_t length;
struct graph *g;
vertex_t previous;
};
static inline void street_print_visitor(vertex_t v, void *arg)
{
struct street_print_visitor_arg *a = (struct street_print_visitor_arg *) arg;
vertex_t prev = a->previous;
size_t cnt = a->length;
if(prev != UNIT ) {
printf("%s (%d) %s ", cnt == 0 ? "| " : "->", v,get_street_name(a->g, prev, v));
a->length++;
}
a->previous = v;
}
#endif /* __PATH_SEARCH_H__ */
8<------------------------ print_graphs.c ------------------------
#include "print_graphs.h"
#include "graphs.h"
void fprint_graph(FILE *fp, struct graph *ug)
{
vertex_t i,j;
fprintf(fp, "digraph\n{\n");
for_each_vertex(ug, i)
if( get_vertex_cost(ug,i) != UNIT )
fprintf(fp,"\t\""VERTEX_FMT"\"[label=\""VERTEX_FMT"\", shape=\"circle\"];\n", i, i);
fprintf(fp,"\n");
for_each_edge(ug, i, j) {
if( get_edge_cost(ug,i,j) != INFINITY ) {
if(get_edge_cost(ug,i,j) != get_edge_cost(ug, j, i)) {
fprintf(fp,"\t\""VERTEX_FMT"\" -> \""VERTEX_FMT"\"[label=\"%s ("COST_FMT")\"];\n",
i, j, i > j ? get_street_name(ug, i, j) : "", get_edge_cost(ug,i,j));
} else {
if(i > j) {
fprintf(fp,"\t\""VERTEX_FMT"\" -> \""VERTEX_FMT"\""
"[arrowhead=\"none\" label=\"%s\n("COST_FMT")\" weight=\""COST_FMT"\"];\n",
i, j, get_street_name(ug, i, j), get_edge_cost(ug,i,j), get_edge_cost(ug,i,j));
}
}
}
}
fprintf(fp,"}\n");
}
8<------------------------ print_graphs.h ------------------------
#ifndef __PRINT_GRAPHS_H__
#define __PRINT_GRAPHS_H__
#include <stdio.h>
#include "types.h"
#include "graphs.h"
/*
# Вывод графов в формате dot #
*/
/*
fprint_graph(fp, g):
Аргументы:
fp - указатель на тип FILE
g - некий граф
Описание:
Функция выводит граф g в поток fp в формате dot (GraphViz).
*/
void fprint_graph(FILE *fp, struct graph *ug);
#endif /* __PRINT_GRAPHS_H__ */
8<------------------------ streets.h.inc ------------------------
declare_street(none, "без названия")
__ds_sep declare_street(none1, "без названия 1")
__ds_sep declare_street(none2, "без названия 2")
__ds_sep declare_street(belova, "ул. Белова")
__ds_sep declare_street(stepana_razina, "ул. Степана Разина")
__ds_sep declare_street(pugacheva, "ул. Пугачёва")
__ds_sep declare_street(ogorodnaya, "ул. Огородная")
__ds_sep declare_street(sergievskaya, "ул. Сергиевская")
__ds_sep declare_street(khalturina, "ул. Халтурина")
__ds_sep declare_street(bobilskaya, "ул. Бобыльская")
__ds_sep declare_street(babushevskaya, "ул. Бабушевская")
__ds_sep declare_street(cooperativnaya, "ул. Кооперативная")
__ds_sep declare_street(sobstvennii, "ул. Собственный")
declare_crossroad2(belova, stepana_razina)
__dc_sep declare_crossroad2(belova, pugacheva)
__dc_sep declare_crossroad2(belova, ogorodnaya)
__dc_sep declare_crossroad2(belova, sergievskaya)
__dc_sep declare_crossroad2(belova, bobilskaya)
__dc_sep declare_crossroad2(stepana_razina, none1)
__dc_sep declare_crossroad2(stepana_razina, none2)
__dc_sep declare_crossroad2(stepana_razina, sergievskaya)
__dc_sep declare_crossroad2(pugacheva, none1)
__dc_sep declare_crossroad2(pugacheva, none2)
__dc_sep declare_crossroad2(pugacheva, sergievskaya)
__dc_sep declare_crossroad2(ogorodnaya, none2)
__dc_sep declare_crossroad2(ogorodnaya, sergievskaya)
__dc_sep declare_crossroad2(sergievskaya, khalturina)
__dc_sep declare_crossroad2(sergievskaya, none2)
__dc_sep declare_crossroad2(sergievskaya, babushevskaya)
__dc_sep declare_crossroad2(khalturina, bobilskaya)
__dc_sep declare_crossroad2(khalturina, babushevskaya)
__dc_sep declare_crossroad2(babushevskaya, none)
__dc_sep declare_crossroad2(sobstvennii, bobilskaya)
//__dc_sep declare_crossroad2(sobstvennii, none3)
//__dc_sep declare_crossroad2(belova, none3)
declare_street_pice(belova, stepana_razina, belova, pugacheva, 100)
__dp_sep declare_street_pice(belova, pugacheva, belova, ogorodnaya, 60)
__dp_sep declare_street_pice(belova, ogorodnaya, belova, sergievskaya, 70)
__dp_sep declare_street_pice(belova, sergievskaya, belova, bobilskaya, 530)
__dp_sep declare_street_pice(stepana_razina, belova, stepana_razina, none1, 211)
__dp_sep declare_street_pice(stepana_razina, none1, stepana_razina, none2, 151)
__dp_sep declare_street_pice(stepana_razina, none2, stepana_razina, sergievskaya, 215)
__dp_sep declare_street_pice(pugacheva, belova, pugacheva, none1, 212)
__dp_sep declare_street_pice(pugacheva, none1, pugacheva, none2, 155)
__dp_sep declare_street_pice(pugacheva, none2, pugacheva, sergievskaya, 232)
__dp_sep declare_street_pice(ogorodnaya, belova, ogorodnaya, none2, 371)
__dp_sep declare_street_pice(ogorodnaya, none2, ogorodnaya, sergievskaya, 240)
__dp_sep declare_street_pice(sergievskaya, stepana_razina, sergievskaya, pugacheva, 119)
__dp_sep declare_street_pice(sergievskaya, pugacheva, sergievskaya, ogorodnaya, 70)
__dp_sep declare_street_pice(sergievskaya, ogorodnaya, sergievskaya, khalturina, 181)
__dp_sep declare_street_pice(sergievskaya, khalturina, sergievskaya, none2, 134)
__dp_sep declare_street_pice(sergievskaya, none2, sergievskaya, ogorodnaya, 371)
__dp_sep declare_street_pice(none2, sergievskaya, none2, ogorodnaya, 62)
__dp_sep declare_street_pice(none2, ogorodnaya,none2, pugacheva, 70)
__dp_sep declare_street_pice(none2, pugacheva, none2, stepana_razina, 112)
__dp_sep declare_street_pice(khalturina, sergievskaya, khalturina, babushevskaya, 152)
__dp_sep declare_street_pice(khalturina, babushevskaya,khalturina, bobilskaya, 353)
__dp_sep declare_street_pice(babushevskaya, khalturina , babushevskaya, none, 316)
__dp_sep declare_street_pice(bobilskaya,khalturina, belova, bobilskaya, 627)
__dp_sep declare_street_pice( bobilskaya, belova, sobstvennii, bobilskaya, 381)
//__dp_sep declare_street_pice(sobstvennii, bobilskaya, sobstvennii, none3, 507)
//__dp_sep declare_street_pice(none3, sobstvennii, belova, none3 , 412)
8<------------------------ types.h ------------------------
#ifndef __TYPES_H__
#define __TYPES_H__
#include <stdint.h>
/*
# Типы #
Более удобные (лично мне) типы , где имя сформирвано сл. образом `sN` -
s - значность типа, т.е. u (unsigned) беззначный,s (signed) значный.
N - размер типа.
*/
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t s8;
typedef int16_t s16;
typedef int32_t s32;
typedef int64_t s64;
#endif /* __TYPES_H__ */
8<------------------------ utils.h ------------------------
#ifndef __UTILS_H__
#define __UTILS_H__
#include <stdio.h>
/*
# Утилиты #
*/
/*
err_printf(fmt,...):
Аргументы:
fmt,... - "printf style" аргументы
Описание:
Выводит сообщение об ошибке с доп. информацией.
Пример:
1
2 void func_X(int i) {
3 err_printf(" hello word! %d", i);
4 }
5
...
n func_X(44);
n+1
При выполнении строки n выведится:
error in func_X() : 3 -- hello word 44
*/
#define err_printf(fmt, ...) fprintf(stderr, "error in %s() : %d -- " fmt "\n\r", __func__, __LINE__ ,##__VA_ARGS__)
/*
dbg_printf(fmt,...):
Аргументы:
fmt,... - "printf style" аргументы
Описание:
Выводит диагностическую информацию с доп. информацией.
Пример:
1
2 void func_X(int i) {
3 dbg_printf(" hello word! %d", i);
4 }
5
...
n func_X(44);
n+1
При выполнении строки n выведится:
debug in func_X() : 3 -- hello word 44
*/
// #define dbg_printf(fmt, ...) fprintf(stdout, "debug from %s() : %d -- " fmt "\n\r", __func__, __LINE__ ,##__VA_ARGS__)
#define dbg_printf(fmt, ...)
/*
ASSERT(condition, if_true, fmt,...):
Аргументы:
condition - некое условие
if_true - действия выполняеме при истинности условия `condition`
fmt,... - "printf style" аргументы функции err_printf()
Описание:
При выполнении условия `condition` выводится сообщение об ошибке и
выполняется код в `if_true`.
Пример:
x = 0.4
ASSERT(x>0.1 && x < 0.5, exit(EXIT_FAILURE), "bad valure for x %f", x)
При выполнении данного кода программа завершится и на экран выведится примерно:
x>0.1 && x < 0.5 bad valure for x 0.4
*/
#define ASSERT(condition, if_true, fmt,...) if(condition) { err_printf( #condition fmt, ##__VA_ARGS__); if_true; }
/*
ARRSIZE(w):
Аргументы:
w - некий статичный массив
Описание:
Восвращает размер _статичного_ массива w
*/
#define ARRSIZE(w) (sizeof(w) / sizeof(w[0]))
#endif /* __UTILS_H__ */
Raw
graphs.c
#include <stdlib.h>
#include <string.h>
#include "graphs.h"
struct graph *alloc_graph(size_t num_vertices, storage_t vertices, storage_t edges)
{
struct graph *g = malloc(sizeof(struct graph));
if(!g) {
err_printf("malloc(1)");
goto err_end;
}
g->num_vertices = num_vertices;
g->matrix = malloc(sizeof(storage_t **)*num_vertices);
if(!g->matrix) {
err_printf("malloc(2)");
goto free_graph;
}
size_t i, j;
for(i=0; i < num_vertices; ++i) {
g->matrix[i] = malloc(sizeof(storage_t)*num_vertices);
if(!g->matrix[i]) {
err_printf("malloc(3)");
goto free_matrix_els;
}
for(j=0; j < num_vertices; ++j)
if( i == j ) {
g->matrix[i][j] = vertices;
} else {
g->matrix[i][j] = edges;
}
// dbg_printf("%d number %d", i, (num_vertices-i));
}
return g;
free_matrix_els:
for(i=0; i < num_vertices && g->matrix[i] ; ++i)
free(g->matrix[i]);
// free_matrix:
free(g->matrix);
free_graph:
free(g);
err_end:
return NULL;
}
void free_graph(struct graph *g)
{
int i;
for(i=0; i < g->num_vertices && g->matrix[i] ; ++i)
free(g->matrix[i]);
free(g->matrix);
free(g);
}
Raw
graphs.h
#ifndef __GRAPHS_H__
#define __GRAPHS_H__
#include "types.h"
#include "utils.h"
#define _for_each_vertex(g, i, begin) for( i = begin; i < (g)->num_vertices; ++i)
#define for_each_vertex(g, i) _for_each_vertex(g, i, 0)
#define for_each_edge(g, i, j) for( i = 0; i < (g)->num_vertices; ++i) \
for(j= i == 0 ? 1 : 0; j<(g)->num_vertices; ++j, j == i ? ++j : 0)
#define num_vertices(g) ((g)->num_vertices)
#define G_DATA_MASK ((storage_t) 0xffffffff)
#define G_UTIL_MASK ((storage_t) 0xffffffff00000000)
//#define G_UTIL_SHIFT 48
#define G_UTIL_SHIFT 32
#define G_DATA_SHIFT 0
#include <limits.h>
#include <stddef.h>
typedef u64 storage_t;
typedef u64 cost_t;
typedef u64 util_t;
#define INFINITY 0xffffffff
//#define INFINITY 0xfffff
typedef u32 vertex_t;
#define UNIT 0xffffffff
#define VERTEX_FMT "%d"
#define EDGE_FMT "%d"
#define COST_FMT "%ld"
struct graph
{
storage_t **matrix;
size_t num_vertices;
};
static inline cost_t get_edge_cost(const struct graph *g, vertex_t s, vertex_t t)
{
return (((g)->matrix[s][t]) & G_DATA_MASK) >> G_DATA_SHIFT ;
}
static inline void set_edge_cost(struct graph *g, vertex_t s, vertex_t t, cost_t cost)
{
((g)->matrix[s][t]) =
((cost << G_DATA_SHIFT) & G_DATA_MASK) |
(((g)->matrix[s][t]) & G_UTIL_MASK);
}
static inline cost_t get_vertex_cost(const struct graph *g, vertex_t a)
{
return (((g)->matrix[a][a]) & G_DATA_MASK) >> G_DATA_SHIFT ;
}
static inline void set_vertex_cost(struct graph *g, vertex_t a, cost_t cost)
{
g->matrix[a][a] =
((cost << G_DATA_SHIFT) & G_DATA_MASK) |
( g->matrix[a][a] & G_UTIL_MASK );
}
static inline util_t get_edge_util(const struct graph *g, vertex_t s, vertex_t t)
{
return (((g)->matrix[s][t]) & G_UTIL_MASK) >> G_UTIL_SHIFT ;
}
static inline void set_edge_util(struct graph *g, vertex_t s, vertex_t t, util_t cost)
{
((g)->matrix[s][t]) =
((cost << G_UTIL_SHIFT) & G_UTIL_MASK) |
(((g)->matrix[s][t]) & G_DATA_MASK);
}
static inline util_t get_vertex_util(const struct graph *g, vertex_t a)
{
return (((g)->matrix[a][a]) & G_UTIL_MASK) >> G_UTIL_SHIFT ;
}
static inline void set_vertex_util(struct graph *g, vertex_t a, util_t cost)
{
g->matrix[a][a] =
((cost << G_UTIL_SHIFT) & G_UTIL_MASK) |
( g->matrix[a][a] & G_DATA_MASK );
}
static inline void clear_vertex_util(struct graph *g, util_t mask)
{
vertex_t v;
for_each_vertex(g, v)
set_vertex_util(g, v, get_vertex_util(g, v) & mask);
}
struct graph *alloc_graph(size_t num_vertices, storage_t vertices, storage_t edges);
void free_graph(struct graph *g);
static inline vertex_t next_neighbor(struct graph *g, vertex_t v, vertex_t prev)
{
int i;
_for_each_vertex(g, i, prev == UNIT ? 0 : (prev+1)) {
if(get_edge_cost(g, i, v) != INFINITY )
return i;
}
return UNIT;
}
#define for_each_neighbor(g, v, a) for(a = next_neighbor(g, v, UNIT); a != UNIT; a = next_neighbor(g, v, a))
char *get_street_name(struct graph *g, vertex_t s, vertex_t t );
#endif /* __GRAPHS_H__ */
Raw
main.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <ncurses.h>
#include "utils.h"
#include "types.h"
#include "graphs.h"
#include "print_graphs.h"
static char *street_names[];
#define UTIL_BITS_GET_FILED(name, num) ( ( (num) >> (name ## _UTIL_SHIFT)) & (name ## _UTIL_MASK) )
#define UTIL_BITS_ENCODE_FILED(name, num) ( ( (num) & (name ## _UTIL_MASK) ) << (name ## _UTIL_SHIFT) )
typedef s32 street_id_t;
#define STREET_ID_UTIL_MASK 0xff
#define STREET_ID_UTIL_SHIFT 0
#define STREET_ID_UTIL_WIDTH 8
static inline street_id_t get_street_id(struct graph *g, vertex_t s, vertex_t t)
{
return UTIL_BITS_GET_FILED(STREET_ID, get_edge_util(g, t, s));
}
static inline void set_street_id(struct graph *g, vertex_t s, vertex_t t, street_id_t id )
{
set_edge_util(g, s, t, UTIL_BITS_ENCODE_FILED(STREET_ID, id));
set_edge_util(g, t, s, UTIL_BITS_ENCODE_FILED(STREET_ID, id));
}
char *get_street_name(struct graph *g, vertex_t s, vertex_t t )
{
return street_names[get_street_id(g, s, t)];
}
static inline void create_road(struct graph *g, vertex_t s, vertex_t t, cost_t len, street_id_t id )
{
set_edge_cost(g, s, t, len);
set_edge_cost(g, t, s, len);
set_vertex_cost(g, t, 0);
set_vertex_cost(g, s, 0);
set_street_id(g, t, s, id);
}
/* -------------------- Build streets -------------------- */
#define __ds_coma ,
#define __dc_coma
#define __dp_coma
#define declare_crossroad2(a, b)
#define declare_street_pice(a, b,c,d,e)
#define declare_street(name, rus) rus
static char *street_names[] = {
#include "streets.h.inc"
};
#undef declare_street
#define declare_street(name, rus) #name, #rus
static char *street_names_eng_rus[] = {
#include "streets.h.inc"
};
#undef declare_street
#define declare_street(name, rus) st_## name
enum streets_e{
#include "streets.h.inc"
};
#undef __ds_coma
#define __ds_coma +
#undef declare_street
#define declare_street(name, rus) 1
static const size_t num_roads =
#include "streets.h.inc"
;
#undef __ds_coma
#undef __dc_coma
#undef __dp_coma
#undef declare_street_pice
#undef declare_crossroad2
#undef declare_street
/* -------------------- Build streets crossings -------------------- */
#define __ds_coma
#define __dc_coma ,
#define __dp_coma
#define declare_street_pice(a, b,c,d,e)
#define declare_crossroad2(name1, name2) cr_ ## name1## _ ## name2
#define declare_street(a,b)
enum crossroads_e
{
#include "streets.h.inc"
};
#undef declare_crossroad2
#define declare_crossroad2(name1, name2) cr_ ## name2 ## _ ## name1
enum crossroads_e_inv
{
#include "streets.h.inc"
};
#undef declare_crossroad2
#define declare_crossroad2(name1, name2) st_##name1, st_##name2, cr_ ## name1 ## _ ## name2
vertex_t street_ids_to_crossings[] = {
#include "streets.h.inc"
};
#undef __dc_coma
#define __dc_coma +
#undef declare_crossroad2
#define declare_crossroad2(name1, name2) 1
static const size_t num_cross_roads =
#include "streets.h.inc"
;
#undef __ds_coma
#undef __dc_coma
#undef __dp_coma
#undef declare_street_pice
#undef declare_crossroad2
#undef declare_street
/* -------------------- Build map -------------------- */
#define __ds_coma
#define __dc_coma
#define __dp_coma ;
#define declare_street_pice(origin1, name1, origin2, name2, len) \
create_road(g, cr_ ## origin1 ## _ ## name1, cr_ ## origin2 ## _ ## name2, len, st_ ## origin1 )
#define declare_crossroad2(a, b)
#define declare_street(a, b)
static inline void __build_map(struct graph *g)
{
#include "streets.h.inc"
;
}
#undef __ds_coma
#undef __dc_coma
#undef __dp_coma
#undef declare_street_pice
#undef declare_crossroad2
#undef declare_street
#include "path_search.h"
#define MEASUTE_MAEN_TIME(mean_time, niter) for(; niter > 0 ; --niter )
typedef int (*find_min_path_cb_t)(struct graph *g, vertex_t source, vertex_t target, visitor_cb_t, void*);
u64 rdtsc(void)
{
u32 lo,hi;
__asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi));
return ((u64)hi << 32) | lo;
}
#include <sched.h>
#include <unistd.h>
int set_max_prio(int policy)
{
pid_t pid = getpid();
struct sched_param sp;
int max_prio = sched_get_priority_max(policy);
if(max_prio == -1) {
fprintf(stderr, "Can't get max prio, proceeding with default prio and sheduling policy.\n");
return -1;
}
sp.sched_priority = max_prio;
if ( sched_setscheduler ( pid, policy, &sp ) == -1 ) {
fprintf(stderr, "Can't set required sheduling policy, proceeding with default.\n");
return -1;
}
return 0;
}
#define PRINT_STATS(g, niter, cb, s, t) print_stats(g, #cb, niter, cb, s, t)
void print_stats(struct graph *g, char *aname, size_t niter, find_min_path_cb_t cb, vertex_t s,vertex_t t )
{
u64 t0, t1, p = 0;
size_t i;
t0 = rdtsc();
for(i = 0; i < niter; ++i) {
ASSERT(cb(g, s, t, void_visitor, NULL),
exit(EXIT_FAILURE), " %s () failed, exitting", aname);
}
t1 = rdtsc();
p = t1 - t0;
printf("executed %30s algorithm %ld times in %10ld cpu cycles, averadge loop time %10ld\n", aname, niter, p, p/niter);
}
void print_all_stats(struct graph *g, size_t nit)
{
if(set_max_prio(SCHED_FIFO) == -1)
fprintf(stderr, "Oops, sounds bad - results might be compromised.\n");
PRINT_STATS(g, nit, floyd_warshall_find_min_path, 0,17 );
PRINT_STATS(g, nit, bellman_ford_find_min_path, 0,17 );
PRINT_STATS(g, nit, dijkstra_find_min_path, 0,17 );
}
void simply_run(struct graph *g)
{
struct street_print_visitor_arg arg;
arg.length = 0; arg.g = g;arg.previous = UNIT;
ASSERT(dijkstra_find_min_path(g, 0, 17, street_print_visitor, (void*) &arg),
exit(EXIT_FAILURE), " *_fin_min_path() failed, exitting" );
printf("\n");
arg.length = 0; arg.g = g;arg.previous = UNIT;
ASSERT(bellman_ford_find_min_path(g, 0, 17, street_print_visitor, (void*) &arg),
exit(EXIT_FAILURE), " *_fin_min_path() failed, exitting" );
printf("\n");
arg.length = 0; arg.g = g;arg.previous = UNIT;
ASSERT(floyd_warshall_find_min_path(g, 0, 17, street_print_visitor, (void*) &arg),
exit(EXIT_FAILURE), " *_fin_min_path() failed, exitting" );
printf("\n");
}
void print_min_path(struct graph *g, vertex_t s, vertex_t t)
{
struct street_print_visitor_arg arg;
arg.length = 0; arg.g = g;arg.previous = UNIT;
ASSERT(dijkstra_find_min_path(g, s, t, street_print_visitor, (void*) &arg),
exit(EXIT_FAILURE), " *_fin_min_path() failed, exitting" );
printf("\n");
}
#define PRINT_MIN_PATH(g, r00, r01, r10, r11 ) print_min_path(g, cr_ ## r00 ## _ ## r01, cr_ ## r10 ## _ ## r11 )
/*
* ==================== getopt ====================
*/
#include <stdbool.h>
char *_get_argument_value_str(char *this, char *next, bool *skip_one)
{
switch(*this) {
case '=': return this + 1;
case '\0':
*skip_one = true;
return next;
default:
return this;
}
}
street_id_t street_id_from_name(char *name)
{
size_t i = 0;
for(; i<ARRSIZE(street_names_eng_rus); ++i) {
if(strcmp(street_names_eng_rus[i], name) == 0)
return i/2;
}
return -1;
}
vertex_t crossroad_from_street_ids(street_id_t s0, street_id_t s1)
{
size_t i = 0;
for(; i<ARRSIZE(street_ids_to_crossings); i += 3) {
if( (street_ids_to_crossings[i] == s0 && street_ids_to_crossings[i+1] == s1) ||
(street_ids_to_crossings[i] == s1 && street_ids_to_crossings[i+1] == s0) )
return street_ids_to_crossings[i+2];
}
return UNIT;
}
int path_from_string(char *s, vertex_t *vs, vertex_t *vt)
{
char *p = strchr(s, ',');
if(!p) return -1;
else *p = '\0';
street_id_t s0 = street_id_from_name(s);
*p = ',';
if(s0 == -1) return -1;
s = strchr(p+1, '+');
if(!s) return -1;
else *s = '\0';
street_id_t s1 = street_id_from_name(p+1);
*s = '+';
if(s1 == -1) return -1;
p = strchr(s+1, ',');
if(!p) return -1;
else *p = '\0';
street_id_t s2 = street_id_from_name(s+1);
*p = ',';
if(s2 == -1) return -1;
street_id_t s3 = street_id_from_name(p+1);
if(s3 == -1) return -1;
*vs = crossroad_from_street_ids(s0, s1);
*vt = crossroad_from_street_ids(s2, s3);
return 0;
}
int main(int argc, char *argv[])
{
struct graph *g = alloc_graph(num_cross_roads, INFINITY, UNIT);
if(!g){
err_printf("alloc_graph()");
return 1;
}
__build_map(g);
vertex_t v, s;
size_t i = 1;
bool skip_one;
char def_path[] = "belova,stepana_razina+khalturina,bobilskaya";
char *path = def_path;
for( skip_one = false; argv[i] && argv[i][0] == '-' ; ++i ) {
switch(argv[i][1]) {
case 'j' : simply_run(g); exit(EXIT_SUCCESS); break;
case 's' : print_all_stats(g, 10000); exit(EXIT_SUCCESS); break;
case 'm' : fprint_graph(stdout, g); exit(EXIT_SUCCESS); break;
case 'p' : path = _get_argument_value_str(&argv[i][2], argv[i+1], &skip_one); break;
case 'h' :
printf("Usage %s [ -s | -m | -h | -j | -p s0,s1+s2,s3 ]\n"
"\t -s print algorithm stats\n"
"\t -j simply run algorithms\n"
"\t -m print map graph\n"
"\t -p fing shortest path form 's0,s1' to 's2,s3'\n"
"\t -h output this help\n"
, argv[0]);
exit(EXIT_SUCCESS);
default:
err_printf("bad flag '%s' %ld", argv[i], i);
exit(EXIT_FAILURE);
}
if(skip_one) {
skip_one = false;
++i;
}
}
// PRINT_MIN_PATH(g, belova,stepana_razina,khalturina,bobilskaya);
if(path_from_string(path, &v, &s) ) {
err_printf("path_from_string(%s)", path);
exit(EXIT_FAILURE);
}
print_min_path(g, v, s);
free_graph(g);
return 0;
}
Raw
Makefile
include nice-display.mk
CFLAGS:=-g -Wall -O0
CLIBS=-lncurses
objs = print_graphs.o graphs.o path_search.o
headers = \
graphs.h \
print_graphs.h \
types.h \
utils.h \
path_search.h
main: main.c $(objs) $(headers)
# Nice output
%.o : %.c %.h
$(call named_stripe,$@,"\E[2m","\E[2m")
$(CC) $(CFLAGS) $(CLIBS) -c $^
%.bin : %.c $(objs) $(headers)
$(call named_stripe,$@)
$(CC) $(CFLAGS) $(CLIBS) -o $@ $^
% : %.c $(objs) $(headers)
$(call named_stripe,$@)
$(CC) $(CFLAGS) $(CLIBS) -o $@ $^
view:
xdot graph.0.dot 2>/dev/null &
xdot graph.p0.dot 2>/dev/null &
xdot graph.pt0.dot 2>/dev/null &
PHONY += view
.PHONY: $(PHONY)
Raw
nice-display.mk
stripe=@for((i=0; i<`tput cols`; ++i)) do echo -n "="; done; echo
# named_stripe() - Print a "named stipe" i.e. '====..==== some name ====...===`
# arguments:
# name - the "name" which will be printed in the stripe
# name_color - the color of the name "name"
# stripe_color - the color of the name "name"
define named_stripe=
@cols=$$[`tput cols`/2 - `echo $(1) | wc -c`/2 - 2]; \
echo -n -e $(3); for((i=0; i<cols; ++i)) do echo -n "="; done; echo -ne "\E[0m";\
for((i=0; i<2; ++i)) do echo -n " "; done; \
\
echo -n -e $(2)"$(1)""\E[0m"; \
for((i=0; i<2; ++i)) do echo -n " "; done; \
echo -n -e $(3); for((i=0; i<cols; ++i)) do echo -n "="; done; echo -e "\E[0m";
endef
Raw
output.txt
$./main -h
Usage ./main [ -s | -m | -h | -j | -p s0,s1+s2,s3 ]
-s print algorithm stats
-j simply run algorithms
-m print map graph
-p fing shortest path form 's0,s1' to 's2,s3'
-h output this help
$ ./main -p 'belova,stepana_razina+khalturina,bobilskaya'
| (17) ул. Халтурина -> (13) ул. Халтурина -> (14) ул. Сергиевская -> (11) без названия 2 -> (2) ул. Огородная -> (1) ул. Белова -> (0) ул. Белова
$ ./main -j
| (13) ул. Халтурина -> (14) ул. Сергиевская -> (11) без названия 2 -> (2) ул. Огородная -> (1) ул. Белова -> (0) ул. Белова
| (13) ул. Халтурина -> (14) ул. Сергиевская -> (11) без названия 2 -> (2) ул. Огородная -> (1) ул. Белова -> (0) ул. Белова
| (13) ул. Халтурина -> (14) ул. Сергиевская -> (11) без названия 2 -> (2) ул. Огородная -> (1) ул. Белова -> (0) ул. Белова
$ sudo ./main -s
[sudo] password for arseni:
executed floyd_warshall_find_min_path algorithm 10000 times in 1381084442 cpu cycles, averadge loop time 138108
executed bellman_ford_find_min_path algorithm 10000 times in 1169512647 cpu cycles, averadge loop time 116951
executed dijkstra_find_min_path algorithm 10000 times in 93751552 cpu cycles, averadge loop time 9375
$ sudo ./main -s
executed floyd_warshall_find_min_path algorithm 10000 times in 1231012946 cpu cycles, averadge loop time 123101
executed bellman_ford_find_min_path algorithm 10000 times in 1283962519 cpu cycles, averadge loop time 128396
executed dijkstra_find_min_path algorithm 10000 times in 82682252 cpu cycles, averadge loop time 8268
$ sudo ./main -s
executed floyd_warshall_find_min_path algorithm 10000 times in 1291067904 cpu cycles, averadge loop time 129106
executed bellman_ford_find_min_path algorithm 10000 times in 1172934844 cpu cycles, averadge loop time 117293
executed dijkstra_find_min_path algorithm 10000 times in 89067981 cpu cycles, averadge loop time 8906
$ sudo ./main -s
executed floyd_warshall_find_min_path algorithm 10000 times in 1300203177 cpu cycles, averadge loop time 130020
executed bellman_ford_find_min_path algorithm 10000 times in 1176755517 cpu cycles, averadge loop time 117675
executed dijkstra_find_min_path algorithm 10000 times in 87138608 cpu cycles, averadge loop time 8713
Raw
path_search.c
#include "path_search.h"
int dijkstra_find_min_path(struct graph *g, vertex_t source, vertex_t target, visitor_cb_t visit, void *data)
{
cost_t *dist = malloc(g->num_vertices*sizeof(cost_t));
vertex_t *prev = malloc(g->num_vertices*sizeof(vertex_t));
vertex_t u,v;
int r = -1;
enum e_Q { PRESENT, ABSENT };
enum e_Q *Q = malloc(g->num_vertices*sizeof(enum e_Q));
size_t Q_size = 0;
if( !dist || !prev || !Q) {
err_printf("malloc() returned NULL");
goto bulk_free;
}
dbg_printf("Initialization");
dist[source] = 0;
prev[source] = UNIT;
for_each_vertex(g, v) {
if( v != source) {
dist[v] = INFINITY;
prev[v] = UNIT;
}
Q[v] = PRESENT;
Q_size ++;
}
dbg_printf("distance[] & prev[] computrtion");
while(Q_size) {
cost_t min_dist;
dbg_printf("u ← vertex in Q with min dist[u]");
min_dist = INFINITY;
for_each_vertex(g, v)
if(Q[v] == PRESENT && dist[v] <= min_dist) {
u = v;
min_dist = dist[v];
}
if(u == target)
break;
Q[u] = ABSENT;
Q_size --;
for_each_neighbor(g, u, v) {
cost_t alt = dist[u] + get_edge_cost(g, u, v);
if(alt < dist[v]) {
dist[v] = alt;
prev[v] = u;
}
}
}
for(v = target; v != UNIT; v = prev[v] )
visit(v, data);
r = 0;
bulk_free:
if(dist)
free(dist);
if(prev)
free(prev);
if(Q)
free(Q);
return r;
}
/*
function BellmanFord(list vertices, list edges, vertex source)
::distance[],predecessor[]
// This implementation takes in a graph, represented as
// lists of vertices and edges, and fills two arrays
// (distance and predecessor) with shortest-path
// (less cost/distance/metric) information
// Step 1: initialize graph
for each vertex v in vertices:
if v is source then distance[v] := 0
else distance[v] := inf
predecessor[v] := null
// Step 2: relax edges repeatedly
for i from 1 to size(vertices)-1:
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
distance[v] := distance[u] + w
predecessor[v] := u
// Step 3: check for negative-weight cycles
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
error "Graph contains a negative-weight cycle"
return distance[], predecessor[]
*/
int bellman_ford_find_min_path(struct graph *g, vertex_t source, vertex_t target, visitor_cb_t visit, void *data)
{
cost_t *dist = malloc(num_vertices(g)*sizeof(cost_t));
vertex_t *prev = malloc(num_vertices(g)*sizeof(vertex_t));
vertex_t v, u;
size_t i;
int r = -1;
if( !dist || !prev ) {
err_printf("malloc() returned NULL");
goto bulk_free;
}
dbg_printf("Step 1: initialize graph");
for_each_vertex(g, v) {
dist[v] = INFINITY;
prev[v] = UNIT;
}
dist[source] = 0;
dbg_printf("Step 2: relax edges repeatedly");
for(i=1; i < num_vertices(g)-1; ++i )
for_each_edge(g, u, v) {
cost_t w = get_edge_cost(g, v, u);
if(w != INFINITY && dist[u] != INFINITY &&
dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
prev[v] = u;
}
}
for_each_edge(g, u, v)
dbg_printf("(%d %d) -- %ld", u, v, get_edge_cost(g, u, v));
dbg_printf(" %d", INFINITY);
for(i=0; i<num_vertices(g); ++i) {
dbg_printf("%d p-> %d d-> %d",i ,prev[i], dist[i]);
}
dbg_printf("Step 3: filling struct vertex_list");
for(v = target; v != UNIT; v = prev[v] )
visit(v, data);
r = 0;
bulk_free:
if(dist)
free(dist);
if(prev)
free(prev);
return r;
}
void free_matrix(void **m, size_t e_count)
{
size_t i;
for(i=0; i<e_count; ++i)
free(m[i]);
free(m);
}
void **alloc_square_matrix(size_t e_count, size_t e_size, u8 init)
{
u8 **m = malloc(e_count *sizeof(u8*));
if(m) {
size_t i;
for(i=0; i<e_count; ++i) {
m[i] = malloc(e_size*e_count);
if(!m[i]) {
free_matrix((void**)m, e_count);
return NULL;
}
memset(m[i], init,e_size*e_count );
}
}
return (void**) m;
}
/*
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
let next be a |V| × |V| array of vertex indices initialized to null
procedure FloydWarshallWithPathReconstruction ()
for each edge (u,v)
dist[u][v] ← w(u,v) // the weight of the edge (u,v)
next[u][v] ← v
for k from 1 to |V| // standard Floyd-Warshall implementation
for i from 1 to |V|
for j from 1 to |V|
if dist[i][k] + dist[k][j] < dist[i][j] then
dist[i][j] ← dist[i][k] + dist[k][j]
next[i][j] ← next[i][k]
procedure Path(u, v)
if next[u][v] = null then
return []
path = [u]
while u ≠ v
u ← next[u][v]
path.append(u)
return path
*/
int floyd_warshall_find_min_path(struct graph *g, vertex_t source, vertex_t target, visitor_cb_t visit, void *data)
{
cost_t **dist = (cost_t **) alloc_square_matrix(num_vertices(g), sizeof(cost_t), 0xff);
vertex_t **next = (vertex_t **)alloc_square_matrix(num_vertices(g), sizeof(vertex_t), 0xff);
vertex_t i, j, k;
int r = -1;
if( !dist || !next ) {
err_printf("malloc() returned NULL");
goto bulk_free;
}
dbg_printf("Step 1: initialize graph");
for_each_edge(g, i, j) {
dist[i][j] = get_edge_cost(g, i, j);
next[i][j] = j;
}
dbg_printf("Step 2: relax edges repeatedly");
for_each_vertex(g, k)
for_each_vertex(g, i)
for_each_vertex(g, j) {
if( dist[i][k] != INFINITY && dist[k][j] != INFINITY &&
dist[i][k] + dist[k][j] < dist[i][j] ) {
dist[i][j] = dist[i][k] + dist[k][j];
next[i][j] = next[i][k];
}
}
i = target;
j = source;
visit(i, data);
while( i != j ) {
i = next[i][j];
visit(i, data);
}
r = 0;
bulk_free:
if(dist)
free_matrix((void**)dist,num_vertices(g));
if(next)
free_matrix((void**)next,num_vertices(g));
return r;
}
Raw
path_search.h
#ifndef __PATH_SEARCH_H__
#define __PATH_SEARCH_H__
#include <stdlib.h>
#include <string.h>
#include "graphs.h"
typedef void (*visitor_cb_t)(vertex_t, void *);
int dijkstra_find_min_path(struct graph *g, vertex_t source, vertex_t target, visitor_cb_t, void*);
int bellman_ford_find_min_path(struct graph *g, vertex_t source, vertex_t target, visitor_cb_t, void*);
int floyd_warshall_find_min_path(struct graph *g, vertex_t source, vertex_t target, visitor_cb_t visit, void *data);
static inline void vertex_print_visitor(vertex_t v, void *arg)
{
size_t *cnt = (size_t*) arg;
printf("%s %d ", *cnt == 0 ? "| " : "->", v);
(*cnt) ++;
}
static inline void void_visitor(vertex_t v, void *arg)
{
}
struct street_print_visitor_arg
{
size_t length;
struct graph *g;
vertex_t previous;
};
static inline void street_print_visitor(vertex_t v, void *arg)
{
struct street_print_visitor_arg *a = (struct street_print_visitor_arg *) arg;
vertex_t prev = a->previous;
size_t cnt = a->length;
if(prev != UNIT ) {
printf("%s (%d) %s ", cnt == 0 ? "| " : "->", v,get_street_name(a->g, prev, v));
a->length++;
}
a->previous = v;
}
#endif /* __PATH_SEARCH_H__ */
Raw
print_graphs.c
#include "print_graphs.h"
#include "graphs.h"
void fprint_graph(FILE *fp, struct graph *ug)
{
vertex_t i,j;
fprintf(fp, "digraph\n{\n");
for_each_vertex(ug, i)
if( get_vertex_cost(ug,i) != UNIT )
fprintf(fp,"\t\""VERTEX_FMT"\"[label=\""VERTEX_FMT"\", shape=\"circle\"];\n", i, i);
fprintf(fp,"\n");
for_each_edge(ug, i, j) {
if( get_edge_cost(ug,i,j) != INFINITY ) {
if(get_edge_cost(ug,i,j) != get_edge_cost(ug, j, i)) {
fprintf(fp,"\t\""VERTEX_FMT"\" -> \""VERTEX_FMT"\"[label=\"%s ("COST_FMT")\"];\n",
i, j, i > j ? get_street_name(ug, i, j) : "", get_edge_cost(ug,i,j));
} else {
if(i > j) {
fprintf(fp,"\t\""VERTEX_FMT"\" -> \""VERTEX_FMT"\""
"[arrowhead=\"none\" label=\"%s\n("COST_FMT")\" weight=\""COST_FMT"\"];\n",
i, j, get_street_name(ug, i, j), get_edge_cost(ug,i,j), get_edge_cost(ug,i,j));
}
}
}
}
fprintf(fp,"}\n");
}
Raw
print_graphs.h
#ifndef __PRINT_GRAPHS_H__
#define __PRINT_GRAPHS_H__
#include <stdio.h>
#include "types.h"
#include "graphs.h"
void fprint_graph(FILE *fp, struct graph *ug);
#endif /* __PRINT_GRAPHS_H__ */
Raw
streets.h.inc
declare_street(none, "без названия")
__ds_coma declare_street(none1, "без названия 1")
__ds_coma declare_street(none2, "без названия 2")
// __ds_coma declare_street(none3, "без названия 3")
__ds_coma declare_street(belova, "ул. Белова")
__ds_coma declare_street(stepana_razina, "ул. Степана Разина")
__ds_coma declare_street(pugacheva, "ул. Пугачёва")
__ds_coma declare_street(ogorodnaya, "ул. Огородная")
__ds_coma declare_street(sergievskaya, "ул. Сергиевская")
__ds_coma declare_street(khalturina, "ул. Халтурина")
__ds_coma declare_street(bobilskaya, "ул. Бобыльская")
__ds_coma declare_street(babushevskaya, "ул. Бабушевская")
__ds_coma declare_street(cooperativnaya, "ул. Кооперативная")
__ds_coma declare_street(sobstvennii, "ул. Собственный")
declare_crossroad2(belova, stepana_razina)
__dc_coma declare_crossroad2(belova, pugacheva)
__dc_coma declare_crossroad2(belova, ogorodnaya)
__dc_coma declare_crossroad2(belova, sergievskaya)
__dc_coma declare_crossroad2(belova, bobilskaya)
__dc_coma declare_crossroad2(stepana_razina, none1)
__dc_coma declare_crossroad2(stepana_razina, none2)
__dc_coma declare_crossroad2(stepana_razina, sergievskaya)
__dc_coma declare_crossroad2(pugacheva, none1)
__dc_coma declare_crossroad2(pugacheva, none2)
__dc_coma declare_crossroad2(pugacheva, sergievskaya)
__dc_coma declare_crossroad2(ogorodnaya, none2)
__dc_coma declare_crossroad2(ogorodnaya, sergievskaya)
__dc_coma declare_crossroad2(sergievskaya, khalturina)
__dc_coma declare_crossroad2(sergievskaya, none2)
__dc_coma declare_crossroad2(sergievskaya, babushevskaya)
__dc_coma declare_crossroad2(khalturina, bobilskaya)
__dc_coma declare_crossroad2(khalturina, babushevskaya)
__dc_coma declare_crossroad2(babushevskaya, none)
__dc_coma declare_crossroad2(sobstvennii, bobilskaya)
//__dc_coma declare_crossroad2(sobstvennii, none3)
//__dc_coma declare_crossroad2(belova, none3)
declare_street_pice(belova, stepana_razina, belova, pugacheva, 100)
__dp_coma declare_street_pice(belova, pugacheva, belova, ogorodnaya, 60)
__dp_coma declare_street_pice(belova, ogorodnaya, belova, sergievskaya, 70)
__dp_coma declare_street_pice(belova, sergievskaya, belova, bobilskaya, 530)
__dp_coma declare_street_pice(stepana_razina, belova, stepana_razina, none1, 211)
__dp_coma declare_street_pice(stepana_razina, none1, stepana_razina, none2, 151)
__dp_coma declare_street_pice(stepana_razina, none2, stepana_razina, sergievskaya, 215)
__dp_coma declare_street_pice(pugacheva, belova, pugacheva, none1, 212)
__dp_coma declare_street_pice(pugacheva, none1, pugacheva, none2, 155)
__dp_coma declare_street_pice(pugacheva, none2, pugacheva, sergievskaya, 232)
__dp_coma declare_street_pice(ogorodnaya, belova, ogorodnaya, none2, 371)
__dp_coma declare_street_pice(ogorodnaya, none2, ogorodnaya, sergievskaya, 240)
__dp_coma declare_street_pice(sergievskaya, stepana_razina, sergievskaya, pugacheva, 119)
__dp_coma declare_street_pice(sergievskaya, pugacheva, sergievskaya, ogorodnaya, 70)
__dp_coma declare_street_pice(sergievskaya, ogorodnaya, sergievskaya, khalturina, 181)
__dp_coma declare_street_pice(sergievskaya, khalturina, sergievskaya, none2, 134)
__dp_coma declare_street_pice(sergievskaya, none2, sergievskaya, ogorodnaya, 371)
__dp_coma declare_street_pice(none2, sergievskaya, none2, ogorodnaya, 62)
__dp_coma declare_street_pice(none2, ogorodnaya,none2, pugacheva, 70)
__dp_coma declare_street_pice(none2, pugacheva, none2, stepana_razina, 112)
__dp_coma declare_street_pice(khalturina, sergievskaya, khalturina, babushevskaya, 152)
__dp_coma declare_street_pice(khalturina, babushevskaya,khalturina, bobilskaya, 353)
__dp_coma declare_street_pice(babushevskaya, khalturina , babushevskaya, none, 316)
__dp_coma declare_street_pice(bobilskaya,khalturina, belova, bobilskaya, 627)
__dp_coma declare_street_pice( bobilskaya, belova, sobstvennii, bobilskaya, 381)
//__dp_coma declare_street_pice(sobstvennii, bobilskaya, sobstvennii, none3, 507)
//__dp_coma declare_street_pice(none3, sobstvennii, belova, none3 , 412)
Raw
types.h
#ifndef __TYPES_H__
#define __TYPES_H__
#include <stdint.h>
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t s8;
typedef int16_t s16;
typedef int32_t s32;
typedef int64_t s64;
#endif /* __TYPES_H__ */
Raw
utils.h
#ifndef __UTILS_H__
#define __UTILS_H__
#ifndef offsetof
# define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
#include <stdio.h>
#define ASSERT(condition, if_true, fmt,...) if(condition) { err_printf( #condition fmt, ##__VA_ARGS__); if_true; }
#define DO_NOTHING if(0) {}
#define DO_EXIT exit(EXIT_FAILURE)
#define DO_HUNG while(1) {};
#define DO_ABORT abort();
#define err_printf(fmt, ...) fprintf(stderr, "error in %s() : %d -- " fmt "\n\r", __func__, __LINE__ ,##__VA_ARGS__)
// #define dbg_printf(fmt, ...) fprintf(stdout, "debug from %s() : %d -- " fmt "\n\r", __func__, __LINE__ ,##__VA_ARGS__)
#define dbg_printf(fmt, ...)
#define ARRSIZE(w) (sizeof(w) / sizeof(w[0]))
#define _CMP_TEMPL(a, op,b) ({ __typeof__(a) __a__ = (a); __typeof__(b) __b__ = (b); __a__ op __b__ ? __a__ : __b__; })
#define MAX(a,b) _CMP_TEMPL(a, >, b)
#define MIN(a,b) _CMP_TEMPL(a, <, b)
#define ABS(a) ({ __typeof__(a) __a__ = (a); __a__ > 0 ? __a__ : -((signed)__a__); })
#define lambda(rtype, body) ({ rtype __fn__ body; __fn__; })
#define likely(x) x
#define unlikely(x) x
//#define dbg_printf(fmt, ...)
#endif /* __UTILS_H__ */
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment