Hamiltonian path for non-tournament graph

[Paul Moore]

I'm looking at the solution to the "Programming Praxis" puzzle "Square-sum puzzle" (https://programmingpraxis.com/2018/01/16/square-sum-puzzle/). The puzzle itself is "Arrange the numbers 1..15 so that all adjacent pairs add up to a perfect square". The given solution (https://programmingpraxis.com/2018/01/16/square-sum-puzzle/2/) is expressed as a graph problem. STep 1 is to create a graph of the numbers 1..15 with adjacent nodes adding up to a perfect square:

    g = nx.Graph()

    for i in range(1,16):

        for tot in (1,4,9,16,25):

            j = tot-i

            if 0 < j < 16 and j != i:

                g.add_edge(i, j)

The solution then notes that a depth-first search of the graph will find the solution - the actual code (written in Scheme, so I find it hard to follow) seems to enumerate all depth first paths through the graphs, looking for one that contains all the nodes of the graph. But that's not how a DFS works in NetworkX (and indeed, none of the DFS algorithms in NetworkX seem to address this problem, except in the very basic sense that I can use dfs_successors to manually implement the algorithm in the solution).

From a bit of research on the web, what I think I want is a Hamiltonian path through the graph. From the Wikipedia article, not all graphs are traceable (contain a Hamiltonian path), but this one is, by the existence of a solution to the original problem. However, the only Hamiltonian path algorithm I can see in NetworkX is for tournament graphs, and this graph is *not* a tournament graph.

Is there an algorithm I can use for this? Should I be looking under a different name? (I often find that I don't know graph theory terminology well enough to find appropriate solutions :-() The problem is small enough that brute force algorithms would be fine - I understand that the general problem does not have an efficient solution, but short of simply reimplementing the solution provided on the "Programming Praxis" site, I don't really know how to approach a solution. What I was hoping was the problem would help me learn a little more about how to use NetworkX to solve problems like this, so just reimplementing the given solution is a little unsatisfying :-)

Does anyone have any suggestions for approaches, or how to tackle this idiomatically using NetworkX?

Thanks,

Paul

[Paul Moore]

On Tuesday, 16 January 2018 12:17:39 UTC, Paul Moore wrote:

I'm looking at the solution to the "Programming Praxis" puzzle "Square-sum puzzle" (https://programmingpraxis.com/2018/01/16/square-sum-puzzle/). The puzzle itself is "Arrange the numbers 1..15 so that all adjacent pairs add up to a perfect square". The given solution (https://programmingpraxis.com/2018/01/16/square-sum-puzzle/2/) is expressed as a graph problem. STep 1 is to create a graph of the numbers 1..15 with adjacent nodes adding up to a perfect square:

    g = nx.Graph()

    for i in range(1,16):

        for tot in (1,4,9,16,25):

            j = tot-i

            if 0 < j < 16 and j != i:

                g.add_edge(i, j)

The solution then notes that a depth-first search of the graph will find the solution - the actual code (written in Scheme, so I find it hard to follow) seems to enumerate all depth first paths through the graphs, looking for one that contains all the nodes of the graph. But that's not how a DFS works in NetworkX (and indeed, none of the DFS algorithms in NetworkX seem to address this problem, except in the very basic sense that I can use dfs_successors to manually implement the algorithm in the solution).

With a bit more research, I found the following brute force solution:

    for i in range(1,16):

        for j in range(1,16):

            for p in nx.all_simple_paths(g, i, j):

                if len(p) == 15:

                    print(p)

This is inefficient, because all_simple_paths is doing a lot of work I don't need. It could be simplified if there were a method that gave "all paths from node N (regardless of destination), stopping when there's nowhere to go or you hit a node you've already seen". I don't know if there's a graph-theory name for such an operation.

Paul

[Moritz Beber]

Hi,

Could you use the single_source_shortest_path methods and then check if they are simple paths?

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To post to this group, send email to networkx...@googlegroups.com.
Visit this group at https://groups.google.com/group/networkx-discuss.
For more options, visit https://groups.google.com/d/optout.

[Paul Moore]

I haven't been able to find a way to. The problem is that the required solution isn't the *shortest* path. The solution (starting from 8, the reverse is also a solution) is

    [8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9]

but there is a shorter path from 8 to 9, namely

    [8, 1, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9]

So SSSP will find that in preference.