#6041 closed enhancement (duplicate)
update NetworkX to version 0.99
Reported by: | mvngu | Owned by: | rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | graph theory | Keywords: | |
Cc: | rlm, jason | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
As the subject says. This is a follow-up to #5934.
Change History (10)
comment:1 Changed 12 years ago by
- Milestone set to sage-4.0.1
comment:2 Changed 12 years ago by
- Summary changed from update NetworkX to version 0.99 to [with spkg, needs work] update NetworkX to version 0.99
You should definitely get a good night's sleep before you tackle that!
I would suggest you start by seeing what needs to be fixed to get the doctests in
devel/sage-main/sage/graphs/base/graph_backends.py
to work properly. This is where Sage and NetworkX mainly plug in to each other. Once those are fixed, I expect much of the rest will be already done.
comment:3 follow-up: ↓ 4 Changed 12 years ago by
I managed to get all doctests in sage/graphs/base/graph_backends.py
to pass, but at the expense of deleting the following methods from the class NetworkXGraphBackend
. Here I assume that NetworkXGraphBackend
is an undirected graph without multiple edges.
loops
-- This is irrelevant with the API changes in NetworkX 0.99, since the classGraph
from NetworkX 0.99 allows for self-loops without having to explicitly set it with a boolean.multiple_edges
-- Again irrelevant since the classGraph
doesn't allow multiple edges. Graphs with multiple edges should now be constructed via the classMultiGraph
(not directed), orMultiDiGraph
which allows for directed arcs.
Here's a diff of the changes to sage/graphs/base/graph_backends.py
:
diff -r 21c6c829ea32 sage/graphs/base/graph_backends.py --- a/sage/graphs/base/graph_backends.py Sat May 16 09:46:59 2009 -0700 +++ b/sage/graphs/base/graph_backends.py Tue May 19 23:47:29 2009 -0700 @@ -499,13 +499,12 @@ """ if N is None: import networkx - N = networkx.XGraph() + N = networkx.Graph() self._nxg = N - def add_edge(self, u, v, l, directed): + def add_edge(self, u, v, l): """ - Add an edge (u,v) to self, with label l. If directed is True, this is - interpreted as an arc from u to v. + Add an edge (u,v) to self, with label l. INPUT: u,v: vertices @@ -514,11 +513,11 @@ DOCTEST: sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend() - sage: G.add_edge(1,2,'a',True) + sage: G.add_edge(1, 2, "a") """ self._nxg.add_edge(u, v, l) - def add_edges(self, edges, directed): + def add_edges(self, edges): """ Add a sequence of edges to self. If directed is True, these are interpreted as arcs. @@ -529,7 +528,7 @@ DOCTEST: sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend() - sage: G.add_edges([],True) + sage: G.add_edges([]) """ for e in edges: try: @@ -537,7 +536,7 @@ except: u,v = e l = None - self.add_edge(u,v,l,directed) + self.add_edge(u, v, l) def add_vertex(self, name): """ @@ -589,7 +588,7 @@ """ return self._nxg.degree(v) - def del_edge(self, u, v, l, directed): + def del_edge(self, u, v, l): """ Deletes the edge (u,v) with label l. @@ -600,9 +599,10 @@ DOCTEST: sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend() - sage: G.del_edge(1,2,'a',True) + sage: G.add_edge(1, 2, "a") + sage: G.del_edge(1, 2, "a") """ - self._nxg.delete_edge(u, v, l) + self._nxg.delete_edge(u, v) def del_vertex(self, v): """ @@ -649,16 +649,16 @@ DOCTEST: sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend() - sage: G.get_edge_label(1,2) + sage: G.get_edge_label(1, 2) Traceback (most recent call last): ... - NetworkXError: Edge (1,2) requested via get_edge does not exist. + NetworkXError: edge (1,2) not in graph """ return self._nxg.get_edge(u, v) - def has_edge(self, u, v, l): + def has_edge(self, u, v): """ - True if self has an edge (u,v) with label l. + True if self has an edge (u,v). INPUT: u,v: vertex labels @@ -669,10 +669,19 @@ DOCTEST: sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend() - sage: G.has_edge(1,2,'a') + sage: G.has_edge(1, 2) False """ - return self._nxg.has_edge(u, v, l) + return self._nxg.has_edge(u, v) + + def has_selfloops(self): + """ + Returns ``True`` if this graph has self-loops; ``False`` otherwise. + """ + if self._nxg.number_of_selfloops() > 0: + return True + else: + return False def has_vertex(self, v): """ @@ -781,8 +790,9 @@ DOCTEST: sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend() + sage: G.add_edges([(0,1), (0,2), (1,2)]) sage: G.iterator_nbrs(0) - <generator object at ...> + <dictionary-keyiterator object at ...> """ return self._nxg.neighbors_iter(v) @@ -802,7 +812,7 @@ sage: G.iterator_in_nbrs(0) Traceback (most recent call last): ... - AttributeError: 'XGraph' object has no attribute 'predecessors_iter' + AttributeError: 'Graph' object has no attribute 'predecessors_iter' """ return self._nxg.predecessors_iter(v) @@ -822,7 +832,7 @@ sage: G.iterator_out_nbrs(0) Traceback (most recent call last): ... - AttributeError: 'XGraph' object has no attribute 'successors_iter' + AttributeError: 'Graph' object has no attribute 'successors_iter' """ return self._nxg.successors_iter(v) @@ -839,49 +849,9 @@ DOCTEST: sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend() sage: G.iterator_verts(0) - <listiterator object at ...> + <generator object at ...> """ - return iter(self._nxg.prepare_nbunch(verts)) - - def loops(self, new): - """ - Get/set whether or not self allows loops. - - INPUT: - new: boolean or None - - DOCTEST: - sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend() - sage: G.loops(True) - sage: G.loops(None) - True - """ - if new is None: - return self._nxg.selfloops - if new: - self._nxg.allow_selfloops() - else: - self._nxg.ban_selfloops() - - def multiple_edges(self, new): - """ - Get/set whether or not self allows multiple edges. - - INPUT: - new: boolean or None - - DOCTEST: - sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend() - sage: G.multiple_edges(True) - sage: G.multiple_edges(None) - True - """ - if new is None: - return self._nxg.multiedges - if new: - self._nxg.allow_multiedges() - else: - self._nxg.ban_multiedges() + return iter(self._nxg.nbunch_iter(verts)) def name(self, new): """ @@ -969,39 +939,24 @@ newd[perm[v]] = newtempd self._nxg.adj = newd - def set_edge_label(self, u, v, l, directed): + def set_edge_label(self, u, v, l): """ Label the edge (u,v) by l. INPUT: u,v: vertices l: edge label - directed: boolean DOCTEST: sage: G = sage.graphs.base.graph_backends.NetworkXGraphBackend() - sage: G.set_edge_label(1,2,'a',True) + sage: # G is empty graph, so it doesn't have the edge (1,2) + sage: G.set_edge_label(1, 2, "a") + sage: # add some edges to G + sage: G.add_edges([(1,2), (1,3), (2,3)]) + sage: G.set_edge_label(1, 2, "b") """ - if not self.has_edge(u, v, None): + if not self.has_edge(u, v): return - if self.multiple_edges(None): - if directed: - self._nxg.succ[u][v] = [l] - self._nxg.pred[v][u] = [l] - else: - self._nxg.adj[u][v] = [l] - self._nxg.adj[v][u] = [l] else: - if directed: - self._nxg.succ[u][v] = l - self._nxg.pred[v][u] = l - else: - self._nxg.adj[u][v] = l - self._nxg.adj[v][u] = l - - - - - - - + self._nxg.adj[u][v] = l + self._nxg.adj[v][u] = l
But the following doctests failed:
sage -t -long "devel/sage-6041/sage/graphs/graph_bundle.py" sage -t -long "devel/sage-6041/sage/graphs/graph_generators.py" sage -t -long "devel/sage-6041/sage/graphs/planarity.pyx" sage -t -long "devel/sage-6041/sage/graphs/graph_fast.pyx" sage -t -long "devel/sage-6041/sage/graphs/graph_isom.pyx" sage -t -long "devel/sage-6041/sage/graphs/schnyder.py" sage -t -long "devel/sage-6041/sage/graphs/graph_coloring.py" sage -t -long "devel/sage-6041/sage/graphs/graph.py" sage -t -long "devel/sage-6041/sage/graphs/chrompoly.pyx" sage -t -long "devel/sage-6041/sage/graphs/print_graphs.py" sage -t -long "devel/sage-6041/sage/graphs/graph_plot.py" sage -t -long "devel/sage-6041/sage/graphs/graph_list.py" sage -t -long "devel/sage-6041/sage/graphs/graph_database.py" sage -t -long "devel/sage-6041/sage/graphs/base/dense_graph.pyx" sage -t -long "devel/sage-6041/sage/graphs/base/sparse_graph.pyx" sage -t -long "devel/sage-6041/sage/graphs/base/c_graph.pyx" sage -t -long "devel/sage-6041/sage/graphs/bipartite_graph.py" sage -t -long "devel/sage-6041/sage/graphs/linearextensions.py" sage -t -long "devel/sage-6041/sage/graphs/base/dense_graph.pyx" sage -t -long "devel/sage-6041/sage/graphs/base/sparse_graph.pyx" sage -t -long "devel/sage-6041/sage/graphs/base/c_graph.pyx"
It looks like anything under sage/graphs/
that uses sage/graphs/base/graph_backends.py
should be changed accordingly.
comment:4 in reply to: ↑ 3 ; follow-up: ↓ 5 Changed 12 years ago by
Replying to mvngu:
I managed to get all doctests in
sage/graphs/base/graph_backends.py
to pass, but at the expense of deleting the following methods from the classNetworkXGraphBackend
. Here I assume thatNetworkXGraphBackend
is an undirected graph without multiple edges.
Incorrect. NetworkXGraphBackend is simply a wrapper for a NetworkX graph, which can be directed, or have multiple edges.
loops
-- This is irrelevant with the API changes in NetworkX 0.99, since the classGraph
from NetworkX 0.99 allows for self-loops without having to explicitly set it with a boolean.multiple_edges
-- Again irrelevant since the classGraph
doesn't allow multiple edges. Graphs with multiple edges should now be constructed via the classMultiGraph
(not directed), orMultiDiGraph
which allows for directed arcs.
This isn't irrelevant, as *Sage* graphs can have loops or multiedges set. What needs to happen is for loops and multiedges to become properties of the backend, and for the appropriate work to go on there. We still need to support these options. You should be working on top of the part-1
patch at #6085, since it implements part of this in graph.py
(and so that we're less likely to be stepping on each other's toes).
Here's a diff of the changes to
sage/graphs/base/graph_backends.py
:
Next time you could probably attach the diff to the ticket... :)
It looks like anything under
sage/graphs/
that usessage/graphs/base/graph_backends.py
should be changed accordingly.
Don't forget all of the rest of Sage! I think you'll find it much easier to adapt the backend to behave exactly as before. Then, all the other doctests should pass - that's what they're there for!
comment:5 in reply to: ↑ 4 ; follow-up: ↓ 6 Changed 12 years ago by
Replying to rlm:
Replying to mvngu:
I managed to get all doctests in
sage/graphs/base/graph_backends.py
to pass, but at the expense of deleting the following methods from the classNetworkXGraphBackend
. Here I assume thatNetworkXGraphBackend
is an undirected graph without multiple edges.Incorrect. NetworkXGraphBackend is simply a wrapper for a NetworkX graph, which can be directed, or have multiple edges.
Agreed. Version 0.99 now has:
Graph
--- An undirected graph class without multiple (parallel) edges.DiGraph
--- A directed graph that allows self-loops, but not multiple (parallel) edges.MultiGraph
--- An undirected graph that allows multiple (parallel) edges with arbitrary data on the edges.MultiDiGraph
--- A directed graph that allows multiple (parallel) edges with arbitrary data on the edges.
These have been lifted off from the NetworkX 0.99 documentation. MultiGraph
is the successor to XGraph
where we allow XGraph
to have multiple edges. And MultiDiGraph
is the successor to XDiGraph
with multiple edges. According to the API change log at
http://networkx.lanl.gov/reference/api_changes.html
Previously XGraph
handle undirected graphs with or without multiple edges, and XDiGraph
handle directed graphs with or without multiple edges. Now there are four graph classes instead of two, for handling the different types of graphs.
loops
-- This is irrelevant with the API changes in NetworkX 0.99, since the classGraph
from NetworkX 0.99 allows for self-loops without having to explicitly set it with a boolean.multiple_edges
-- Again irrelevant since the classGraph
doesn't allow multiple edges. Graphs with multiple edges should now be constructed via the classMultiGraph
(not directed), orMultiDiGraph
which allows for directed arcs.This isn't irrelevant, as *Sage* graphs can have loops or multiedges set. What needs to happen is for loops and multiedges to become properties of the backend, and for the appropriate work to go on there. We still need to support these options. You should be working on top of the
part-1
patch at #6085, since it implements part of this ingraph.py
(and so that we're less likely to be stepping on each other's toes).
Thanks you for the pointer.
Here's a diff of the changes to
sage/graphs/base/graph_backends.py
:Next time you could probably attach the diff to the ticket... :)
No, the diff isn't meant to be committed in the future. It's there for discussion and to explore ways to maintain compatibility with the existing API in graph_backends.py
. But as you can see, the diff clearly breaks compatibility :-)
It looks like anything under
sage/graphs/
that usessage/graphs/base/graph_backends.py
should be changed accordingly.Don't forget all of the rest of Sage! I think you'll find it much easier to adapt the backend to behave exactly as before. Then, all the other doctests should pass - that's what they're there for!
OK, let me see what I can do.
comment:6 in reply to: ↑ 5 Changed 12 years ago by
Replying to mvngu:
Replying to rlm:
Replying to mvngu:
Previously
XGraph
handle undirected graphs with or without multiple edges, andXDiGraph
handle directed graphs with or without multiple edges. Now there are four graph classes instead of two, for handling the different types of graphs.
Actually, there were also Graph
and DiGraph
, which did not have labels...
Here's a diff of the changes to
sage/graphs/base/graph_backends.py
:Next time you could probably attach the diff to the ticket... :)
No, the diff isn't meant to be committed in the future. It's there for discussion and to explore ways to maintain compatibility with the existing API in
graph_backends.py
.
You can still post diffs as attachments. It makes the discussion much easier to follow when you're reading the ticket, and it keeps clutter down. Just add the note "not to be applied" if you're worried...
It looks like anything under
sage/graphs/
that usessage/graphs/base/graph_backends.py
should be changed accordingly.Don't forget all of the rest of Sage! I think you'll find it much easier to adapt the backend to behave exactly as before. Then, all the other doctests should pass - that's what they're there for!
OK, let me see what I can do.
It should be possible to get all of the doctests in Sage working by changing only things which call networkx
directly (i.e. things involving import networkx
), and the NetworkXGraphBackend
class in graph_backends.py
. Keep in mind that there are several interchangeable backends. In your diff, you were actually changing the signature of some of the backend functions-- this is bad.
comment:7 Changed 12 years ago by
There is another patch at #6085 now: You should be working on top of part-1
and part-2
.
comment:8 Changed 12 years ago by
- Cc jason added
comment:9 Changed 11 years ago by
- Milestone changed from sage-4.3 to sage-duplicate/invalid/wontfix
- Report Upstream set to N/A
- Resolution set to duplicate
- Status changed from needs_work to closed
- Summary changed from [with spkg, needs work] update NetworkX to version 0.99 to update NetworkX to version 0.99
This ticket is now a duplicate of #7608. The latter has a patch and an updated NetworkX 1.0rc1 package.
A new spkg is up at
http://sage.math.washington.edu/home/mvngu/patch/networkx-0.99.p1.spkg
Unfortunately, as I suspected version 0.99 of NetworkX breaks a lot of doctests:
I'll upload patches against the relevant modules shortly, unless someone who is awake beats me to it (I'm going to sleep now :-).