Skip to main content

A graph library

Project description

graph

Build Status

A simple graph library...
... A bit like networkx, just without the overhead...
... similar to graph-tool, without the Python 2.7 legacy...


Install:

pip install graph-theory

Import:

import Graph
g = Graph()

Modules:

module description
from graph import Graph, Graph2D, Graph3D Elementary methods (see basic methods below), 2D and 3D graphs.
from graph.assignment_problem import ... solvers for assignment problem, the Weapons-Target Assignment Problem, ...
from graph.flow_problem import ... maximum flow
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.scheduling import sp_solver Scheduling problem solver.
from graph.search import ... shortest path, breadth-first, depth-first
from graph.topology import ... Topological comparisons and operators: make/assert subgraph, detect partitions, path comparisons, cycle detection, path verification, network range
from graph.transform import ... Isomorphic transformation methods like adjacency matrix, all-pairs-shortest path, etc.

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

methods description
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.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.
similar to d.get(key, 3)
g.del_edge(1,2) removes edge between nodes 1 and 2
g.edges(path=[path]) returns a list of edges (along a path if given).
g.edges(from_node=1) returns edges outgoing from node 1
g.edges(to_node=2) returns edges incoming to node 2
len(g.edges()) returns the number of edges
g.from_dict(d) updates the graph from a dictionary
g.to_dict() dumps the graph as a dictionary
g.from_list(L) updates the graph from a list
g.to_list() dumps the graph as a list of edges
g.shortest_path(start,end) finds the path with smallest edge sum
g.breadth_first_search(start,end) finds the with least number of hops
g.depth_first_search(start,end) finds a path between 2 nodes (start, end) using DFS and backtracking.
g.distance_from_path(path) finds the distance following a given path.
g.maximum_flow(source,sink) finds the maximum flow between a source and a sink
g.solve_tsp() solves the traveling salesman problem for the graph
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 cycles in the graph
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.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_paths(start,end) finds all combinations of paths between 2 nodes.

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
[(1,a,3), (a,2,0),
(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
g_a.add_edge(1,2,3)
g_b.add_edge(1,2,4)
Most graph algorithms don't work with multiple values

Specialised modules:

from graph import Graph
from graph import Graph2D
from graph import Graph3D
from graph.hashing import merkle_tree
from graph.assignment_problem import ap_solver
from graph.assignment_problem import wtap_solver
from graph.scheduling_problem import sp_solver

Examples contains a number of tutorial/solutions to common operations research and computer science problems, which are made simple when treated as a graph.

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.

Project details


Release history Release notifications | RSS feed

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

graph-theory-2019.11.13.56955.tar.gz (26.3 kB view hashes)

Uploaded Source

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page