Opened 2 years ago

Closed 2 years ago

#18929 closed enhancement (fixed)

Include igraph library

Reported by: borassi Owned by:
Priority: major Milestone: sage-6.9
Component: packages: optional Keywords: igraph library
Cc: ncohen, dcoudert, vbraun Merged in:
Authors: Michele Borassi Reviewers: Nathann Cohen, David Coudert
Report Upstream: N/A Work issues:
Branch: c4685c5 (Commits) Commit: c4685c504bc1603e44b3493213c7545baf415497
Dependencies: Stopgaps:

Description (last modified by borassi)

Include igraph library ![1] in Sagemath, so that we can use its algorithms. Add routines to convert Sage graphs into igraph and viceversa. The input files are available through the following links:

  • for igraph.tar.gz: igraph.org/nightly/get/c/igraph-0.7.1.tar.gz
  • for python-igraph.tar.gz: igraph.org/nightly/get/python/python-igraph-0.7.0.tar.gz

The modified files (with script spkg_src) are available through the following links:

  • for igraph.tar.gz (the same as the previous one): https://drive.google.com/file/d/0B5D_YOccuV6xNFFUYnZFYzg0bkk/view?usp=sharing
  • for python-igraph.tar.gz (we had to replace - with _ in the filename and in a folder): https://drive.google.com/file/d/0B5D_YOccuV6xcURsT1BpLUpqZ0E/view?usp=sharing

If we manage to include igraph, we will have access to 62 algorithms on graphs: 29 of them are not available in Sage, yet ![2].

![1]http://igraph.org/python/

![2] https://docs.google.com/spreadsheets/d/1Iu1hkQtRn9J-sgfZbQTu2RoXzyjoMEWP5-cm3nAwnWE/edit#gid=0

Change History (45)

comment:1 Changed 2 years ago by borassi

  • Authors set to Michele Borassi
  • Cc ncohen dcoudert vbraun added
  • Component changed from PLEASE CHANGE to packages: optional
  • Description modified (diff)
  • Keywords igraph library added
  • Status changed from new to needs_info
  • Type changed from PLEASE CHANGE to enhancement

Hello!

With this ticket, I would like to add igraph library to Sage. I have tried to follow as much as possible the instructions in ![1], to include the following external libraries:

  • igraph-0.7.1, available in ![2] (the C/C++ core of igraph);
  • python-igraph-0.7.0, available in ![3] (the Python interface).

In order to build this code, you should do the following.

  • Download the two .tar.gz source code files [2,3] and put them in folder SAGE_ROOT/upstream (this folder is not synchronized with git).
  • run the script SAGE_ROOT/build/pkgs/python_igraph/spkg-src from folder SAGE_ROOT, with command ./build/pkgs/python_igraph/spkg-src. The problem is that Sage does not like dashes inside the package name: the script converts the file python-igraph-0.7.0.tar.gz into python_igraph-0.7.0.gz (it is also necessary to modify the name of a folder inside the tar archive).

I am not really sure about the procedure (in particular, about spkg-src), so I would like to have feedback, also related to ticket #18826.

Thank you very much!

Michele

![1] doc.sagemath.org/html/en/developer/packaging.html

![2] http://igraph.org/c/#downloads![3] http://igraph.org/python/#downloads

comment:2 Changed 2 years ago by borassi

  • Branch set to u/borassi/include_igraph_library

comment:3 Changed 2 years ago by git

  • Commit set to 388abfbfec5b9d8255ff83efbdfc4a61a076ffce

Branch pushed to git repo; I updated commit sha1. New commits:

388abfbModified spkg-src according to Nathann's suggestions.

comment:4 Changed 2 years ago by borassi

  • Status changed from needs_info to needs_review

Hello!

I have modified spkg-src, taking inspiration from the spkg-src file of bzip2 in ticket #18826. I have added the dependencies, but I'm not really sure if I have done it correctly (I have no idea of where variable $(IGRAPH) is defined).

Thank you very much!

Michele

comment:5 Changed 2 years ago by ncohen

  • Status changed from needs_review to needs_work

Helloooooooo Michele,

I have not installed the two igraph packages yet (the reason will follow) but it seems that you did well with the 'dependencies' file. The 'IGRAPH' variable is a bit magic it's true: it is generated from the package's name, and you should find it in SAGE_ROOT/build/make/Makefile somewhere. If you look for PYTHON_IGRAPH you should see the dependency that you added in this 'dependencies' file.

I added a small commit at public/18929 that does not do anything smart. I flagged the new doctests with # optional - python_igraph so that they are only run if the python_igraph is installed (they would break otherwise), though there remains some problem to deal with: you cannot import 'igraph' in the (Di)Graph constructor, for this package is optional. I ran the tests before installing the package, and well.. Everything break. Even this:

sage: Graph()
...
ImportError: No module named igraph

Sooo perhaps you should 'detect' the presence of this module with something like that (unless you find something better):

try:
    import igraph
    _python_igraph_available = True
except ImportError:
    _python_igraph_available = False    

In the same way, your 'import igraph' in GenericGraph.igraph_graph would generate, when called on a machine on which the package is not installed, an ImportError. We usually try to give something easier to work with, like an error message advising to install a package named <package_name> to enable this feature.

Have fuuuuuuun,

Nathann

comment:6 Changed 2 years ago by git

  • Commit changed from 388abfbfec5b9d8255ff83efbdfc4a61a076ffce to 1ca4c05f87ac4bc0637982b53521e723f96f2071

Branch pushed to git repo; I updated commit sha1. New commits:

efac72fMerge branch 'develop' into t/18929/include_igraph_library
cc5c10etrac #18929: Merged with 6.8
8c49588trac #18929: Reviewer's commit
a82f7f2Merged with Nathann's work
1ca4c05Solved bug if igraph is not installed

comment:7 Changed 2 years ago by borassi

Hellooooooooooo!

Ups, you were right: if igraph is not installed, nothing works anymore. I have corrected it, and I have included your commit (we both merged with 6.8...).

Now everything should work (I have performed a test of all the graph part, and all tests were passed).

See you, Michele

comment:8 Changed 2 years ago by ncohen

Hello again Michele,

I was about to try to install the two packages and so I downloaded igraph's sources, but it seems that there is something wrong with the checksums:

(tmp|✔)~/.Sage$ sage -i igraph
Found local metadata for igraph-0.7.1
Invalid checksum for cached file /home/ncohen/.Sage/upstream/igraph-0.7.1.tar.gz, deleting

Could you also provide direct links toward the archive files in the ticket's description? This is for the release manager who will have to add them to Sage's repository.

In the second case, i.e. the python_igraph file (as it is not vanilla upstream), it means uploading it on some server of yours so that it can be downloaded from there. The purpose of ticket #18826 is precisely to give us an easy way to 'check', in such situations, that the archive uploaded by one of us is exactly what it should.

Nathann

comment:9 Changed 2 years ago by ncohen

Oh, and something else I forgot: it is not sufficient to add the edges in order to get the graph: isolated vertices would not appear in this case.

Nathann

comment:10 Changed 2 years ago by borassi

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

Hello!

I have done it: sorry, but I'm not very experienced with new packages, so I need lots of advices and comments, even to solve stupid issues...

Michele

comment:11 Changed 2 years ago by git

  • Commit changed from 1ca4c05f87ac4bc0637982b53521e723f96f2071 to ac2c5c39a65c1ef8e003219bf59fc9f6e35f61e1

Branch pushed to git repo; I updated commit sha1. New commits:

ac2c5c3Solved a problem with isolated vertices

comment:12 follow-up: Changed 2 years ago by ncohen

Hello again Michele,

Don't worry about the many steps it takes to get this through. I also worry that I may be a bit boring, with all these things I add one by one to your stack because I cannot seem to figure out them all at the same time.

I installed the two packages, and things went well. I still have a question about the igraph package: upstream is apparently a 'fake' .tar.gz archive (it is not gzipped) -> is this why your igraph package is 'not exactly' (up to md5sum hash) equal to upstream?

While looking at the (Di)Graph constructor, I thought that something unlikely may happen: 1) Somebody has a igraph object in a Sage session 2) igraph is not installed in Sage I thought that it could happen if by some chance such an object was obtained through pickling.

Perhaps it sounds stupid. This being said, I also 'fixed' something else: importing modules is not totally free, and it was even the bottleneck in some design code I met in the past. For this reason, it is better to not import things in potentially critical parts of the code (the graph constructor can be one of those, for instance when you enumerate graphs up to isomorphism) and so I tried to make it less frequent. This commit is located at public/18929, you can take/remove what you like/do not like in it.

Have you figured out this GPL2 vs GPLv2+ issue I mentionned in an email?

Byeeeeeeeeeee,

Nathann

P.S.: I had some issue when installing the package, which I reported upstream (https://github.com/igraph/igraph/issues/842)

comment:13 Changed 2 years ago by ncohen

  • Status changed from needs_review to needs_info

comment:14 in reply to: ↑ 12 ; follow-up: Changed 2 years ago by borassi

Hello!

Replying to ncohen:

Hello again Michele,

Don't worry about the many steps it takes to get this through. I also worry that I may be a bit boring, with all these things I add one by one to your stack because I cannot seem to figure out them all at the same time.

I installed the two packages, and things went well. I still have a question about the igraph package: upstream is apparently a 'fake' .tar.gz archive (it is not gzipped) -> is this why your igraph package is 'not exactly' (up to md5sum hash) equal to upstream?

What do you mean by 'fake' .tar.gz archive? Anyway, I have downloaded again the file igraph.tar.gz, and I have run again the sage -sh sage-fix-pkg-checksums script, hoping it will solve the problem. Does it?

While looking at the (Di)Graph constructor, I thought that something unlikely may happen: 1) Somebody has a igraph object in a Sage session 2) igraph is not installed in Sage I thought that it could happen if by some chance such an object was obtained through pickling.

Perhaps it sounds stupid. This being said, I also 'fixed' something else: importing modules is not totally free, and it was even the bottleneck in some design code I met in the past. For this reason, it is better to not import things in potentially critical parts of the code (the graph constructor can be one of those, for instance when you enumerate graphs up to isomorphism) and so I tried to make it less frequent. This commit is located at public/18929, you can take/remove what you like/do not like in it.

I have included the commit.

Have you figured out this GPL2 vs GPLv2+ issue I mentionned in an email?

The igraph file COPYING that comes with both packages starts with:

GNU GENERAL PUBLIC LICENSE Version 2, June 1991

So I believe it is GPLv2. However, it does not seem to be a problem: http://www.gnu.org/licenses/gpl-faq.en.html#WhatDoesCompatMean. Moreover, also package latte_int is distributed with Sage with GPLv2.

Byeeeeeeeeeee,

Nathann

P.S.: I had some issue when installing the package, which I reported upstream (https://github.com/igraph/igraph/issues/842)

Ouch, yes, the problem is libxml2. I have uninstalled it from my computer, and I have re-installed igraph (without Sage): the problem still appears, even if ./configure realizes that libxml2 is missing, because it writes "GraphML format support -- no". Probably it is an igraph bug.

In order to solve this problem, I have added a check in the spkg-install script, and I had to modify the sage-spkg file to allow an error which depends on the user. Do you agree with this modification? Or do you think I should do something less "invasive"? Because I do not like that we tell the user to contact sage-devel if (s)he only has to install libxml2.

comment:15 Changed 2 years ago by git

  • Commit changed from ac2c5c39a65c1ef8e003219bf59fc9f6e35f61e1 to d6770f994d05bc9443445fbdeedd2a8215806077

Branch pushed to git repo; I updated commit sha1. New commits:

b4adbbatrac #18929: Reviewer's commit
8c837bdIncluded Nathann's work
d6770f9Check that libxml2 is installed

comment:16 in reply to: ↑ 14 ; follow-up: Changed 2 years ago by ncohen

Hello,

What do you mean by 'fake' .tar.gz archive?

Sigh.... After some debugging, it seems that if I click on "source code" at this address (http://igraph.org/c/#downloads) I get a file like that:

~$ file igraph-0.7.1.tar.gz            
igraph-0.7.1.tar.gz: POSIX tar archive

If I copy/paste the url and download it with wget I get a file like that:

~$ file igraph-0.7.1.tar.gz 
igraph-0.7.1.tar.gz: gzip compressed data, last modified: Tue Apr 22 19:55:20 2014, max compression, from Unix

Anyway. It works, sorry for the misunderstanding.

So I believe it is GPLv2. However, it does not seem to be a problem: http://www.gnu.org/licenses/gpl-faq.en.html#WhatDoesCompatMean. Moreover, also package latte_int is distributed with Sage with GPLv2.

Yes yes you are right. It would have been a problem for a standard package, but of course not for an optional one.

In order to solve this problem, I have added a check in the spkg-install script, and I had to modify the sage-spkg file to allow an error which depends on the user. Do you agree with this modification?

Oh. Well, I did not want to say that it had to be modified on our side. I merely wanted to tell you what had happened and that it had been reported upstream. For me it is not a very important problem, and for as long as upstream knows and fixes it I do not think that we should care O_o

Nathann

comment:17 Changed 2 years ago by git

  • Commit changed from d6770f994d05bc9443445fbdeedd2a8215806077 to d060ccbddf96281324e021e49b6e20758a01cb26

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

61f72f3Included igraph in sage.
222c2dcConversion Sage graphs - igraph graphs
83b5970Small correction in the documentation
e09511fModified spkg-src according to Nathann's suggestions.
59098e6trac #18929: Reviewer's commit
acd870bSolved bug if igraph is not installed
20ca006Solved a problem with isolated vertices
36f998atrac #18929: Reviewer's commit
fa916b4Included Nathann's work
d060ccbCheck that libxml2 is installed

comment:18 in reply to: ↑ 16 Changed 2 years ago by borassi

In order to solve this problem, I have added a check in the spkg-install script, and I had to modify the sage-spkg file to allow an error which depends on the user. Do you agree with this modification?

Oh. Well, I did not want to say that it had to be modified on our side. I merely wanted to tell you what had happened and that it had been reported upstream. For me it is not a very important problem, and for as long as upstream knows and fixes it I do not think that we should care O_o

Ok, I went back to the previous version: if it is not installed, an error explaining the problem is raised before any installation.

comment:19 Changed 2 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_info to positive_review

Okayyyyyy, good !

Nathann

comment:20 Changed 2 years ago by borassi

  • Status changed from positive_review to needs_work

Wait a second: I was trying to make a better interface, that takes into account vertex/edge labels and weight... To be uploaded soon!

comment:21 Changed 2 years ago by git

  • Commit changed from d060ccbddf96281324e021e49b6e20758a01cb26 to facc0faa1906a9f5744de908915163aab575722a

Branch pushed to git repo; I updated commit sha1. New commits:

facc0faConversion of graph name, edge labels, vertex name, and edge weight

comment:22 Changed 2 years ago by borassi

  • Status changed from needs_work to needs_review

Done!

comment:23 Changed 2 years ago by git

  • Commit changed from facc0faa1906a9f5744de908915163aab575722a to b5c421f1902bb9c41a01d1359d1fc0c2407f4e5f

Branch pushed to git repo; I updated commit sha1. New commits:

b5c421fRemoved trailing whitespaces

comment:24 Changed 2 years ago by git

  • Commit changed from b5c421f1902bb9c41a01d1359d1fc0c2407f4e5f to 24920b6ffa69b6e92efabf359970a96464912d8e

Branch pushed to git repo; I updated commit sha1. New commits:

ea6a7f8Merged with 6.9.beta0
24920b6Small correction

comment:25 follow-up: Changed 2 years ago by ncohen

Helooooooo Michele,

I finished reviewing this ticket again. I'm sorry but if there is one thing I cannot stand, it is to see heaps of code meant to deal with edge labels/multile edges/loops/weights. Dozens of line which do nothing but wrap junk into another kind of junk.

Well.

I added a commit at public/18929 which does the following modifications, which you can of course accept/discuss/reject:

  • documentation of igraph input -- I removed the end of the sentence about what is done with weights/names/etc. It is not said for other formats and it is how it is expected to work. I thought that the shortest was the best.
  • removed some trailing whitespaces
  • changed the message in which you mentionned a 'network'. Graphs are.. Well, nobody exactly knows. Depending on who you talk to, when you say "a graph" people hear "social network graph", "router graph", "planar graph", "vertex-transitive graph", "cayley graph", and many others. Networks do exist, but that would not make *any* sense for some of those guys, so I stuck to the 'graph' terminology.
  • I "compressed" a bit the copy/paste meant to handle names, by using the relabel function. For this I had to change a line in GenericGraph.relabel related to _boundary, but this #O&O#&&^@)#%*( is meant to be removed in #17462 anyway.
  • Try to not use except Exception if you can avoid it. That's too large. If there is a typo in the line before it, it will catch this too and you don't want that. Also, try to keep as little as possible in a try/except.

Finally, I have to say that I can't bring myself to give a positive review to this latest commit. Much of what it does is, to me, meant to be done by the user. We cannot adapt to the many forms he wants his data to take in the igraph graph, so I think that the best we should do is ... "keep it simple and reliable". Guessing that 'label' is a special key in the dictionary is (to me) going way too far, and I am tempted to do the same for weights. Of course their labels *have* to be dictionaries and ours can be anything. That's unpleasant, but turning our label into a {'label':label} in their data structure, and setting their dictionary to be our edge label is to me the best we can do.

So yes, if you apply translation several times you will not converge. Honestly, I do not care at all.

Sooooo, sorry for that. You have several ways out:

  • Get this ticket reviewed by somebody else (I will not force my view, I just won't review it myself -- no way)
  • Remove the commits you added since my last 'positive review' so that this ticket can get merged, and move those label commits to another ticket.

As you wish.

Have fun,

Nathann

comment:26 in reply to: ↑ 25 Changed 2 years ago by borassi

Hellooooooo!

Well, I go for a variation of the first solution you proposed: simplifying as much as possible the interface with igraph. In particular, I have removed the graph name, and vertex and edge attributes are provided by the user in "igraph-style" (http://igraph.org/python/doc/igraph.Graph-class.html#__init__). There are several examples on how to do it in my new code.

For the igraph=>sage conversion, I have used your relabel function for vertex names, while the edge label is simply kept as it was in igraph (only problem: empty labels in igraph translate to {} label in Sage, not to None).

More answers below! Hope you like this new commit!

See you,

Michele

Replying to ncohen:

Helooooooo Michele,

I finished reviewing this ticket again. I'm sorry but if there is one thing I cannot stand, it is to see heaps of code meant to deal with edge labels/multile edges/loops/weights. Dozens of line which do nothing but wrap junk into another kind of junk.

Well.

I added a commit at public/18929 which does the following modifications, which you can of course accept/discuss/reject:

  • documentation of igraph input -- I removed the end of the sentence about what is done with weights/names/etc. It is not said for other formats and it is how it is expected to work. I thought that the shortest was the best.

Accept

  • removed some trailing whitespaces

Accept

  • changed the message in which you mentionned a 'network'. Graphs are.. Well, nobody exactly knows. Depending on who you talk to, when you say "a graph" people hear "social network graph", "router graph", "planar graph", "vertex-transitive graph", "cayley graph", and many others. Networks do exist, but that would not make *any* sense for some of those guys, so I stuck to the 'graph' terminology.

Accept

  • I "compressed" a bit the copy/paste meant to handle names, by using the relabel function. For this I had to change a line in GenericGraph.relabel related to _boundary, but this #O&O#&&^@)#%*( is meant to be removed in #17462 anyway.

Accept

  • Try to not use except Exception if you can avoid it. That's too large. If there is a typo in the line before it, it will catch this too and you don't want that. Also, try to keep as little as possible in a try/except.

Accept (modified also in the digraph file)

Finally, I have to say that I can't bring myself to give a positive review to this latest commit. Much of what it does is, to me, meant to be done by the user. We cannot adapt to the many forms he wants his data to take in the igraph graph, so I think that the best we should do is ... "keep it simple and reliable". Guessing that 'label' is a special key in the dictionary is (to me) going way too far, and I am tempted to do the same for weights. Of course their labels *have* to be dictionaries and ours can be anything. That's unpleasant, but turning our label into a {'label':label} in their data structure, and setting their dictionary to be our edge label is to me the best we can do.

Unfortunately, I don't think so. The problem occurs if we want to convert weighted graphs (and some of the algorithms we want to "steal" are on weighted graph). Indeed, an igraph graph is weighted if edges contain an attribute 'weight', and with this conversion there is no way to obtain that. My solution is to let the user provide the labels.

So yes, if you apply translation several times you will not converge. Honestly, I do not care at all.

Now, if the starting graph has "igraph-friendly" labels and the user provides the right attributes, it converges (see the examples).

Sooooo, sorry for that. You have several ways out:

  • Get this ticket reviewed by somebody else (I will not force my view, I just won't review it myself -- no way)
  • Remove the commits you added since my last 'positive review' so that this ticket can get merged, and move those label commits to another ticket.

As you wish.

Have fun,

Nathann

comment:27 Changed 2 years ago by git

  • Commit changed from 24920b6ffa69b6e92efabf359970a96464912d8e to fc693a955362964e4c7bb73c75b74c65e7dbebef

Branch pushed to git repo; I updated commit sha1. New commits:

bcb85c1trac #18929: Review
fc693a9Simplified handling of labels

comment:28 Changed 2 years ago by dcoudert

Hello,

I tried to install igraph and more precisely ./sage -i python_igraph but I have checksum error. What should I do?

David.

comment:29 Changed 2 years ago by borassi

Did you follow the whole procedure to install igraph? In particular, you should do the following:

  • Download the two .tar.gz source code files [1,2] and put them in folder SAGE_ROOT/upstream (this folder is not synchronized with git).
  • run the script SAGE_ROOT/build/pkgs/python_igraph/spkg-src through sage -sh ./build/pkgs/python_igraph/spkg-src from folder SAGE_ROOT (you can also run it from any other folder).

Another possible procedure is to download the modified tarballs from [3,4] and put them in the folder SAGE_ROOT/upstream. Then, ./sage -i python_igraph should work.

If you still have problems, could you tell me which of the two procedure fails, and if it still fails after running the command sage -sh sage-fix-pkg-checksums?

Thank you very much,

Michele

![1] ​http://igraph.org/c/#downloads!

![2] ​http://igraph.org/python/#downloads

![3] https://drive.google.com/file/d/0B5D_YOccuV6xNFFUYnZFYzg0bkk/view?usp=sharing

![4] https://drive.google.com/file/d/0B5D_YOccuV6xcURsT1BpLUpqZ0E/view?usp=sharing

comment:30 follow-ups: Changed 2 years ago by dcoudert

My first trial was with the source code from [1] and [2]. One difficulty is that [2] gives python-igraph... and not python_igraph...

Now I'm trying with [4] and it's working... but then it says that igraph is not installed. So I'm running ./sage -i igraph using the source code from [3] (should work also with [1]).

The point is that before installing igraph, I installed this patch and performed the following test:

sage: G = graphs.PetersenGraph()
sage: G.igraph_graph()
---------------------------------------------------------------------------
ImportError                               Traceback (most recent call last)
<ipython-input-2-07a5568607db> in <module>()
----> 1 G.igraph_graph()

/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.pyc in igraph_graph(self, vertex_attrs, edge_attrs)
   1432             raise ImportError("The package igraph is not available. To " +
   1433                               "install it, run Sage with option -i " +
-> 1434                               "python_igraph.")
   1435 
   1436         v_to_int = {v:i for i,v in enumerate(self.vertices())}

ImportError: The package igraph is not available. To install it, run Sage with option -i python_igraph.
sage: 

I don't know if the installation of python_igraph is expected to install igraph as well or not. If not, then the error message should be improved.

Now that it is working, I did

sage: G = graphs.PetersenGraph()
sage: H = G.igraph_graph()
sage: H.<TAB>

and got access to the list of methods. It is surprizing to see that we have both graph algorithms and graph generators (e.g. Barabasi, Erdos_Renyi, etc.), but I assume there is nothing you can do to avoid that. Not a big deal. Also, some methods for digraphs (e.g., all_st_mincuts) are accessible from undirected graphs and so an error is raised, but again I assume there is nothing we can do about it.

sage: H.is_directed()
False
sage: H.all_st_mincuts(0,2)
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
<ipython-input-22-8251331c5c90> in <module>()
----> 1 H.all_st_mincuts(Integer(0),Integer(2))

/Users/dcoudert/sage/local/lib/python2.7/site-packages/python_igraph-0.7.0-py2.7-macosx-10.9-x86_64.egg/igraph/__init__.pyc in all_st_mincuts(self, source, target, capacity)
    390           graphs. Algorithmica 15, 351--372, 1996.
    391         """
--> 392         value, cuts, parts = GraphBase.all_st_mincuts(self, source, target, capacity)
    393         return [Cut(self, value, cut=cut, partition=part)
    394                 for cut, part in izip(cuts, parts)]

NotImplementedError: Error at st-cuts.c:1320: S-t cuts can only be listed in directed graphs, Unimplemented function call

Anyway, its working.

I will now try to understand the point of disagreement between you and Nathann.

David.

comment:31 in reply to: ↑ 30 ; follow-up: Changed 2 years ago by borassi

Replying to dcoudert:

My first trial was with the source code from [1] and [2]. One difficulty is that [2] gives python-igraph... and not python_igraph...

This is exactly the reason why I made the spkg-src script (Sage cannot install packages with dashes inside their names).

Now I'm trying with [4] and it's working... but then it says that igraph is not installed. So I'm running ./sage -i igraph using the source code from [3] (should work also with [1]).

The point is that before installing igraph, I installed this patch and performed the following test:

sage: G = graphs.[wiki:PetersenGraph]()
sage: G.igraph_graph()
---------------------------------------------------------------------------
ImportError                               Traceback (most recent call last)
<ipython-input-2-07a5568607db> in <module>()
----> 1 G.igraph_graph()

/Users/dcoudert/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.pyc in igraph_graph(self, vertex_attrs, edge_attrs)
1432             raise ImportError("The package igraph is not available. To " +
1433                               "install it, run Sage with option -i " +
-> 1434                               "python_igraph.")
1435 
1436         v_to_int = {v:i for i,v in enumerate(self.vertices())}

ImportError: The package igraph is not available. To install it, run Sage with option -i python_igraph.
sage: 

I don't know if the installation of python_igraph is expected to install igraph as well or not. If not, then the error message should be improved.

Hmmmmm, good question. I added igraph to the dependencies of python_igraph, but maybe it is not sufficient (see comments 4-5)... Nathann??

Now that it is working, I did

sage: G = graphs.[wiki:PetersenGraph]()
sage: H = G.igraph_graph()
sage: H.<TAB>

and got access to the list of methods. It is surprizing to see that we have both graph algorithms and graph generators (e.g. Barabasi, Erdos_Renyi, etc.), but I assume there is nothing you can do to avoid that. Not a big deal. Also, some methods for digraphs (e.g., all_st_mincuts) are accessible from undirected graphs and so an error is raised, but again I assume there is nothing we can do about it.

sage: H.is_directed()
False
sage: H.all_st_mincuts(0,2)
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
<ipython-input-22-8251331c5c90> in <module>()
----> 1 H.all_st_mincuts(Integer(0),Integer(2))

/Users/dcoudert/sage/local/lib/python2.7/site-packages/python_igraph-0.7.0-py2.7-macosx-10.9-x86_64.egg/igraph/__init__.pyc in all_st_mincuts(self, source, target, capacity)
390           graphs. Algorithmica 15, 351--372, 1996.
391         """
--> 392         value, cuts, parts = GraphBase.all_st_mincuts(self, source, target, capacity)
393         return [Cut(self, value, cut=cut, partition=part)
394                 for cut, part in izip(cuts, parts)]

NotImplementedError: Error at st-cuts.c:1320: S-t cuts can only be listed in directed graphs, Unimplemented function call

Anyway, its working.

I will now try to understand the point of disagreement between you and Nathann.

David.

comment:32 follow-up: Changed 2 years ago by dcoudert

could you resolve the merge conflict with last beta (beta1). Thanks.

comment:33 Changed 2 years ago by git

  • Commit changed from fc693a955362964e4c7bb73c75b74c65e7dbebef to 93dee5e3d8e20b2fd19da57644f0f67e645171de

Branch pushed to git repo; I updated commit sha1. New commits:

93dee5eMerged with beta1

comment:34 in reply to: ↑ 32 Changed 2 years ago by borassi

could you resolve the merge conflict with last beta (beta1). Thanks.

Done!

comment:35 in reply to: ↑ 31 Changed 2 years ago by ncohen

Hmmmmm, good question. I added igraph to the dependencies of python_igraph, but maybe it is not sufficient (see comments 4-5)... Nathann??

Yeah, I know. The dependency is taken into consideration only if you install the package by typing 'make python_igraph'. It is ignored if you run 'sage -i python_igraph'. Why? Because Jeroen likes it.

I think that it is plainly stupid, and already had to complain on a ticket (#18859) which replaced *all* instructions to install a package through "sage -i <pkgname>" with "make <pkgname>" (which is obviously less practical for beginners).

To me, the 'most natural' command for users (i.e. 'sage -i pkgname') should install the package, and take dependencies into account.

If you agree with Jeroen you have nothing to do, if you do not care you have nothing to do, if you have any other opinion please voice it on sage-devel, or nothing will happen.

Nathann

Last edited 2 years ago by ncohen (previous) (diff)

comment:36 in reply to: ↑ 30 Changed 2 years ago by ncohen

I will now try to understand the point of disagreement between you and Nathann.

There is none anymore. If you are satisfied with this patch, then it is 'positively reviewed' and can make it in.

Nathann

comment:37 follow-up: Changed 2 years ago by dcoudert

  • Milestone changed from sage-6.8 to sage-6.9

Hello,

I thought these two lines were removed from graph.py and digraph.py in #17462, but I see them in your commits...

    -  ``boundary`` - a list of boundary vertices, if
       empty, graph is considered as a 'graph without boundary'

David.

comment:38 Changed 2 years ago by git

  • Commit changed from 93dee5e3d8e20b2fd19da57644f0f67e645171de to 655943e1481a7f80fc60f9f26529c8a7c1e64216

Branch pushed to git repo; I updated commit sha1. New commits:

655943eCorrected merge error

comment:39 in reply to: ↑ 37 Changed 2 years ago by borassi

Sorry, wrong merge... Now it should be correct!

comment:40 Changed 2 years ago by dcoudert

  • Reviewers changed from Nathann Cohen to Nathann Cohen, David Coudert
  • Status changed from needs_review to positive_review

One last thing: in the doc of the igraph_graph method, you should mention explicitely that it requires the optional package python_igraph. It does not appear on html page sage/src/doc/output/html/en/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.igraph_graph

comment:41 Changed 2 years ago by dcoudert

  • Status changed from positive_review to needs_work

sorry... needs work for the doc ;)

comment:42 Changed 2 years ago by git

  • Commit changed from 655943e1481a7f80fc60f9f26529c8a7c1e64216 to c4685c504bc1603e44b3493213c7545baf415497

Branch pushed to git repo; I updated commit sha1. New commits:

c4685c5Corrected doc and error message if igraph is not installed

comment:43 Changed 2 years ago by borassi

Done, and I have also modified the error message if python_igraph is not installed.

comment:44 Changed 2 years ago by dcoudert

  • Status changed from needs_work to positive_review

Perfect!

comment:45 Changed 2 years ago by vbraun

  • Branch changed from u/borassi/include_igraph_library to c4685c504bc1603e44b3493213c7545baf415497
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.