# Type hierarchy for TSP instances?

**URL:** <https://discourse.julialang.org/t/type-hierarchy-for-tsp-instances/23123>\
**Category:** General Usage\
**Created:** [April 13, 2019, 11:13pm UTC](https://discourse.julialang.org/t/type-hierarchy-for-tsp-instances/23123 "2019-04-13T23:13:29Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![evanfields](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/evanfields/32/1744_2.png) [@evanfields](https://discourse.julialang.org/u/evanfields)\
**Post date:** [April 13, 2019, 11:13pm UTC](https://discourse.julialang.org/t/type-hierarchy-for-tsp-instances/23123/1 "2019-04-13T23:13:30Z")

</div>

It’s time to give my neglected [Traveling Salesman problem package](https://github.com/evanfields/TravelingSalesmanHeuristics.jl) some attention. One of the biggest issues: right now, all TSP problem instances are specified by a dense distance matrix, and no heuristics take advantage of problem specific structure.

I’d like to create one or more `TSPInstance` types which contain information about the properties of the given instance, e.g. whether the problem is symmetric, metric, Euclidean, etc. Broadly I see two ways to do this:

- Have the `TSPInstance` type(s) contain fields indicating instance attributes. E.g. a field like `issymmetric::Bool` and define `is_sym_instance(p::TSPInstance) = p.issymmetric`. Then a user-facing function like `solve_tsp` can do something like

```julia
if is_sym_instance(p)
    tsp_solution = _symmetric_heuristic(p)
else
    tsp_solution = _generic_heuristic(p)
end

```

- Use the type system more aggressively. Have `SymmetricTSPInstance <: AbstractTSPInstance` and `GeneralTSPInstance <: AbstractTSPInstance`. Then define heuristic methods, as appropriate, for specialized types, and `solve_tsp` doesn’t need to explicitly check the properties of a problem instance; dynamic dispatch takes care of that.

The second solution feels more Julian, but my concern is that the relevant attributes of TSP problem instances don’t naturally fit into a tree structure, which the type system enforces. For example, we might have big, medium, and small instances, symmetric/metric/Euclidean instances, nonnegative instances, etc. Creating a concrete type for each possible combination of instance attributes would seem to require a large number of types.

So, any suggestions for an elegant/idiomatic way to attach attributes to a TSP instance type without requiring a huge and intricate type hierarchy?

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [April 14, 2019, 6:07am UTC](https://discourse.julialang.org/t/type-hierarchy-for-tsp-instances/23123/2 "2019-04-14T06:07:16Z")

</div>

> [@evanfields](#):
>
> The second solution feels more Julian, but my concern is that the relevant attributes of TSP problem instances don’t naturally fit into a tree structure, which the type system enforces.

Then don’t use it. It is also Julian to write a simple user-facing API for a polyalgorithm, eg that’s how `\(::Matrix, ::Matrix)` & friends are implemented. The internal functions called by this can be type-stable, and heavily optimized for some special cases, and it will work fine.

I know little about the TSP, but given your description, I would just

1. store the relevant information in slots of a `struct` that has enough information to select the relevant specialized algorithm, or generate it on demand if that is an alternative (eg checking symmetry),
2. implement those algorithms in separate functions,
3. have a user-facing function (eg `solve_tsp`) select the relevant one.

In general, I think that concocting elaborate parametric type hierarchies is something that most Julia users go through at some point as part of the learning process, then realize that it is more of a constraint without any benefits. I regret most instances of doing something like this, and go back to duck typing when I refactor code, mostly keeping the types when I need them for dispatch.

---

<div class="post-metadata">

**Author:** ![leethargo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/leethargo/32/6004_2.png) [@leethargo](https://discourse.julialang.org/u/leethargo)\
**Post date:** [April 14, 2019, 10:41am UTC](https://discourse.julialang.org/t/type-hierarchy-for-tsp-instances/23123/3 "2019-04-14T10:41:54Z")

</div>

A third way might be to define traits, that can apply to multiple (sub)types? That way, one is not bound to a tree structure, but does not have to specify the attributes per instance, only per instance-type.