graph-theory
# graph-theory
[](https://codecov.io/gh/root-11/graph-theory)
[](https://pepy.tech/project/graph-theory)
[](https://pepy.tech/project/graph-theory/month)
[](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 bugs in `__eq__`, `copy` and `has_cycles`.
Raw data
{
"_id": null,
"home_page": "https://github.com/root-11/graph-theory",
"name": "graph-theory",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.7",
"maintainer_email": null,
"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": null,
"download_url": null,
"platform": "any",
"description": "# graph-theory\n\n[](https://codecov.io/gh/root-11/graph-theory)\n[](https://pepy.tech/project/graph-theory)\n[](https://pepy.tech/project/graph-theory/month)\n[](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 bugs in `__eq__`, `copy` and `has_cycles`.\n\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "A graph library",
"version": "2023.7.7",
"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": "96311e27eaa7419a3bd512e71c9168dcf993344bb47ded4b4e19de059c0acb27",
"md5": "d6e633822f4434a9cc240683f37c82ab",
"sha256": "4d33f4f73f7dddf1e36166056e93f82accca4854efcc8c25eb85f8c609385a8d"
},
"downloads": -1,
"filename": "graph_theory-2023.7.7-py3-none-any.whl",
"has_sig": false,
"md5_digest": "d6e633822f4434a9cc240683f37c82ab",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.7",
"size": 62667,
"upload_time": "2024-04-29T21:42:04",
"upload_time_iso_8601": "2024-04-29T21:42:04.476686Z",
"url": "https://files.pythonhosted.org/packages/96/31/1e27eaa7419a3bd512e71c9168dcf993344bb47ded4b4e19de059c0acb27/graph_theory-2023.7.7-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-04-29 21:42:04",
"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"
}
