图库
graph-theor的Python项目详细描述
图表
一个简单的图形库…
…有点像networkx，只是没有开销…
…类似于Graph工具，没有Python2.7遗留版本…
import Graph
g = Graph()
就这样。
可用方法：
| methods | description |
|---|---|
| ^{ | assert if g contains node a |
| ^{ | adds a node (with a pointer to object ^{ |
| ^{ | returns object attached to node 1. |
| ^{ | deletes node1 and all it's edges. |
| ^{ | returns a list of nodes |
| ^{ | returns the number of nodes |
| ^{ | returns nodes with edges from node 1 |
| ^{ | returns nodes with edges to node 2 |
| ^{ | returns nodes with 2 incoming edges |
| ^{ | returns nodes with 2 outgoing edges |
| ^{ | adds edge to g for vector ^{ |
| ^{ | returns value of edge between nodes 1 and 2 |
| ^{ | returns ^{ similar to ^{ |
| ^{ | removes edge between nodes 1 and 2 |
| ^{ | returns a list of edges (along a path if given). |
| ^{ | returns edges outgoing from node 1 |
| ^{ | returns edges incoming to node 2 |
| ^{ | returns the number of edges |
| ^{ | updates the graph from a dictionary |
| ^{ | dumps the graph as a dictionary |
| ^{ | updates the graph from a list |
| ^{ | dumps the graph as a list of edges |
| ^{ | finds the path with smallest edge sum |
| ^{ | finds the with least number of hops |
| ^{ | finds a path between 2 nodes (start, end) using DFS and backtracking. |
| ^{ | finds the distance following a given path. |
| ^{ | finds the maximum flow between a source and a sink |
| ^{ | solves the traveling salesman problem for the graph |
| ^{ | determines if graph ^{ |
| ^{ | determines if graph is n-partite |
| ^{ | determines if there are cycles in the graph |
| ^{ | compares two paths, returns True if they're the same. |
| ^{ | constructs the adjacency matrix for the graph. |
| ^{ | finds the shortest path between all nodes. |
| ^{ | finds the shortest tree for all pairs. |
| ^{ | asserts whether a path ^{ |
| ^{ | finds all combinations of paths between 2 nodes. |
常见问题解答
| want to | doesn't work | do instead | but why? |
|---|---|---|---|
| have multiple edges between two nodes | ^{ | Add dummy nodes ^{ ^{ | Explicit is better than implicit. |
| multiple values on an edge | ^{ | Have two graphs ^{ ^{ | Most graph algorithms don't work with multiple values |
示例
示例包含了一些常见操作研究的教程/解决方案 以及计算机科学问题，当把它们当作一个图来处理时就变得简单了。
| module | function | description |
|---|---|---|
| assignment_problem.py | assignment_problem | solves the assignment problem |
| hashgraph.py | merkle_tree | datablocks |
| hashgraph.py | graph_hash | computes the sha256 of a graphs nodes and edges |
| hashgraph.py | flow_graph_hash | computes the sha256 of a graph with multiple sources and sinks |
| knapsack_problem.py | knapsack problem | solves the knapsack problem |
| wtap.py | weapons-target assignment problem | solves the WTAP problem. |
欢迎加入QQ群-->： 979659372
