Opened 4 years ago

Closed 4 years ago

#19385 closed enhancement (fixed)

Refactor DiGraph.__init__

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.9
Component: graph theory Keywords:
Cc: borassi, dcoudert, dimpase, vdelecroix, SimonKing Merged in:
Authors: Nathann Cohen Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: ced3658 (Commits) Commit: ced36581c5258b40dc9e72a986fbaa9b7e12a8cc
Dependencies: #19381 Stopgaps:

Description

As was done earlier with #19381, this branch strips some code out of digraph.py and stores it in graph_input.py.

Fortunately, most of graph_input.py can be reused for digraphs, so that's a net decrease in code volume in general.

Nathann

P.S.: I cannot believe all that this code does in order to guess what the user meants when he provides bad/incomplete/crazy input.

Change History (29)

comment:1 follow-up: Changed 4 years ago by ncohen

  • Branch set to u/ncohen/19385
  • Commit set to cf53613abb473f53411b50bd2ddc049050cd6dbc
  • Dependencies set to #19381
  • Status changed from new to needs_review

Simon: sorry to disturb, but I think I will need your help for this branch. All doctests pass in graph/ except for a test in DiGraph.path_semigroup that I absolutely do not understand :-/

Here is a trace, though it will appear soon on the patchbot (and I expect other related doctests to fail in combinat/).

Nathann

File "digraph.py", line 2671, in sage.graphs.digraph.DiGraph.path_semigroup
Failed example:
    F = Q.path_semigroup(); F
Exception raised:
...
      File "sage/misc/cachefunc.pyx", line 563, in genexpr (build/cythonized/sage/misc/cachefunc.c:2439)
        return tuple(_cache_key(item) for item in o)
      File "sage/misc/cachefunc.pyx", line 561, in sage.misc.cachefunc._cache_key (build/cythonized/sage/misc/cachefunc.c:2644)
        o = o._cache_key()
      File "sage/structure/sage_object.pyx", line 410, in sage.structure.sage_object.SageObject._cache_key (build/cythonized/sage/structure/sage_object.c:2918)
        raise TypeError("{} is not hashable and does not implement _cache_key()".format(type(self)))
    TypeError: <class 'sage.graphs.digraph.DiGraph'> is not hashable and does not implement _cache_key()
**********************************************************************

Last 10 new commits:

efb842btrac #19381: disclaimer
d9522bbtrac #19381: seidel adjacency matrix
f0f8ee4trac #19381: adjacency matrix
7a51fdetrac #19381: Fix seidel adjacency
5abbd4btrac #19381: Incidence matrix
cf7f515trac #19381: dict_of_dicts
f9fc7a8trac #19381: dict of lists
dd28d93trac #19381: dig6
9bdf527trac #19381: Typo
cf53613trac #19385: Refactor DiGraph.__init__

comment:2 in reply to: ↑ 1 ; follow-up: Changed 4 years ago by SimonKing

Replying to ncohen:

File "digraph.py", line 2671, in sage.graphs.digraph.DiGraph.path_semigroup
Failed example:
    F = Q.path_semigroup(); F
Exception raised:
...
      File "sage/misc/cachefunc.pyx", line 563, in genexpr (build/cythonized/sage/misc/cachefunc.c:2439)
        return tuple(_cache_key(item) for item in o)
      File "sage/misc/cachefunc.pyx", line 561, in sage.misc.cachefunc._cache_key (build/cythonized/sage/misc/cachefunc.c:2644)
        o = o._cache_key()
      File "sage/structure/sage_object.pyx", line 410, in sage.structure.sage_object.SageObject._cache_key (build/cythonized/sage/structure/sage_object.c:2918)
        raise TypeError("{} is not hashable and does not implement _cache_key()".format(type(self)))
    TypeError: <class 'sage.graphs.digraph.DiGraph'> is not hashable and does not implement _cache_key()
**********************************************************************

I'll have a look. Obviously, we should either use an immutable version of a digraph, or (something which seems to be new) implement _cache_key.

comment:3 in reply to: ↑ 2 Changed 4 years ago by ncohen

I'll have a look. Obviously, we should either use an immutable version of a digraph, or (something which seems to be new) implement _cache_key.

I tried to make Q immutable but the result was the same. And anyway, this branch shouldn't have any effect on that :-/

Nathann

comment:4 Changed 4 years ago by tscrim

Somehow you're breaking this behavior:

Q = Q.copy(immutable=True, weighted=True)

and the result is a mutable digraph.

comment:5 Changed 4 years ago by tscrim

sage: hash(Q.copy(immutable=True))
8019503473919971649
sage: hash(Q.copy(immutable=True, weighted=True))
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-4-dab47b1641ed> in <module>()
----> 1 hash(Q.copy(immutable=True, weighted=True))

/home/travis/sage/src/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (/home/travis/sage/src/build/cythonized/sage/misc/cachefunc.c:14346)()
   2213         if self.cache is None:
   2214             f = self.f
-> 2215             self.cache = f(self._instance)
   2216         return self.cache
   2217 

/home/travis/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.pyc in __hash__(self)
    576             if self.allows_multiple_edges():
    577                 from collections import Counter
--> 578                 edge_items = Counter(edge_items).items()
    579             return hash((frozenset(self.vertex_iterator()),
    580                          self._weighted,

/home/travis/sage/local/lib/python/collections.pyc in __init__(self, iterable, **kwds)
    451         '''
    452         super(Counter, self).__init__()
--> 453         self.update(iterable, **kwds)
    454 
    455     def __missing__(self, key):

/home/travis/sage/local/lib/python/collections.pyc in update(self, iterable, **kwds)
    533                 self_get = self.get
    534                 for elem in iterable:
--> 535                     self[elem] = self_get(elem, 0) + 1
    536         if kwds:
    537             self.update(kwds)

TypeError: unhashable type: 'list'

comment:6 Changed 4 years ago by ncohen

Oh. Great, thanks !!

Nathann

comment:7 Changed 4 years ago by tscrim

Working it down a little more. With this branch:

sage: Q = DiGraph({1:{2:['a','c']}, 2:{3:['b']}}, immutable=True, weighted=True)
sage: Q.weighted()
True
sage: hash(Q)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-15-9389487dfecf> in <module>()
----> 1 hash(Q)

/home/travis/sage/src/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (/home/travis/sage/src/build/cythonized/sage/misc/cachefunc.c:14346)()
   2213         if self.cache is None:
   2214             f = self.f
-> 2215             self.cache = f(self._instance)
   2216         return self.cache
   2217 

/home/travis/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.pyc in __hash__(self)
    579             return hash((frozenset(self.vertex_iterator()),
    580                          self._weighted,
--> 581                          frozenset(edge_items)))
    582         raise TypeError("This graph is mutable, and thus not hashable. "
    583                         "Create an immutable copy by `g.copy(immutable=True)`")

TypeError: unhashable type: 'list'

comment:8 Changed 4 years ago by tscrim

However this seems to work for normal graphs:

sage: Q = Graph({1:{2:['a','c']}, 2:{3:['b']}}, immutable=True, weighted=True)
sage: hash(Q)
2304336980638771825

comment:9 Changed 4 years ago by ncohen

Yeah yeah the problem is very simple: instead of creating several edges labelled 'a','b','c' it creates one edge with a list as a label. Which is not hashable.

Nathann

comment:10 follow-up: Changed 4 years ago by ncohen

I hate multiple edges, and I hate labels. Dozens of lines of copy/paste to handle stupid combinations of cases that nobody uses.

comment:11 Changed 4 years ago by git

  • Commit changed from cf53613abb473f53411b50bd2ddc049050cd6dbc to 99c8601b947b746cfd0cbbca4c836b82b3ac5dde

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

99c8601trac #19385: Dictionary of lists for a digraph with labelled multiple edges. How I wish I could forget those stupid things.

comment:12 Changed 4 years ago by ncohen

Fixed. Thanks for your help T_T

Nathann

comment:13 follow-up: Changed 4 years ago by tscrim

  • Reviewers set to Travis Scrimshaw

This LGTM except for this change:

-            sage: G = DiGraph(M,sparse=True); G
+            sage: G = DiGraph(M,sparse=True,weighted=True); G

I'm worried that this change of behavior of how you handle weighted graphs could break other people's code. Unfortunately I can't comment on the correctness of either behavior, but it might have been a "feature" that others were using.

comment:14 in reply to: ↑ 13 Changed 4 years ago by ncohen

I'm worried that this change of behavior of how you handle weighted graphs could break other people's code. Unfortunately I can't comment on the correctness of either behavior, but it might have been a "feature" that others were using.

If you build a graph from a matrix in which all weights are 1 it is not considered as weighted. If any weight is different from 1 then it is considered to be weighted.

To me, this looks like a dangerous behaviour.

Nathann

comment:15 Changed 4 years ago by ncohen

Do you insist on my adding a heuristic which you admit you do not use, which will set this unreliable behaviour to what it was? This way everybody will be able to create weighted graphs without knowing exactly how, and have bugs once in a while when all weights happen to be one.

It just takes one line, and it will be dedicated.

Nathann

comment:16 Changed 4 years ago by ncohen

Of course, if the matrix has weights different from +1-1 BUT the graph is considered to have multiple edges, then those weights will be considered as multiple edges.

This constructor is full of corner cases like that. Where we try to guess what exactly the user did not know he wanted.

Half of the code sets flags depending on the values of others. And I am sick of trying to analyse corner-cases where you are really not sure of what should happen.

Nathann

comment:17 Changed 4 years ago by ncohen

I don't even know what the default behaviour is when neither weighted nor mutiple edges is specified, and if the matrix has weights different from +1/-1. Will it be multiple edges? Will it be weights? *suspense*

sage: Graph(2*graphs.PetersenGraph().adjacency_matrix())
Multi-graph on 10 vertices

Wouhou ! It's multiple edges.

Nathann

comment:18 Changed 4 years ago by ncohen

Of course, if now some of the weights is not integer, then what will it be ?...

sage: Graph(0.5*graphs.PetersenGraph().adjacency_matrix())
Graph on 10 vertices
sage: Graph(0.5*graphs.PetersenGraph().adjacency_matrix()).weighted()
True

Weighted !!!!

Nathann

comment:19 Changed 4 years ago by ncohen

So please, help me and let us drop those unsufferable behaviour that makes this code 90% bullshit trying to figure out some sensible interpretation for the many kind of garbage that it accepts.

comment:20 follow-up: Changed 4 years ago by tscrim

If you are willing to help whoever posts to sage-devel asking why their weighted graph code no longers works, than you can set a positive review to this.

comment:21 in reply to: ↑ 10 Changed 4 years ago by SimonKing

Replying to ncohen:

I hate multiple edges, and I hate labels. Dozens of lines of copy/paste to handle stupid combinations of cases that nobody uses.

I do use multiple edges, loops and labels.

comment:22 follow-up: Changed 4 years ago by SimonKing

I believe explicit is better than implicit. And it induces a very bad gut feeling when c*G for a graph G returns a weighted graph or a multi-graph depending on whether c is integer or rational.

comment:23 in reply to: ↑ 22 Changed 4 years ago by ncohen

I believe explicit is better than implicit. And it induces a very bad gut feeling when c*G for a graph G returns a weighted graph or a multi-graph depending on whether c is integer or rational.

+1 here. Not only it drives me mad, but the code has to deal with all that and decide it (and God it is ugly), and of course this comes at the cost of over-analysing the input, which takes time.

Nathann

comment:24 in reply to: ↑ 20 Changed 4 years ago by ncohen

  • Status changed from needs_review to positive_review

If you are willing to help whoever posts to sage-devel asking why their weighted graph code no longers works, than you can set a positive review to this.

Gladly. Anyway, I prefer to explain why people have to be explicit in what they want rather than explain the 10 different combinations of parameters that [will/will not] yield what they expect.

Thank you.

Nathann

comment:25 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work

Documentation doesn't build as is evident from the patchbot log

comment:26 Changed 4 years ago by git

  • Commit changed from 99c8601b947b746cfd0cbbca4c836b82b3ac5dde to d09d3847fcf55f661e9be98cd4dfb3226e8d9a9d

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

57d73bftrac #19385: Merged with 6.9
d09d384trac #19385: <insert rant about loops and multiple edges>

comment:27 Changed 4 years ago by git

  • Commit changed from d09d3847fcf55f661e9be98cd4dfb3226e8d9a9d to ced36581c5258b40dc9e72a986fbaa9b7e12a8cc

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

ced3658trac #19385: Typo T_T

comment:28 Changed 4 years ago by ncohen

  • Status changed from needs_work to positive_review

Sorry :-/

comment:29 Changed 4 years ago by vbraun

  • Branch changed from u/ncohen/19385 to ced36581c5258b40dc9e72a986fbaa9b7e12a8cc
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.