payload: {"action":"created","issue":{"url":"https://api.github.com/repos/networkx/networkx/issues/3480","repository_url":"https://api.github.com/repos/networkx/networkx","labels_url":"https://api.github.com/repos/networkx/networkx/issues/3480/labels{/name}","comments_url":"https://api.github.com/repos/networkx/networkx/issues/3480/comments","events_url":"https://api.github.com/repos/networkx/networkx/issues/3480/events","html_url":"https://github.com/networkx/networkx/issues/3480","id":454856328,"node_id":"MDU6SXNzdWU0NTQ4NTYzMjg=","number":3480,"title":"Network simplex does not terminate in certain cases","user":{"login":"plammens","id":18049056,"node_id":"MDQ6VXNlcjE4MDQ5MDU2","avatar_url":"https://avatars2.githubusercontent.com/u/18049056?v=4","gravatar_id":"","url":"https://api.github.com/users/plammens","html_url":"https://github.com/plammens","followers_url":"https://api.github.com/users/plammens/followers","following_url":"https://api.github.com/users/plammens/following{/other_user}","gists_url":"https://api.github.com/users/plammens/gists{/gist_id}","starred_url":"https://api.github.com/users/plammens/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/plammens/subscriptions","organizations_url":"https://api.github.com/users/plammens/orgs","repos_url":"https://api.github.com/users/plammens/repos","events_url":"https://api.github.com/users/plammens/events{/privacy}","received_events_url":"https://api.github.com/users/plammens/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2019-06-11T19:09:07Z","updated_at":"2019-06-12T08:13:23Z","closed_at":null,"author_association":"NONE","body":"The implementation of `networkx.network_simplex` does not terminate in certain specific cases in which the selection of the exiting basic variable while on a degenerate base forms an infinite cycle. The documentation says the implementation uses the \"leaving arc rule\" to prevent cycling, but apparently it's not working.\r\n\r\nI believe the culprit is the selection of the entering edge: \r\n\r\nhttps://github.com/networkx/networkx/blob/2db5f8663deacc501c7472c3a60884a2ca8be45a/networkx/algorithms/flow/networksimplex.py#L325-L326\r\n\r\nSelecting the entering nonbasic variable as the one with the minimum reduced cost is a known source of cycling in the general simplex algorithm, and I would believe it still applies here. It causes problems in those rare (in non-academic problems) cases in which a degenerate base is found.\r\n\r\nThe most straightforward solution is using [Bland's rule](https://en.wikipedia.org/wiki/Bland%27s_rule), which according to this comment is already implemented:\r\n\r\nhttps://github.com/networkx/networkx/blob/2db5f8663deacc501c7472c3a60884a2ca8be45a/networkx/algorithms/flow/networksimplex.py#L307-L310\r\n\r\nEven so, it's still cycling, so there's something wrong with the implementation.\r\n\r\nCC: @ysitu @loicseguin \r\n\r\n### Reproducible example\r\n\r\nSince it's hard to make a *minimal* reproducible example, I'll just show the specific case I was working on. I haven't been able to reproduce it otherwise, sorry.\r\n\r\nPreliminaries (these aren't actually relevant to the core of the problem itself, it's just what I was working on when I stumbled on this):\r\n\r\n```python\r\nfrom typing import Dict, Iterable, Set, Tuple\r\n\r\nimport math\r\nimport networkx as nx\r\nimport pandas as pd\r\nfrom haversine import Unit, haversine\r\nfrom haversine.haversine import _AVG_EARTH_RADIUS_KM\r\n\r\n# Constants\r\n_AVG_EARTH_RADIUS_M = 1000 * _AVG_EARTH_RADIUS_KM\r\n\r\n_URL_STATION_INFO = 'https://api.bsmsa.eu/ext/api/bsm/gbfs/v2/en/station_information'\r\n_URL_STATION_STATUS = 'https://api.bsmsa.eu/ext/api/bsm/gbfs/v2/en/station_status'\r\n_DATA_COLUMNS = ['lat', 'lon', 'num_bikes_available', 'num_docks_available']\r\n\r\n\r\nclass Coordinate:\r\n    \"\"\"Represents a geographical coordinate.\"\"\"\r\n    __slots__ = 'lat', 'lon'\r\n    lat: float  # latitude\r\n    lon: float  # longitude\r\n\r\n    def __init__(self, latitude: float, longitude: float):\r\n        self.lat = latitude\r\n        self.lon = longitude\r\n\r\n    def __iter__(self):\r\n        yield self.lat\r\n        yield self.lon\r\n\r\n    def __repr__(self):\r\n        return f'({self.lat}, {self.lon})'\r\n\r\n    def __str__(self):\r\n        return f'({self.lat}º N, {self.lon}º E)'\r\n\r\n\r\nclass StationWrapper:\r\n    \"\"\"\r\n    Wrapper for a Bicing station. Can be constructed from any object that has\r\n    the same attributes as the rows in the DataFrame returned by ``fetch_data``.\r\n    Implements some extra utilities on top of the data storage.\r\n    \"\"\"\r\n\r\n    def __init__(self, station):\r\n        self.__station = station\r\n\r\n    def __getattr__(self, item):\r\n        return getattr(self.__station, item)\r\n\r\n    def __repr__(self):\r\n        return repr(self.__station)\r\n\r\n    @property\r\n    def coords(self):\r\n        \"\"\"Get the coordinates for this station as a ``Coordinate`` object\"\"\"\r\n        return Coordinate(self.lat, self.lon)\r\n\r\n\r\nclass BicingGraph(nx.Graph):\r\n    def __init__(self, stations: Iterable, **attr):\r\n        super().__init__(**attr)\r\n        self.add_nodes_from(stations)\r\n        self._distance: float = 0.0\r\n\r\n    @classmethod\r\n    def from_dataframe(cls, stations: pd.DataFrame, **kwargs) -> 'BicingGraph':\r\n        rows = stations.itertuples(name='Station')\r\n        return cls(tuple(map(StationWrapper, rows)), **kwargs)\r\n\r\n    def construct_graph(self, dist: float):\r\n        \"\"\"\r\n        Construct geometric graph with a new distance\r\n        :param dist: new distance, in meters\r\n        \"\"\"\r\n        if dist < 0:\r\n            raise ValueError(\"distance should be non-negative\")\r\n\r\n        self.remove_edges_from(tuple(self.edges))  # No method to clear all edges in networkx's API\r\n        if dist > 0:\r\n            self._add_edges_in_grid(_DistanceGrid(self.nodes, dist), dist)\r\n        self._distance = dist\r\n\r\n    def _add_edges_in_grid(self, grid: '_DistanceGrid', dist: float):\r\n        \"\"\"\r\n        Helper method for ``construct_graph``. Adds edges among neighbouring\r\n        nodes in a pre-constructed grid.\r\n        :param grid: grid such that within each cell all nodes are within `dist`\r\n        meters apart\r\n        :param dist: distance\r\n        \"\"\"\r\n\r\n        def neighbours(cell_idx: Tuple[int, int]) -> Iterable[Tuple[int, int]]:\r\n            i, j = cell_idx\r\n            step_range = (0, -1, 1)\r\n            indices = ((i + di, j + dj) for di in step_range for dj in step_range)\r\n            next(indices)  # discard (i + 0, j + 0)\r\n            return indices\r\n\r\n        grid_dict = grid.cell_dict\r\n        for index, cell in grid_dict.items():\r\n            # connect neighbours:\r\n            for neighbour_index in neighbours(index):\r\n                neighbour = grid_dict.get(neighbour_index, tuple())  # default is empty cell\r\n                self.add_edges_from((a, b) for a in cell for b in neighbour\r\n                                    if distance(a, b) <= dist)\r\n            # mark cell as empty (to avoid repeated computations)\r\n            cell.clear()\r\n\r\n    def distribute(self, min_bikes: int, min_free_docks: int) -> Tuple[float, dict]:\r\n        if not isinstance(min_bikes, int) or not isinstance(min_free_docks, int) or \\\r\n                min_bikes < 0 or min_free_docks < 0:\r\n            raise ValueError(\"constraints should be non-negative integers\")\r\n\r\n        self._write_bike_demands(min_bikes, min_free_docks)\r\n        self._write_edge_costs()\r\n        return nx.network_simplex(self.to_directed(),\r\n                                  demand='bike_demand', weight='distance')\r\n\r\n    def _write_bike_demands(self, min_bikes: int, min_free_docks: int):\r\n        total_demand: int = 0\r\n\r\n        for node, attributes in self.nodes(data=True):\r\n            bikes, free_docks = node.num_bikes_available, node.num_docks_available\r\n            total_docks = bikes + free_docks\r\n            if total_docks < min_bikes + min_free_docks:\r\n                raise nx.NetworkXUnfeasible(\r\n                    f'cannot satisfy constraints min_bikes={min_bikes}, min_free_docks='\r\n                    f'{min_free_docks} on a station with {total_docks} total docks'\r\n                )\r\n\r\n            bike_deficit = ramp(min_bikes - bikes)\r\n            dock_deficit = ramp(min_free_docks - free_docks)\r\n            demand = bike_deficit or -dock_deficit\r\n            assert bikes + demand >= min_bikes\r\n            assert free_docks - demand >= min_free_docks\r\n\r\n            attributes['bike_demand'] = demand\r\n            total_demand += demand\r\n\r\n        self._distribute_surplus_demand(min_bikes, min_free_docks, total_demand)\r\n\r\n    def _distribute_surplus_demand(self, min_bikes: int, min_free_docks: int, total_demand: int):\r\n        gen = iter(self.nodes(data=True))\r\n        while total_demand < 0:\r\n            # Try to find free docks in which to place surplus bikes\r\n            node, attributes = next(gen)\r\n            demand = attributes['bike_demand']\r\n            free_docks = node.num_docks_available\r\n            surplus_docks = min([free_docks - demand - min_free_docks, -total_demand])\r\n            demand += surplus_docks\r\n\r\n            total_demand += surplus_docks\r\n            attributes['bike_demand'] = demand\r\n\r\n        while total_demand > 0:\r\n            # Try to find surplus bikes to satisfy demand\r\n            node, attributes = next(gen)\r\n            demand = attributes['bike_demand']\r\n            bikes = node.num_bikes_available\r\n            surplus_bikes = min([bikes + demand - min_free_docks, total_demand])\r\n            demand -= surplus_bikes\r\n            total_demand -= surplus_bikes\r\n            attributes['bike_demand'] = demand\r\n\r\n    def _write_edge_costs(self):\r\n        for u, v, attributes in self.edges(data=True):\r\n            attributes['distance'] = distance(u, v)\r\n\r\n\r\nclass _DistanceGrid:\r\n    \"\"\"\r\n    Helper class for the construction of a geometric graph; specifically, for\r\n    ``BicingGraph.construct_graph``. Represents a grid of geographical locations\r\n    such that each pair of points within a cell is less than a certain distance apart.\r\n    \"\"\"\r\n\r\n    def __init__(self, nodes: Iterable, dist: float):\r\n        \"\"\"Construct a grid with the given distance\r\n        :param nodes: iterable of geographical location objects (with 'lat' and 'lon' attributes)\r\n        :param dist: maximum distance between points in a single cell\r\n        \"\"\"\r\n        bottom_left = Coordinate(min(n.lat for n in nodes), min(n.lon for n in nodes))\r\n\r\n        delta_lat, delta_lon = self._get_degree_side_lengths(bottom_left.lat, dist)\r\n        grid = {}\r\n        for node in nodes:\r\n            lat_index = int((node.lat - bottom_left.lat) / delta_lat)\r\n            lon_index = int((node.lon - bottom_left.lon) / delta_lon)\r\n            grid.setdefault((lat_index, lon_index), set()).add(node)\r\n\r\n        self._grid: Dict[Tuple[int, int], Set] = grid\r\n\r\n    @property\r\n    def cell_dict(self) -> Dict[Tuple[int, int], Set]:\r\n        return self._grid\r\n\r\n    @staticmethod\r\n    def _get_degree_side_lengths(lat: float, dist: float) -> Tuple[float, float]:\r\n        \"\"\"\r\n        Calculate the (approximate) latitude/longitude degree-increments of the sides of a\r\n        \"square\" on the earth's surface such that any pair of points within it is at most\r\n        ``dist`` meters away. Here we assume the Earth is a sphere and we\r\n        approximate great-circle distances with planar distances.\r\n\r\n        :param lat: latitude degrees at which to perform computations\r\n        :param dist: maximum distance between points in a single cell\r\n        :return: the ``(latitude, longitude)`` degree increments\r\n        \"\"\"\r\n\r\n        # Scale the distance so that every pair of points in a (planar) square with this\r\n        # side length is at most ``self._distance`` meters apart:\r\n        side_length = dist\r\n\r\n        lat = math.radians(lat)\r\n        latitude_radius = _AVG_EARTH_RADIUS_M * math.cos(lat)\r\n        return math.degrees(side_length / _AVG_EARTH_RADIUS_M), \\\r\n               math.degrees(side_length / latitude_radius)\r\n\r\n\r\ndef distance(station1: StationWrapper, station2: StationWrapper) -> float:\r\n    \"\"\"Utility for the distance between two stations, in meters\"\"\"\r\n    return haversine(tuple(station1.coords), tuple(station2.coords), unit=Unit.METERS)\r\n\r\n\r\ndef fetch_stations() -> pd.DataFrame:\r\n    \"\"\"Fetches Bicing station data from the official database URL\"\"\"\r\n    info = _fetch_station_data_from_json(_URL_STATION_INFO)\r\n    status = _fetch_station_data_from_json(_URL_STATION_STATUS)\r\n    merged = info.join(status, how='inner')\r\n    return merged[_DATA_COLUMNS]\r\n\r\n\r\ndef _fetch_station_data_from_json(url: str) -> pd.DataFrame:\r\n    json_data = pd.read_json(url).data.stations\r\n    return pd.DataFrame.from_records(data=json_data, index='station_id')\r\n\r\n\r\ndef ramp(x):\r\n    \"\"\"\r\n    :param x: numeric value\r\n    :return: max{0, x}\r\n    \"\"\"\r\n    return x if x > 0 else 0\r\n```\r\n\r\nHere is the error producing code:\r\n\r\n```\r\nstations = fetch_stations()\r\ngraph = BicingGraph.from_dataframe(stations.iloc)\r\ngraph.construct_graph(10000.0)\r\ngraph.distribute(4, 3)\r\n```\r\n\r\nThe `nx.network_simplex(self.to_directed(), demand='bike_demand', weight='distance')` call in `BicingGraph.distribute` does not terminate.\r\n\r\n---------------\r\n\r\nI've confirmed this was a cycling issue by adding the following `print` statement in  [line 525 of `networkx.network_simplex`](https://github.com/networkx/networkx/blob/2db5f8663deacc501c7472c3a60884a2ca8be45a/networkx/algorithms/flow/networksimplex.py#L525):\r\n\r\n```python\r\n    ...\r\n    # Pivot loop\r\n    for i, p, q in find_entering_edges():\r\n        print(i, p, q)\r\n        Wn, We = find_cycle(i, p, q)\r\n        ...\r\n```\r\n\r\nWhile running the previous example this sequence repeated over and over:\r\n\r\n```text\r\n...\r\n212 250 106\r\n616 92 250\r\n1387 250 320\r\n74 250 37\r\n90 250 45\r\n160 250 80\r\n...\r\n```"},"comment":{"url":"https://api.github.com/repos/networkx/networkx/issues/comments/501168157","html_url":"https://github.com/networkx/networkx/issues/3480#issuecomment-501168157","issue_url":"https://api.github.com/repos/networkx/networkx/issues/3480","id":501168157,"node_id":"MDEyOklzc3VlQ29tbWVudDUwMTE2ODE1Nw==","user":{"login":"plammens","id":18049056,"node_id":"MDQ6VXNlcjE4MDQ5MDU2","avatar_url":"https://avatars2.githubusercontent.com/u/18049056?v=4","gravatar_id":"","url":"https://api.github.com/users/plammens","html_url":"https://github.com/plammens","followers_url":"https://api.github.com/users/plammens/followers","following_url":"https://api.github.com/users/plammens/following{/other_user}","gists_url":"https://api.github.com/users/plammens/gists{/gist_id}","starred_url":"https://api.github.com/users/plammens/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/plammens/subscriptions","organizations_url":"https://api.github.com/users/plammens/orgs","repos_url":"https://api.github.com/users/plammens/repos","events_url":"https://api.github.com/users/plammens/events{/privacy}","received_events_url":"https://api.github.com/users/plammens/received_events","type":"User","site_admin":false},"created_at":"2019-06-12T08:13:23Z","updated_at":"2019-06-12T08:13:23Z","author_association":"NONE","body":"Alright, I think this was totally my fault. I was using `float`s as edge weights. It works when I convert to `int`. Sorry."}}
other: {"actor":{"display_login":"plammens"}}