Opened 8 years ago

Closed 8 years ago

#13698 closed enhancement (fixed)

Access to graph routines of the GLPK

Reported by: christiankuper Owned by: jason, jkantor
Priority: major Milestone: sage-5.10
Component: numerical Keywords: out-of-kilter, minflow, maxflow, critical path, GLPK
Cc: ncohen, dcoudert Merged in: sage-5.10.beta0
Authors: Christian Kuper Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12415 Stopgaps:

Description (last modified by christiankuper)

Certain types of linear problems can be more efficiently solved with algorithms more specialized than the simplex algorithm. An example of such problems is a mincost problem. The GLPK provides a set of graph / network algorithms which currently have got not interface to Sage.

This patch implements a new backend intended to provide access to the GLPK graph / network routines. The initial implementation should provide an interface to

  • glp_mincost_okalg - Solving mincost problems with the out-of-kilter algorithm
  • glp_maxflow_ffalg - Solving maxflow problems with the Ford-Fulkerson algorithm
  • glp_cpp - Solving critical path problems

In addition it provides support for reading and writing problem data to files

Apply :

Attachments (8)

trac_13698_glpk_graph_rout.patch (66.2 KB) - added by christiankuper 8 years ago.
Access to out-of-kilter and other glpk graph algos
trac_13698-rev.patch (33.5 KB) - added by ncohen 8 years ago.
trac_13698_rev.patch (33.4 KB) - added by christiankuper 8 years ago.
trac_13698-rev.2.patch (33.4 KB) - added by christiankuper 8 years ago.
trac_13698-rev2.patch (1.6 KB) - added by christiankuper 8 years ago.
Modifications to trac_13698-rev.patch
trac_13698_glpk_graph_routv2.patch (53.4 KB) - added by ncohen 8 years ago.
Reference to sage_graph removed and revised formatting
trac_13698-rev3.patch (6.7 KB) - added by ncohen 8 years ago.
trac_13698-rev4.patch (3.5 KB) - added by christiankuper 8 years ago.
Fixed errors cause by Solaris Sparc

Download all attachments as: .zip

Change History (66)

Changed 8 years ago by christiankuper

Access to out-of-kilter and other glpk graph algos

comment:1 Changed 8 years ago by christiankuper

  • Status changed from new to needs_review

comment:2 Changed 8 years ago by christiankuper

Still waiting for a review

Christian

comment:3 follow-ups: Changed 8 years ago by ncohen

  • Status changed from needs_review to needs_work

Hellooooooooo Christian !!!

Your patch is still waiting for a review, but such large patches eat my week-ends. And I also have #13808 too deal with T_T I uploaded a patch which does some (uninteresting) changes to your patch. I also have a list of comments. I can see that you put a lot of work in this patch, but you add a big amount of things in Sage so it is bound to take some time again ^^;

  • create_graph method : why is this a method, and not just part of the init function ? If I do the following, it looks like memory keeps being allocated and is never freed !
    gbe = GLPKGraphBackend()
    gbe.create_graph()
    gbe.create_graph()
    gbe.create_graph()
    ...
    
  • Can't all occurrences of if self.graph is NULL: be removed from the file ? self.graph() can never be null !
  • self.graph() can be null if something went wrong with the memory allocation. An exception should be raised if that happens.
  • I had never seen this property Python thing but it feels weird to have two ways to set/get this graph_name parameter. Could you chose between one of those ? (same for other properties defined in the module)
  • Note from personal experience : I regret to have exposed "name" functions in the LP interface. It has always been a mess to maintain, it takes a loooooooooot of code just to deal with it, and I really do not see the point. It's up to you in this case but in you stead I would not expose anything related to names ^^;
  • It looks like you need to free memory in methods like del_vertices when you allocate it, for instance your num variable.
  • Considering that the Graph methods in Sage are Graph.add_vertices and Graph.delete_vertices, could you copy the same names in your interface ? Or do you think that it is a bad idea ? (same with edges)
  • arc_exists is has_edge in Sage. Or has_arc if you prefer.
  • I had not seen this delete_graph method when I made my first comment. But here again, I feel that this should not be a meethod, and be a part of __destruct__ instead :-)
  • read_graph : in Sage's way of doing things, this should be part of the constructor. Something like "you can build an empty graph, or build it from a file`
  • It would be nice to have an index of methods at the top of the module's documentation, as we have at the top of the following page : http://www.sagemath.org/doc/reference/sage/graphs/graph.html. It takes some time to do it, and it is hell to do unless you know how to use emacs/vim macros.. If you feel like doing it, I will do it myself when this patch will be almost done.
  • It would be nice to say what ccdata is supposed to be, somewhere.
  • It would make sense to update GenericGraph?.flow() so that it can use GLPK as a solver. Actually, the best would be to have in your new module a function converting a Sage graph to a GLPK graph, so that the code in GenericGraph? would stay short. This way we could also begin to compare performances.

Have a nice sunday eveniiiiiiiiiiiiiing ! :-P

Nathann

comment:4 in reply to: ↑ 3 Changed 8 years ago by christiankuper

Replying to ncohen:

Hello Nathann,

sorry, I did not mean to push you for a review (I know the patch is big) but thanks a million for your fast and very constructive comments. You really gave me something to chew on ;-), but this is fun.

Thanks again!!!

Christian

comment:5 in reply to: ↑ 3 ; follow-up: Changed 8 years ago by christiankuper

Replying to ncohen:

Hi Nathann,

finally I find the time start working on your comments, maybe I can bother you with a few questions again ;-)

  • create_graph method : why is this a method, and not just part of the init function ? If I do the following, it looks like memory keeps being allocated and is never freed !

Absolutly correct, changed that!

  • Can't all occurrences of if self.graph is NULL: be removed from the file ? self.graph() can never be null !
  • self.graph() can be null if something went wrong with the memory allocation. An exception should be raised if that happens.

Got it again, residues from prior version :$ Killed them all and added a memory check with the appropriate exception.

  • I had never seen this property Python thing but it feels weird to have two ways to set/get this graph_name parameter. Could you chose between one of those ? (same for other properties defined in the module)

Ok, you might be right here.

  • Note from personal experience : I regret to have exposed "name" functions in the LP interface. It has always been a mess to maintain, it takes a loooooooooot of code just to deal with it, and I really do not see the point. It's up to you in this case but in you stead I would not expose anything related to names ^^;

You might be right that this feature makes no sense but I do not fully grap what the problems you mention could be. Can you give me a hint here?

  • It looks like you need to free memory in methods like del_vertices when you allocate it, for instance your num variable.

Yup! Learned something again and will pay attention to mallocs in the future, I promise ;-)

  • Considering that the Graph methods in Sage are Graph.add_vertices and Graph.delete_vertices, could you copy the same names in your interface ? Or do you think that it is a bad idea ? (same with edges)

Hmm, do you mean the same names only or the full interface (names and arguments and output)? Although it would require a bit of work it might be sensible to go for the second alternative: A standard (same job = same function call) within a software like Sage would make sense. What do you think?

  • arc_exists is has_edge in Sage. Or has_arc if you prefer.

dito

  • I had not seen this delete_graph method when I made my first comment. But here again, I feel that this should not be a meethod, and be a part of __destruct__ instead :-)

Right, see above.

  • read_graph : in Sage's way of doing things, this should be part of the constructor. Something like "you can build an empty graph, or build it from a file`

Right, see above

  • It would be nice to have an index of methods at the top of the module's documentation, as we have at the top of the following page : http://www.sagemath.org/doc/reference/sage/graphs/graph.html. It takes some time to do it, and it is hell to do unless you know how to use emacs/vim macros.. If you feel like doing it, I will do it myself when this patch will be almost done.

Yes, you are right, but as you say, when the patch is almost done ;-

  • It would be nice to say what ccdata is supposed to be, somewhere.

Ah, yes indeed ;-=

  • It would make sense to update GenericGraph?.flow() so that it can use GLPK as a solver. Actually, the best would be to have in your new module a function converting a Sage graph to a GLPK graph, so that the code in GenericGraph? would stay short. This way we could also begin to compare performances.

That's a cool idea, let's see what I can do ;-)

Thanks again for your support!!!!

Christian

comment:6 in reply to: ↑ 5 Changed 8 years ago by ncohen

Helloooooooooo !!

  • Note from personal experience : I regret to have exposed "name" functions in the LP interface. It has always been a mess to maintain, it takes a loooooooooot of code just to deal with it, and I really do not see the point. It's up to you in this case but in you stead I would not expose anything related to names ^^;

You might be right that this feature makes no sense but I do not fully grap what the problems you mention could be. Can you give me a hint here?

Oh. Well, actually nothing serious. I just exposed the "names" methods from the LP solvers, and it turned out later that they behaved quite differently (some things were named in a solver that were no named in others), some had maximum lengths, sometimes created segfaults... And in the end, all this for nothing, as it would have been smarter to implement the names directly in Sage itself (if at all) and note use those defined inside of the solvers. Anyway, I still don't see the points of these names :-P

Have fuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuun ! :-)

Nathann

comment:7 Changed 8 years ago by christiankuper

Just a small update to assure I am still working on this patch: When implementing the suggested changes I found a way to create a segfault - want to remove this bug before uploading a new version.

comment:8 Changed 8 years ago by christiankuper

Hello,

I reworked the patch considerably based on Nathann's comments above. The major changes:

  • Assured syncronization of created extension types and the glpk_graph
  • Removed potential memory leaks
  • Renamed methods to align with existing Sage Graph method names, and
  • added some methods to align with existing Sage Graph
  • Removed exposure of "name" property of glpk graph
  • Moved reading files to constructor
  • Added repr to extension types
  • Added import method for Sage Graphs

Looking forward for feedback

Christian

comment:9 Changed 8 years ago by ncohen

Apply trac_13698_glpk_graph_routv2.patch

comment:10 Changed 8 years ago by christiankuper

  • Status changed from needs_work to needs_review

Added index and removed some errors in the doc.

comment:11 Changed 8 years ago by ncohen

Hmmmmm.... I'm sorry to say this but I read this patch 3 times, on three different days (with long intervals in between), and each time it made me very angry.. There's something like 1500 lines of code in there whose role is to do :

get_something()
    return self.backend.something
set_something(x)
    self.backend.something = x

each time checking that the backend exists, and with doctests.. Honestly, we have to find a way around this. 1500 lines of code.Including doctests, of course. 1500 lines.

I'll walk a bit and go eat something to change my mind, then think about it again.

Nathann

comment:12 Changed 8 years ago by ncohen

Thinking of __get__ and __set__ right now...

I also wrote to Cython's google group.

https://groups.google.com/d/topic/cython-users/b8Il3DLGhoI/discussion

Nathann

comment:13 Changed 8 years ago by christiankuper

Hello Nathann,

first of all: Thanks for the time you invest in helping me on this! Sorry for making you angry, not my intention - I just did the best I could. But I know how to take your well meant beatings by now ;-)

If I understand you correctly: You are basically saying that I need to find a way around the GLPKArc and GLPKVertex classes. Is that correct?

Christian

comment:14 Changed 8 years ago by ncohen

Helloooooooo Christian !

Well, I'm angry because I cannot think of a good way around, that's why... If I had one in mind that would have just been a good remark for the review, but I don't know how to do it either, and all the things I have in mind are surrounded by big fat "Bad work" signs :-P

I hope that we wil find a way around, or that the Cython guys have something in mind. But indeed, it's more or less about removing those two classes, which are just C structures exposed in Cython.

I would be even angrier if there was no way around. But of course that was a couple of hours ago. I had a burger and a pint off cider since, and this make a very big difference :-D

Have fuuuuuuuuuuuuuuuuuuuuuuuun !

Nathann

comment:15 Changed 8 years ago by christiankuper

Hello Nathann,

I am just bending my mind around this issue. There is one idea I have currently. My line of thinking: Basically the main purpose of this patch is using graph algos in GLPK. What do you think of the following approach: Leaving all the basic graph definitions to the Sage Graph classes. When a solving routines is called: Create the GLPKGraph on the fly from the Sage Graph, solve via GLPK and feed the solution into a solution dict. What do you think?

Christian

comment:16 Changed 8 years ago by ncohen

Well, to be honest I did not really know what you had in mind with this patch... If you only want to be able to call GLPK algorithms on some graphs, indeed this patch is going too far. But well, let's first wait for an answer from the Cython guys. Perhaps we can have both for free ;-)

Nathann

comment:17 Changed 8 years ago by christiankuper

  • Status changed from needs_review to needs_work

comment:18 Changed 8 years ago by christiankuper

Following Nathann's comment I removed the two classes GLPKArc and GLPKVertex and replaced the access using dicts. Doing this I tried to stick as close as possible to the exitsitng definitions in GenericGraph? for consistency.

Eager to know whether this approach "feels better". ;-)

Christian

comment:19 Changed 8 years ago by christiankuper

  • Status changed from needs_work to needs_review

comment:20 Changed 8 years ago by ncohen

Two quick things :

  • Why do you keep a pointer toward Sage's graph self.sage_graph ? There are several problem with this design : the graph may be modified by the user, while you keep a pointer toward a graph that gets modified. Secondly, as it seems you only need it for two methods, you might as well give the graph as a parameter to those two methods, and get rid of the parameter.
  • Don't do this :
        sage: from sage.numerical.backends.glpk_graph_backend \ 
    import GLPKGraphBackend
    

If you *need* to split lines, do it this way :

sage: from sage.numerical.backends.glpk_graph_backend \ 
...      import GLPKGraphBackend

But you really shouldn't split lines so often. It' meant to make code easier to read (a least I believe it is), but sometimes it really doesn't help. As they appear really often, I think that you should let this line stay even if it is very long. Besides, you very often don't need to add a terinal \. For instance, this :

 	830	                return (u, v, {"low":(<c_a_data *>a.data).low, \ 
 	831	                               "cap":(<c_a_data *>a.data).cap, \ 
 	832	                               "cost":(<c_a_data *>a.data).cost, \ 
 	833	                               "x":(<c_a_data *>a.data).x}) 

Can be replaced by

 	830	                return (u, v, {"low":(<c_a_data *>a.data).low, 
 	831	                               "cap":(<c_a_data *>a.data).cap, 
 	832	                               "cost":(<c_a_data *>a.data).cost, 
 	833	                               "x":(<c_a_data *>a.data).x}) 

It works, because Python knows the line is not finished : some parenthesis are still open at this step, and it's waiting for } and ).

Nathann

comment:21 Changed 8 years ago by christiankuper

Thanks for your quick reply and the hints, Nathann. This time they were not to hard to include ;-)

Have a nice weekend

Christian

comment:22 Changed 8 years ago by ncohen

  • Cc dcoudert added

comment:23 follow-ups: Changed 8 years ago by ncohen

  • Status changed from needs_review to needs_info

Hellooooooooooooooo Christian.

Well, I think I spent my whole saturday on your patch. Here is a patch to apply on topof yours, which changes many things among which the following :

  • set_vertex/set_vertices were renamed to set_vertex_demand and set_vertices_demand as they define "rhs", and as the help of get_vertex says that "rhs" represents the demand in mincost flow algorithms. As a result, they do not take a dictionary as an argument anymore but only a numerical value, as it is only meant to define a numerical value and nothing else.
  • some unimportant reformatting of the index of method at the tp of the document. It goes beyond 80 characters, but it is easier to read this way.
  • fname is not fname but "data". data can be a filename, None, or a Sage graph.
  • You can use "::" wherever you like, not only after "EXAMPLES".
  • import_generic_graph looks like trouble if you call it after having defined edges and vertices in the graph. And its use did not seem very sensible at this step. Hence I removed the function, which is now part of the class constructor.
  • In this import_generic_graph function you were trying to guess the value of rhs from the vertex name, by casting it to a float. Are you aware that most of our graph's vertices are integers ? And that no two vertices can have the same name ? This would let rhs be defined to 0, 2, 3, 4, 5 ... in a graph without anybody noticing, wouldn't it ? I removed that part of the code. Honestly I do not like the fact that rhs is guessed from the result of Graph.get_vertex (if it happens to be a numerical value or a dictionary) as it seems to be that users could have stuff defined in rhs without knowing it. Looks dangerous. If you agree I would be glad to see it removed, otherwise I will not complain anymore.
  • I hate the fact that vertices are necessarily represented by strings. But that's not your fault of course, the API is written like that.
  • I hate the fact that there is no function in the API to look for an edge, and that you have to do it yourself.

And many, many other small details in the code. A bugfix in add_vertices random stuff everywhere.

Well. Tell me what you think about it. I don't know if all this will be heavily used for itself, but we will a least have to expose the flow algorithms inside of the Graph.connectivity methods later on. Thank you for your work for I know it has taken a lifetime, and I think this patch will be ready very soon.

See youuuuuuuuuuuuuuuuuuuuuuuuuuuu !!!

Nathann

P.S. : Pleaaaaaaaaaaase. No other "patch bombs". These things are too big to review at once :-P

Changed 8 years ago by ncohen

comment:24 Changed 8 years ago by ncohen

  • Description modified (diff)

Apply trac_13698_glpk_graph_routv2.patch, trac_13698-rev.patch

comment:25 in reply to: ↑ 23 Changed 8 years ago by christiankuper

Hello Nathann,

first of all: Thanks a million for all the time you invested helping me get this of the ground!!!! I promise: I will never ever again come up with something as long as this patch. I really underestimated the work needed - a typical newbie error :-(

I haven't had the time to go through all your changes in detail but all you say and did looks sensible and like improvements to me. Give me a day or two to check it all.

Thank you again

Christian

comment:26 in reply to: ↑ 23 Changed 8 years ago by christiankuper

Hello Nathann,

  • set_vertex/set_vertices were renamed to set_vertex_demand and set_vertices_demand as they define "rhs", and as the help of get_vertex says that "rhs" represents the demand in mincost flow algorithms. As a result, they do not take a dictionary as an argument anymore but only a numerical value, as it is only meant to define a numerical value and nothing else.
  • some unimportant reformatting of the index of method at the tp of the document. It goes beyond 80 characters, but it is easier to read this way.
  • fname is not fname but "data". data can be a filename, None, or a Sage graph.
  • You can use "::" wherever you like, not only after "EXAMPLES".

Thanks for all the good changes!

  • import_generic_graph looks like trouble if you call it after having defined edges and vertices in the graph. And its use did not seem very sensible at this step. Hence I removed the function, which is now part of the class constructor.

You're absolutely right

  • In this import_generic_graph function you were trying to guess the value of rhs from the vertex name, by casting it to a float. Are you aware that most of our graph's vertices are integers ? And that no two vertices can have the same name ? This would let rhs be defined to 0, 2, 3, 4, 5 ... in a graph without anybody noticing, wouldn't it ? I removed that part of the code. Honestly I do not like the fact that rhs is guessed from the result of Graph.get_vertex (if it happens to be a numerical value or a dictionary) as it seems to be that users could have stuff defined in rhs without knowing it. Looks dangerous. If you agree I would be glad to see it removed, otherwise I will not complain anymore.

You are absolutely correct, I hadn't thought of that. I removed the "guessing".

  • I hate the fact that vertices are necessarily represented by strings. But that's not your fault of course, the API is written like that.
  • I hate the fact that there is no function in the API to look for an edge, and that you have to do it yourself.

I agree, the API is not perfect. I had thought about the "vertices must be strings" issue and do have some ideas for a workaround to leave it aside for now.

Thanks again!!!!

Christian

Changed 8 years ago by christiankuper

Changed 8 years ago by christiankuper

comment:27 Changed 8 years ago by christiankuper

  • Description modified (diff)
  • Status changed from needs_info to needs_review

comment:28 Changed 8 years ago by christiankuper

I hope I did the modifications with the 2 patches correctly. I could not replace the trac_13698-rev.patch so I had to upload it with as trac_13698-rev.2.patch

comment:29 follow-up: Changed 8 years ago by ncohen

  • Status changed from needs_review to needs_work

Hmmmmmmmmmm ... O_o

It turns out that this patch does not apply on beta2 anymore because #6495 changes the way the doc files are stored.

Could I also ask you to upload the difference between your patch and mine instead of replacing one ? My patch was rather long and I have no way to see what is the difference between yours and mine :-)

Nathann

Changed 8 years ago by christiankuper

Modifications to trac_13698-rev.patch

comment:30 Changed 8 years ago by christiankuper

  • Description modified (diff)
  • Status changed from needs_work to needs_info

comment:31 in reply to: ↑ 29 ; follow-up: Changed 8 years ago by christiankuper

Hello Nathann,

It turns out that this patch does not apply on beta2 anymore because #6495 changes the way the doc files are stored.

Can you give me a hint what I need to do?

Could I also ask you to upload the difference between your patch and mine instead of replacing one ? My patch was rather long and I have no way to see what is the difference between yours and mine :-)

I hope I understood you correctly. I put my last changes (only a few lines) into a seperate patch.

Christian

comment:32 in reply to: ↑ 31 Changed 8 years ago by ncohen

Helloooooooooooooooooooo !!!

Can you give me a hint what I need to do?

Oh. Well, download beta2 and rebase the patch, but I will do that in a second :-)

I hope I understood you correctly. I put my last changes (only a few lines) into a seperate patch.

Yepyepyep ! Looks good ! I will re-read everything once and we should be ok afterwards !

Nathann

Changed 8 years ago by ncohen

Reference to sage_graph removed and revised formatting

comment:33 Changed 8 years ago by ncohen

Apply trac_13698_glpk_graph_routv2.patch, trac_13698-rev.patch, trac_13698-rev2.patch

comment:34 Changed 8 years ago by ncohen

  • Description modified (diff)
  • Reviewers set to Nathann Cohen
  • Status changed from needs_info to needs_review

Helloooooooooo again ! I just went over the patch again and changed a few characters. I added several 's' to verbs so that they would either all have one, nd I removed a variable named "graph_sol" which was not really useful as a class parameter.

If you as ok with this then we can set this ticket to positive review ! ;-)

Have fuuuuuuuuuuuuuuuuuuuuuun !!

Nathann

Changed 8 years ago by ncohen

comment:35 Changed 8 years ago by christiankuper

Hello Nathann,

Thank you for the improvements you made! I feel absolutly comfortable with the changes in the trac_13698-rev3.patch.

Thanks again!!!

Christian

comment:36 Changed 8 years ago by ncohen

  • Status changed from needs_review to positive_review

Well, then... Positive review ! And we will have to expose this flow method from inside the graph library eventually :-)

Nathann

comment:37 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.8 to sage-5.9

comment:38 Changed 8 years ago by jdemeyer

  • Dependencies set to #12415

With #12415:

sage -t devel/sage/sage/numerical/backends/glpk_graph_backend.pyx
**********************************************************************
File "devel/sage/sage/numerical/backends/glpk_graph_backend.pyx", line 156, in sage.numerical.backends.glpk_graph_backend.GLPKGraphBackend
Failed example:
    gbe.write_graph(SAGE_TMP+"/graph.txt")
Expected:
    0
Got:
    Writing graph to `/tmp/dotsagem31030/temp/sage.math.washington.edu/13336/graph.txt'...
    2 lines were written
    0
**********************************************************************

and more like this...

comment:39 Changed 8 years ago by jdemeyer

  • Status changed from positive_review to needs_work

comment:40 Changed 8 years ago by christiankuper

Ok,it seems that #12415 means that the "..." placeholder is not accepted any more (at least for some outputs). Removing "..." resulted in successful doctest.

comment:41 Changed 8 years ago by christiankuper

  • Description modified (diff)
  • Status changed from needs_work to needs_review

comment:42 Changed 8 years ago by ncohen

  • Status changed from needs_review to positive_review

comment:43 Changed 8 years ago by ncohen

I'm pretty sure that I fixed this doctest problem somewhere else, but I don't remember right now ^^;

Nathann

comment:44 Changed 8 years ago by jdemeyer

  • Status changed from positive_review to needs_work

I get this failure on Solaris SPARC:

sage -t --long devel/sage/sage/numerical/backends/glpk_graph_backend.pyx
**********************************************************************
File "devel/sage/sage/numerical/backends/glpk_graph_backend.pyx", line 1340, in sage.numerical.backends.glpk_graph_backend.GLPKGraphBackend.cpp
Failed example:
    print 1, v["rhs"], v["es"], v["ls"]
Expected:
    1 1.0 0.0 2.0
Got:
    1 1.0 5.30498947741e-315 0.0
**********************************************************************

comment:45 Changed 8 years ago by christiankuper

  • Status changed from needs_work to needs_review

Added a tolerance check to cope with the SPARC Solaris error.

comment:46 Changed 8 years ago by ncohen

  • Status changed from needs_review to positive_review

comment:47 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.9.beta4
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:48 Changed 8 years ago by jdemeyer

  • Merged in sage-5.9.beta4 deleted
  • Resolution fixed deleted
  • Status changed from closed to new

It still fails exactly the same test as before on Solaris SPARC:

sage -t --long devel/sage/sage/numerical/backends/glpk_graph_backend.pyx
**********************************************************************
File "devel/sage/sage/numerical/backends/glpk_graph_backend.pyx", line 1340, in sage.numerical.backends.glpk_graph_backend.GLPKGraphBackend.cpp
Failed example:
    print 1, v["rhs"], v["es"], v["ls"] # abs tol 1e-6
Expected:
    1 1.0 0.0 2.0
Got:
    1 1.0 5.30498947741e-315 0.0
Tolerance exceeded in 1 of 4
    2.0 vs 0.0
**********************************************************************

Changed 8 years ago by christiankuper

Fixed errors cause by Solaris Sparc

comment:49 Changed 8 years ago by christiankuper

The only "unique" aspect in the method causing the error is the pointers passed to the GLPK library function. This is the only function where the pointer of two parameters is defined like "x*sizeof(double) + y*sizeof(long)" - and these two values are causing the errors. All other pointers are defined like "x*sizeof(double)". Therefore I suspect that "sizeof(long)" is causing the errors.

I therefore redefined the "c_v_data" structure so the <long> value is the last value. This now allows all pointers to be defined as "x*sizeof(double)", i.e. without sizeof long. In addition defined the field in the data structure as "long" and not as "int".

Hopefully this removes the failure in the test on a Solaris. Due to the lack of a solaris machine I cannot verify this myself, therefore I tried to explain the reasoning behind the changes I did.

Christian

comment:50 Changed 8 years ago by christiankuper

  • Status changed from new to needs_review

comment:51 follow-up: Changed 8 years ago by ncohen

Why don't you think it was just caused by the fact that "cut" used to be of "int" type in the structure's definition, and seemed to be counted as "sizeof(long)" int glp_cpp ?

Besides, if this line (the call to glp_cpp) has to be changed, wouldn't others need to be changed too ?

Nathann

comment:52 in reply to: ↑ 51 Changed 8 years ago by christiankuper

Replying to ncohen:

Why don't you think it was just caused by the fact that "cut" used to be of "int" type in the structure's definition, and seemed to be counted as "sizeof(long)" int glp_cpp ?

You are probably right, just to be on the safe side I did both ;-)

Besides, if this line (the call to glp_cpp) has to be changed, wouldn't others need to be changed too ?

Yes of course, I changed "glp_maxflow_ffalg" call too, which I did. All other function calls are not affected as they do not need the affected fields of the structure.

Christian

BTW: Of course I re-ran the tests and all passed!

Last edited 8 years ago by christiankuper (previous) (diff)

comment:53 Changed 8 years ago by ncohen

Well, I guess it's worth a try then. Though your patch contains no modification to glp_maxflow_ffalg.

Nathann

comment:54 Changed 8 years ago by ncohen

Ooops my mistake.

Sorry.

It does.

Nathann

comment:55 follow-up: Changed 8 years ago by ncohen

  • Status changed from needs_review to positive_review

Ok, it makes sense. Let's ask Jeroen to give it another try :-)

Nathann

comment:56 in reply to: ↑ 55 Changed 8 years ago by christiankuper

Replying to ncohen:

Ok, it makes sense. Let's ask Jeroen to give it another try :-)

Nathann

Thank you !!!!!!!!!

comment:57 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.9 to sage-5.10

comment:58 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.10.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.