| Name | scgraph JSON |
| Version |
2.3.0
JSON |
| download |
| home_page | None |
| Summary | Determine an approximate route between two points on earth. |
| upload_time | 2024-06-13 14:51:04 |
| maintainer | None |
| docs_url | None |
| author | None |
| requires_python | >=3.10 |
| license | None |
| keywords |
|
| VCS |
 |
| bugtrack_url |
|
| requirements |
No requirements were recorded.
|
| Travis-CI |
No Travis.
|
| coveralls test coverage |
No coveralls.
|
# scgraph
[](https://badge.fury.io/py/scgraph)
[](https://opensource.org/licenses/MIT)
Supply chain graph package for Python
## Documentation
Getting Started: https://github.com/connor-makowski/scgraph
Low Level: https://connor-makowski.github.io/scgraph/scgraph/core.html
## Key Features
- Calculate the shortest path between two points on earth using a latitude / longitude pair
- Inputs:
- A latitude / longitude pair for the origin
- A latitude / longitude pair for the destination
- Calculation:
- Algorithms:
- Dijkstra's algorithm (Modified for sparse networks)
- Modified to support sparse network data structures
- Makowski's Modified Sparse Dijkstra algorithm
- Modified for O(n) performance on particularly sparse networks
- Possible future support for other algorithms
- Distances:
- Uses the [haversine formula](https://en.wikipedia.org/wiki/Haversine_formula) to calculate the distance between two points on earth
- Returns:
- `path`:
- A list of dictionaries (`latitude` and `longitude`) that make up the shortest path
- `length`:
- The distance in kilometers between the two points
- Antimeridian support
- Arbitrary start and end points
- Arbitrary network data sets
## Setup
Make sure you have Python 3.10.x (or higher) installed on your system. You can download it [here](https://www.python.org/downloads/).
Support for python3.6-3.9 is available up to version 2.2.0
## Installation
```
pip install scgraph
```
## Use with Google Colab
- [Getting Started](https://colab.research.google.com/github/connor-makowski/scgraph/blob/main/examples/getting_started.ipynb)
- [Creating A Multi Path Geojson](https://colab.research.google.com/github/connor-makowski/scgraph/blob/main/examples/multi_path_geojson.ipynb)
- [Modifying A Geograph](https://colab.research.google.com/github/connor-makowski/scgraph/blob/main/examples/geograph_modifications.ipynb)
# Getting Started
## Basic Usage
Get the shortest path between two points on earth using a latitude / longitude pair
In this case, calculate the shortest maritime path between Shanghai, China and Savannah, Georgia, USA.
```py
# Use a maritime network geograph
from scgraph.geographs.marnet import marnet_geograph
# Get the shortest path between
output = marnet_geograph.get_shortest_path(
origin_node={"latitude": 31.23,"longitude": 121.47},
destination_node={"latitude": 32.08,"longitude": -81.09},
output_units='km'
)
print('Length: ',output['length']) #=> Length: 19596.4653
```
In the above example, the `output` variable is a dictionary with three keys: `length` and `coordinate_path`.
- `length`: The distance between the passed origin and destination when traversing the graph along the shortest path
- Notes:
- This will be in the units specified by the `output_units` parameter.
- `output_units` options:
- `km` (kilometers - default)
- `m` (meters)
- `mi` (miles)
- `ft` (feet)
- `coordinate_path`: A list of lists [`latitude`,`longitude`] that make up the shortest path
For more examples including viewing the output on a map, see the [example notebook](https://colab.research.google.com/github/connor-makowski/scgraph/blob/main/examples/getting_started.ipynb).
## Included GeoGraphs
- marnet_geograph:
- What: A maritime network data set from searoute
- Use: `from scgraph.geographs.marnet import marnet_geograph`
- Attribution: [searoute](https://github.com/genthalili/searoute-py)
- Length Measurement: Kilometers
- [Marnet Picture](https://raw.githubusercontent.com/connor-makowski/scgraph/main/static/marnet.png)
- oak_ridge_maritime_geograph:
- What: A maritime data set from the Oak Ridge National Laboratory campus
- Use: `from scgraph.geographs.oak_ridge_maritime import oak_ridge_maritime_geograph`
- Attribution: [Oak Ridge National Laboratory](https://www.ornl.gov/) with data from [Geocommons](http://geocommons.com/datasets?id=25)
- Length Measurement: Kilometers
- [Oak Ridge Maritime Picture](https://raw.githubusercontent.com/connor-makowski/scgraph/main/static/oak_ridge_maritime.png)
- north_america_rail_geograph:
- What: Class 1 Rail network for North America
- Use: `from scgraph.geographs.north_america_rail import north_america_rail_geograph`
- Attribution: [U.S. Department of Transportation: ArcGIS Online](https://geodata.bts.gov/datasets/usdot::north-american-rail-network-lines-class-i-freight-railroads-view/about)
- Length Measurement: Kilometers
- [North America Rail Picture](https://raw.githubusercontent.com/connor-makowski/scgraph/main/static/north_america_rail.png)
- us_freeway_geograph:
- What: Freeway network for the United States
- Use: `from scgraph.geographs.us_freeway import us_freeway_geograph`
- Attribution: [U.S. Department of Transportation: ArcGIS Online](https://hub.arcgis.com/datasets/esri::usa-freeway-system-over-1500k/about)
- Length Measurement: Kilometers
- [US Freeway Picture](https://raw.githubusercontent.com/connor-makowski/scgraph/main/static/us_freeway.png)
- `scgraph_data` geographs:
- What: Additional geographs are available in the `scgraph_data` package
- Note: These include larger geographs like the world highways geograph and world railways geograph.
- Installation: `pip install scgraph_data`
- Use: `from scgraph_data.world_highways import world_highways_geograph`
- See: [scgraph_data](https://github.com/connor-makowski/scgraph_data) for more information and all available geographs.
## Advanced Usage
Using `scgraph_data` geographs:
- Note: Make sure to install the `scgraph_data` package before using these geographs
```py
from scgraph_data.world_railways import world_railways_geograph
# Get the shortest path between Kalamazoo Michigan and Detroit Michigan by Train
output = world_railways_geograph.get_shortest_path(
origin_node={"latitude": 42.29,"longitude": -85.58},
destination_node={"latitude": 42.33,"longitude": -83.05}
)
```
Get a geojson line path of an output for easy visualization:
- Note: `mapshaper.org` and `geojson.io` are good tools for visualizing geojson files
```py
from scgraph.geographs.marnet import marnet_geograph
from scgraph.utils import get_line_path
# Get the shortest sea path between Sri Lanka and Somalia
output = marnet_geograph.get_shortest_path(
origin_node={"latitude": 7.87,"longitude": 80.77},
destination_node={"latitude": 5.15,"longitude": 46.20}
)
# Write the output to a geojson file
get_line_path(output, filename='output.geojson')
```
Modify an existing geograph: See the notebook [here](https://colab.research.google.com/github/connor-makowski/scgraph/blob/main/examples/geograph_modifications.ipynb)
You can specify your own custom graphs for direct access to the solving algorithms. This requires the use of the low level `Graph` class
```py
from scgraph import Graph
# Define an arbitrary graph
# See the graph definitions here:
# https://connor-makowski.github.io/scgraph/scgraph/core.html#GeoGraph
graph = [
{1: 5, 2: 1},
{0: 5, 2: 2, 3: 1},
{0: 1, 1: 2, 3: 4, 4: 8},
{1: 1, 2: 4, 4: 3, 5: 6},
{2: 8, 3: 3},
{3: 6}
]
# Optional: Validate your graph
Graph.validate_graph(graph=graph)
# Get the shortest path between idx 0 and idx 5
output = Graph.dijkstra_makowski(graph=graph, origin_id=0, destination_id=5)
#=> {'path': [0, 2, 1, 3, 5], 'length': 10}
```
You can also use a slightly higher level `GeoGraph` class to work with latitude / longitude pairs
```py
from scgraph import GeoGraph
# Define nodes
# See the nodes definitions here:
# https://connor-makowski.github.io/scgraph/scgraph/core.html#GeoGraph
nodes = [
# London
[51.5074, -0.1278],
# Paris
[48.8566, 2.3522],
# Berlin
[52.5200, 13.4050],
# Rome
[41.9028, 12.4964],
# Madrid
[40.4168, -3.7038],
# Lisbon
[38.7223, -9.1393]
]
# Define a graph
# See the graph definitions here:
# https://connor-makowski.github.io/scgraph/scgraph/core.html#GeoGraph
graph = [
# From London
{
# To Paris
1: 311,
},
# From Paris
{
# To London
0: 311,
# To Berlin
2: 878,
# To Rome
3: 1439,
# To Madrid
4: 1053
},
# From Berlin
{
# To Paris
1: 878,
# To Rome
3: 1181,
},
# From Rome
{
# To Paris
1: 1439,
# To Berlin
2: 1181,
},
# From Madrid
{
# To Paris
1: 1053,
# To Lisbon
5: 623
},
# From Lisbon
{
# To Madrid
4: 623
}
]
# Create a GeoGraph object
my_geograph = GeoGraph(nodes=nodes, graph=graph)
# Optional: Validate your graph
my_geograph.validate_graph()
# Optional: Validate your nodes
my_geograph.validate_nodes()
# Get the shortest path between two points
# In this case, Birmingham England and Zaragoza Spain
# Since Birmingham and Zaragoza are not in the graph,
# the algorithm will add them into the graph.
# See: https://connor-makowski.github.io/scgraph/scgraph/core.html#GeoGraph.get_shortest_path
# Expected output would be to go from
# Birmingham -> London -> Paris -> Madrid -> Zaragoza
output = my_geograph.get_shortest_path(
# Birmingham England
origin_node = {'latitude': 52.4862, 'longitude': -1.8904},
# Zaragoza Spain
destination_node = {'latitude': 41.6488, 'longitude': -0.8891}
)
print(output)
# {
# 'length': 1799.4323,
# 'coordinate_path': [
# [52.4862, -1.8904],
# [51.5074, -0.1278],
# [48.8566, 2.3522],
# [40.4168, -3.7038],
# [41.6488, -0.8891]
# ]
# }
```
## Attributions and Thanks
Originally inspired by [searoute](https://github.com/genthalili/searoute-py) including the use of one of their [datasets](https://github.com/genthalili/searoute-py/blob/main/searoute/data/marnet_densified_v2_old.geojson) that has been modified to work properly with this package.
Raw data
{
"_id": null,
"home_page": null,
"name": "scgraph",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.10",
"maintainer_email": null,
"keywords": null,
"author": null,
"author_email": "Connor Makowski <conmak@mit.edu>",
"download_url": "https://files.pythonhosted.org/packages/46/92/f53a073b2ae9fde5c01308381fcda01f640848859e487a37789f7c88d33f/scgraph-2.3.0.tar.gz",
"platform": null,
"description": "# scgraph\n[](https://badge.fury.io/py/scgraph)\n[](https://opensource.org/licenses/MIT)\n\nSupply chain graph package for Python\n\n\n\n\n## Documentation\n\nGetting Started: https://github.com/connor-makowski/scgraph\n\nLow Level: https://connor-makowski.github.io/scgraph/scgraph/core.html\n\n\n## Key Features\n\n- Calculate the shortest path between two points on earth using a latitude / longitude pair\n - Inputs:\n - A latitude / longitude pair for the origin\n - A latitude / longitude pair for the destination\n - Calculation:\n - Algorithms:\n - Dijkstra's algorithm (Modified for sparse networks)\n - Modified to support sparse network data structures\n - Makowski's Modified Sparse Dijkstra algorithm\n - Modified for O(n) performance on particularly sparse networks\n - Possible future support for other algorithms\n - Distances:\n - Uses the [haversine formula](https://en.wikipedia.org/wiki/Haversine_formula) to calculate the distance between two points on earth\n - Returns:\n - `path`:\n - A list of dictionaries (`latitude` and `longitude`) that make up the shortest path\n - `length`:\n - The distance in kilometers between the two points\n- Antimeridian support\n- Arbitrary start and end points\n- Arbitrary network data sets\n \n\n\n## Setup\n\nMake sure you have Python 3.10.x (or higher) installed on your system. You can download it [here](https://www.python.org/downloads/).\n\nSupport for python3.6-3.9 is available up to version 2.2.0\n\n## Installation\n\n```\npip install scgraph\n```\n\n## Use with Google Colab\n\n- [Getting Started](https://colab.research.google.com/github/connor-makowski/scgraph/blob/main/examples/getting_started.ipynb) \n- [Creating A Multi Path Geojson](https://colab.research.google.com/github/connor-makowski/scgraph/blob/main/examples/multi_path_geojson.ipynb)\n- [Modifying A Geograph](https://colab.research.google.com/github/connor-makowski/scgraph/blob/main/examples/geograph_modifications.ipynb)\n\n\n# Getting Started\n\n## Basic Usage\n\nGet the shortest path between two points on earth using a latitude / longitude pair\nIn this case, calculate the shortest maritime path between Shanghai, China and Savannah, Georgia, USA.\n\n```py\n# Use a maritime network geograph\nfrom scgraph.geographs.marnet import marnet_geograph\n\n# Get the shortest path between \noutput = marnet_geograph.get_shortest_path(\n origin_node={\"latitude\": 31.23,\"longitude\": 121.47}, \n destination_node={\"latitude\": 32.08,\"longitude\": -81.09},\n output_units='km'\n)\nprint('Length: ',output['length']) #=> Length: 19596.4653\n```\n\nIn the above example, the `output` variable is a dictionary with three keys: `length` and `coordinate_path`.\n\n- `length`: The distance between the passed origin and destination when traversing the graph along the shortest path\n - Notes: \n - This will be in the units specified by the `output_units` parameter. \n - `output_units` options:\n - `km` (kilometers - default)\n - `m` (meters)\n - `mi` (miles)\n - `ft` (feet)\n- `coordinate_path`: A list of lists [`latitude`,`longitude`] that make up the shortest path\n\nFor more examples including viewing the output on a map, see the [example notebook](https://colab.research.google.com/github/connor-makowski/scgraph/blob/main/examples/getting_started.ipynb).\n\n## Included GeoGraphs\n\n- marnet_geograph:\n - What: A maritime network data set from searoute\n - Use: `from scgraph.geographs.marnet import marnet_geograph`\n - Attribution: [searoute](https://github.com/genthalili/searoute-py)\n - Length Measurement: Kilometers\n - [Marnet Picture](https://raw.githubusercontent.com/connor-makowski/scgraph/main/static/marnet.png)\n- oak_ridge_maritime_geograph:\n - What: A maritime data set from the Oak Ridge National Laboratory campus\n - Use: `from scgraph.geographs.oak_ridge_maritime import oak_ridge_maritime_geograph`\n - Attribution: [Oak Ridge National Laboratory](https://www.ornl.gov/) with data from [Geocommons](http://geocommons.com/datasets?id=25)\n - Length Measurement: Kilometers\n - [Oak Ridge Maritime Picture](https://raw.githubusercontent.com/connor-makowski/scgraph/main/static/oak_ridge_maritime.png)\n- north_america_rail_geograph:\n - What: Class 1 Rail network for North America\n - Use: `from scgraph.geographs.north_america_rail import north_america_rail_geograph`\n - Attribution: [U.S. Department of Transportation: ArcGIS Online](https://geodata.bts.gov/datasets/usdot::north-american-rail-network-lines-class-i-freight-railroads-view/about)\n - Length Measurement: Kilometers\n - [North America Rail Picture](https://raw.githubusercontent.com/connor-makowski/scgraph/main/static/north_america_rail.png)\n- us_freeway_geograph:\n - What: Freeway network for the United States\n - Use: `from scgraph.geographs.us_freeway import us_freeway_geograph`\n - Attribution: [U.S. Department of Transportation: ArcGIS Online](https://hub.arcgis.com/datasets/esri::usa-freeway-system-over-1500k/about)\n - Length Measurement: Kilometers\n - [US Freeway Picture](https://raw.githubusercontent.com/connor-makowski/scgraph/main/static/us_freeway.png)\n- `scgraph_data` geographs:\n - What: Additional geographs are available in the `scgraph_data` package\n - Note: These include larger geographs like the world highways geograph and world railways geograph.\n - Installation: `pip install scgraph_data`\n - Use: `from scgraph_data.world_highways import world_highways_geograph`\n - See: [scgraph_data](https://github.com/connor-makowski/scgraph_data) for more information and all available geographs.\n\n## Advanced Usage\n\nUsing `scgraph_data` geographs:\n- Note: Make sure to install the `scgraph_data` package before using these geographs\n```py\nfrom scgraph_data.world_railways import world_railways_geograph\n\n# Get the shortest path between Kalamazoo Michigan and Detroit Michigan by Train\noutput = world_railways_geograph.get_shortest_path(\n origin_node={\"latitude\": 42.29,\"longitude\": -85.58}, \n destination_node={\"latitude\": 42.33,\"longitude\": -83.05}\n)\n```\n\nGet a geojson line path of an output for easy visualization:\n- Note: `mapshaper.org` and `geojson.io` are good tools for visualizing geojson files\n```py\nfrom scgraph.geographs.marnet import marnet_geograph\nfrom scgraph.utils import get_line_path\n\n # Get the shortest sea path between Sri Lanka and Somalia\noutput = marnet_geograph.get_shortest_path(\n origin_node={\"latitude\": 7.87,\"longitude\": 80.77}, \n destination_node={\"latitude\": 5.15,\"longitude\": 46.20}\n)\n# Write the output to a geojson file\nget_line_path(output, filename='output.geojson')\n```\n\nModify an existing geograph: See the notebook [here](https://colab.research.google.com/github/connor-makowski/scgraph/blob/main/examples/geograph_modifications.ipynb)\n\n\nYou can specify your own custom graphs for direct access to the solving algorithms. This requires the use of the low level `Graph` class\n\n```py\nfrom scgraph import Graph\n\n# Define an arbitrary graph\n# See the graph definitions here: \n# https://connor-makowski.github.io/scgraph/scgraph/core.html#GeoGraph\ngraph = [\n {1: 5, 2: 1},\n {0: 5, 2: 2, 3: 1},\n {0: 1, 1: 2, 3: 4, 4: 8},\n {1: 1, 2: 4, 4: 3, 5: 6},\n {2: 8, 3: 3},\n {3: 6}\n]\n\n# Optional: Validate your graph\nGraph.validate_graph(graph=graph)\n\n# Get the shortest path between idx 0 and idx 5\noutput = Graph.dijkstra_makowski(graph=graph, origin_id=0, destination_id=5)\n#=> {'path': [0, 2, 1, 3, 5], 'length': 10}\n```\n\nYou can also use a slightly higher level `GeoGraph` class to work with latitude / longitude pairs\n\n```py\nfrom scgraph import GeoGraph\n\n# Define nodes\n# See the nodes definitions here: \n# https://connor-makowski.github.io/scgraph/scgraph/core.html#GeoGraph\nnodes = [\n # London\n [51.5074, -0.1278],\n # Paris\n [48.8566, 2.3522],\n # Berlin\n [52.5200, 13.4050],\n # Rome\n [41.9028, 12.4964],\n # Madrid\n [40.4168, -3.7038],\n # Lisbon\n [38.7223, -9.1393]\n]\n# Define a graph\n# See the graph definitions here: \n# https://connor-makowski.github.io/scgraph/scgraph/core.html#GeoGraph\ngraph = [\n # From London\n {\n # To Paris\n 1: 311,\n },\n # From Paris\n {\n # To London\n 0: 311, \n # To Berlin\n 2: 878, \n # To Rome\n 3: 1439,\n # To Madrid\n 4: 1053\n },\n # From Berlin\n {\n # To Paris \n 1: 878,\n # To Rome\n 3: 1181,\n },\n # From Rome\n {\n # To Paris\n 1: 1439,\n # To Berlin\n 2: 1181,\n },\n # From Madrid\n {\n # To Paris\n 1: 1053,\n # To Lisbon\n 5: 623\n },\n # From Lisbon\n {\n # To Madrid\n 4: 623\n }\n]\n\n# Create a GeoGraph object\nmy_geograph = GeoGraph(nodes=nodes, graph=graph)\n\n# Optional: Validate your graph\nmy_geograph.validate_graph()\n\n# Optional: Validate your nodes\nmy_geograph.validate_nodes()\n\n# Get the shortest path between two points\n# In this case, Birmingham England and Zaragoza Spain\n# Since Birmingham and Zaragoza are not in the graph,\n# the algorithm will add them into the graph.\n# See: https://connor-makowski.github.io/scgraph/scgraph/core.html#GeoGraph.get_shortest_path\n# Expected output would be to go from\n# Birmingham -> London -> Paris -> Madrid -> Zaragoza\n\noutput = my_geograph.get_shortest_path(\n # Birmingham England\n origin_node = {'latitude': 52.4862, 'longitude': -1.8904},\n # Zaragoza Spain\n destination_node = {'latitude': 41.6488, 'longitude': -0.8891}\n)\nprint(output)\n# {\n# 'length': 1799.4323, \n# 'coordinate_path': [\n# [52.4862, -1.8904], \n# [51.5074, -0.1278], \n# [48.8566, 2.3522], \n# [40.4168, -3.7038], \n# [41.6488, -0.8891]\n# ]\n# }\n\n```\n\n## Attributions and Thanks\nOriginally inspired by [searoute](https://github.com/genthalili/searoute-py) including the use of one of their [datasets](https://github.com/genthalili/searoute-py/blob/main/searoute/data/marnet_densified_v2_old.geojson) that has been modified to work properly with this package.\n",
"bugtrack_url": null,
"license": null,
"summary": "Determine an approximate route between two points on earth.",
"version": "2.3.0",
"project_urls": {
"Bug Tracker": "https://github.com/connor-makowski/scgraph/issues",
"Documentation": "https://connor-makowski.github.io/scgraph/core.html",
"Homepage": "https://github.com/connor-makowski/scgraph"
},
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "665a4dccf4a5f2b89420a6d81ff8a6e1454a319ec20b4967530e975d4b449899",
"md5": "8faac7f3b3ead9b08bc3ad63584c3ea4",
"sha256": "28754e57fb796a127bd2d8fa1e7257ad204569a1fd0a569b130bf926bf92c272"
},
"downloads": -1,
"filename": "scgraph-2.3.0-py3-none-any.whl",
"has_sig": false,
"md5_digest": "8faac7f3b3ead9b08bc3ad63584c3ea4",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.10",
"size": 947503,
"upload_time": "2024-06-13T14:50:58",
"upload_time_iso_8601": "2024-06-13T14:50:58.833743Z",
"url": "https://files.pythonhosted.org/packages/66/5a/4dccf4a5f2b89420a6d81ff8a6e1454a319ec20b4967530e975d4b449899/scgraph-2.3.0-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "4692f53a073b2ae9fde5c01308381fcda01f640848859e487a37789f7c88d33f",
"md5": "e45ddf008f712d46f05f85fd1d825a51",
"sha256": "cef9f5b39a37cc97fe1c2819e14a975aa49caf1083504a63be07906c7e5d68e5"
},
"downloads": -1,
"filename": "scgraph-2.3.0.tar.gz",
"has_sig": false,
"md5_digest": "e45ddf008f712d46f05f85fd1d825a51",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.10",
"size": 942066,
"upload_time": "2024-06-13T14:51:04",
"upload_time_iso_8601": "2024-06-13T14:51:04.803187Z",
"url": "https://files.pythonhosted.org/packages/46/92/f53a073b2ae9fde5c01308381fcda01f640848859e487a37789f7c88d33f/scgraph-2.3.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-06-13 14:51:04",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "connor-makowski",
"github_project": "scgraph",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"requirements": [],
"lcname": "scgraph"
}
