Skip to content

Instantly share code, notes, and snippets.

@amedama41 amedama41/
Created Jun 28, 2014

What would you like to do?
Graph algorithm visualization sample
import Tkinter
import socket
import struct
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect(('', 35555))
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
buf = sock.recv(4 * 8)
except socket.error, (value, msg):
print 'socket.error: ', msg, value
if not buf:
print 'socket closed'
(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)
#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;
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));
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& 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(""), std::uint16_t(std::stoi(argv[1]))}
auto socket = ip::tcp::socket{io_service};
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))));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.