|PyPI version| |PyPI status| |PyPI pyversions| |PyPI license| |CI| |CodeCov| |Documentation Status| |Code style| |GitHub issues|
.. |PyPI version| image:: https://badge.fury.io/py/nographs.svg
:target: https://pypi.python.org/pypi/nographs/
.. |PyPI status| image:: https://img.shields.io/pypi/status/nographs.svg
:target: https://pypi.python.org/pypi/nographs/
.. |PyPI pyversions| image:: https://img.shields.io/pypi/pyversions/nographs.svg
:target: https://pypi.python.org/pypi/nographs/
.. |PyPy versions| image:: https://img.shields.io/badge/PyPy-3.11-blue
:target: https://pypi.python.org/pypi/nographs/
.. |PyPI license| image:: https://img.shields.io/pypi/l/nographs.svg
:target: https://github.com/HeWeMel/nographs/blob/main/LICENSE
.. |CI| image:: https://github.com/hewemel/nographs/workflows/CI%20(tests,%20flake8,%20mypy)/badge.svg?branch=main
:target: https://github.com/hewemel/nographs/actions?query=workflow%3ACI%20(pip)
.. |CodeCov| image:: https://img.shields.io/codecov/c/gh/HeWeMel/NoGraphs/main
:target: https://codecov.io/gh/HeWeMel/NoGraphs
.. |Documentation Status| image:: https://readthedocs.org/projects/nographs/badge/?version=latest
:target: http://nographs.readthedocs.io/?badge=latest
.. |Code style| image:: https://img.shields.io/badge/code%20style-black-000000.svg
:target: https://github.com/psf/black
.. |GitHub issues| image:: https://img.shields.io/github/issues/HeWeMel/nographs.svg
:target: https://GitHub.com/HeWeMel/nographs/issues/
NoGraphs: Graph analysis on the fly
===================================
NoGraphs simplifies the analysis of graphs that can not or should not be fully
computed, stored or adapted, e.g. infinite graphs, large graphs and graphs with
expensive computations.
(Here, the word *graph* denotes the
`thing with vertices and edges <https://en.wikipedia.org/wiki/Glossary_of_graph_theory>`_,
not with diagrams.)
The approach: Graphs are
**computed and/or adapted in application code on the fly**
(when needed and as far as needed). Also,
**the analysis and the reporting of results by the library happen on the fly**
(when, and as far as, results can already be derived).
Think of it as *graph analysis - the lazy (evaluation) way*.
**Documentation**
- `Homepage of the documentation <https://nographs.readthedocs.io>`__
- `Installation guide <https://nographs.readthedocs.io/en/latest/installation.html>`__
- `Tutorial <https://nographs.readthedocs.io/en/latest/concept_and_examples.html>`__
(contains many `examples <https://nographs.readthedocs.io/en/latest/concept_and_examples.html#examples>`__)
- `API reference <https://nographs.readthedocs.io/en/latest/api.html>`__
**Feature overview**
- Unidirectional traversal algorithms: DFS, BFS, topological search,
Dijkstra, A\* and MST.
- Bidirectional search algorithms: BFS and Dijkstra.
- Results: Reachability, depth, distance, paths and trees.
Paths can be
calculated with vertices, edges, or attributed edges,
and can be iterated in both directions.
- Flexible graph notion:
- Infinite directed multigraphs with loops and
attributes (this includes
multiple adjacency, cycles, self-loops,
directed edges,
weighted edges and attributed edges).
- Infinite graphs are supported, but need to be
locally finite (i.e., a vertex has only finitely many outgoing edges).
- Generic API:
- Vertices: Can be anything except for None. Hashable vertices can be
used directly, unhashable vertices can be used together with
hashable identifiers.
- Edge weights and distances: Wide range of data types
supported (float, int, Decimal, mpmath.mpf and others), e.g.,
for high precision computations.
- Edge attributes: Any object, e.g, a container
with further data.
- Identity and equivalence of vertices can be chosen / defined.
- Bookkeeping: Several sets of bookkeeping data structures
are predefined, optimized for different situations (data types used by the
application, hashing vs. indexing, collections for *Python* objects or *C* native
data types,...); Adaptable and extendable, e.g., specialized
collections of 3rd party libraries can be integrated easily and runtime
efficiently
- Flexible API: The concept of implicit graphs that NoGraphs is based on
allows for an API that eases
operations like
graph pruning, graph abstraction, the typical binary
graph operations (union, intersection, several types of products), the
computation of search-aware graphs, the combination of
problem reduction with lazy evaluation,
and traversals of vertex equivalence classes on the fly.
Bookkeeping data can be
pre-initialized and accessed during computations.
- Typing: The API can be used fully typed (optionally).
- Implementation: Pure Python (>=3.9). It introduces no further dependencies.
- CI tests: For all supported versions of Python and both supported interpreters
CPython and PyPy, both code and docs, 100% code coverage.
- Runtime and memory performance: Have been goals (CPython). In its domain, it often
even outperforms Rust- and C-based libraries. Using PyPy improves its performance
further.
**Extras** (outside of the core of NoGraphs)
- Computation of exact solutions for (small)
traveling salesman problems (shortest / longest route,
positive / zero / negative edge weights, graph does not need to be complete)
- Dijkstra shortest paths algorithm for
infinitely branching graphs with locally sorted edges.
- Example for computing the
longest path
between two vertices in a weighted, acyclic graph.
- Gadget functions for test purposes. They make the easy task of
adapting existing explicit test graphs a no brainer, may they be
stored in edge indices or edge iterables
or in arrays.
**Example**
Our graph is directed, weighted and has infinitely many edges. These edges are
defined in application code by the following function. For a vertex *i*
(here: an integer) as the first of two
parameters, it yields the edges that start at *i* as tuples
*(end_vertex, edge_weight)*. What a strange graph - we do not know how it
looks like...
.. code-block:: python
>>> def next_edges(i, _):
... j = (i + i // 6) % 6
... yield i + 1, j * 2 + 1
... if i % 2 == 0:
... yield i + 6, 7 - j
... elif i % 1200000 > 5:
... yield i - 6, 1
We would like to find out the *distance* of vertex 5 from vertex 0, i.e., the minimal
necessary sum of edge weights of any path from 0 to 5, and (one of) the *shortest
paths* from 0 to 5.
We do not know which part of the graph is necessary to look at in order to find the
shortest path and to make sure, it is really the shortest. So, we use the
traversal strategy *TraversalShortestPaths* of NoGraphs.
It implements the well-known *Dijkstra* graph algorithm in the lazy evaluation
style of NoGraphs.
.. code-block:: python
>>> import nographs as nog
>>> traversal = nog.TraversalShortestPaths(next_edges)
We ask NoGraphs to traverse the graph starting at vertex 0, to calculate paths
while doing so, and to stop when visiting vertex 5.
.. code-block:: python
>>> traversal.start_from(0, build_paths=True).go_to(5)
5
The state data of this vertex visit contains our results:
.. code-block:: python
>>> traversal.distance
24
>>> traversal.paths[5]
(0, 1, 2, 3, 4, 10, 16, 17, 11, 5)
We learn that we need to examine the graph at least till vertex 17 to find the
shortest path from 0 to 5. It is not easy to see that from the definition
of the graph...
A part of the graph, the vertices up to 41, is shown in the following picture.
Arrows denote directed edges. The edges in red show shortest paths from
0 to other vertices.
.. image:: https://nographs.readthedocs.io/en/latest/_images/nographs_example_graph.PNG
:class: with-shadow
:width: 600px
**And now?**
Can you imagine...
- An infinite generator of primes, defined by just a graph and
a call to a standard graph algorithm?
- Or a graph that defines an infinite set
of Towers of Hanoi problems in a generic way, without fixing the number of
towers, disk sizes, and the start and goal configuration - and a specific
problem instance is solved by just one library call?
- Or a way for computing an exact solution for traveling salesman problems,
that is based on just a graph and a call of the Dijkstra single source shortest path
algorithm?
- Or graphs that are dynamically
computed based on other graphs, or on analysis results about other graphs,
or even on partial analysis results for already processed parts of the same graph?
Let's `build it <https://nographs.readthedocs.io/en/latest/installation.html>`__.
Welcome to NoGraphs!
Raw data
{
"_id": null,
"home_page": "https://github.com/HeWeMel/nographs",
"name": "nographs",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.9, <4",
"maintainer_email": "",
"keywords": "graph,network,search,traverse,analysis,infinite,lazy,shortest,distance,depth,DFS,breadth,BFS,Dijkstra,topological,spanning,MST,TSP",
"author": "Dr. Helmut Melcher",
"author_email": "HeWeMel@web.de",
"download_url": "https://files.pythonhosted.org/packages/1f/9a/03a38561d3518753adcaac40ad3e2f6cae9f8e462d643526e404c3ea2a7c/nographs-3.3.2.tar.gz",
"platform": null,
"description": "|PyPI version| |PyPI status| |PyPI pyversions| |PyPI license| |CI| |CodeCov| |Documentation Status| |Code style| |GitHub issues|\r\n\r\n.. |PyPI version| image:: https://badge.fury.io/py/nographs.svg\r\n :target: https://pypi.python.org/pypi/nographs/\r\n\r\n.. |PyPI status| image:: https://img.shields.io/pypi/status/nographs.svg\r\n :target: https://pypi.python.org/pypi/nographs/\r\n\r\n.. |PyPI pyversions| image:: https://img.shields.io/pypi/pyversions/nographs.svg\r\n :target: https://pypi.python.org/pypi/nographs/\r\n\r\n.. |PyPy versions| image:: https://img.shields.io/badge/PyPy-3.11-blue\r\n :target: https://pypi.python.org/pypi/nographs/\r\n\r\n.. |PyPI license| image:: https://img.shields.io/pypi/l/nographs.svg\r\n :target: https://github.com/HeWeMel/nographs/blob/main/LICENSE\r\n\r\n.. |CI| image:: https://github.com/hewemel/nographs/workflows/CI%20(tests,%20flake8,%20mypy)/badge.svg?branch=main\r\n :target: https://github.com/hewemel/nographs/actions?query=workflow%3ACI%20(pip)\r\n\r\n.. |CodeCov| image:: https://img.shields.io/codecov/c/gh/HeWeMel/NoGraphs/main\r\n :target: https://codecov.io/gh/HeWeMel/NoGraphs\r\n\r\n.. |Documentation Status| image:: https://readthedocs.org/projects/nographs/badge/?version=latest\r\n :target: http://nographs.readthedocs.io/?badge=latest\r\n\r\n.. |Code style| image:: https://img.shields.io/badge/code%20style-black-000000.svg\r\n :target: https://github.com/psf/black\r\n\r\n.. |GitHub issues| image:: https://img.shields.io/github/issues/HeWeMel/nographs.svg\r\n :target: https://GitHub.com/HeWeMel/nographs/issues/\r\n\r\n\r\nNoGraphs: Graph analysis on the fly\r\n===================================\r\n\r\nNoGraphs simplifies the analysis of graphs that can not or should not be fully\r\ncomputed, stored or adapted, e.g. infinite graphs, large graphs and graphs with\r\nexpensive computations.\r\n(Here, the word *graph* denotes the\r\n`thing with vertices and edges <https://en.wikipedia.org/wiki/Glossary_of_graph_theory>`_,\r\nnot with diagrams.)\r\n\r\nThe approach: Graphs are\r\n**computed and/or adapted in application code on the fly**\r\n(when needed and as far as needed). Also,\r\n**the analysis and the reporting of results by the library happen on the fly**\r\n(when, and as far as, results can already be derived).\r\n\r\nThink of it as *graph analysis - the lazy (evaluation) way*.\r\n\r\n**Documentation**\r\n\r\n- `Homepage of the documentation <https://nographs.readthedocs.io>`__\r\n- `Installation guide <https://nographs.readthedocs.io/en/latest/installation.html>`__\r\n- `Tutorial <https://nographs.readthedocs.io/en/latest/concept_and_examples.html>`__\r\n (contains many `examples <https://nographs.readthedocs.io/en/latest/concept_and_examples.html#examples>`__)\r\n- `API reference <https://nographs.readthedocs.io/en/latest/api.html>`__\r\n\r\n**Feature overview**\r\n\r\n- Unidirectional traversal algorithms: DFS, BFS, topological search,\r\n Dijkstra, A\\* and MST.\r\n- Bidirectional search algorithms: BFS and Dijkstra.\r\n- Results: Reachability, depth, distance, paths and trees.\r\n Paths can be\r\n calculated with vertices, edges, or attributed edges,\r\n and can be iterated in both directions.\r\n- Flexible graph notion:\r\n\r\n - Infinite directed multigraphs with loops and\r\n attributes (this includes\r\n multiple adjacency, cycles, self-loops,\r\n directed edges,\r\n weighted edges and attributed edges).\r\n - Infinite graphs are supported, but need to be\r\n locally finite (i.e., a vertex has only finitely many outgoing edges).\r\n\r\n- Generic API:\r\n\r\n - Vertices: Can be anything except for None. Hashable vertices can be\r\n used directly, unhashable vertices can be used together with\r\n hashable identifiers.\r\n - Edge weights and distances: Wide range of data types\r\n supported (float, int, Decimal, mpmath.mpf and others), e.g.,\r\n for high precision computations.\r\n - Edge attributes: Any object, e.g, a container\r\n with further data.\r\n - Identity and equivalence of vertices can be chosen / defined.\r\n - Bookkeeping: Several sets of bookkeeping data structures\r\n are predefined, optimized for different situations (data types used by the\r\n application, hashing vs. indexing, collections for *Python* objects or *C* native\r\n data types,...); Adaptable and extendable, e.g., specialized\r\n collections of 3rd party libraries can be integrated easily and runtime\r\n efficiently\r\n\r\n- Flexible API: The concept of implicit graphs that NoGraphs is based on\r\n allows for an API that eases\r\n operations like\r\n graph pruning, graph abstraction, the typical binary\r\n graph operations (union, intersection, several types of products), the\r\n computation of search-aware graphs, the combination of\r\n problem reduction with lazy evaluation,\r\n and traversals of vertex equivalence classes on the fly.\r\n Bookkeeping data can be\r\n pre-initialized and accessed during computations.\r\n- Typing: The API can be used fully typed (optionally).\r\n- Implementation: Pure Python (>=3.9). It introduces no further dependencies.\r\n- CI tests: For all supported versions of Python and both supported interpreters\r\n CPython and PyPy, both code and docs, 100% code coverage.\r\n- Runtime and memory performance: Have been goals (CPython). In its domain, it often\r\n even outperforms Rust- and C-based libraries. Using PyPy improves its performance\r\n further.\r\n\r\n**Extras** (outside of the core of NoGraphs)\r\n\r\n- Computation of exact solutions for (small)\r\n traveling salesman problems (shortest / longest route,\r\n positive / zero / negative edge weights, graph does not need to be complete)\r\n- Dijkstra shortest paths algorithm for\r\n infinitely branching graphs with locally sorted edges.\r\n- Example for computing the\r\n longest path\r\n between two vertices in a weighted, acyclic graph.\r\n- Gadget functions for test purposes. They make the easy task of\r\n adapting existing explicit test graphs a no brainer, may they be\r\n stored in edge indices or edge iterables\r\n or in arrays.\r\n\r\n**Example**\r\n\r\nOur graph is directed, weighted and has infinitely many edges. These edges are\r\ndefined in application code by the following function. For a vertex *i*\r\n(here: an integer) as the first of two\r\nparameters, it yields the edges that start at *i* as tuples\r\n*(end_vertex, edge_weight)*. What a strange graph - we do not know how it\r\nlooks like...\r\n\r\n.. code-block:: python\r\n\r\n >>> def next_edges(i, _):\r\n ... j = (i + i // 6) % 6\r\n ... yield i + 1, j * 2 + 1\r\n ... if i % 2 == 0:\r\n ... yield i + 6, 7 - j\r\n ... elif i % 1200000 > 5:\r\n ... yield i - 6, 1\r\n\r\nWe would like to find out the *distance* of vertex 5 from vertex 0, i.e., the minimal\r\nnecessary sum of edge weights of any path from 0 to 5, and (one of) the *shortest\r\npaths* from 0 to 5.\r\n\r\nWe do not know which part of the graph is necessary to look at in order to find the\r\nshortest path and to make sure, it is really the shortest. So, we use the\r\ntraversal strategy *TraversalShortestPaths* of NoGraphs.\r\nIt implements the well-known *Dijkstra* graph algorithm in the lazy evaluation\r\nstyle of NoGraphs.\r\n\r\n.. code-block:: python\r\n\r\n >>> import nographs as nog\r\n >>> traversal = nog.TraversalShortestPaths(next_edges)\r\n\r\nWe ask NoGraphs to traverse the graph starting at vertex 0, to calculate paths\r\nwhile doing so, and to stop when visiting vertex 5.\r\n\r\n.. code-block:: python\r\n\r\n >>> traversal.start_from(0, build_paths=True).go_to(5)\r\n 5\r\n\r\nThe state data of this vertex visit contains our results:\r\n\r\n.. code-block:: python\r\n\r\n >>> traversal.distance\r\n 24\r\n >>> traversal.paths[5]\r\n (0, 1, 2, 3, 4, 10, 16, 17, 11, 5)\r\n\r\nWe learn that we need to examine the graph at least till vertex 17 to find the\r\nshortest path from 0 to 5. It is not easy to see that from the definition\r\nof the graph...\r\n\r\nA part of the graph, the vertices up to 41, is shown in the following picture.\r\nArrows denote directed edges. The edges in red show shortest paths from\r\n0 to other vertices.\r\n\r\n.. image:: https://nographs.readthedocs.io/en/latest/_images/nographs_example_graph.PNG\r\n :class: with-shadow\r\n :width: 600px\r\n\r\n**And now?**\r\n\r\nCan you imagine...\r\n\r\n- An infinite generator of primes, defined by just a graph and\r\n a call to a standard graph algorithm?\r\n- Or a graph that defines an infinite set\r\n of Towers of Hanoi problems in a generic way, without fixing the number of\r\n towers, disk sizes, and the start and goal configuration - and a specific\r\n problem instance is solved by just one library call?\r\n- Or a way for computing an exact solution for traveling salesman problems,\r\n that is based on just a graph and a call of the Dijkstra single source shortest path\r\n algorithm?\r\n- Or graphs that are dynamically\r\n computed based on other graphs, or on analysis results about other graphs,\r\n or even on partial analysis results for already processed parts of the same graph?\r\n\r\nLet's `build it <https://nographs.readthedocs.io/en/latest/installation.html>`__.\r\n\r\nWelcome to NoGraphs!\r\n",
"bugtrack_url": null,
"license": "",
"summary": "Graph analysis \u2013 the lazy (evaluation) way: Analysis on the fly, for graphs, that are computed and/or adapted on the fly.",
"version": "3.3.2",
"project_urls": {
"Bug Reports": "https://github.com/hewemel/nographs/issues",
"Documentation": "https://nographs.readthedocs.io/",
"Homepage": "https://github.com/HeWeMel/nographs",
"Source": "https://github.com/hewemel/nographs/"
},
"split_keywords": [
"graph",
"network",
"search",
"traverse",
"analysis",
"infinite",
"lazy",
"shortest",
"distance",
"depth",
"dfs",
"breadth",
"bfs",
"dijkstra",
"topological",
"spanning",
"mst",
"tsp"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "fcf5c0952600365c500f83e18a7a3ab4aca60cc58e3f3ae190bd3507a3b79204",
"md5": "85e8c744145489006346f4d4e47cb1cd",
"sha256": "c40d0ce86fc8f99e1418f43483c19fec5eeb5c160edfbbe489b0796c60c3e5ce"
},
"downloads": -1,
"filename": "nographs-3.3.2-py3-none-any.whl",
"has_sig": false,
"md5_digest": "85e8c744145489006346f4d4e47cb1cd",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.9, <4",
"size": 79706,
"upload_time": "2024-02-04T19:13:51",
"upload_time_iso_8601": "2024-02-04T19:13:51.658204Z",
"url": "https://files.pythonhosted.org/packages/fc/f5/c0952600365c500f83e18a7a3ab4aca60cc58e3f3ae190bd3507a3b79204/nographs-3.3.2-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "1f9a03a38561d3518753adcaac40ad3e2f6cae9f8e462d643526e404c3ea2a7c",
"md5": "c6670f84cd75356819488d7913465c5e",
"sha256": "9a2db9c85805cdaba4f3a6a4b24e500985be293d9ca1b3c10aab1356e28440b1"
},
"downloads": -1,
"filename": "nographs-3.3.2.tar.gz",
"has_sig": false,
"md5_digest": "c6670f84cd75356819488d7913465c5e",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.9, <4",
"size": 105871,
"upload_time": "2024-02-04T19:13:53",
"upload_time_iso_8601": "2024-02-04T19:13:53.433587Z",
"url": "https://files.pythonhosted.org/packages/1f/9a/03a38561d3518753adcaac40ad3e2f6cae9f8e462d643526e404c3ea2a7c/nographs-3.3.2.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-02-04 19:13:53",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "HeWeMel",
"github_project": "nographs",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "nographs"
}
JSON
