ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 24 Jun 2016 05:23:38 -0500Make graph from matrixhttp://ask.sagemath.org/question/33903/make-graph-from-matrix/Hi,
I'm a new user of SageMath and maybe my question is very simple or already answered somewhere but I wasn't able to find an answer to my problem. For my studies I have to implement a brute-force algorithm for solving the travelling salesman problem. I found out, that SM already has a solver for this problem that handles Graph - objects. I wan't to use it to check the results of my algorithm. I wrote some input data as a dictionary to feed into both alg, but if I wan't to do it for more than a few cities (I can handle only a few with bruteforce anyway because of the time it takes to calculate all the possibilities) and I've found a matrix with distances between cities. It is available here
https:// people.sc.fsu.edu/~jburkardt/datasets/cities/cities.html
(ha30_dist.txt)
I threw the first two lines out and I can import this file with numpy.loadtxt(). But later, when I try to make Graph using this matrix, I get the error:
*"ValueError: There must be one or two nonzero entries per column in an incidence matrix. Got entries [39, 22, 59, 54..."*. What am I doing wrong?
GreetingsThu, 23 Jun 2016 14:56:02 -0500http://ask.sagemath.org/question/33903/make-graph-from-matrix/Answer by kcrisman for <p>Hi,</p>
<p>I'm a new user of SageMath and maybe my question is very simple or already answered somewhere but I wasn't able to find an answer to my problem. For my studies I have to implement a brute-force algorithm for solving the travelling salesman problem. I found out, that SM already has a solver for this problem that handles Graph - objects. I wan't to use it to check the results of my algorithm. I wrote some input data as a dictionary to feed into both alg, but if I wan't to do it for more than a few cities (I can handle only a few with bruteforce anyway because of the time it takes to calculate all the possibilities) and I've found a matrix with distances between cities. It is available here</p>
<p>https:// people.sc.fsu.edu/~jburkardt/datasets/cities/cities.html
(ha30_dist.txt)</p>
<p>I threw the first two lines out and I can import this file with numpy.loadtxt(). But later, when I try to make Graph using this matrix, I get the error:
<em>"ValueError: There must be one or two nonzero entries per column in an incidence matrix. Got entries [39, 22, 59, 54..."</em>. What am I doing wrong?</p>
<p>Greetings</p>
http://ask.sagemath.org/question/33903/make-graph-from-matrix/?answer=33904#post-id-33904Incidence and adjacency matrices will have plus or minus one depending on whether vertices lead to other vertices or are adjacent. What you want is to make a *complete* graph, and then label the *edges*, I think.
The [TSP solver](http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.traveling_salesman_problem) assumes you have weighted edges already. See that documentation for ways to either add edges one by one, or you can separately use `add_edge_label`. In any case, you'll have to probably take your matrix and programmatically use those values to set the edge labels. Probably by going through the columns, and then through the rows in each column - but watch out, since such a matrix had better be symmetric, so you only need the first i-1 entries of the ith column, I suppose!Thu, 23 Jun 2016 22:04:53 -0500http://ask.sagemath.org/question/33903/make-graph-from-matrix/?answer=33904#post-id-33904Comment by littlemd for <p>Incidence and adjacency matrices will have plus or minus one depending on whether vertices lead to other vertices or are adjacent. What you want is to make a <em>complete</em> graph, and then label the <em>edges</em>, I think.</p>
<p>The <a href="http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.traveling_salesman_problem">TSP solver</a> assumes you have weighted edges already. See that documentation for ways to either add edges one by one, or you can separately use <code>add_edge_label</code>. In any case, you'll have to probably take your matrix and programmatically use those values to set the edge labels. Probably by going through the columns, and then through the rows in each column - but watch out, since such a matrix had better be symmetric, so you only need the first i-1 entries of the ith column, I suppose!</p>
http://ask.sagemath.org/question/33903/make-graph-from-matrix/?comment=33905#post-id-33905Thanks for your answer! I know what to do nowFri, 24 Jun 2016 05:23:38 -0500http://ask.sagemath.org/question/33903/make-graph-from-matrix/?comment=33905#post-id-33905