[sage-support] Re: cannot install sage: gfortran-7.2.0 failed to build

[Dima Pasechnik]

On Wednesday, March 7, 2018 at 5:53:19 PM UTC, Matthew Lancellotti wrote:
>
> I simply ran 'make'.
>

if you change branches, it might be wise to re-run ./bootstrap and 
./configure, as configuration data in configure.ac
etc might change between the branches.
 

>
> Updating Xcode fixed the issue.
>
>
> On Wednesday, March 7, 2018 at 12:04:47 AM UTC-5, Dima Pasechnik wrote:
>>
>>
>>
>> On Tuesday, March 6, 2018 at 11:56:59 PM UTC, Matthew Lancellotti wrote:
>>>
>>> sage: latest version (8.1) (from https://github.com/sagemath/sage, last 
>>> updated Dec 17, 2017).  tried both master branch and develop branch.
>>> OS: Mac OSX 10.13.3
>>> Xcode version 9.0.1
>>>
>>>
>>> I cloned the latest version of sage from the git repository.  When 
>>> attempting to `make` sage, I run into the error `The following package(s) 
>>> may have failed to build...gfortran-7.2.0`.  I will attach the log file 
>>> shortly.  Near the bottom of the file it says:
>>>
>>> The directory that should contain system headers does not exist:
>>>   /usr/include
>>> make[5]: *** [stmp-fixinc] Error 1
>>> make[5]: *** Waiting for unfinished jobs
>>> rm gcc.pod gfortran.pod
>>> make[4]: *** [all-gcc] Error 2
>>> make[3]: *** [all] Error 2
>>>
>>> I tried using brew to manually install gfortran.  Brew said that it 
>>> ships with gcc.  I used brew to update my system to the latest version of 
>>> gcc.  It didn't help.  Currently, I am updating my Xcode to 9.2 to see if 
>>> that helps.  Also, should my "system headers" exist?  If so, where are they?
>>>
>>
>> System headers should be in /usr/include
>> You also need XCode's command line tools to be installed.
>>
>> It could be that presence of Homebrew in your PATH breaks things.
>>
>> As well, please tell us the sequence of commands you executed.
>> Did you run ./bootstrap and
>> ./configure (with what parameters?)
>> before running make?
>>
>>   
>>
>

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

[sage-support] Re: cannot install sage: gfortran-7.2.0 failed to build

[Matthew Lancellotti]

I simply ran 'make'.

Updating Xcode fixed the issue.


On Wednesday, March 7, 2018 at 12:04:47 AM UTC-5, Dima Pasechnik wrote:
>
>
>
> On Tuesday, March 6, 2018 at 11:56:59 PM UTC, Matthew Lancellotti wrote:
>>
>> sage: latest version (8.1) (from https://github.com/sagemath/sage, last 
>> updated Dec 17, 2017).  tried both master branch and develop branch.
>> OS: Mac OSX 10.13.3
>> Xcode version 9.0.1
>>
>>
>> I cloned the latest version of sage from the git repository.  When 
>> attempting to `make` sage, I run into the error `The following package(s) 
>> may have failed to build...gfortran-7.2.0`.  I will attach the log file 
>> shortly.  Near the bottom of the file it says:
>>
>> The directory that should contain system headers does not exist:
>>   /usr/include
>> make[5]: *** [stmp-fixinc] Error 1
>> make[5]: *** Waiting for unfinished jobs
>> rm gcc.pod gfortran.pod
>> make[4]: *** [all-gcc] Error 2
>> make[3]: *** [all] Error 2
>>
>> I tried using brew to manually install gfortran.  Brew said that it ships 
>> with gcc.  I used brew to update my system to the latest version of gcc.  
>> It didn't help.  Currently, I am updating my Xcode to 9.2 to see if that 
>> helps.  Also, should my "system headers" exist?  If so, where are they?
>>
>
> System headers should be in /usr/include
> You also need XCode's command line tools to be installed.
>
> It could be that presence of Homebrew in your PATH breaks things.
>
> As well, please tell us the sequence of commands you executed.
> Did you run ./bootstrap and
> ./configure (with what parameters?)
> before running make?
>
>   
>

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

[sage-support] Re: Graph canonical form directly on matrices

[Dima Pasechnik]

On Wednesday, March 7, 2018 at 8:44:52 AM UTC, Christian Stump wrote:
>
> Dear Dima,
>
> Ultimately, the classical canonical form/isomorphism implementations run 
>> on (di)graphs represented by 0-1 matrices, often
>> with bit entries. So that's how bliss_digraph is represented too.
>>
>
> Thanks for this info clarifying that it seems impossible to feed the 
> algorithm any other kind of integer matrix. 
>

It is perfectly possible to implement  canonical form/isomorphism of 
edge-labelled (di)graphs in the same vein as un-labelled ones.
(I did it as a part of a project in my undergraduate years, the code (in 
Fortran IV :-)) is unfortunately lost. It should not be too hard to re-do.)
It's just I'm not aware of such implementations available anywhere.



>
> Anyhow, the main inefficiency in your approach is coming from constructing 
>> unnecessarily big graphs.
>>
>
> Also thanks for this reference, for the general problem this is certainly 
> the correct approach. In my example cases though (as mentioned above), I 
> have only very few edge labels (usually only two) so I doubt this 
> improvement would change the overall performance. 
>

OK, in this case indeed it won't be noticeable.


>
> If you implemented this in Sage, it would be a great contribution! 
>>
>
> I agree that this would be very worth having! But my cython skills are too 
> weak to do this in the appropriate speed context.
>
> One question here: am I correct that the best we can currently hope for is 
> to
>
> 1. feed the algorithm a list of labelled edges
> 2. turn this list of labelled edges into a list of unlabelled edges 
> representing the edge-labelled graph as in Section 13
> 3. feed this to either the bliss or the nauty algorithm
> 4. get back an unlabelled graph
> 5. turn this back into an edge labelled graph
>

 the only improvement I could see in your scheme is that bliss/nauty can 
return a permutation you need to apply to your graph to make it canonical, 
and it would be probably more efficient to apply it (after the dropping the 
extra vertices you created) directly to your original labelled (di)graph.

Still faster would be to make a Sage graph backend compatible with bliss or 
nauty API in the sense that they could operate directly on
the graph you created, but this is much more work, naturally.
   

>  
>
>> Also, I am not sure whether bliss is faster than nauty (nauty also is a 
>> Sage standard package, but lacks a cython interface)
>>
>
> The only reason I use bliss over nauty is that it can return only a list 
> of edges rather than creating the output DiGraph. And in the tests I did, 
> 1/3 of the time was spend on constructing the canonical form and 2/3 were 
> used to turn these output edges into a DiGraph (this compares bliss with 
> and without constructing the output graph, nauty was as fast as bliss with 
> output graph construction).
>
> Cheers, Christian
>

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

[sage-support] Re: Graph canonical form directly on matrices

[Christian Stump]

Dear Simon and Dima,

I moved this to https://trac.sagemath.org/ticket/24924 for better 
traceability and to show you some code snippets...

Cheers, Christian

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

[sage-support] Re: Graph canonical form directly on matrices

[Simon King]

Dear Christian,

On 2018-03-07, Christian Stump  wrote:
> Anyway, looking at sage/graphs/bliss.pyx, it seems easy to modify your 
>> code to directly create a bliss graph.
>>
>
> Help there is highly appreciated :-), I don't know how to do that 
> appropriately...

Just have a look at sage/graphs/bliss.pyx. Apparently it uses c++, so,
that needs to be taken into account when cythoning and compiling. See
module_list.py, where it says:
OptionalExtension("sage.graphs.bliss",
  ["sage/graphs/bliss.pyx"],
  language = "c++",
  libraries = ['bliss'],
  package = 'bliss'),

Apparently, it is then

  cdef Digraph *g = new Digraph(order)

to create a Digraph with a given number of vertices (which are always
numbered in range(order)), and then an edge from v1 to v2 is added like
this:

  g.add_edge(v1,v2)

In your code you basically do the same. Only problem: It seems that
you need to provide the number of vertices during initialisation of g.
But in your code, you add more vertices on the fly, IIRC. But this can
certainly be solved.

Best regards,
Simon


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

[sage-support] Re: Graph canonical form directly on matrices

[Christian Stump]

Dear Simon,

Anyway, looking at sage/graphs/bliss.pyx, it seems easy to modify your 
> code to directly create a bliss graph.
>

Help there is highly appreciated :-), I don't know how to do that 
appropriately...

Christian 

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

[sage-support] Re: Graph canonical form directly on matrices

[Christian Stump]

Dear Dima,

Ultimately, the classical canonical form/isomorphism implementations run on 
> (di)graphs represented by 0-1 matrices, often
> with bit entries. So that's how bliss_digraph is represented too.
>

Thanks for this info clarifying that it seems impossible to feed the 
algorithm any other kind of integer matrix. 

Anyhow, the main inefficiency in your approach is coming from constructing 
> unnecessarily big graphs.
>

Also thanks for this reference, for the general problem this is certainly 
the correct approach. In my example cases though (as mentioned above), I 
have only very few edge labels (usually only two) so I doubt this 
improvement would change the overall performance. 

If you implemented this in Sage, it would be a great contribution! 
>

I agree that this would be very worth having! But my cython skills are too 
weak to do this in the appropriate speed context.

One question here: am I correct that the best we can currently hope for is 
to

1. feed the algorithm a list of labelled edges
2. turn this list of labelled edges into a list of unlabelled edges 
representing the edge-labelled graph as in Section 13
3. feed this to either the bliss or the nauty algorithm
4. get back an unlabelled graph
5. turn this back into an edge labelled graph
 

> Also, I am not sure whether bliss is faster than nauty (nauty also is a 
> Sage standard package, but lacks a cython interface)
>

The only reason I use bliss over nauty is that it can return only a list of 
edges rather than creating the output DiGraph. And in the tests I did, 1/3 
of the time was spend on constructing the canonical form and 2/3 were used 
to turn these output edges into a DiGraph (this compares bliss with and 
without constructing the output graph, nauty was as fast as bliss with 
output graph construction).

Cheers, Christian

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

[sage-support] Re: Graph canonical form directly on matrices

[Simon King]

On 2018-03-07, Dima Pasechnik  wrote:
> Ultimately, the classical canonical form/isomorphism implementations run on 
> (di)graphs represented by 0-1 matrices, often
> with bit entries. So that's how bliss_digraph is represented too.
> Constructing it directly might be beneficial, especially if you have a 
> problem of doing this on many small matrices

For the record: I guess one should then at least provide a
sage/graphs/bliss.pxd header, or better: Move those parts of
sage/graphs/bliss.pyx that are merely library bindings to
sage/libs/bliss.*

Anyway, looking at sage/graphs/bliss.pyx, it seems easy to modify your
code to directly create a bliss graph.

Cheers,
Simon

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