NoGraphs
  • Overview
  • Installation
  • Concept & examples
    • On the fly - the basics
    • Examples
      • Breadth First Search in a maze
      • Breadth First Search for the Towers of Hanoi
      • Depths first search in the integers
      • DFS forest: edges, predecessor relation, and paths
      • DFS forest: events, edge types, and successor relation
      • DFS: all paths and walks
      • Topological sorting of process steps
      • Critical path in a weighted, acyclic graph (using topological search)
      • Longest path in a weighted, acyclic graph (using topological search)
      • Shortest paths in a maze with weights
      • Shortest path search with distance heuristic (A* search)
  • Graphs and adaptation
    • Graphs without edge attributes
    • Graphs with edge attributes
    • Vertices
    • Edge weights
    • Supported special cases
  • Search-aware graphs and start vertices
    • Search-aware graphs
    • Search-aware start vertices
  • Graph pruning, abstraction, multiplication, union and intersection
  • Traversal algorithms
    • Classes for all graphs
    • Classes for weighted graphs
    • State and standard methods of traversal objects
    • Methods for depth and distance ranges
    • Skipping vertex expansion in TraversalDepthFirst
    • Traversing trees
    • Usage in typed code
  • Bidirectional search algorithms
  • Problem reduction - the lazy way
    • The concept
    • Example: Traveling salesman - solved by Dijkstra Shortest Paths
    • Example: Shortest paths in infinitely branching graphs with sorted edges
    • Example: Longest simple path between two vertices - based on DFS
    • Example: Strongly connected components - based on DFS
    • Example: Biconnected components of a connected undirected graph - based on DFS
  • Identity and equivalence of vertices
  • Choosing and changing internal data structures
    • Choosing the optimal gear
    • Defining your own gear
    • Pre-initializing bookkeeping data
  • Gadgets
    • Graphs stored in edge indices or edge iterables
      • Function nographs.adapt_edge_iterable
      • Function adapt_edge_index
    • Graphs stored in arrays
      • Class Array
      • Class Position
      • Example: Hand-made NextVertices function for a maze
  • Performance
    • Qualitative analysis
    • Setting, graph and analysis tasks
    • Comparison of NoGraphs gears
      • Gears
      • Raw data
      • Choosing the optimal gear makes quite a difference
      • (Not really) dense subsets of the natural numbers
    • Comparison to other libraries
      • Libraries
      • Raw data
      • Configuration of NoGraphs
      • One analysis task, and search covers graph: NoGraphs mostly fastest
      • Larger graph, or smaller part to be analyzed: Advantage for NoGraphs
      • More analysis tasks, same graph: Advantage for C and Rust libraries
      • Switching to another interpreter: Advantage for NoGraphs
    • Details about the measurements
    • Comments about the used test code
  • API reference - NoGraphs
    • Type variables for graph adaptation
      • T_vertex
      • T_vertex_id
      • T_weight
      • T_labels
    • Function signatures for graph adaptation
      • Vertex identity
        • VertexToID
        • vertex_as_id()
      • Outgoing edges
        • UnweightedLabeledOutEdge
        • WeightedUnlabeledOutEdge
        • WeightedLabeledOutEdge
      • Next vertices and next edges functions
        • T_strategy
        • NextVertices
        • NextEdges
        • NextLabeledEdges
        • NextWeightedEdges
        • NextWeightedLabeledEdges
        • BNextVertices
        • BNextEdges
        • BNextLabeledEdges
        • BNextWeightedEdges
        • BNextWeightedLabeledEdges
      • Edges as part of trees or paths
        • UnweightedUnlabeledFullEdge
        • UnweightedLabeledFullEdge
        • WeightedUnlabeledFullEdge
        • WeightedLabeledFullEdge
        • WeightedFullEdge
        • WeightedOrLabeledFullEdge
        • AnyFullEdge
    • Traversal and search strategies
      • Strategy
        • Strategy.state_to_str()
    • Traversal strategies
      • Common methods
        • Traversal
      • Traversal classes for all graphs
        • TraversalBreadthFirst
        • TraversalDepthFirst
        • TraversalNeighborsThenDepthFlex
        • TraversalTopologicalSort
      • Traversal classes for weighted graphs
        • TraversalShortestPaths
        • TraversalAStar
        • TraversalMinimumSpanningTree
    • Bidirectional search strategies
      • BSearchBreadthFirstFlex
        • BSearchBreadthFirstFlex
        • BSearchBreadthFirst
      • BSearchShortestPathFlex
        • BSearchShortestPathFlex
        • BSearchShortestPath
    • Paths containers and paths
      • Paths
        • Paths.__contains__()
        • Paths.predecessor()
        • Paths.iter_vertices_to_start()
        • Paths.iter_vertices_from_start()
        • Paths.iter_edges_to_start()
        • Paths.iter_edges_from_start()
        • Paths.iter_labeled_edges_to_start()
        • Paths.iter_labeled_edges_from_start()
        • Paths.__getitem__()
      • Path
        • Path.iter_vertices_from_start()
        • Path.iter_vertices_to_start()
        • Path.iter_edges_from_start()
        • Path.iter_edges_to_start()
        • Path.iter_labeled_edges_to_start()
        • Path.iter_labeled_edges_from_start()
    • Gears
      • The protocols
        • GearWithoutDistances
        • Gear
      • Gears for hashable vertex ids
        • GearForHashableVertexIDs
        • GearDefault
        • GearForHashableVertexIDsAndIntsMaybeFloats
        • GearForHashableVertexIDsAndDecimals
        • GearForHashableVertexIDsAndFloats
      • Gears for integer vertex ids
        • GearForIntVertexIDs
        • GearForIntVertexIDsAndIntsMaybeFloats
        • GearForIntVertexIDsAndDecimals
        • GearForIntVertexIDsAndCFloats
        • GearForIntVertexIDsAndCInts
      • Gears for integer vertices and ids
        • GearForIntVerticesAndIDs
        • GearForIntVerticesAndIDsAndIntsMaybeFloats
        • GearForIntVerticesAndIDsAndDecimals
        • GearForIntVerticesAndIDsAndCFloats
        • GearForIntVerticesAndIDsAndCInts
  • API reference - extras
    • Gadgets for adapting edge data
      • adapt_edge_index()
      • adapt_edge_iterable()
    • Gadgets for adapting array data and positions
      • Common types
        • nographs.Vector
        • nographs.Limits
      • Position
        • Position
      • Array
        • Array
    • Traveling Salesman
      • traveling_salesman_flex()
      • traveling_salesman()
      • GettableProto
        • GettableProto.__getitem__()
    • Shortest paths in infinitely branching graphs
      • State
      • TraversalShortestPathsInfBranchingSortedFlex
        • TraversalShortestPathsInfBranchingSortedFlex.distance
        • TraversalShortestPathsInfBranchingSortedFlex.paths
        • TraversalShortestPathsInfBranchingSortedFlex.distances
        • TraversalShortestPathsInfBranchingSortedFlex.start_from()
        • TraversalShortestPathsInfBranchingSortedFlex.go_for_distance_range()
      • TraversalShortestPathsInfBranchingSorted
  • Index
  • ChangeLog
NoGraphs
  • Search

© Copyright 2022 - 2025, Helmut Melcher.

Built with Sphinx using a theme provided by Read the Docs.