Repository files navigation

NoGraphs simplifies the analysis of graphs that can not or should not be fullycomputed, stored or adapted, e.g. infinite graphs, large graphs and graphs withexpensive computations.(Here, the wordgraph denotes thething with vertices and edges,not with diagrams.)

The approach: Graphs arecomputed 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 asgraph analysis - the lazy (evaluation) way.

Documentation

• Homepage of the documentation
• Installation guide
• Tutorial(contains manyexamples)
• API reference

Feature overview

• Unidirectional traversal algorithms: DFS, BFS, topological search,Dijkstra, A* and MST.
• Bidirectional search algorithms: BFS and Dijkstra.
• Results: Reachability, depth, distance, and paths.Paths can becalculated with vertices, edges, or attributed edges,and can be iterated in both directions.Additionally, for DFS:forest, all kinds of edge types, both entering and leaving events,and DFS tree edges orall paths or all walks.
• Flexible graph notion:
  • Infinite directed multigraphs with loops andattributes (this includesmultiple adjacency, cycles, self-loops,directed edges,weighted edges and attributed edges).
  • Infinite graphs are supported, but need to belocally finite (i.e., a vertex has only finitely many outgoing edges).
• Generic API:
  • Vertices: Can be anything except for None. Hashable vertices can beused directly, unhashable vertices can be used together withhashable identifiers.
  • Edge weights and distances: Wide range of data typessupported (float, int, Decimal, mpmath.mpf and others), e.g.,for high precision computations.
  • Edge attributes: Any object, e.g, a containerwith further data.
  • Identity and equivalence of vertices can be chosen / defined.
  • Bookkeeping: Several sets of bookkeeping data structuresare predefined, optimized for different situations (data types used by theapplication, hashing vs. indexing, collections forPython objects orC nativedata types,...); Adaptable and extendable, e.g., specializedcollections of 3rd party libraries can be integrated easily and runtimeefficiently
• Flexible API: The concept of implicit graphs that NoGraphs is based onallows for an API that easesoperations likegraph pruning, graph abstraction, the typical binarygraph operations (union, intersection, several types of products), thecomputation of search-aware graphs, the combination ofproblem reduction with lazy evaluation,and traversals of vertex equivalence classes on the fly.Bookkeeping data can bepre-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 interpretersCPython and PyPy, both code and docs, 100% code coverage.
• Runtime and memory performance: Have been goals (CPython). In its domain, it ofteneven outperforms Rust- and C-based libraries. Using PyPy improves its performancefurther.

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 forinfinitely branching graphs with locally sorted edges.
• Gadget functions for test purposes. They make the easy task ofadapting existing explicit test graphs a no brainer, may they bestored in edge indices or edge iterablesor in arrays.

Examples with further algorithms

• Depth-limited search
• Iterative deepening depth-first search
• Critical pathin a weighted, acyclic graph
• Longest pathbetween two vertices in a weighted, acyclic graph
• Longest pathbetween two vertices in a weighted graph or in an unweighted graph
• Strongly connected componentsof a graph
• Biconnected components of a connected undirected graph

Example

Our graph is directed, weighted and has infinitely many edges. These edges aredefined in application code by the following function. For a vertexi(here: an integer) as the first of twoparameters, it yields the edges that start ati as tuples(end_vertex, edge_weight). What a strange graph - we do not know how itlooks like...

>>>defnext_edges(i,_):...j= (i+i//6)%6...yieldi+1,j*2+1...ifi%2==0:...yieldi+6,7-j...elifi%1200000>5:...yieldi-6,1

We would like to find out thedistance of vertex 5 from vertex 0, i.e., the minimalnecessary sum of edge weights of any path from 0 to 5, and (one of) theshortestpaths from 0 to 5.

We do not know which part of the graph is necessary to look at in order to find theshortest path and to make sure, it is really the shortest. So, we use thetraversal strategyTraversalShortestPaths of NoGraphs.It implements the well-knownDijkstra graph algorithm in the lazy evaluationstyle of NoGraphs.

>>>importnographsasnog>>>traversal=nog.TraversalShortestPaths(next_edges)

We ask NoGraphs to traverse the graph starting at vertex 0, to calculate pathswhile doing so, and to stop when visiting vertex 5.

>>>traversal.start_from(0,build_paths=True).go_to(5)5

The state data of this vertex visit contains our results:

>>>traversal.distance24>>>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 theshortest path from 0 to 5. It is not easy to see that from the definitionof 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 from0 to other vertices.

And now?

Can you imagine...

• An infinite generator of primes, defined by just a graph anda call to a standard graph algorithm?
• Or a graph that defines an infinite setof Towers of Hanoi problems in a generic way, without fixing the number oftowers, disk sizes, and the start and goal configuration - and a specificproblem 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 pathalgorithm?
• Or graphs that are dynamicallycomputed 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'sbuild it.

Welcome to NoGraphs!