Interfacing with C++: Minimum Spanning Tree

You can see this app running online at: Minimum Spanning Tree

What this app does:

  • Generates a minimum spanning tree, using Kruskal’s algorithm, for a given road network.
  • The input is a road network, described using intersections and their adjacent roads.
  • The output is a minimum spanning tree based on road length.

This app aims to demonstrate:

  • Integrating Tropofy with C++

Setup Instructions

Use the app name 'tropofy_spanning_tree' to quickstart as in Running and Debugging Tropofy Apps

More detailed installation instructions can be found at Compiling C++ Python Extensions.

Full Source

"""
Author:      www.tropofy.com

Copyright 2015 Tropofy Pty Ltd, all rights reserved.

This source file is part of Tropofy and governed by the Tropofy terms of service
available at: http://www.tropofy.com/terms_of_service.html

This source file is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE. See the license files for details.
"""

import pkg_resources
from math import radians, cos, sin, asin, sqrt
from sqlalchemy.types import Float, Boolean, Text
from sqlalchemy.schema import Column, ForeignKeyConstraint, UniqueConstraint
from sqlalchemy.orm import relationship
from simplekml import Kml, Style, IconStyle, Icon, LineStyle

from tropofy.app import AppWithDataSets, Step, StepGroup
from tropofy.widgets import ExecuteFunction, SimpleGrid, KMLMap
from tropofy.database.tropofy_orm import DataSetMixin
from tropofy.file_io import read_write_xl

import exmod


class Intersection(DataSetMixin):
    name = Column(Text, nullable=False)
    latitude = Column(Float, nullable=False)
    longitude = Column(Float, nullable=False)

    def __init__(self, name, latitude, longitude):
        self.name = name
        self.latitude = latitude
        self.longitude = longitude

    @classmethod
    def get_table_args(cls):
        return (UniqueConstraint('data_set_id', 'name'),)


class Road(DataSetMixin):
    start_name = Column(Text, nullable=False)
    end_name = Column(Text, nullable=False)
    spanning_tree = Column(Boolean, nullable=True)

    start_intersection = relationship(Intersection, foreign_keys=[start_name])
    end_intersection = relationship(Intersection, foreign_keys=[end_name])

    def __init__(self, start_name, end_name, spanning_tree):
        self.start_name = start_name
        self.end_name = end_name
        self.spanning_tree = spanning_tree

    @classmethod
    def get_table_args(cls):
        return (
            UniqueConstraint('data_set_id', 'start_name', 'end_name'),
            ForeignKeyConstraint(['start_name', 'data_set_id'], ['intersection.name', 'intersection.data_set_id'], ondelete='CASCADE', onupdate='CASCADE'),
            ForeignKeyConstraint(['end_name', 'data_set_id'], ['intersection.name', 'intersection.data_set_id'], ondelete='CASCADE', onupdate='CASCADE')
        )


class IntersectionKMLMap(KMLMap):
    def get_kml(self, app_session):
        kml = Kml()

        def LongLat(l):
            return (l.longitude, l.latitude)

        mylocstyle = Style(iconstyle=IconStyle(scale=0.1, icon=Icon(href='https://maps.google.com/mapfiles/kml/paddle/blu-circle-lv.png')))
        LocsFolder = kml.newfolder(name="Intersections")
        for p in [LocsFolder.newpoint(name=str(loc.name), coords=[LongLat(loc)]) for loc in app_session.data_set.query(Intersection).all()]:
            p.style = mylocstyle

        return kml.kml()


class RoadKMLMap(KMLMap):
    def get_kml(self, app_session):
        kml = Kml()

        def LongLat(l):
            return (l.longitude, l.latitude)

        mylocstyle = Style(iconstyle=IconStyle(scale=0.1, icon=Icon(href='https://maps.google.com/mapfiles/kml/paddle/blu-circle-lv.png')))
        LocsFolder = kml.newfolder(name="Locations")
        for p in [LocsFolder.newpoint(name=str(loc.name), coords=[LongLat(loc)]) for loc in app_session.data_set.query(Intersection).all()]:
            p.style = mylocstyle

        mylinestyle = Style(linestyle=LineStyle(color='FF7171C6', width=4))
        LinesFolder = kml.newfolder(name="Lines")
        for line in [LinesFolder.newlinestring(name='line', coords=[LongLat(l.start_intersection), LongLat(l.end_intersection)]) for l in app_session.data_set.query(Road).all()]:
            line.style = mylinestyle

        return kml.kml()


class SpanningTreeKMLMap(KMLMap):
    def get_kml(self, app_session):
        kml = Kml()

        def LongLat(l):
            return (l.longitude, l.latitude)

        mylocstyle = Style(iconstyle=IconStyle(scale=0.1, icon=Icon(href='https://maps.google.com/mapfiles/kml/paddle/blu-circle-lv.png')))
        LocsFolder = kml.newfolder(name="Locations")
        for p in [LocsFolder.newpoint(name=str(loc.name), coords=[LongLat(loc)]) for loc in app_session.data_set.query(Intersection).all()]:
            p.style = mylocstyle

        mylinestyle = Style(linestyle=LineStyle(color='FF7171C6', width=4))
        LinesFolder = kml.newfolder(name="Lines")
        for line in [LinesFolder.newlinestring(name='line', coords=[LongLat(l.start_intersection), LongLat(l.end_intersection)]) for l in app_session.data_set.query(Road).filter(Road.spanning_tree == True)]:
            line.style = mylinestyle

        return kml.kml()

def haversine(lon1, lat1, lon2, lat2):
    lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2])
    dlon = lon2 - lon1
    dlat = lat2 - lat1
    a = sin(dlat / 2) ** 2 + cos(lat1) * cos(lat2) * sin(dlon / 2) ** 2
    c = 2 * asin(sqrt(a))
    km = 6367 * c
    return km


class ExecuteSolverFunction(ExecuteFunction):

    execution_data_set = None  # Warning! This will not work for concurrent users.

    def get_button_text(self, app_session):
        return "Find Spanning Tree"

    def execute_function(self, app_session):
        ExecuteSolverFunction.execution_data_set = app_session.data_set
        exmod.callback(self.add_road_to_spanning_tree)

        app_session.task_manager.send_progress_message("Start Kruskals Algorithm")

        arcs = app_session.data_set.query(Road).all()
        nodes = app_session.data_set.query(Intersection).all()

        for road in arcs:
            start_intersection = road.start_intersection
            end_intersection = road.end_intersection
            distance = haversine(start_intersection.longitude, start_intersection.latitude, end_intersection.longitude, end_intersection.latitude)
            exmod.add_edge(distance, str(road.start_name), str(road.end_name))

        app_session.task_manager.send_progress_message("Network Statistics")
        app_session.task_manager.send_progress_message("Arcs: " + str(len(arcs)))
        app_session.task_manager.send_progress_message("Nodes: " + str(len(nodes)))

        exmod.solve_kruskal()
        
        app_session.task_manager.send_progress_message("Finish Kruskals Algorithm")


    def add_road_to_spanning_tree(self, start_name, end_name):
        road = ExecuteSolverFunction.execution_data_set.query(Road).filter_by(start_name=start_name, end_name=end_name).one()
        road.spanning_tree = True


class SpanningTreeApp(AppWithDataSets):

    def get_name(self):
        return "Minimum Spanning Tree"

    def get_examples(self):
        return {"Data for Brisbane": self.load_example_data_for_brisbane}

    def get_static_content_path(self, app_session):
        return pkg_resources.resource_filename('te_spanning_tree', 'static')

    def get_gui(self):
        step_group1 = StepGroup(name='Input')
        step_group1.add_step(Step(
            name='Intersections',
            widgets=[
                SimpleGrid(Intersection),
                IntersectionKMLMap()
            ]
        ))
        
        step_group1.add_step(Step(
            name='Roads',
            widgets=[
                SimpleGrid(Road),
                RoadKMLMap(),
            ]
        ))

        step_group2 = StepGroup(name='Engine')
        step_group2.add_step(Step(name='Optimise', widgets=[ExecuteSolverFunction()]))

        step_group3 = StepGroup(name='Output')
        step_group3.add_step(Step(name='Minimum Spanning Tree', widgets=[SpanningTreeKMLMap()]))

        return [step_group1, step_group2, step_group3]

    @staticmethod
    def load_example_data_for_brisbane(app_session):
        read_write_xl.ExcelReader.load_data_from_excel_file_on_disk(
            app_session,
            pkg_resources.resource_filename('te_spanning_tree', 'spanning_tree_example_data.xlsx')
        )

    def get_icon_url(self):
        return "/{}/static/{}/spanning_tree.png".format(
            self.url_name,
            self.get_app_version()
        )

C++ File

#include <Python.h>
#include <exception>
#include <algorithm>
#include <vector>
#include <map>
#include <string>

#define CEdge std::pair<std::string, std::string>

static PyObject* exmodError = NULL;
static PyObject* exmodCallback = NULL;

std::vector<std::pair<double, CEdge > > graph;
std::vector<std::pair<double, CEdge > > min_span_tree;
std::map<std::string, std::string> parent;

static std::string find_set(std::string x)
{
    if(x != parent[x])
    {
        parent[x] = find_set(parent[x]);
    }
    return parent[x];
}

static void kruskal()
{
    sort(graph.begin(), graph.end());

    for(int i = 0; i < (int)graph.size(); i++)
    {
        std::string pu = find_set(graph[i].second.first);
        std::string pv = find_set(graph[i].second.second);
		if (pu.compare(pv) != 0)
        {
            min_span_tree.push_back(graph[i]);
            parent[pu] = parent[pv];
        }
    }
}

static PyObject* exmod_solve_kruskal(PyObject* self, PyObject *args)
{
	kruskal();

    for(int i = 0; i < (int)min_span_tree.size(); i++)
    {
		PyObject* arglist = Py_BuildValue("(ss)", min_span_tree[i].second.first.c_str(),
											min_span_tree[i].second.second.c_str());

		PyObject* result = PyObject_CallObject(exmodCallback, arglist);

		Py_DECREF(arglist);
		if (result == NULL)
		{
			return NULL;
		}
		Py_DECREF(result);
    }

	return Py_None;
}

static PyObject* exmod_add_edge(PyObject* self, PyObject* args)
{
    PyObject* result = NULL;
	const char* orig = NULL;
	const char* dest = NULL;
	const double weight = 0.0;

	if(PyArg_ParseTuple(args, "dss", &weight, &orig, &dest))
	{
		parent[orig] = orig;
		parent[dest] = dest;
		graph.push_back(std::pair<double, CEdge >(weight, CEdge(orig, dest)));
		result = Py_None;
	}

	return result;
}

static PyObject* exmod_callback(PyObject *dummy, PyObject *args)
{
    PyObject* result = NULL;
    PyObject* temp;

    if (PyArg_ParseTuple(args, "O:set_callback", &temp)) {
        if (!PyCallable_Check(temp))
        {
            PyErr_SetString(PyExc_TypeError, "parameter must be callable");
            return NULL;
        }

        Py_XINCREF(temp);
        Py_XDECREF(exmodCallback);
        exmodCallback = temp;
        Py_INCREF(Py_None);
        result = Py_None;
    }

    return result;
}

static PyMethodDef exmod_methods[] = {
	{"solve_kruskal",	exmod_solve_kruskal,	METH_VARARGS,	"Say hello from C and print message"},
	{"add_edge",		exmod_add_edge,			METH_VARARGS,	"Add two number in C"},
	{"callback",		exmod_callback,			METH_VARARGS,	"Register the callback function with exmod"},
	{NULL,				NULL,					0,				NULL}
};

PyMODINIT_FUNC initexmod(void)
{
	PyObject* m = NULL;
	m = Py_InitModule("exmod", exmod_methods);
	if (m == NULL)
	{
		return;
	}

	exmodError = PyErr_NewException("exmod.error", NULL, NULL);
	Py_INCREF(exmodError);

	PyModule_AddObject(m, "error", exmodError);
}