Graph algorithm visualization sample

gui.py

import Tkinter
import socket
import struct

sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect(('127.0.0.1', 35555))
sock.setblocking(False)

root = Tkinter.Tk()
canvas = Tkinter.Canvas(root, width = 700, height = 700)
vmap = {}

def draw_circle(x, y):
    return canvas.create_oval(x - 5, y - 5, x + 5, y + 5)

def draw_dot_line(x1, y1, x2, y2):
    canvas.create_line(x1, y1, x2, y2, dash=(1,1))

def draw_line(x1, y1, x2, y2):
    canvas.create_line(x1, y1, x2, y2, width=2, arrow=Tkinter.LAST)

def change_color(id, color):
    canvas.itemconfigure(id, fill = color)

def try_recv():
    global sock
    try:
        buf = sock.recv(4 * 8)
    except socket.error, (value, msg):
        print 'socket.error: ', msg, value
    if not buf:
        print 'socket closed'
        return

    (type, vindex, x, y) = struct.unpack('=2Q2d', buf)
    print type, vindex, x, y

    if type == 0:
        vmap[vindex] = (x, y, draw_circle(x, y))
    elif type == 1:
        change_color(vmap[vindex][2], 'red')
    elif type == 2:
        change_color(vmap[vindex][2], 'blue')
    elif type == 3:
        draw_dot_line(vmap[vindex][0], vmap[vindex][1], x, y)
    elif type == 4:
        draw_line(vmap[vindex][0], vmap[vindex][1], x, y)

    root.after(10 if type == 3 or type == 4 else 1000, try_recv)

canvas.pack(expand=True, fill=Tkinter.BOTH)
root.after(2000, try_recv)
root.focus_set()
root.mainloop()

server.cpp

#include <cstdint>
#include <random>
#include <string>
#include <boost/asio/buffer.hpp>
#include <boost/asio/io_service.hpp>
#include <boost/asio/ip/tcp.hpp>
#include <boost/format.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/fruchterman_reingold.hpp>
#include <boost/graph/random_layout.hpp>
#include <boost/graph/small_world_generator.hpp>
#include <boost/graph/topology.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/property_iter_range.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/range/algorithm/for_each.hpp>


struct message {
	std::uint64_t type;    // message type
	std::uint64_t vindex;
	double coord_x;
	double coord_y;

	auto buffer() const
		-> boost::asio::const_buffers_1
	{
		return boost::asio::buffer(this, sizeof(*this));
	}
};

template <class Socket, class IndexMap, class CoordMap, class BaseVisitor>
class mygraph_visitor : public BaseVisitor
{
	using vertex_t = typename boost::property_traits<IndexMap>::key_type;
public:
	mygraph_visitor(Socket& socket, IndexMap index_map, CoordMap coord_map)
		: socket_{socket}, index_map_{index_map}, coord_map_{coord_map}
		, predecessor_map_{index_map_}
	{
	}

	template <class V, class G>
	void discover_vertex(V v, G&)
	{
		send(0, v, v);
	}

	template <class V, class G>
	void examine_vertex(V v, G&)
	{
		if (predecessor_map_.storage_begin() == predecessor_map_.storage_end()) {
			send(1, v, v);
		}
		else {
			send(4, get(predecessor_map_, v), v);
			send(2, v, v);
		}
	}

	template <class E, class G>
	void examine_edge(E e, G& g)
	{
		send(3, source(e, g), target(e, g));
	}

	template <class E, class G>
	void tree_edge(E e, G& g)
	{
		put(predecessor_map_, target(e, g), source(e, g));
	}

private:
	template <class V>
	void send(std::uint32_t const type, V source, V target)
	{
		auto const coord = get(coord_map_, target);
		auto const m = message{type, get(index_map_, source), coord[0], coord[1]};
		socket_.send(m.buffer());
	}

private:
	Socket& socket_;
	IndexMap index_map_;
	CoordMap coord_map_;
	boost::vector_property_map<vertex_t, IndexMap> predecessor_map_;
};

template <class BaseVisitor, class Socket, class IndexMap, class CoordMap>
auto make_mygraph_visitor(Socket& socket, IndexMap index_map, CoordMap coord_map)
	-> mygraph_visitor<Socket, IndexMap, CoordMap, BaseVisitor>
{
	return {socket, index_map, coord_map};
}




struct vertex_position_t {
	using kind = boost::vertex_property_tag;
} vertex_position;

template <class Graph>
auto small_world_graph(std::size_t const num_v)
	-> Graph
{
	using sw_iterator = boost::small_world_iterator<std::mt19937, Graph>;
	auto gen = std::mt19937{static_cast<std::mt19937::result_type>(std::time(nullptr))};
	return Graph{sw_iterator{gen, num_v, 4, 0.15}, sw_iterator{}, num_v};
}

template <class Graph, class PositionMap>
void layout(Graph& graph, PositionMap position_map, double const scale)
{
	using topology = boost::square_topology<std::mt19937>;
	auto gen = std::mt19937{static_cast<std::mt19937::result_type>(std::time(nullptr))};

	boost::random_graph_layout(graph, position_map, topology{gen, scale});
	boost::fruchterman_reingold_force_directed_layout(graph, position_map, topology{gen, scale});

	boost::for_each(boost::get_property_iter_range(graph, vertex_position), [=](auto& point) {
		point[0] += scale;
		point[1] += scale;
	});
}


int main(int argc, char* argv[])
{
	if (argc != 2) {
		std::cerr << boost::format("Usage: %1% <port>") % argv[0] << std::endl;
		return 0;
	}

	using topology = boost::square_topology<std::mt19937>;
	using graph_t = boost::adjacency_list<
			  boost::vecS, boost::vecS, boost::directedS
			, boost::property<vertex_position_t, topology::point_type>
	>;

	auto graph = small_world_graph<graph_t>(15);

	layout(graph, get(vertex_position, graph), 300);

	namespace ip = boost::asio::ip;
	boost::asio::io_service io_service{};
	auto acceptor = ip::tcp::acceptor{
		io_service, {ip::address::from_string("127.0.0.1"), std::uint16_t(std::stoi(argv[1]))}
	};
	auto socket = ip::tcp::socket{io_service};

	acceptor.accept(socket);

	boost::breadth_first_search(graph, boost::vertex(1, graph)
			, boost::visitor(make_mygraph_visitor<boost::default_bfs_visitor>(
					socket, get(boost::vertex_index, graph), get(vertex_position, graph))));
}