graph-theory


Namegraph-theory JSON
Version 2023.7.6 PyPI version JSON
download
home_pagehttps://github.com/root-11/graph-theory
SummaryA graph library
upload_time2024-03-13 20:03:35
maintainer
docs_urlNone
authorhttps://github.com/root-11
requires_python>=3.7
licenseMIT
keywords adjacency adjacent algorithms all pairs shortest path analysis assignment problem complex-networks component components congestions critical critical-path cycle discrete mathematics finite finite state machine flow flow-problem fsm generate generation graph graph theory graph-algorithms graph-analysis graph-generation graph-hash graph-theory graph-visualization graphs hash hash-tree hill-climbing jam machine math mathematics maths matrix merkle merkle-tree method minimise minimize minimum minimum-spanning-trees network networks optimisation optimise optimization optimize pairs path python random graph search shortest shortest-path simple simple-path solver spanning state theory traffic traffic-jam traffic-jam-solver tree tsp tsp-solver
VCS
bugtrack_url
requirements No requirements were recorded.
Travis-CI No Travis.
coveralls test coverage
            # graph-theory
![Build status](https://github.com/root-11/graph-theory/actions/workflows/python-test.yml/badge.svg)
[![codecov](https://codecov.io/gh/root-11/graph-theory/branch/master/graph/badge.svg?token=hWbKhIXskp)](https://codecov.io/gh/root-11/graph-theory)
[![Downloads](https://pepy.tech/badge/graph-theory)](https://pepy.tech/project/graph-theory)
[![Downloads](https://pepy.tech/badge/graph-theory/month)](https://pepy.tech/project/graph-theory/month)
[![PyPI version](https://badge.fury.io/py/graph-theory.svg)](https://badge.fury.io/py/graph-theory)


A simple graph library...<br>
*... A bit like networkx, just without the overhead...*<br> 
*... similar to graph-tool, without the Python 2.7 legacy...*<br>
*... with code that you can explain to your boss...*<br>

Detailed tutorial evolving in the [examples section](https://github.com/root-11/graph-theory/blob/master/examples/readme.md).

---------------------------
Install:

    pip install graph-theory

Upgrade:

    pip install graph-theory --upgrade --no-cache

Testing:

    pytest tests

---------------------------
Import:

    import Graph
    g = Graph()  

    import Graph3d
    g3d = Graph3D()

---------------------------

Modules:

| module | description |
|:---|:---|
| `from graph import Graph, Graph3D` | Elementary methods (see basic methods below) for Graph and Graph3D.|
| `from graph import ...` | All methods available on Graph (see table below) |
| `from graph.assignment_problem import ...` | solvers for assignment problem, the Weapons-Target Assignment Problem, ... |
| `from graph.hash import ...` | graph hash functions: graph hash, merkle tree, flow graph hash | 
| `from graph.random import ...` | graph generators for random, 2D and 3D graphs. |
| `from graph.transshipment_problem import ...` | solvers for the transshipment problem |
| `from graph.traffic_scheduling_problem import ...` | solvers for the traffic jams (and slide puzzle) |
| `from graph.visuals import ...` | methods for creating matplotlib plots |
| `from graph.finite_state_machine import ...` | finite state machine |


All module functions are available from Graph and Graph3D (where applicable).

| Graph | Graph3D | methods                                          | returns                                                                                                                                                                                                               | example |
|:---:|:---:|:-------------------------------------------------|:----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|---|
| + | + | `a in g`                                         | assert if g contains node a                                                                                                                                                                                           | |
| + | + | `g.add_node(n, [obj])`                           | adds a node (with a pointer to object `obj` if given)                                                                                                                                                                 ||
| + | + | `g.copy()`                                       | returns a shallow copy of `g`                                                                                                                                                                                         ||
| + | + | `g.node(node1)`                                  | returns object attached to node 1                                                                                                                                                                                     ||
| + | + | `g.del_node(node1)`                              | deletes node1 and all it's edges                                                                                                                                                                                      ||
| + | + | `g.nodes()`                                      | returns a list of nodes                                                                                                                                                                                               ||
| + | + | `len(g.nodes())`                                 | returns the number of nodes                                                                                                                                                                                           ||
| + | + | `g.nodes(from_node=1)`                           | returns nodes with edges from node 1                                                                                                                                                                                  ||
| + | + | `g.nodes(to_node=2)`                             | returns nodes with edges to node 2                                                                                                                                                                                    ||
| + | + | `g.nodes(in_degree=2)`                           | returns nodes with 2 incoming edges                                                                                                                                                                                   ||
| + | + | `g.nodes(out_degree=2)`                          | returns nodes with 2 outgoing edges                                                                                                                                                                                   ||
| + | + | `g.add_edge(1,2,3)`                              | adds edge to g for vector `(1,2)` with value `3`                                                                                                                                                                      ||
| + | + | `g.edge(1,2)`                                    | returns value of edge between nodes 1 and 2                                                                                                                                                                           ||
| + | + | `g.edge(1,2,default=3)`                          | returns `default=3` if `edge(1,2)` doesn't exist. <br>similar to `d.get(key, 3)`                                                                                                                                      ||
| + | + | `g.del_edge(1,2)`                                | removes edge between nodes 1 and 2                                                                                                                                                                                    ||
| + | + | `g.edges()`                                      | returns a list of edges                                                                                                                                                                                               ||
| + | + | `len(g.edges())`                                 | returns the number of edges                                                                                                                                                                                           ||
| + | + | `g.edges(path=[path])`                           | returns a list of edges (along a path if given).                                                                                                                                                                      ||
| + | + | `same_path(p1,p2)`                               | compares two paths to determine if they contain same sequences <br>ex.: `[1,2,3] == [2,3,1]`                                                                                                                          ||
| + | + | `g.edges(from_node=1)`                           | returns edges outgoing from node 1                                                                                                                                                                                    ||
| + | + | `g.edges(to_node=2)`                             | returns edges incoming to node 2                                                                                                                                                                                      ||
| + | + | `g.from_dict(d)`                                 | updates the graph from a dictionary                                                                                                                                                                                   ||
| + | + | `g.to_dict()`                                    | returns the graph as a dictionary                                                                                                                                                                                     ||
| + | + | `g.from_list(L)`                                 | updates the graph from a list                                                                                                                                                                                         ||
| + | + | `g.to_list()`                                    | return the graph as a list of edges                                                                                                                                                                                   ||
| + | + | `g.shortest_path(start,end [, memoize, avoids])` | returns the distance and path for path with smallest edge sum <br> If `memoize=True`, sub results are cached for faster access if repeated calls.<br> If `avoids=set()`, then these nodes are not a part of the path. ||
| + | + | `g.shortest_path_bidirectional(start,end)`       | returns distance and path for the path with smallest edge sum using bidrectional search.                                                                                                                              ||
| + | + | `g.is_connected(start,end)`                      | determines if there is a path from start to end                                                                                                                                                                       ||
| + | + | `g.breadth_first_search(start,end)`              | returns the number of edges and path with fewest edges                                                                                                                                                                ||
| + | + | `g.breadth_first_walk(start,end)`                | returns a generator for a BFS walk                                                                                                                                                                                    ||
| + | + | `g.degree_of_separation(n1,n2)`                  | returns the distance between two nodes using BFS                                                                                                                                                                      ||
| + | + | `g.distance_map(starts,ends, reverse)`           | returns a dictionary with the distance from any start to any end (or reverse)                                                                                                                                         ||
| + | + | `g.network_size(n1, degree_of_separation)`       | returns the nodes within the range given by `degree_of_separation`                                                                                                                                                    ||
| + | + | `g.topological_sort(key)`                        | returns a generator that yields node in order from a non-cyclic graph.                                                                                                                                                ||
| + | + | `g.critical_path()`                              | returns the distance of the critical path and a list of Tasks.                                                                                                                                                        | [Example](examples/solving%20search%20problems.ipynb) |
| + | + | `g.critical_path_minimize_for_slack()`           | returns graph with artificial dependencies that minimises slack.                                                                                                                                                      | [Example](examples/solving%20search%20problems.ipynb)|
| + | + | `g.phase_lines()`                                | returns a dictionary with the phase_lines for a non-cyclic graph.                                                                                                                                                     ||
| + | + | `g.sources(n)`                                   | returns the source_tree of node `n`                                                                                                                                                                                   ||
| + | + | `g.depth_first_search(start,end)`                | returns path using DFS and backtracking                                                                                                                                                                               ||
| + | + | `g.depth_scan(start, criteria)`                  | returns set of nodes where criteria is True                                                                                                                                                                           ||
| + | + | `g.distance_from_path(path)`                     | returns the distance for path.                                                                                                                                                                                        ||
| + | + | `g.maximum_flow(source,sink)`                    | finds the maximum flow between a source and a sink                                                                                                                                                                    ||
| + | + | `g.maximum_flow_min_cut(source,sink)`            | finds the maximum flow minimum cut between a source and a sink                                                                                                                                                        ||
| + | + | `g.minimum_cost_flow(inventory, capacity)`       | finds the total cost and flows of the capacitated minimum cost flow.                                                                                                                                                  ||
| + | + | `g.solve_tsp()`                                  | solves the traveling salesman problem for the graph.<br>Available methods: 'greedy' (default) and 'bnb                                                                                                                ||
| + | + | `g.subgraph_from_nodes(nodes)`                   | returns the subgraph of `g` involving `nodes`                                                                                                                                                                         ||
| + | + | `g.is_subgraph(g2)`                              | determines if graph `g2` is a subgraph in g                                                                                                                                                                           ||
| + | + | `g.is_partite(n)`                                | determines if graph is n-partite                                                                                                                                                                                      ||
| + | + | `g.has_cycles()`                                 | determines if there are any cycles in the graph                                                                                                                                                                       ||
| + | + | `g.components()`                                 | returns set of nodes in each component in `g`                                                                                                                                                                         ||
| + | + | `g.same_path(p1,p2)`                             | compares two paths, returns True if they're the same                                                                                                                                                                  ||
| + | + | `g.adjacency_matrix()`                           | returns the adjacency matrix for the graph                                                                                                                                                                            ||
| + | + | `g.all_pairs_shortest_paths()`                   | finds the shortest path between all nodes                                                                                                                                                                             ||
| + | + | `g.minsum()`                                     | finds the node(s) with shortest total distance to all other nodes                                                                                                                                                     ||
| + | + | `g.minmax()`                                     | finds the node(s) with shortest maximum distance to all other nodes                                                                                                                                                   ||
| + | + | `g.shortest_tree_all_pairs()`                    | finds the shortest tree for all pairs                                                                                                                                                                                 ||
| + | + | `g.has_path(p)`                                  | asserts whether a path `p` exists in g                                                                                                                                                                                ||
| + | + | `g.all_simple_paths(start,end)`                  | finds all simple paths between 2 nodes                                                                                                                                                                                ||
| + | + | `g.all_paths(start,end)`                         | finds all combinations of paths between 2 nodes                                                                                                                                                                       ||
| - | + | `g3d.distance(n1,n2)`                            | returns the spatial distance between `n1` and `n2`                                                                                                                                                                    ||
| - | + | `g3d.n_nearest_neighbour(n1, [n])`               | returns the `n` nearest neighbours to node `n1`                                                                                                                                                                       ||
| - | + | `g3d.plot()`                                     | returns matplotlib plot of the graph.                                                                                                                                                                                 ||


## FAQ

| want to... | doesn't work... | do instead... | ...but why? |
|:---|:---|:---|:---|
| have multiple edges between two nodes | `Graph(from_list=[(1,2,3), (1,2,4)]` | Add dummy nodes<br>`[(1,a,3), (a,2,0),`<br>` (1,b,4),(b,2,0)]` | Explicit is better than implicit. |
| multiple values on an edge | `g.add_edge(1,2,{'a':3, 'b':4})` | Have two graphs<br>`g_a.add_edge(1,2,3)`<br>`g_b.add_edge(1,2,4)` | Most graph algorithms don't work with multiple values |
|do repeated calls to shortest path|`g.shortest_path(a,b)` is slow|Use `g.shortest_path(a,b,memoize=True)` instead|memoize uses bidirectional search and caches sub-results along the shortest path for future retrievals|

## Credits:

- Arturo Soucase for packaging and testing. 
- Peter Norvig for inspiration on TSP from [pytudes](https://github.com/norvig/pytudes/blob/master/ipynb/TSP.ipynb).
- Harry Darby for the mountain river map.
- Kyle Downey for depth_scan algorithm.
- Ross Blandford for munich firebrigade centre -, traffic jam - and slide puzzle - test cases.
- Avi Kelman for type-tolerant search, and a number of micro optimizations.
- Joshua Crestone for all simple paths test.
- CodeMartyLikeYou for detecting a bug in `@memoize` 
- Tom Carroll for detecting the bug in del_edge and inspiration for topological sort.
- Sappique for discovering bug in `__eq__` and `has_cycles`.


            

Raw data

            {
    "_id": null,
    "home_page": "https://github.com/root-11/graph-theory",
    "name": "graph-theory",
    "maintainer": "",
    "docs_url": null,
    "requires_python": ">=3.7",
    "maintainer_email": "",
    "keywords": "adjacency,adjacent,algorithms,all pairs shortest path,analysis,assignment problem,complex-networks,component,components,congestions,critical,critical-path,cycle,discrete mathematics,finite,finite state machine,flow,flow-problem,fsm,generate,generation,graph,Graph Theory,graph-algorithms,graph-analysis,graph-generation,graph-hash,graph-theory,graph-visualization,graphs,hash,hash-tree,hill-climbing,jam,machine,math,Mathematics,maths,matrix,merkle,merkle-tree,method,minimise,minimize,minimum,minimum-spanning-trees,network,Networks,optimisation,optimise,optimization,optimize,pairs,path,python,random graph,search,shortest,shortest-path,simple,simple-path,solver,spanning,state,theory,traffic,traffic-jam,traffic-jam-solver,tree,tsp,tsp-solver",
    "author": "https://github.com/root-11",
    "author_email": "",
    "download_url": "",
    "platform": "any",
    "description": "# graph-theory\n![Build status](https://github.com/root-11/graph-theory/actions/workflows/python-test.yml/badge.svg)\n[![codecov](https://codecov.io/gh/root-11/graph-theory/branch/master/graph/badge.svg?token=hWbKhIXskp)](https://codecov.io/gh/root-11/graph-theory)\n[![Downloads](https://pepy.tech/badge/graph-theory)](https://pepy.tech/project/graph-theory)\n[![Downloads](https://pepy.tech/badge/graph-theory/month)](https://pepy.tech/project/graph-theory/month)\n[![PyPI version](https://badge.fury.io/py/graph-theory.svg)](https://badge.fury.io/py/graph-theory)\n\n\nA simple graph library...<br>\n*... A bit like networkx, just without the overhead...*<br> \n*... similar to graph-tool, without the Python 2.7 legacy...*<br>\n*... with code that you can explain to your boss...*<br>\n\nDetailed tutorial evolving in the [examples section](https://github.com/root-11/graph-theory/blob/master/examples/readme.md).\n\n---------------------------\nInstall:\n\n    pip install graph-theory\n\nUpgrade:\n\n    pip install graph-theory --upgrade --no-cache\n\nTesting:\n\n    pytest tests\n\n---------------------------\nImport:\n\n    import Graph\n    g = Graph()  \n\n    import Graph3d\n    g3d = Graph3D()\n\n---------------------------\n\nModules:\n\n| module | description |\n|:---|:---|\n| `from graph import Graph, Graph3D` | Elementary methods (see basic methods below) for Graph and Graph3D.|\n| `from graph import ...` | All methods available on Graph (see table below) |\n| `from graph.assignment_problem import ...` | solvers for assignment problem, the Weapons-Target Assignment Problem, ... |\n| `from graph.hash import ...` | graph hash functions: graph hash, merkle tree, flow graph hash | \n| `from graph.random import ...` | graph generators for random, 2D and 3D graphs. |\n| `from graph.transshipment_problem import ...` | solvers for the transshipment problem |\n| `from graph.traffic_scheduling_problem import ...` | solvers for the traffic jams (and slide puzzle) |\n| `from graph.visuals import ...` | methods for creating matplotlib plots |\n| `from graph.finite_state_machine import ...` | finite state machine |\n\n\nAll module functions are available from Graph and Graph3D (where applicable).\n\n| Graph | Graph3D | methods                                          | returns                                                                                                                                                                                                               | example |\n|:---:|:---:|:-------------------------------------------------|:----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|---|\n| + | + | `a in g`                                         | assert if g contains node a                                                                                                                                                                                           | |\n| + | + | `g.add_node(n, [obj])`                           | adds a node (with a pointer to object `obj` if given)                                                                                                                                                                 ||\n| + | + | `g.copy()`                                       | returns a shallow copy of `g`                                                                                                                                                                                         ||\n| + | + | `g.node(node1)`                                  | returns object attached to node 1                                                                                                                                                                                     ||\n| + | + | `g.del_node(node1)`                              | deletes node1 and all it's edges                                                                                                                                                                                      ||\n| + | + | `g.nodes()`                                      | returns a list of nodes                                                                                                                                                                                               ||\n| + | + | `len(g.nodes())`                                 | returns the number of nodes                                                                                                                                                                                           ||\n| + | + | `g.nodes(from_node=1)`                           | returns nodes with edges from node 1                                                                                                                                                                                  ||\n| + | + | `g.nodes(to_node=2)`                             | returns nodes with edges to node 2                                                                                                                                                                                    ||\n| + | + | `g.nodes(in_degree=2)`                           | returns nodes with 2 incoming edges                                                                                                                                                                                   ||\n| + | + | `g.nodes(out_degree=2)`                          | returns nodes with 2 outgoing edges                                                                                                                                                                                   ||\n| + | + | `g.add_edge(1,2,3)`                              | adds edge to g for vector `(1,2)` with value `3`                                                                                                                                                                      ||\n| + | + | `g.edge(1,2)`                                    | returns value of edge between nodes 1 and 2                                                                                                                                                                           ||\n| + | + | `g.edge(1,2,default=3)`                          | returns `default=3` if `edge(1,2)` doesn't exist. <br>similar to `d.get(key, 3)`                                                                                                                                      ||\n| + | + | `g.del_edge(1,2)`                                | removes edge between nodes 1 and 2                                                                                                                                                                                    ||\n| + | + | `g.edges()`                                      | returns a list of edges                                                                                                                                                                                               ||\n| + | + | `len(g.edges())`                                 | returns the number of edges                                                                                                                                                                                           ||\n| + | + | `g.edges(path=[path])`                           | returns a list of edges (along a path if given).                                                                                                                                                                      ||\n| + | + | `same_path(p1,p2)`                               | compares two paths to determine if they contain same sequences <br>ex.: `[1,2,3] == [2,3,1]`                                                                                                                          ||\n| + | + | `g.edges(from_node=1)`                           | returns edges outgoing from node 1                                                                                                                                                                                    ||\n| + | + | `g.edges(to_node=2)`                             | returns edges incoming to node 2                                                                                                                                                                                      ||\n| + | + | `g.from_dict(d)`                                 | updates the graph from a dictionary                                                                                                                                                                                   ||\n| + | + | `g.to_dict()`                                    | returns the graph as a dictionary                                                                                                                                                                                     ||\n| + | + | `g.from_list(L)`                                 | updates the graph from a list                                                                                                                                                                                         ||\n| + | + | `g.to_list()`                                    | return the graph as a list of edges                                                                                                                                                                                   ||\n| + | + | `g.shortest_path(start,end [, memoize, avoids])` | returns the distance and path for path with smallest edge sum <br> If `memoize=True`, sub results are cached for faster access if repeated calls.<br> If `avoids=set()`, then these nodes are not a part of the path. ||\n| + | + | `g.shortest_path_bidirectional(start,end)`       | returns distance and path for the path with smallest edge sum using bidrectional search.                                                                                                                              ||\n| + | + | `g.is_connected(start,end)`                      | determines if there is a path from start to end                                                                                                                                                                       ||\n| + | + | `g.breadth_first_search(start,end)`              | returns the number of edges and path with fewest edges                                                                                                                                                                ||\n| + | + | `g.breadth_first_walk(start,end)`                | returns a generator for a BFS walk                                                                                                                                                                                    ||\n| + | + | `g.degree_of_separation(n1,n2)`                  | returns the distance between two nodes using BFS                                                                                                                                                                      ||\n| + | + | `g.distance_map(starts,ends, reverse)`           | returns a dictionary with the distance from any start to any end (or reverse)                                                                                                                                         ||\n| + | + | `g.network_size(n1, degree_of_separation)`       | returns the nodes within the range given by `degree_of_separation`                                                                                                                                                    ||\n| + | + | `g.topological_sort(key)`                        | returns a generator that yields node in order from a non-cyclic graph.                                                                                                                                                ||\n| + | + | `g.critical_path()`                              | returns the distance of the critical path and a list of Tasks.                                                                                                                                                        | [Example](examples/solving%20search%20problems.ipynb) |\n| + | + | `g.critical_path_minimize_for_slack()`           | returns graph with artificial dependencies that minimises slack.                                                                                                                                                      | [Example](examples/solving%20search%20problems.ipynb)|\n| + | + | `g.phase_lines()`                                | returns a dictionary with the phase_lines for a non-cyclic graph.                                                                                                                                                     ||\n| + | + | `g.sources(n)`                                   | returns the source_tree of node `n`                                                                                                                                                                                   ||\n| + | + | `g.depth_first_search(start,end)`                | returns path using DFS and backtracking                                                                                                                                                                               ||\n| + | + | `g.depth_scan(start, criteria)`                  | returns set of nodes where criteria is True                                                                                                                                                                           ||\n| + | + | `g.distance_from_path(path)`                     | returns the distance for path.                                                                                                                                                                                        ||\n| + | + | `g.maximum_flow(source,sink)`                    | finds the maximum flow between a source and a sink                                                                                                                                                                    ||\n| + | + | `g.maximum_flow_min_cut(source,sink)`            | finds the maximum flow minimum cut between a source and a sink                                                                                                                                                        ||\n| + | + | `g.minimum_cost_flow(inventory, capacity)`       | finds the total cost and flows of the capacitated minimum cost flow.                                                                                                                                                  ||\n| + | + | `g.solve_tsp()`                                  | solves the traveling salesman problem for the graph.<br>Available methods: 'greedy' (default) and 'bnb                                                                                                                ||\n| + | + | `g.subgraph_from_nodes(nodes)`                   | returns the subgraph of `g` involving `nodes`                                                                                                                                                                         ||\n| + | + | `g.is_subgraph(g2)`                              | determines if graph `g2` is a subgraph in g                                                                                                                                                                           ||\n| + | + | `g.is_partite(n)`                                | determines if graph is n-partite                                                                                                                                                                                      ||\n| + | + | `g.has_cycles()`                                 | determines if there are any cycles in the graph                                                                                                                                                                       ||\n| + | + | `g.components()`                                 | returns set of nodes in each component in `g`                                                                                                                                                                         ||\n| + | + | `g.same_path(p1,p2)`                             | compares two paths, returns True if they're the same                                                                                                                                                                  ||\n| + | + | `g.adjacency_matrix()`                           | returns the adjacency matrix for the graph                                                                                                                                                                            ||\n| + | + | `g.all_pairs_shortest_paths()`                   | finds the shortest path between all nodes                                                                                                                                                                             ||\n| + | + | `g.minsum()`                                     | finds the node(s) with shortest total distance to all other nodes                                                                                                                                                     ||\n| + | + | `g.minmax()`                                     | finds the node(s) with shortest maximum distance to all other nodes                                                                                                                                                   ||\n| + | + | `g.shortest_tree_all_pairs()`                    | finds the shortest tree for all pairs                                                                                                                                                                                 ||\n| + | + | `g.has_path(p)`                                  | asserts whether a path `p` exists in g                                                                                                                                                                                ||\n| + | + | `g.all_simple_paths(start,end)`                  | finds all simple paths between 2 nodes                                                                                                                                                                                ||\n| + | + | `g.all_paths(start,end)`                         | finds all combinations of paths between 2 nodes                                                                                                                                                                       ||\n| - | + | `g3d.distance(n1,n2)`                            | returns the spatial distance between `n1` and `n2`                                                                                                                                                                    ||\n| - | + | `g3d.n_nearest_neighbour(n1, [n])`               | returns the `n` nearest neighbours to node `n1`                                                                                                                                                                       ||\n| - | + | `g3d.plot()`                                     | returns matplotlib plot of the graph.                                                                                                                                                                                 ||\n\n\n## FAQ\n\n| want to... | doesn't work... | do instead... | ...but why? |\n|:---|:---|:---|:---|\n| have multiple edges between two nodes | `Graph(from_list=[(1,2,3), (1,2,4)]` | Add dummy nodes<br>`[(1,a,3), (a,2,0),`<br>` (1,b,4),(b,2,0)]` | Explicit is better than implicit. |\n| multiple values on an edge | `g.add_edge(1,2,{'a':3, 'b':4})` | Have two graphs<br>`g_a.add_edge(1,2,3)`<br>`g_b.add_edge(1,2,4)` | Most graph algorithms don't work with multiple values |\n|do repeated calls to shortest path|`g.shortest_path(a,b)` is slow|Use `g.shortest_path(a,b,memoize=True)` instead|memoize uses bidirectional search and caches sub-results along the shortest path for future retrievals|\n\n## Credits:\n\n- Arturo Soucase for packaging and testing. \n- Peter Norvig for inspiration on TSP from [pytudes](https://github.com/norvig/pytudes/blob/master/ipynb/TSP.ipynb).\n- Harry Darby for the mountain river map.\n- Kyle Downey for depth_scan algorithm.\n- Ross Blandford for munich firebrigade centre -, traffic jam - and slide puzzle - test cases.\n- Avi Kelman for type-tolerant search, and a number of micro optimizations.\n- Joshua Crestone for all simple paths test.\n- CodeMartyLikeYou for detecting a bug in `@memoize` \n- Tom Carroll for detecting the bug in del_edge and inspiration for topological sort.\n- Sappique for discovering bug in `__eq__` and `has_cycles`.\n\n",
    "bugtrack_url": null,
    "license": "MIT",
    "summary": "A graph library",
    "version": "2023.7.6",
    "project_urls": {
        "Homepage": "https://github.com/root-11/graph-theory"
    },
    "split_keywords": [
        "adjacency",
        "adjacent",
        "algorithms",
        "all pairs shortest path",
        "analysis",
        "assignment problem",
        "complex-networks",
        "component",
        "components",
        "congestions",
        "critical",
        "critical-path",
        "cycle",
        "discrete mathematics",
        "finite",
        "finite state machine",
        "flow",
        "flow-problem",
        "fsm",
        "generate",
        "generation",
        "graph",
        "graph theory",
        "graph-algorithms",
        "graph-analysis",
        "graph-generation",
        "graph-hash",
        "graph-theory",
        "graph-visualization",
        "graphs",
        "hash",
        "hash-tree",
        "hill-climbing",
        "jam",
        "machine",
        "math",
        "mathematics",
        "maths",
        "matrix",
        "merkle",
        "merkle-tree",
        "method",
        "minimise",
        "minimize",
        "minimum",
        "minimum-spanning-trees",
        "network",
        "networks",
        "optimisation",
        "optimise",
        "optimization",
        "optimize",
        "pairs",
        "path",
        "python",
        "random graph",
        "search",
        "shortest",
        "shortest-path",
        "simple",
        "simple-path",
        "solver",
        "spanning",
        "state",
        "theory",
        "traffic",
        "traffic-jam",
        "traffic-jam-solver",
        "tree",
        "tsp",
        "tsp-solver"
    ],
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "blake2b_256": "646d30e8556be58f7be354edf8cf3c55bf8b315d7f1eccdf97f5a052573c8d16",
                "md5": "6beae8fc9c99e49bd9a248b0224313b9",
                "sha256": "9030aee88aa1db6c778f73338c143a4c872eb9ed5fad5eb9a768ebeb75541340"
            },
            "downloads": -1,
            "filename": "graph_theory-2023.7.6-py3-none-any.whl",
            "has_sig": false,
            "md5_digest": "6beae8fc9c99e49bd9a248b0224313b9",
            "packagetype": "bdist_wheel",
            "python_version": "py3",
            "requires_python": ">=3.7",
            "size": 62554,
            "upload_time": "2024-03-13T20:03:35",
            "upload_time_iso_8601": "2024-03-13T20:03:35.858153Z",
            "url": "https://files.pythonhosted.org/packages/64/6d/30e8556be58f7be354edf8cf3c55bf8b315d7f1eccdf97f5a052573c8d16/graph_theory-2023.7.6-py3-none-any.whl",
            "yanked": false,
            "yanked_reason": null
        }
    ],
    "upload_time": "2024-03-13 20:03:35",
    "github": true,
    "gitlab": false,
    "bitbucket": false,
    "codeberg": false,
    "github_user": "root-11",
    "github_project": "graph-theory",
    "travis_ci": false,
    "coveralls": true,
    "github_actions": true,
    "requirements": [],
    "lcname": "graph-theory"
}
        
Elapsed time: 0.22073s