Graph structure

Types

typedef __uint32_t	t_uint;
typedef __int32_t	t_int;

Structures

typedef struct			s_graph
{
	t_node **restrict	nodes;
	void *restrict		mem;
	size_t			size;
	t_uint			start;
	t_uint			end;
}				t_graph;

For understand look at this example:

typedef struct		s_node
{
	t_uint		count_connects	: 30;
	t_uint		marked		: 1;
	t_uint		in_queue	: 1;
	t_uint		separate	: 1;
	t_uint		marked_sep	: 1;
	t_uint		parent		: 30;
	t_int		weight		: 31;
	t_uint		in_new_way	: 1;
}			t_node;

# define MARKED_IN		0
# define MARKED_OUT		1

Value of marked_sep matter only if separate == 1. Marked_sep can be MARKED_IN or MARKED_OUT

From here on will be assumed that our ant's farm can't consist from more than (UINT32_MAX >> 2) rooms (can be written in a 30-bits number). Otherwise, in case ((UINT32_MAX >> 2) + 1) rooms, at least 20 GB of RAM will be required for this programm (and this is in the case of zero connections). This trick will allow us to store each graph node in 12 bytes, and each connection only in 4 bytes.

typedef struct			s_connect
{
	t_uint			dst	: 30;
	t_int			state	: 2;
}				t_connect;

# define CONNECT_BASE_STATE	1
# define CONNECT_NEGATIVE	-1
# define CONNECT_FORBIDDEN	0

Some benefits and asymptotic analysis for graph:

N - number of nodes, C - count connect for node

• access operation to node : O(1)
• get next connect for node: O(1)
• find particular connect : O(log(C))

Also thanks to the competent packaging of structures and the location of the entire graph on one piece of memory, we achieve the highest possible level of cacheability and speed of the graph traversal.

In addition, the use of flags to separate nodes and links allows us to look for a solution by changing only the state of the graph, but not changing the graph itself.