{
"info": {
"author": "Bjorn Madsen",
"author_email": "bjorn.madsen@operationsresearchgroup.com",
"bugtrack_url": null,
"classifiers": [
"Development Status :: 5 - Production/Stable",
"Intended Audience :: Science/Research",
"License :: OSI Approved :: MIT License",
"Natural Language :: English",
"Programming Language :: Python :: 3.6"
],
"description": "# graph\n[](https://travis-ci.org/root-11/graph-theory.svg?branch=master)\n\n\n\nA simple graph library...
\n*... A bit like networkx, just without the overhead...*
\n*... similar to graph-tool, without the Python 2.7 legacy...*
\n\n\n---------------------------\nInstall:\n\n pip install graph-theory\n\n---------------------------\nImport:\n\n import Graph\n g = Graph()\n\n---------------------------\n\nModules:\n\n| module | description |\n|:---|:---|\n| `from graph import Graph, Graph2D, Graph3D` | Elementary methods (see basic methods below), 2D and 3D graphs.|\n| `from graph.assignment_problem import ...` | solvers for assignment problem, the Weapons-Target Assignment Problem, ... |\n| `from graph.flow_problem import ...` | maximum flow |\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.scheduling import sp_solver` | Scheduling problem solver. |\n| `from graph.search import ...` | shortest path, breadth-first, depth-first |\n| `from graph.topology import ...` | Topological comparisons and operators: make/assert subgraph, detect partitions, path comparisons, cycle detection, path verification, network range |\n| `from graph.transform import ...` | Isomorphic transformation methods like adjacency matrix, all-pairs-shortest path, etc. | \n\n\nAll module functions are available from Graph, Graph2D and Graph3D (where applicable).\n\n| methods | description |\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.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.
similar to `d.get(key, 3)`|\n| `g.del_edge(1,2)` | removes edge between nodes 1 and 2 |\n| `g.edges(path=[path])` | returns a list of edges (along a path if given). |\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| `len(g.edges())` | returns the number of edges |\n| `g.from_dict(d)` | updates the graph from a dictionary |\n| `g.to_dict()` | dumps the graph as a dictionary |\n| `g.from_list(L)` | updates the graph from a list |\n| `g.to_list()` | dumps the graph as a list of edges |\n| `g.shortest_path(start,end)` | finds the path with smallest edge sum |\n| `g.breadth_first_search(start,end)` | finds the with least number of hops |\n| `g.depth_first_search(start,end)` | finds a path between 2 nodes (start, end) using DFS and backtracking. |\n| `g.distance_from_path(path)` | finds the distance following a given path. |\n| `g.maximum_flow(source,sink)` | finds the maximum flow between a source and a sink|\n| `g.solve_tsp()` | solves the traveling salesman problem for the graph|\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 cycles in the graph |\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.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_paths(start,end)` | finds all combinations of paths between 2 nodes.|\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
`[(1,a,3), (a,2,0),`
` (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
`g_a.add_edge(1,2,3)`
`g_b.add_edge(1,2,4)` | Most graph algorithms don't work with multiple values | \n\n## Specialised modules:\n\n from graph import Graph\n from graph import Graph2D\n from graph import Graph3D\n from graph.hashing import merkle_tree\n from graph.assignment_problem import ap_solver\n from graph.assignment_problem import wtap_solver\n from graph.scheduling_problem import sp_solver\n\n\nExamples contains a number of tutorial/solutions to common operations research\nand computer science problems, which are made simple when treated as a graph.\n\n| module | function | description |\n|:---|:---|:---|\n| assignment_problem.py | assignment_problem | solves the assignment problem |\n| hashgraph.py | merkle_tree | datablocks |\n| hashgraph.py | graph_hash | computes the sha256 of a graphs nodes and edges |\n| hashgraph.py | flow_graph_hash | computes the sha256 of a graph with multiple sources and sinks |\n| knapsack_problem.py | knapsack problem | solves the knapsack problem |\n| wtap.py | weapons-target assignment problem | solves the WTAP problem. |",
"description_content_type": "text/markdown",
"docs_url": null,
"download_url": "",
"downloads": {
"last_day": -1,
"last_month": -1,
"last_week": -1
},
"home_page": "https://github.com/root-11/graph-theory",
"keywords": "graph graphs optimization tsp shortest-path",
"license": "MIT",
"maintainer": "",
"maintainer_email": "",
"name": "graph-theory",
"package_url": "https://pypi.org/project/graph-theory/",
"platform": "any",
"project_url": "https://pypi.org/project/graph-theory/",
"project_urls": {
"Homepage": "https://github.com/root-11/graph-theory"
},
"release_url": "https://pypi.org/project/graph-theory/2019.10.14.42373/",
"requires_dist": null,
"requires_python": "",
"summary": "A graph library",
"version": "2019.10.14.42373"
},
"last_serial": 5970878,
"releases": {
"2019.10.14.42373": [
{
"comment_text": "",
"digests": {
"md5": "12e2427e60f38355588a71bb208f14b0",
"sha256": "e28df26c99ef472c4d2e21fa2baa0eca58170aedd6f8b71bb714a573b7332b2d"
},
"downloads": -1,
"filename": "graph-theory-2019.10.14.42373.tar.gz",
"has_sig": false,
"md5_digest": "12e2427e60f38355588a71bb208f14b0",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 25497,
"upload_time": "2019-10-14T10:49:48",
"url": "https://files.pythonhosted.org/packages/19/82/8c0e29067a1de15e3e426808bd7e2dd326bc37c50f03fc5faab3c8a08271/graph-theory-2019.10.14.42373.tar.gz"
}
],
"2019.5.10.35639": [
{
"comment_text": "",
"digests": {
"md5": "6390168904753f822da7e376c3e052b4",
"sha256": "0aa5601b3d6d8ba3a5fbbb1a27c2a99b962a8f967c264abe7f3e59df468756d2"
},
"downloads": -1,
"filename": "graph-theory-2019.5.10.35639.tar.gz",
"has_sig": false,
"md5_digest": "6390168904753f822da7e376c3e052b4",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 11368,
"upload_time": "2019-05-10T08:57:30",
"url": "https://files.pythonhosted.org/packages/c7/92/30a0a4c642ad66c8142b4651bd3ce4c8d13cef80714ce2b85084bb79fb33/graph-theory-2019.5.10.35639.tar.gz"
}
],
"2019.5.10.37010": [
{
"comment_text": "",
"digests": {
"md5": "7749b867caf6cda09a15730904e4bf60",
"sha256": "f35d4d4df966078ffca9daf60d46da645a62ebc993c1b8d7c3a4a8afe9671f1c"
},
"downloads": -1,
"filename": "graph-theory-2019.5.10.37010.tar.gz",
"has_sig": false,
"md5_digest": "7749b867caf6cda09a15730904e4bf60",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 19060,
"upload_time": "2019-05-10T09:28:00",
"url": "https://files.pythonhosted.org/packages/66/2b/8920fc636d1589508c67e0ea5e275bea53a41326cbfbffedc5c11afab408/graph-theory-2019.5.10.37010.tar.gz"
}
],
"2019.5.20.52321": [
{
"comment_text": "",
"digests": {
"md5": "d1e59f55011dbb38517c50da2018f555",
"sha256": "948b65fdd06db08e232ec27d4192600f6ed5215667cd2098151375ad710e7479"
},
"downloads": -1,
"filename": "graph-theory-2019.5.20.52321.tar.gz",
"has_sig": false,
"md5_digest": "d1e59f55011dbb38517c50da2018f555",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 19045,
"upload_time": "2019-05-20T13:35:58",
"url": "https://files.pythonhosted.org/packages/f6/f2/d8ce5b82fe7645dab49614c3a1d2fc546a9f4ba78ca96faab9171ffeba86/graph-theory-2019.5.20.52321.tar.gz"
}
]
},
"urls": [
{
"comment_text": "",
"digests": {
"md5": "12e2427e60f38355588a71bb208f14b0",
"sha256": "e28df26c99ef472c4d2e21fa2baa0eca58170aedd6f8b71bb714a573b7332b2d"
},
"downloads": -1,
"filename": "graph-theory-2019.10.14.42373.tar.gz",
"has_sig": false,
"md5_digest": "12e2427e60f38355588a71bb208f14b0",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 25497,
"upload_time": "2019-10-14T10:49:48",
"url": "https://files.pythonhosted.org/packages/19/82/8c0e29067a1de15e3e426808bd7e2dd326bc37c50f03fc5faab3c8a08271/graph-theory-2019.10.14.42373.tar.gz"
}
]
}