prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  `OrderedGraph.subgraph` does not maintain the order of the nodes
  A subgraph built from a `OrderedGraph` should keep the order of the nodes, yet nodes in the subgraph are neither in the order of the initial graph, nor in the order of the selection. The issue can be seen from the following snippet:
  
  ```python
  graph = nx.OrderedGraph()
  nodes = list(range(10))
  random.shuffle(nodes)
  graph.add_nodes_from(nodes)  # key order is (7, 2, 1, 9, 0, 8, 6, 4, 3, 5)
  
  # We create a selection in the same order as the initial graph keys
  to_keep = [key for key in graph if key % 2 == 0]  # [2, 0, 8, 6, 4]
  subgraph = graph.subgraph(to_keep)  # (0, 2, 4, 6, 8)
  
  # We create a selection in a different order
  subgraph = graph.subgraph([5, 3, 1])  # (1, 3, 5)
  ```
  
  From what I see, the issue is due to `Graph.subgraph` passing the selection to `nx.filters.show_nodes` that transforms it to a set. The nodes in the subgraph are then in the order of the set; as sets do not preserve the order, the order of the initial graph if not preserved.
  
  </issue>
  <code>
  [start of networkx/classes/ordered.py]
  1 """
  2 Consistently ordered variants of the default base classes.
  3 
  4 The Ordered (Di/Multi/MultiDi) Graphs give a consistent order for reporting of
  5 nodes and edges.  The order of node reporting agrees with node adding, but for
  6 edges, the order is not necessarily the order that the edges were added.
  7 
  8 In general, you should use the default (i.e., unordered) graph classes.
  9 However, there are times (e.g., when testing) when you may need the
  10 order preserved.
  11 """
  12 from collections import OrderedDict
  13 
  14 from .graph import Graph
  15 from .multigraph import MultiGraph
  16 from .digraph import DiGraph
  17 from .multidigraph import MultiDiGraph
  18 
  19 __all__ = []
  20 
  21 __all__.extend([
  22     'OrderedGraph',
  23     'OrderedDiGraph',
  24     'OrderedMultiGraph',
  25     'OrderedMultiDiGraph',
  26 ])
  27 
  28 
  29 class OrderedGraph(Graph):
  30     """Consistently ordered variant of :class:`~networkx.Graph`."""
  31     node_dict_factory = OrderedDict
  32     adjlist_outer_dict_factory = OrderedDict
  33     adjlist_inner_dict_factory = OrderedDict
  34     edge_attr_dict_factory = OrderedDict
  35 
  36     def fresh_copy(self):
  37         """Return a fresh copy graph with the same data structure.
  38 
  39         A fresh copy has no nodes, edges or graph attributes. It is
  40         the same data structure as the current graph. This method is
  41         typically used to create an empty version of the graph.
  42         """
  43         return OrderedGraph()
  44 
  45 
  46 class OrderedDiGraph(DiGraph):
  47     """Consistently ordered variant of :class:`~networkx.DiGraph`."""
  48     node_dict_factory = OrderedDict
  49     adjlist_outer_dict_factory = OrderedDict
  50     adjlist_inner_dict_factory = OrderedDict
  51     edge_attr_dict_factory = OrderedDict
  52 
  53     def fresh_copy(self):
  54         """Return a fresh copy graph with the same data structure.
  55 
  56         A fresh copy has no nodes, edges or graph attributes. It is
  57         the same data structure as the current graph. This method is
  58         typically used to create an empty version of the graph.
  59         """
  60         return OrderedDiGraph()
  61 
  62 
  63 class OrderedMultiGraph(MultiGraph):
  64     """Consistently ordered variant of :class:`~networkx.MultiGraph`."""
  65     node_dict_factory = OrderedDict
  66     adjlist_outer_dict_factory = OrderedDict
  67     adjlist_inner_dict_factory = OrderedDict
  68     edge_key_dict_factory = OrderedDict
  69     edge_attr_dict_factory = OrderedDict
  70 
  71     def fresh_copy(self):
  72         """Return a fresh copy graph with the same data structure.
  73 
  74         A fresh copy has no nodes, edges or graph attributes. It is
  75         the same data structure as the current graph. This method is
  76         typically used to create an empty version of the graph.
  77         """
  78         return OrderedMultiGraph()
  79 
  80 
  81 class OrderedMultiDiGraph(MultiDiGraph):
  82     """Consistently ordered variant of :class:`~networkx.MultiDiGraph`."""
  83     node_dict_factory = OrderedDict
  84     adjlist_outer_dict_factory = OrderedDict
  85     adjlist_inner_dict_factory = OrderedDict
  86     edge_key_dict_factory = OrderedDict
  87     edge_attr_dict_factory = OrderedDict
  88 
  89     def fresh_copy(self):
  90         """Return a fresh copy graph with the same data structure.
  91 
  92         A fresh copy has no nodes, edges or graph attributes. It is
  93         the same data structure as the current graph. This method is
  94         typically used to create an empty version of the graph.
  95         """
  96         return OrderedMultiDiGraph()
  97
  [end of networkx/classes/ordered.py]
  </code>
  
  I need you to solve this issue by generating a single patch file that I can apply directly to this repository using git apply. Please respond with a single patch file in the following format.
  <patch>
  diff --git a/file.py b/file.py
  --- a/file.py
  +++ b/file.py
  @@ -1,27 +1,35 @@
   def euclidean(a, b):
  -    while b:
  -        a, b = b, a % b
  -    return a
  +    if b == 0:
  +        return a
  +    return euclidean(b, a % b)
   
   
   def bresenham(x0, y0, x1, y1):
       points = []
       dx = abs(x1 - x0)
       dy = abs(y1 - y0)
  -    sx = 1 if x0 < x1 else -1
  -    sy = 1 if y0 < y1 else -1
  -    err = dx - dy
  +    x, y = x0, y0
  +    sx = -1 if x0 > x1 else 1
  +    sy = -1 if y0 > y1 else 1
   
  -    while True:
  -        points.append((x0, y0))
  -        if x0 == x1 and y0 == y1:
  -            break
  -        e2 = 2 * err
  -        if e2 > -dy:
  -            err -= dy
  -            x0 += sx
  -        if e2 < dx:
  -            err += dx
  -            y0 += sy
  +    if dx > dy:
  +        err = dx / 2.0
  +        while x != x1:
  +            points.append((x, y))
  +            err -= dy
  +            if err < 0:
  +                y += sy
  +                err += dx
  +            x += sx
  +    else:
  +        err = dy / 2.0
  +        while y != y1:
  +            points.append((x, y))
  +            err -= dx
  +            if err < 0:
  +                x += sx
  +                err += dy
  +            y += sy
  +
  +    points.append((x, y))
       return points
  
  </patch>
golden_diff: diff --git a/networkx/classes/ordered.py b/networkx/classes/ordered.py
  --- a/networkx/classes/ordered.py
  +++ b/networkx/classes/ordered.py
  @@ -1,5 +1,10 @@
   """
   Consistently ordered variants of the default base classes.
  +Note that if you are using Python 3.6, you shouldn't need these classes
  +because the dicts in Python 3.6 are ordered.
  +Note also that there are many differing expectations for the word "ordered"
  +and that these classes may not provide the order you expect.
  +The intent here is to give a consistent order not a particular order.
   
   The Ordered (Di/Multi/MultiDi) Graphs give a consistent order for reporting of
   nodes and edges.  The order of node reporting agrees with node adding, but for
  @@ -8,6 +13,17 @@
   In general, you should use the default (i.e., unordered) graph classes.
   However, there are times (e.g., when testing) when you may need the
   order preserved.
  +
  +Special care is required when using subgraphs of the Ordered classes.
  +The order of nodes in the subclass is not necessarily the same order
  +as the original class.  In general it is probably better to avoid using
  +subgraphs and replace with code similar to:
  +
  +    # instead of SG = G.subgraph(ordered_nodes)
  +    SG=nx.OrderedGraph()
  +    SG.add_nodes_from(ordered_nodes)
  +    SG.add_edges_from((u, v) for (u, v) in G.edges() if u in SG if v in SG)
  +
   """
   from collections import OrderedDict
  
verification_info: {"golden_diff": "diff --git a/networkx/classes/ordered.py b/networkx/classes/ordered.py\n--- a/networkx/classes/ordered.py\n+++ b/networkx/classes/ordered.py\n@@ -1,5 +1,10 @@\n \"\"\"\n Consistently ordered variants of the default base classes.\n+Note that if you are using Python 3.6, you shouldn't need these classes\n+because the dicts in Python 3.6 are ordered.\n+Note also that there are many differing expectations for the word \"ordered\"\n+and that these classes may not provide the order you expect.\n+The intent here is to give a consistent order not a particular order.\n \n The Ordered (Di/Multi/MultiDi) Graphs give a consistent order for reporting of\n nodes and edges.  The order of node reporting agrees with node adding, but for\n@@ -8,6 +13,17 @@\n In general, you should use the default (i.e., unordered) graph classes.\n However, there are times (e.g., when testing) when you may need the\n order preserved.\n+\n+Special care is required when using subgraphs of the Ordered classes.\n+The order of nodes in the subclass is not necessarily the same order\n+as the original class.  In general it is probably better to avoid using\n+subgraphs and replace with code similar to:\n+\n+    # instead of SG = G.subgraph(ordered_nodes)\n+    SG=nx.OrderedGraph()\n+    SG.add_nodes_from(ordered_nodes)\n+    SG.add_edges_from((u, v) for (u, v) in G.edges() if u in SG if v in SG)\n+\n \"\"\"\n from collections import OrderedDict\n", "issue": "`OrderedGraph.subgraph` does not maintain the order of the nodes\nA subgraph built from a `OrderedGraph` should keep the order of the nodes, yet nodes in the subgraph are neither in the order of the initial graph, nor in the order of the selection. The issue can be seen from the following snippet:\r\n\r\n```python\r\ngraph = nx.OrderedGraph()\r\nnodes = list(range(10))\r\nrandom.shuffle(nodes)\r\ngraph.add_nodes_from(nodes)  # key order is (7, 2, 1, 9, 0, 8, 6, 4, 3, 5)\r\n\r\n# We create a selection in the same order as the initial graph keys\r\nto_keep = [key for key in graph if key % 2 == 0]  # [2, 0, 8, 6, 4]\r\nsubgraph = graph.subgraph(to_keep)  # (0, 2, 4, 6, 8)\r\n\r\n# We create a selection in a different order\r\nsubgraph = graph.subgraph([5, 3, 1])  # (1, 3, 5)\r\n```\r\n\r\nFrom what I see, the issue is due to `Graph.subgraph` passing the selection to `nx.filters.show_nodes` that transforms it to a set. The nodes in the subgraph are then in the order of the set; as sets do not preserve the order, the order of the initial graph if not preserved.\n", "before_files": [{"content": "\"\"\"\nConsistently ordered variants of the default base classes.\n\nThe Ordered (Di/Multi/MultiDi) Graphs give a consistent order for reporting of\nnodes and edges.  The order of node reporting agrees with node adding, but for\nedges, the order is not necessarily the order that the edges were added.\n\nIn general, you should use the default (i.e., unordered) graph classes.\nHowever, there are times (e.g., when testing) when you may need the\norder preserved.\n\"\"\"\nfrom collections import OrderedDict\n\nfrom .graph import Graph\nfrom .multigraph import MultiGraph\nfrom .digraph import DiGraph\nfrom .multidigraph import MultiDiGraph\n\n__all__ = []\n\n__all__.extend([\n    'OrderedGraph',\n    'OrderedDiGraph',\n    'OrderedMultiGraph',\n    'OrderedMultiDiGraph',\n])\n\n\nclass OrderedGraph(Graph):\n    \"\"\"Consistently ordered variant of :class:`~networkx.Graph`.\"\"\"\n    node_dict_factory = OrderedDict\n    adjlist_outer_dict_factory = OrderedDict\n    adjlist_inner_dict_factory = OrderedDict\n    edge_attr_dict_factory = OrderedDict\n\n    def fresh_copy(self):\n        \"\"\"Return a fresh copy graph with the same data structure.\n\n        A fresh copy has no nodes, edges or graph attributes. It is\n        the same data structure as the current graph. This method is\n        typically used to create an empty version of the graph.\n        \"\"\"\n        return OrderedGraph()\n\n\nclass OrderedDiGraph(DiGraph):\n    \"\"\"Consistently ordered variant of :class:`~networkx.DiGraph`.\"\"\"\n    node_dict_factory = OrderedDict\n    adjlist_outer_dict_factory = OrderedDict\n    adjlist_inner_dict_factory = OrderedDict\n    edge_attr_dict_factory = OrderedDict\n\n    def fresh_copy(self):\n        \"\"\"Return a fresh copy graph with the same data structure.\n\n        A fresh copy has no nodes, edges or graph attributes. It is\n        the same data structure as the current graph. This method is\n        typically used to create an empty version of the graph.\n        \"\"\"\n        return OrderedDiGraph()\n\n\nclass OrderedMultiGraph(MultiGraph):\n    \"\"\"Consistently ordered variant of :class:`~networkx.MultiGraph`.\"\"\"\n    node_dict_factory = OrderedDict\n    adjlist_outer_dict_factory = OrderedDict\n    adjlist_inner_dict_factory = OrderedDict\n    edge_key_dict_factory = OrderedDict\n    edge_attr_dict_factory = OrderedDict\n\n    def fresh_copy(self):\n        \"\"\"Return a fresh copy graph with the same data structure.\n\n        A fresh copy has no nodes, edges or graph attributes. It is\n        the same data structure as the current graph. This method is\n        typically used to create an empty version of the graph.\n        \"\"\"\n        return OrderedMultiGraph()\n\n\nclass OrderedMultiDiGraph(MultiDiGraph):\n    \"\"\"Consistently ordered variant of :class:`~networkx.MultiDiGraph`.\"\"\"\n    node_dict_factory = OrderedDict\n    adjlist_outer_dict_factory = OrderedDict\n    adjlist_inner_dict_factory = OrderedDict\n    edge_key_dict_factory = OrderedDict\n    edge_attr_dict_factory = OrderedDict\n\n    def fresh_copy(self):\n        \"\"\"Return a fresh copy graph with the same data structure.\n\n        A fresh copy has no nodes, edges or graph attributes. It is\n        the same data structure as the current graph. This method is\n        typically used to create an empty version of the graph.\n        \"\"\"\n        return OrderedMultiDiGraph()\n", "path": "networkx/classes/ordered.py"}]}