The main issue is that the hamiltonian path method calls the longest path method.
We should provide a dedicated ILP for hamiltonian path that could optionally search for a hamiltonian path of minimum/maximum cost. Le mardi 6 février 2018 19:39:32 UTC+1, Dima Pasechnik a écrit : > > > > On Tuesday, February 6, 2018 at 5:18:02 PM UTC, Avinandan Das wrote: >> >> Consider the following :- >> >> a=[[0, 4, 8], [9, 0, 9], [1000, 1000, 0]] >> a=Matrix(a) >> H=DiGraph(a,weighted=True) >> H.hamiltonian_path(used_edge_labels=True) >> >> This returns (1009, Subgraph of (): Digraph on 3 vertices) but the >> minimum weight Hamiltonian path has weight 13. >> > > Looking at the source code, it seems that it actually returns maximum > weight Hamiltonian path. > > https://github.com/sagemath/sage/blob/07d6c37d18811e2b377a9689790a7c5e24da16ba/src/sage/graphs/generic_graph.py#L7137 > > > > > > I suppose we should amend the documentation. > >> >> I have installed sage-8.1 and my operating system is Ubuntu 14.04 LTS (64 >> bit) and my processor is Intel® Core™ i5-3210M CPU @ 2.50GHz × 4 . >> > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
