from unittest import TestCase

import numpy as np
import time
import math
from numpy.testing import assert_allclose

try:
    from nose.tools import assert_count_equal, assert_equal
except ImportError:
    from nose.tools import assert_items_equal as assert_count_equal

import networkx as nx
from networkx.algorithms.shortest_paths.weighted import witness_matrix, path, minimum_weight_triangle, \
    minimum_weight_path


class TestPreprocessingAlgorithm(TestCase):

    # data.conference.small.small.includesprofit.txt
    # nodelist=['bitfinex_omg', 'bitfinex_eth', 'bittrex_gno', 'poloniex_emc2', 'bitfinex_eur', 'bittrex_gnt', 'poloniex_xpm', 'bitflyer_bch', 'bittrex_rep', 'poloniex_bcn', 'qryptos_zec', 'cexio_btc', 'bitstamp_ltc', 'qryptos_xrp', 'gdax_usd', 'quoine_aud', 'bitfinex_gnt', 'poloniex_rep', 'poloniex_maid', 'poloniex_btm', 'bitsquare_usd', 'bitfinex_edo', 'poloniex_cvc', 'bithumb_bch', 'poloniex_bcy', 'poloniex_xcp', 'poloniex_burst', 'poloniex_nxt', 'bitfinex_ltc', 'quoine_eth', 'poloniex_pot', 'poloniex_vrc', 'bitfinex_zrx', 'bittrex_strat', 'bitsquare_eur', 'quoine_eur', 'poloniex_xmr', 'quadriga_usd', 'bittrex_vox', 'btce_nmc', 'bitfinex_bat', 'poloniex_omni', 'kraken_btc', 'bitfinex_xmr', 'luno_zar', 'kraken_eur', 'qryptos_xmr', 'kraken_dash', 'btce_bch', 'qryptos_btc', 'bitstamp_xrp', 'kraken_ltc', 'gdax_ltc', 'gemini_btc', 'poloniex_strat', 'bittrex_xem', 'poloniex_dash', 'bittrex_xrp', 'bittrex_eth', 'bithumb_etc', 'bithumb_ltc', 'poloniex_sc', 'gdax_gbp', 'kraken_xmr', 'kraken_rep', 'poloniex_xem', 'quoine_php', 'quoine_jpy', 'poloniex_pasc', 'bithumb_zec', 'bitflyer_usd', 'bitfinex_rep', 'bitsquare_ltc', 'bitfinex_btg', 'bitsquare_eth', 'poloniex_fldc', 'poloniex_btcd', 'bitfinex_das', 'poloniex_nav', 'kraken_zec', 'okcoin_usd', 'bittrex_vrm', 'bithumb_dash', 'kraken_usdt', 'cexio_eur', 'bitfinex_tnb', 'kraken_etc', 'bithumb_xmr', 'bithumb_eth', 'bittrex_edg', 'quadriga_btg', 'poloniex_pink', 'poloniex_storj', 'luno_btc', 'poloniex_ric', 'poloniex_zrx', 'quoine_sgd', 'kraken_usd', 'poloniex_ppc', 'bitflyer_eth', 'bithumb_qtum', 'bittrex_qtum', 'bitfinex_xrp', 'bittrex_xvg', 'kraken_xrp', 'kraken_icn', 'bitfinex_trx', 'kraken_mln', 'bitfinex_qtum', 'bitsquare_btc', 'gemini_usd', 'cexio_bch', 'poloniex_zec', 'poloniex_nmc', 'kraken_gbp', 'bitfinex_avt', 'bittrex_fun', 'bittrex_ada', 'btce_eth', 'bittrex_xmr', 'cexio_xrp', 'kraken_jpy', 'bittrex_dcr', 'bitfinex_snt', 'cexio_eth', 'poloniex_bch', 'poloniex_gno', 'qryptos_eth', 'bitfinex_usd', 'bithumb_eos', 'quadriga_eth', 'poloniex_ardr', 'bitfinex_zec', 'poloniex_huc', 'poloniex_gas', 'bitfinex_neo', 'bittrex_bcc', 'bittrex_btg', 'bitfinex_btc', 'quoine_hkd', 'poloniex_gnt', 'poloniex_bts', 'bitfinex_rcn', 'quoine_idr', 'poloniex_steem', 'poloniex_nxc', 'bitstamp_bch', 'poloniex_btc', 'poloniex_dcr', 'gdax_eur', 'poloniex_lbc', 'gdax_btc', 'bittrex_dash', 'bithumb_btc', 'btce_ltc', 'bitfinex_eos', 'poloniex_etc', 'bitfinex_iot', 'poloniex_sys', 'bittrex_omg', 'btce_eur', 'bittrex_sc', 'quoine_usd', 'bitstamp_eur', 'quadriga_cad', 'poloniex_xbc', 'kraken_eos', 'bittrex_btc', 'poloniex_ltc', 'poloniex_eth', 'poloniex_game', 'bittrex_vtc', 'bitstamp_usd', 'kraken_bch', 'qryptos_etc', 'bittrex_ltc', 'poloniex_amp', 'bitfinex_san', 'bitfinex_elf', 'poloniex_omg', 'kraken_gno', 'kraken_str', 'poloniex_dgb', 'gdax_bch', 'poloniex_vtc', 'cexio_usd', 'btce_usd', 'btce_zec', 'poloniex_neos', 'kraken_eth', 'bittrex_bat', 'bitflyer_btc', 'poloniex_fct', 'quoine_btc', 'bitfinex_husd', 'okcoin_btc', 'qryptos_ltc', 'bitstamp_btc', 'bittrex_neo', 'bittrex_etc', 'bitfinex_fun', 'bitfinex_dat', 'bittrex_usdt', 'bittrex_snt', 'poloniex_xvc', 'poloniex_str', 'bittrex_mln', 'bitfinex_hbtc', 'poloniex_blk', 'poloniex_lsk', 'kraken_cad', 'okcoin_ltc', 'qryptos_rep', 'poloniex_via', 'btce_ppc', 'bithumb_krw', 'quadriga_ltc', 'bithumb_btg', 'bittrex_blk', 'poloniex_bela', 'bitfinex_etp', 'quadriga_btc', 'bithumb_xrp', 'bitstamp_eth', 'bitfinex_etc', 'poloniex_flo', 'bitfinex_bch', 'quoine_bch', 'poloniex_exp', 'poloniex_xrp', 'gemini_eth', 'poloniex_clam', 'poloniex_rads', 'bittrex_zec', 'bittrex_zen', 'poloniex_grc', 'gdax_eth', 'poloniex_usdt', 'bittrex_vrc', 'quadriga_bch', 'btce_rur', 'poloniex_sbd', 'btce_btc']

    # data.conference.small.small.txt
    # nodelist=['bitfinex_husd', 'kraken_zec', 'quoine_jpy', 'bithumb_eos', 'poloniex_grc', 'bittrex_neo', 'bittrex_ada', 'bitfinex_btg', 'bitfinex_edo', 'bithumb_xrp', 'bittrex_vtc', 'bitfinex_rep', 'bittrex_gnt', 'poloniex_bts', 'kraken_xrp', 'quoine_hkd', 'quadriga_eth', 'bitfinex_ltc', 'kraken_gbp', 'poloniex_steem', 'bitsquare_eur', 'poloniex_emc2', 'poloniex_bcn', 'bitfinex_tnb', 'poloniex_usdt', 'bitfinex_rcn', 'btce_usd', 'bittrex_fun', 'cexio_bch', 'bitfinex_omg', 'bitfinex_xrp', 'bithumb_qtum', 'bitstamp_eth', 'btce_btc', 'poloniex_exp', 'kraken_gno', 'gemini_btc', 'poloniex_zrx', 'cexio_btc', 'bithumb_eth', 'quoine_btc', 'kraken_usdt', 'bittrex_btg', 'poloniex_ltc', 'poloniex_xem', 'bittrex_qtum', 'kraken_btc', 'bithumb_xmr', 'bittrex_zen', 'bithumb_dash', 'bitsquare_ltc', 'poloniex_burst', 'qryptos_btc', 'bittrex_mln', 'kraken_bch', 'bittrex_vrm', 'poloniex_btc', 'poloniex_vrc', 'poloniex_bch', 'bitstamp_ltc', 'okcoin_usd', 'luno_btc', 'poloniex_xbc', 'quadriga_btg', 'quoine_bch', 'poloniex_maid', 'poloniex_eth', 'bitfinex_etc', 'okcoin_btc', 'bittrex_btc', 'bitstamp_xrp', 'bitflyer_usd', 'gdax_gbp', 'kraken_dash', 'kraken_cad', 'kraken_icn', 'poloniex_gno', 'poloniex_str', 'poloniex_xvc', 'poloniex_strat', 'poloniex_zec', 'poloniex_omni', 'quoine_eur', 'poloniex_bela', 'bitfinex_bch', 'kraken_jpy', 'bitsquare_btc', 'bittrex_ltc', 'quadriga_cad', 'quadriga_usd', 'bittrex_zec', 'bitflyer_btc', 'bittrex_xrp', 'qryptos_eth', 'gdax_eth', 'poloniex_xrp', 'cexio_xrp', 'poloniex_sys', 'poloniex_flo', 'bittrex_eth', 'poloniex_xpm', 'bittrex_blk', 'poloniex_etc', 'bitfinex_zec', 'poloniex_amp', 'bitfinex_das', 'poloniex_nxc', 'quadriga_bch', 'bitfinex_hbtc', 'bittrex_usdt', 'poloniex_xmr', 'gdax_ltc', 'bittrex_strat', 'kraken_ltc', 'bitfinex_avt', 'quadriga_btc', 'poloniex_btcd', 'quoine_eth', 'gdax_btc', 'bitfinex_eos', 'bitstamp_btc', 'cexio_eth', 'bittrex_dash', 'poloniex_vtc', 'poloniex_fct', 'poloniex_rep', 'bittrex_xvg', 'gdax_bch', 'bittrex_edg', 'bitfinex_trx', 'qryptos_etc', 'bittrex_rep', 'qryptos_ltc', 'qryptos_xmr', 'bithumb_etc', 'bitfinex_snt', 'bitstamp_bch', 'poloniex_omg', 'kraken_eur', 'bitfinex_eth', 'bitfinex_etp', 'kraken_str', 'bittrex_vrc', 'quoine_php', 'bithumb_btg', 'poloniex_lbc', 'poloniex_nxt', 'bitfinex_gnt', 'bitfinex_iot', 'btce_eur', 'poloniex_game', 'poloniex_lsk', 'poloniex_storj', 'quoine_aud', 'bithumb_ltc', 'bitfinex_fun', 'okcoin_ltc', 'kraken_etc', 'bitsquare_usd', 'poloniex_via', 'poloniex_sbd', 'poloniex_nav', 'poloniex_xcp', 'poloniex_neos', 'poloniex_btm', 'gemini_usd', 'kraken_rep', 'bitflyer_eth', 'bittrex_xmr', 'quoine_idr', 'poloniex_fldc', 'poloniex_bcy', 'bitfinex_dat', 'qryptos_zec', 'poloniex_pot', 'kraken_mln', 'bitfinex_btc', 'quoine_sgd', 'qryptos_rep', 'poloniex_pasc', 'poloniex_dcr', 'poloniex_blk', 'kraken_eth', 'bitfinex_zrx', 'bittrex_gno', 'bitstamp_eur', 'bittrex_dcr', 'poloniex_ardr', 'quadriga_ltc', 'poloniex_dgb', 'poloniex_gas', 'cexio_eur', 'kraken_xmr', 'kraken_eos', 'poloniex_ppc', 'poloniex_clam', 'bitfinex_usd', 'bitflyer_bch', 'btce_ppc', 'bithumb_zec', 'poloniex_ric', 'bittrex_snt', 'btce_nmc', 'bitstamp_usd', 'poloniex_sc', 'bittrex_bcc', 'bittrex_bat', 'bitfinex_san', 'bittrex_omg', 'btce_ltc', 'cexio_usd', 'btce_eth', 'bithumb_krw', 'quoine_usd', 'poloniex_gnt', 'gemini_eth', 'gdax_eur', 'btce_bch', 'bitfinex_xmr', 'bitfinex_bat', 'bitfinex_elf', 'bitfinex_qtum', 'gdax_usd', 'bitfinex_neo', 'poloniex_pink', 'luno_zar', 'poloniex_nmc', 'poloniex_huc', 'bittrex_xem', 'poloniex_cvc', 'qryptos_xrp', 'bithumb_btc', 'bitfinex_eur', 'bitsquare_eth', 'btce_zec', 'poloniex_dash', 'bittrex_etc', 'btce_rur', 'bittrex_sc', 'bittrex_vox', 'poloniex_rads', 'bithumb_bch', 'kraken_usd']
    # data.sorted.txt
    # nodelist=['bittrex_agrs', 'coinone_xrp', 'bittrex_dope', 'bittrex_mana', 'bittrex_brk', 'poloniex_huc', 'bitfinex_bch', 'gdax_eth', 'bittrex_pdc', 'bittrex_sngls', 'poloniex_nxc', 'binance_qtum', 'poloniex_usdt', 'bittrex_swift', 'bittrex_neos', 'bittrex_exp', 'poloniex_clam', 'binance_oax', 'bittrex_steem', 'hitbtc_ltc', 'poloniex_ardr', 'bittrex_amp', 'okcoin_usd', 'poloniex_nxt', 'korbit_bch', 'gemini_eth', 'bittrex_part', 'bittrex_gbyte', 'bithumb_btg', 'bittrex_nmr', 'korbit_xrp', 'bittrex_bcy', 'bittrex_bcc', 'bittrex_trig', 'poloniex_xmr', 'hitbtc_ver', 'bittrex_ubq', 'bittrex_dmd', 'bittrex_sphr', 'bithumb_eth', 'bittrex_xmr', 'bittrex_snt', 'poloniex_dgb', 'bittrex_nxt', 'bitfinex_qtum', 'bittrex_safex', 'bittrex_adt', 'poloniex_pink', 'bittrex_vrm', 'korbit_btc', 'bittrex_vtr', 'huobipro_bcc', 'poloniex_cvc', 'poloniex_xbc', 'poloniex_exp', 'poloniex_sys', 'bittrex_tix', 'bittrex_gld', 'okcoin_etc', 'bittrex_nav', 'poloniex_sbd', 'poloniex_xpm', 'bittrex_vox', 'binance_neo', 'bittrex_ardr', 'bittrex_lgd', 'bittrex_omni', 'bittrex_cfi', 'bittrex_block', 'poloniex_xrp', 'bittrex_rads', 'poloniex_dcr', 'bitfinex_btg', 'poloniex_lbc', 'bittrex_neo', 'poloniex_steem', 'bittrex_lun', 'bittrex_sc', 'bittrex_hmq', 'bitfinex_omg', 'bittrex_lsk', 'bittrex_xcp', 'poloniex_omni', 'binance_bnb', 'poloniex_zec', 'bittrex_1st', 'bittrex_nbt', 'bittrex_xst', 'coinone_qtum', 'bittrex_xmg', 'binance_etc', 'bittrex_myst', 'bitfinex_usd', 'bittrex_xlm', 'poloniex_flo', 'bittrex_dyn', 'bittrex_tks', 'bittrex_xaur', 'bittrex_vrc', 'bittrex_apx', 'huobipro_etc', 'bittrex_omg', 'bittrex_via', 'bittrex_kore', 'korbit_eth', 'bittrex_emc', 'poloniex_rep', 'poloniex_vtc', 'bittrex_etc', 'poloniex_emc2', 'bittrex_gcr', 'poloniex_str', 'bitfinex_neo', 'okcoin_ltc', 'bittrex_seq', 'bittrex_mona', 'gdax_ltc', 'hitbtc_eth', 'gdax_gbp', 'huobipro_btc', 'bittrex_edg', 'okcoin_bch', 'bittrex_lmc', 'bittrex_ptc', 'bithumb_xrp', 'bittrex_waves', 'bittrex_incnt', 'bittrex_gup', 'hitbtc_das', 'poloniex_gnt', 'bittrex_rlc', 'bittrex_brx', 'bittrex_flo', 'bittrex_rep', 'poloniex_bcy', 'poloniex_rads', 'bittrex_dtb', 'poloniex_maid', 'hitbtc_adx', 'bithumb_ltc', 'bittrex_kmd', 'bittrex_thc', 'bithumb_etc', 'poloniex_bts', 'poloniex_storj', 'hitbtc_ppc', 'bittrex_xem', 'bittrex_trust', 'bittrex_ebst', 'gemini_usd', 'bittrex_fair', 'bittrex_cvc', 'poloniex_etc', 'korbit_krw', 'bitfinex_xmr', 'bittrex_nlg', 'bittrex_vib', 'poloniex_nav', 'hitbtc_snt', 'bittrex_wings', 'bittrex_mue', 'poloniex_gno', 'bittrex_sls', 'bittrex_nxs', 'bittrex_egc', 'bitfinex_avt', 'poloniex_bcn', 'bittrex_qrl', 'bittrex_powr', 'bittrex_clam', 'gdax_eur', 'bittrex_pkb', 'bittrex_dnt', 'poloniex_btcd', 'bittrex_bat', 'poloniex_amp', 'bittrex_ioc', 'bittrex_mtl', 'hitbtc_zrx', 'poloniex_fct', 'bittrex_gbg', 'bittrex_start', 'bithumb_xmr', 'bittrex_excl', 'poloniex_blk', 'bittrex_blk', 'bittrex_zcl', 'bitfinex_eos', 'bittrex_usdt', 'bittrex_zen', 'bittrex_music', 'bittrex_grs', 'poloniex_pasc', 'hitbtc_usdt', 'binance_eth', 'hitbtc_xmr', 'hitbtc_bch', 'bittrex_infx', 'poloniex_fldc', 'binance_btc', 'bittrex_rise', 'bittrex_fct', 'bitfinex_zec', 'bittrex_btc', 'bittrex_efl', 'bittrex_aeon', 'poloniex_eth', 'bithumb_krw', 'gemini_btc', 'okcoin_eth', 'bittrex_sbd', 'hitbtc_qtu', 'bittrex_ada', 'bittrex_rcn', 'bittrex_xzc', 'poloniex_lsk', 'bittrex_dgd', 'poloniex_bch', 'bittrex_cloak', 'bithumb_qtum', 'bittrex_aur', 'poloniex_via', 'bitfinex_btc', 'bittrex_iop', 'bittrex_sib', 'poloniex_sc', 'poloniex_vrc', 'coinone_btc', 'bittrex_mer', 'bittrex_btcd', 'bittrex_xvc', 'bittrex_ok', 'bittrex_meme', 'huobipro_ltc', 'hitbtc_emg', 'gdax_btc', 'bittrex_zec', 'bittrex_ion', 'bittrex_grc', 'bittrex_ptoy', 'bittrex_shift', 'bittrex_erc', 'coinone_bch', 'bitfinex_ltc', 'coinone_eth', 'bittrex_dash', 'bittrex_xwc', 'bittrex_strat', 'bittrex_bsd', 'hitbtc_btc', 'poloniex_dash', 'poloniex_doge', 'bitfinex_iota', 'bittrex_maid', 'bittrex_snrg', 'bittrex_byc', 'hitbtc_xrp', 'hitbtc_cnd', 'poloniex_xcp', 'poloniex_nmc', 'poloniex_grc', 'coinone_ltc', 'bittrex_geo', 'hitbtc_tbtc', 'bittrex_sys', 'bithumb_bch', 'poloniex_omg', 'poloniex_btm', 'bittrex_pink', 'bitfinex_eth', 'bittrex_rby', 'bittrex_mln', 'bittrex_dct', 'bittrex_ant', 'bittrex_ftc', 'bithumb_dash', 'bittrex_fldc', 'hitbtc_zec', 'poloniex_xvc', 'bitfinex_edo', 'bittrex_nxc', 'bittrex_bay', 'poloniex_strat', 'poloniex_ppc', 'bitfinex_xrp', 'bittrex_crw', 'bittrex_trst', 'poloniex_btc', 'bittrex_salt', 'bitfinex_dash', 'poloniex_game', 'bithumb_btc', 'bittrex_synx', 'okcoin_btc', 'bittrex_cure', 'poloniex_burst', 'bittrex_lbc', 'bittrex_slr', 'bittrex_vtc', 'bittrex_club', 'bittrex_ark', 'bithumb_zec', 'bittrex_pivx', 'bittrex_gnt', 'bittrex_xel', 'bittrex_gno', 'hitbtc_str', 'bittrex_dgb', 'binance_hsr', 'poloniex_bela', 'poloniex_xem', 'bittrex_tx', 'bittrex_gam', 'korbit_etc', 'bittrex_unb', 'huobipro_eth', 'binance_ltc', 'poloniex_pot', 'bittrex_enrg', 'coinone_krw', 'poloniex_neos', 'bittrex_storj', 'bittrex_eng', 'bittrex_swt', 'bittrex_emc2', 'binance_dnt', 'bitfinex_san', 'gdax_usd', 'bittrex_xrp', 'bitfinex_etc', 'bittrex_ltc', 'bittrex_qwark', 'bitfinex_etp', 'bittrex_mco', 'bittrex_game', 'binance_gas', 'bittrex_golos', 'bittrex_qtum', 'hitbtc_dic', 'bittrex_pot', 'bittrex_spr', 'coinone_etc', 'bittrex_ppc', 'bittrex_dcr', 'poloniex_ric', 'bittrex_pay', 'bittrex_btg', 'bittrex_cpc', 'bittrex_adx', 'poloniex_zrx', 'bittrex_cann', 'poloniex_ltc', 'bittrex_bnt', 'bittrex_fun', 'bittrex_eth', 'bittrex_blitz', 'bittrex_crb', 'poloniex_gas']
    nodelist = ['bitfinex_avt', 'bitfinex_btc', 'bitfinex_eth', 'bitfinex_usd', 'bitfinex_eur', 'bitfinex_bat', 'bitfinex_bch', 'bitfinex_btg', 'bitfinex_dat', 'bitfinex_edo', 'bitfinex_elf', 'bitfinex_eos', 'bitfinex_etc', 'bitfinex_etp', 'bitfinex_fun', 'bitfinex_gnt', 'bitfinex_iot', 'bitfinex_ltc', 'bitfinex_neo', 'bitfinex_omg', 'bitfinex_qtum', 'bitfinex_rcn', 'bitfinex_rep', 'bitfinex_san', 'bitfinex_snt', 'bitfinex_tnb', 'bitfinex_trx', 'bitfinex_xmr', 'bitfinex_xrp', 'bitfinex_zec', 'bitfinex_zrx', 'bitflyer_btc', 'bitsquare_btc', 'bitstamp_btc', 'bittrex_btc', 'btce_btc', 'cexio_btc', 'gdax_btc', 'gemini_btc', 'kraken_btc', 'okcoin_btc', 'poloniex_btc', 'qryptos_btc', 'quadriga_btc', 'quoine_btc', 'bitflyer_eth', 'bitsquare_eth', 'bitstamp_eth', 'bittrex_eth', 'btce_eth', 'cexio_eth', 'gdax_eth', 'gemini_eth', 'kraken_eth', 'poloniex_eth', 'qryptos_eth', 'quoine_eth', 'bitflyer_usd', 'bitsquare_usd', 'bitstamp_usd', 'btce_usd', 'cexio_usd', 'gdax_usd', 'gemini_usd', 'kraken_usd', 'okcoin_usd', 'quadriga_usd', 'quoine_usd', 'bitflyer_eur', 'bitsquare_eur', 'bitstamp_eur', 'btce_eur', 'cexio_eur', 'gdax_eur', 'kraken_eur', 'quoine_eur', 'bittrex_bat', 'bitflyer_bch', 'bitstamp_bch', 'btce_bch', 'cexio_bch', 'gdax_bch', 'kraken_bch', 'poloniex_bch', 'quadriga_bch', 'quoine_bch', 'bittrex_btg', 'quadriga_btg', 'bitfinex_das', 'bitfinex_hbtc', 'bitfinex_husd', 'kraken_eos', 'bittrex_etc', 'kraken_etc', 'poloniex_etc', 'qryptos_etc', 'bittrex_fun', 'bittrex_gnt', 'poloniex_gnt', 'bitsquare_ltc', 'bitstamp_ltc', 'bittrex_ltc', 'btce_ltc', 'gdax_ltc', 'kraken_ltc', 'okcoin_ltc', 'poloniex_ltc', 'qryptos_ltc', 'quadriga_ltc', 'bittrex_neo', 'bittrex_omg', 'poloniex_omg', 'bithumb_qtum', 'bittrex_qtum', 'bittrex_rep', 'kraken_rep', 'poloniex_rep', 'qryptos_rep', 'bittrex_snt', 'bittrex_xmr', 'kraken_xmr', 'poloniex_xmr', 'qryptos_xmr', 'bitstamp_xrp', 'bittrex_xrp', 'cexio_xrp', 'kraken_xrp', 'poloniex_xrp', 'qryptos_xrp', 'bittrex_zec', 'btce_zec', 'kraken_zec', 'poloniex_zec', 'qryptos_zec', 'poloniex_zrx', 'bithumb_bch', 'bithumb_krw', 'bithumb_btc', 'bithumb_btg', 'bithumb_eos', 'bithumb_etc', 'bithumb_eth', 'bithumb_ltc', 'bithumb_xmr', 'bithumb_xrp', 'bithumb_zec', 'bithumb_dash', 'bittrex_ada', 'bittrex_usdt', 'bittrex_dash', 'bittrex_bcc', 'bittrex_xvg', 'poloniex_usdt', 'bittrex_blk', 'bittrex_dcr', 'bittrex_edg', 'bittrex_gno', 'bittrex_strat', 'bittrex_sc', 'bittrex_mln', 'bittrex_vox', 'bittrex_vrc', 'bittrex_vrm', 'bittrex_vtc', 'bittrex_xem', 'bittrex_zen', 'kraken_dash', 'poloniex_dash', 'poloniex_blk', 'poloniex_dcr', 'kraken_gno', 'poloniex_gno', 'poloniex_strat', 'poloniex_sc', 'kraken_mln', 'poloniex_vrc', 'poloniex_vtc', 'poloniex_xem', 'btce_rur', 'btce_nmc', 'btce_ppc', 'gdax_gbp', 'kraken_gbp', 'kraken_cad', 'kraken_jpy', 'kraken_icn', 'kraken_str', 'kraken_usdt', 'quadriga_cad', 'quoine_jpy', 'poloniex_str', 'luno_btc', 'luno_zar', 'poloniex_burst', 'poloniex_ardr', 'poloniex_bela', 'poloniex_btcd', 'poloniex_clam', 'poloniex_emc2', 'poloniex_fldc', 'poloniex_game', 'poloniex_amp', 'poloniex_bcy', 'poloniex_btm', 'poloniex_bts', 'poloniex_cvc', 'poloniex_dgb', 'poloniex_exp', 'poloniex_fct', 'poloniex_flo', 'poloniex_gas', 'poloniex_grc', 'poloniex_huc', 'poloniex_lbc', 'poloniex_lsk', 'poloniex_maid', 'poloniex_neos', 'poloniex_omni', 'poloniex_pasc', 'poloniex_pink', 'poloniex_rads', 'poloniex_nxt', 'poloniex_steem', 'poloniex_storj', 'poloniex_nav', 'poloniex_nmc', 'poloniex_nxc', 'poloniex_pot', 'poloniex_ppc', 'poloniex_ric', 'poloniex_sbd', 'poloniex_sys', 'poloniex_via', 'poloniex_xbc', 'poloniex_xcp', 'poloniex_xpm', 'poloniex_xvc', 'poloniex_bcn', 'quadriga_eth', 'quoine_sgd', 'quoine_aud', 'quoine_hkd', 'quoine_idr', 'quoine_php']
    # nodelist = ['kraken_eth', 'gdax_ltc', 'quoine_usd', 'quoine_bch', 'gdax_eur', 'gdax_btc', 'kraken_btc', 'quoine_eth', 'gdax_gbp', 'quoine_btc', 'kraken_etc', 'gdax_usd', 'gdax_bch', 'gdax_eth', 'kraken_ltc', 'kraken_bch', 'kraken_usd']

    def test_witness_matrix(self):
        elist = [('a', 'b', 1), ('b', 'c', 7), ('c', 'e', 2), ('b', 'd', 5), ('d', 'c', 1), ('d', 'e', 5),
                 ('e', 'f', 4), ('f', 'g', 1), ('f', 'h', 2), ('g', 'h', 3), ('h', 'b', 4), ('h', 'a', 3)]

        G = nx.DiGraph()
        G.add_weighted_edges_from(elist)
        i, j, k = minimum_weight_triangle(G, nodelist=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'])
        A = nx.to_numpy_array(G, nodelist=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'])
        A[A == 0] = np.inf
        np.fill_diagonal(A, 0)
        B = A
        W = witness_matrix(A, B)
        p1 = path(A, W, i, j)
        p2 = path(A, W, j, k)
        p3 = path(A, W, k, i)

        print(p1, p2, p3)

    def test_small_min_wt_path(self):
        elist = [('a', 'b', 1), ('b', 'c', 1), ('c', 'd', 2), ('d', 'e', 2), ('e', 'a', 1), ('b', 'd', 5)]
        G = nx.DiGraph()
        G.add_weighted_edges_from(elist)
        path = minimum_weight_path(G, ['a', 'b', 'c', 'd', 'e'])
        assert_equal(path, [0, 1, 2, 3, 4, 0])

    def test_big_min_wt_path(self):
        elist = [('a', 'b', 1), ('b', 'c', 7), ('c', 'e', 2), ('b', 'd', 5), ('d', 'c', 1), ('d', 'e', 5),
                 ('e', 'f', 4), ('f', 'g', 1), ('f', 'h', 2), ('g', 'h', 3), ('h', 'b', 4), ('h', 'a', 3)]

        G = nx.DiGraph()
        G.add_weighted_edges_from(elist)
        path = minimum_weight_path(G, ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'])
        assert_equal(path, [0, 1, 3, 2, 4, 5, 7, 0])

    def test_witness_matrix_small(self):
        elist = [('a', 'b', 1), ('b', 'c', 1), ('c', 'd', 2), ('d', 'e', 2), ('e', 'a', 1), ('b', 'd', 5)]

        G = nx.DiGraph()
        G.add_weighted_edges_from(elist)
        i, j, k = minimum_weight_triangle(G, nodelist=['a', 'b', 'c', 'd', 'e'])
        A = nx.to_numpy_matrix(G, nodelist=['a', 'b', 'c', 'd', 'e'])
        A[A == 0] = np.inf
        np.fill_diagonal(A, 0)
        B = A
        W = witness_matrix(A, B)
        p1 = path(A, W, i, j)
        p2 = path(A, W, j, k)
        p3 = path(A, W, k, i)
        print(p1, p2, p3)


    def test_data_transformation(self):
        start = time.time()
        elist = [('a', 'b', 1), ('b', 'c', 1), ('c', 'd', 1/2), ('d', 'e', 1/10), ('e', 'a', 1), ('b', 'd', 1/5),
                 ('b', 'a', 1), ('c', 'b', 1), ('d', 'c', 2), ('e', 'd', 10), ('a', 'e', 1), ('d', 'b', 5)]

        elist = list(map(lambda x: (x[0], x[1], math.floor(np.log(x[2] * 10) * 1000 + 1)), elist))

        G = nx.DiGraph()
        G.add_weighted_edges_from(elist)
        i, j, k = minimum_weight_triangle(G, nodelist=['a', 'b', 'c', 'd', 'e'])
        A = nx.to_numpy_matrix(G, nodelist=['a', 'b', 'c', 'd', 'e'])
        A[A == 0] = np.inf
        np.fill_diagonal(A, 0)
        B = A
        W = witness_matrix(A, B)
        end = time.time()
        print(end - start)
        p1 = path(W, i, j)
        p2 = path(W, j, k)
        p3 = path(W, k, i)
        print(p1, p2, p3)


    def construct_graph(self):
        def load_data():
            markets = dict()

            with open("../../../data.conference.txt", "r") as data:
                for line in data:
                    pair1, pair2, weight = line.split(",")
                    market1, currency1 = pair1.split("_")
                    currency2 = pair2.split("_")[1]  # remove newline character from the end
                    current_markets = markets.get(market1, dict())
                    currency_1_list = current_markets.get(currency1, [])
                    currency_2_list = current_markets.get(currency2, [])
                    currency_1_list.append(currency2)
                    currency_2_list.append(currency1)
                    current_markets[currency1] = currency_1_list
                    current_markets[currency2] = currency_2_list
                    markets[market1] = current_markets
            return markets

        def add_inter_exchange_edges(G, markets):
            for exchange, currencies in markets.items():
                for from_currency in currencies.keys():
                    add_inter_exchange_edge(G, markets, from_currency, exchange)
            return G

        def add_inter_exchange_edge(G, markets, from_currency, from_exchange):
            for to_exchange, currencies in markets.items():
                if to_exchange == from_exchange:
                    continue
                to_currency = currencies.get(from_currency)
                if not to_currency:
                    continue

                base_currencies = ['btc','eth','usd','ltc','krw','cny']
                from_currency = from_currency.lower()
                inter_exchange_rate = None
                for base_currency in base_currencies:
                    if base_currency == from_currency:
                        continue
                    market_1_rate = G.get_edge_data("{}_{}".format(from_exchange, from_currency), "{}_{}".format(from_exchange, base_currency))
                    market_2_rate = G.get_edge_data("{}_{}".format(to_exchange, from_currency), "{}_{}".format(to_exchange, base_currency))
                    if market_1_rate is not None and market_2_rate is not None:
                        inter_exchange_rate = market_1_rate['weight'] / market_2_rate['weight']
                        break

                if inter_exchange_rate == None:
                    continue
                max_spread = 0.99
                min_spread = 0.99999
                # G.add_edge("{}_{}".format(from_exchange, from_currency.lower()), "{}_{}".format(from_exchange, from_currency.lower()), weight=(1/inter_exchange_rate) * ((min_spread - max_spread) * np.random.random_sample() + max_spread))
                G.add_edge("{}_{}".format(to_exchange, from_currency.lower()), "{}_{}".format(from_exchange, from_currency.lower()), weight=1/0.99999)#(1/inter_exchange_rate) * (1/0.99999))
                G.add_edge("{}_{}".format(from_exchange, from_currency.lower()), "{}_{}".format(to_exchange, from_currency.lower()), weight=1)#inter_exchange_rate)
        raw_graph = nx.read_edgelist("../../../data.conference.txt",
                                     delimiter=",",
                                     create_using=nx.DiGraph(),
                                     data=(('weight', float),))  # type: nx.DiGraph

        # Add nodes to G2, filter inter market edges where 1=btc and 2=btc.

        processed_graph = nx.DiGraph()
        max_spread = 0.99
        min_spread = 0.99999
        for first_node, second_node in raw_graph.edges():
            weight = raw_graph.get_edge_data(first_node, second_node)['weight']
            first_node = first_node.lower()
            second_node = second_node.lower()
            # processed_graph.add_edge(first_node, second_node, weight=(1/weight) * ((1/(min_spread - max_spread)) * np.random.random_sample() + max_spread))
            processed_graph.add_edge(first_node, second_node, weight=(1/weight) * (1/0.99999))
            processed_graph.add_edge(second_node, first_node, weight=weight)

        add_inter_exchange_edges(processed_graph, load_data())

        weights = nx.get_edge_attributes(processed_graph, 'weight')
        min_weight = np.min(list(weights.values()))

        elist = list(processed_graph.edges(data='weight'))
        elist = list(map(lambda x: (x[0], x[1], math.ceil(np.log(x[2] * (1/min_weight)) * 1000000 + 1)), elist))

        G = nx.DiGraph()
        G.add_weighted_edges_from(elist)
        return G, processed_graph


    def window(self, data, win_size):
        tmp = [iter(data[i:]) for i in range(win_size)]
        return zip(*tmp)

    def test_real_data(self):
        G, processed_graph = self.construct_graph()
        path = minimum_weight_path(G, nodelist=self.nodelist)

        weights = nx.get_edge_attributes(processed_graph, 'weight')
        pairs = list(self.window(path, 2))

        formula = ""
        profit = 1
        for elem1, elem2 in pairs:
            if elem1 == elem2:
                continue
            profit *= 1/weights[(self.nodelist[elem1], self.nodelist[elem2])]
            formula += "%s * " % (1/weights[(self.nodelist[elem1], self.nodelist[elem2])])
        formula += " = %s" % profit
        print(formula)
        print(profit)
        print(path)
        print(list(map(lambda x: (self.nodelist[x[0]], self.nodelist[x[1]]), pairs)))
        assert_equal(profit, 1.3)
        assert_equal(path, [1, 2, 3])

    def test_witness_matrix_bak(self):
        G = nx.DiGraph()
        elist = [(1, 2, 5), (2, 3, 4), (3, 1, 1), (3, 4, 7), (4, 5, 5)]
        G.add_weighted_edges_from(elist)
        D = nx.to_numpy_matrix(G)
        D[D == 0] = np.inf
        np.fill_diagonal(D, 0)
        W = witness_matrix(D, D)
        print(W)
        Y = np.array([[0, 1, 1, 1, 1],
                      [2, 1, 2, 2, 2],
                      [0, 0, 2, 3, 3],
                      [np.inf, np.inf, np.inf, 3, 4],
                      [np.inf, np.inf, np.inf, np.inf, 4]])
        assert_allclose(W, Y)

f = TestPreprocessingAlgorithm()
f.test_real_data()