# Source code for dwave_networkx.algorithms.tsp

# Copyright 2018 D-Wave Systems Inc.
#
#    you may not use this file except in compliance with the License.
#    You may obtain a copy of the License at
#
#
#    Unless required by applicable law or agreed to in writing, software
#    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
#    See the License for the specific language governing permissions and
#
# =============================================================================
from __future__ import division

import itertools

from collections import defaultdict

__all__ = ["traveling_salesperson",
"traveling_salesperson_qubo",
"traveling_salesman",
"traveling_salesman_qubo",
"is_hamiltonian_path",
]

def traveling_salesperson(G, sampler=None, lagrange=None, weight='weight',
start=None, **sampler_args):
"""Returns an approximate minimum traveling salesperson route.

Defines a QUBO with ground states corresponding to the
minimum routes and uses the sampler to sample
from it.

A route is a cycle in the graph that reaches each node exactly once.
A minimum route is a route with the smallest total edge weight.

Parameters
----------
G : NetworkX graph
The graph on which to find a minimum traveling salesperson route.
This should be a complete graph with non-zero weights on every edge.

sampler :
A binary quadratic model sampler. A sampler is a process that
samples from low energy states in models defined by an Ising
equation or a Quadratic Unconstrained Binary Optimization
Problem (QUBO). A sampler is expected to have a 'sample_qubo'
and 'sample_ising' method. A sampler is expected to return an
iterable of samples, in order of increasing energy. If no
sampler is provided, one must be provided using the
set_default_sampler function.

lagrange : number, optional (default None)
Lagrange parameter to weight constraints (visit every city once)
versus objective (shortest distance route).

weight : optional (default 'weight')
The name of the edge attribute containing the weight.

start : node, optional
If provided, the route will begin at start.

sampler_args :
Additional keyword parameters are passed to the sampler.

Returns
-------
route : list
List of nodes in order to be visited on a route

Examples
--------

>>> import dimod
...
>>> G = nx.Graph()
>>> G.add_weighted_edges_from({(0, 1, .1), (0, 2, .5), (0, 3, .1), (1, 2, .1),
...                            (1, 3, .5), (2, 3, .1)})
>>> dnx.traveling_salesperson(G, dimod.ExactSolver(), start=0) # doctest: +SKIP
[0, 1, 2, 3]

Notes
-----
Samplers by their nature may not return the optimal solution. This
function does not attempt to confirm the quality of the returned
sample.

"""
# Get a QUBO representation of the problem
Q = traveling_salesperson_qubo(G, lagrange, weight)

# use the sampler to find low energy states
response = sampler.sample_qubo(Q, **sampler_args)

sample = response.first.sample

route = [None]*len(G)
for (city, time), val in sample.items():
if val:
route[time] = city

if start is not None and route[0] != start:
# rotate to put the start in front
idx = route.index(start)
route = route[-idx:] + route[:-idx]

return route

traveling_salesman = traveling_salesperson

[docs]def traveling_salesperson_qubo(G, lagrange=None, weight='weight'):
"""Return the QUBO with ground states corresponding to a minimum TSP route.

If :math:|G| is the number of nodes in the graph, the resulting qubo will have:

* :math:|G|^2 variables/nodes
* :math:2 |G|^2 (|G| - 1) interactions/edges

Parameters
----------
G : NetworkX graph
A complete graph in which each edge has a attribute giving its weight.

lagrange : number, optional (default None)
Lagrange parameter to weight constraints (no edges within set)
versus objective (largest set possible).

weight : optional (default 'weight')
The name of the edge attribute containing the weight.

Returns
-------
QUBO : dict
The QUBO with ground states corresponding to a minimum travelling
salesperson route. The QUBO variables are labelled (c, t) where c
is a node in G and t is the time index. For instance, if ('a', 0)
is 1 in the ground state, that means the node 'a' is visted first.

"""
N = G.number_of_nodes()

if lagrange is None:
# If no lagrange parameter provided, set to 'average' tour length.
# Usually a good estimate for a lagrange parameter is between 75-150%
# of the objective function value, so we come up with an estimate for
# tour length and use that.
if G.number_of_edges()>0:
lagrange = G.size(weight=weight)*G.number_of_nodes()/G.number_of_edges()
else:
lagrange = 2

# some input checking
if N in (1, 2) or len(G.edges) != N*(N-1)//2:
msg = "graph must be a complete graph with at least 3 nodes or empty"
raise ValueError(msg)

# Creating the QUBO
Q = defaultdict(float)

# Constraint that each row has exactly one 1
for node in G:
for pos_1 in range(N):
Q[((node, pos_1), (node, pos_1))] -= lagrange
for pos_2 in range(pos_1+1, N):
Q[((node, pos_1), (node, pos_2))] += 2.0*lagrange

# Constraint that each col has exactly one 1
for pos in range(N):
for node_1 in G:
Q[((node_1, pos), (node_1, pos))] -= lagrange
for node_2 in set(G)-{node_1}:
# QUBO coefficient is 2*lagrange, but we are placing this value
# above *and* below the diagonal, so we put half in each position.
Q[((node_1, pos), (node_2, pos))] += lagrange

# Objective that minimizes distance
for u, v in itertools.combinations(G.nodes, 2):
for pos in range(N):
nextpos = (pos + 1) % N

# going from u -> v
Q[((u, pos), (v, nextpos))] += G[u][v][weight]

# going from v -> u
Q[((v, pos), (u, nextpos))] += G[u][v][weight]

return Q

traveling_salesman_qubo = traveling_salesperson_qubo

def is_hamiltonian_path(G, route):
"""Determines whether the given list forms a valid TSP route.

A travelling salesperson route must visit each city exactly once.

Parameters
----------
G : NetworkX graph

The graph on which to check the route.

route : list

List of nodes in the order that they are visited.

Returns
-------
is_valid : bool
True if route forms a valid travelling salesperson route.

"""

return (set(route) == set(G))