Skip to main content

vcsgraph

A Python library providing graph algorithms optimized for version control systems.

Overview

vcsgraph is a high-performance graph algorithms library specifically designed for working with version control system (VCS) data structures. It provides efficient implementations of common graph operations needed by VCS tools, with both pure Python and Rust-accelerated implementations for performance-critical operations.

Features

  • Topological Sorting: Multiple algorithms for sorting commits/revisions in topological order
  • Graph Traversal: Efficient algorithms for traversing revision graphs and finding common ancestors
  • Multi-parent Support: Handle complex merge scenarios with multiple parent revisions
  • Known Graph Operations: Optimized operations on graphs where the full structure is known in advance
  • Rust Acceleration: Performance-critical algorithms implemented in Rust with Python bindings via PyO3

Installation

pip install vcsgraph

Key Components

Graph Operations

The Graph class provides fundamental graph operations:

  • Finding least common ancestors (LCA)
  • Finding unique ancestors
  • Computing differences between revision sets
  • Finding merge bases between branches

Topological Sorting

Multiple sorting implementations optimized for different use cases:

  • topo_sort(): Fast sorting when the complete result is needed
  • TopoSorter: Iterator-based sorting for processing partial results
  • MergeSorter: Specialized sorting that preserves merge history

Multi-parent Diffs

The MultiParent class handles complex diff scenarios with multiple parent revisions, essential for three-way merges and conflict resolution.

Known Graph

The KnownGraph class provides optimized operations when the complete graph structure is known, enabling faster ancestor calculations and traversals.

Usage Examples

Basic Topological Sort

from vcsgraph import topo_sort

# Define a graph as a list of (node, parents) tuples
graph = [
    (b'rev1', []),
    (b'rev2', [b'rev1']),
    (b'rev3', [b'rev1']),
    (b'rev4', [b'rev2', b'rev3']),
]

# Sort nodes topologically (parents before children)
sorted_nodes = topo_sort(graph)

Using Graph for Ancestry Operations

from vcsgraph import Graph, DictParentsProvider

# Create a parents provider from a dictionary
ancestry = {
    b'rev1': (b'null:',),
    b'rev2a': (b'rev1',),
    b'rev2b': (b'rev1',),
    b'rev3': (b'rev2a',),
    b'rev4': (b'rev3', b'rev2b'),
}
parents_provider = DictParentsProvider(ancestry)

# Create a graph and find merge bases
graph = Graph(parents_provider)
merge_base = graph.find_merge_base(b'rev2a', b'rev2b')

Working with Known Graphs

from vcsgraph import KnownGraph

# Create a known graph from parent relationships
parent_map = {
    b'rev1': (b'null:',),
    b'rev2': (b'rev1',),
    b'rev3': (b'rev2',),
}
kg = KnownGraph(parent_map)

# Get heads (revisions with no children)
heads = kg.heads([b'rev1', b'rev2', b'rev3'])

Performance

The library uses Rust for performance-critical operations while maintaining a Python interface. Key optimizations include:

  • Memory-efficient graph representations
  • Optimized ancestor searching algorithms
  • Lazy evaluation where possible
  • Caching of frequently accessed data

License

This project is licensed under the GNU General Public License v2 or later. See the COPYING.txt file for details.

Origins

This library was originally part of the Breezy version control system and has been extracted as a standalone package for use in other VCS-related projects.

Download files

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

Source Distribution

vcsgraph-0.3.2.tar.gz (99.2 kB view details)

Uploaded Source

Built Distributions

If you're not sure about the file name format, learn more about wheel file names.

vcsgraph-0.3.2-cp313-cp313-manylinux_2_28_x86_64.whl (639.1 kB view details)

Uploaded CPython 3.13manylinux: glibc 2.28+ x86-64

vcsgraph-0.3.2-cp313-cp313-manylinux_2_28_aarch64.whl (599.6 kB view details)

Uploaded CPython 3.13manylinux: glibc 2.28+ ARM64

vcsgraph-0.3.2-cp312-cp312-manylinux_2_28_x86_64.whl (639.5 kB view details)

Uploaded CPython 3.12manylinux: glibc 2.28+ x86-64

vcsgraph-0.3.2-cp312-cp312-manylinux_2_28_aarch64.whl (600.2 kB view details)

Uploaded CPython 3.12manylinux: glibc 2.28+ ARM64

vcsgraph-0.3.2-cp311-cp311-manylinux_2_28_x86_64.whl (642.4 kB view details)

Uploaded CPython 3.11manylinux: glibc 2.28+ x86-64

vcsgraph-0.3.2-cp311-cp311-manylinux_2_28_aarch64.whl (605.1 kB view details)

Uploaded CPython 3.11manylinux: glibc 2.28+ ARM64

vcsgraph-0.3.2-cp310-cp310-manylinux_2_28_x86_64.whl (644.9 kB view details)

Uploaded CPython 3.10manylinux: glibc 2.28+ x86-64

vcsgraph-0.3.2-cp310-cp310-manylinux_2_28_aarch64.whl (608.1 kB view details)

Uploaded CPython 3.10manylinux: glibc 2.28+ ARM64

File details

Details for the file vcsgraph-0.3.2.tar.gz.

File metadata

  • Download URL: vcsgraph-0.3.2.tar.gz
  • Upload date:
  • Size: 99.2 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/6.1.0 CPython/3.13.12

File hashes

Hashes for vcsgraph-0.3.2.tar.gz
Algorithm Hash digest
SHA256 814a429ba0372b9e443c88b9708eee4bfac33aad3e97dc64fb4e5ffe34e1102b
MD5 521f27085a9f725d76de0ae31277ab0f
BLAKE2b-256 ff7af2d48eb3ee38aca9b11644a8240f16c6d445f2027437c566db71b6afcd0f

See more details on using hashes here.

Provenance

The following attestation bundles were made for vcsgraph-0.3.2.tar.gz:

Publisher: wheels.yaml on breezy-team/vcsgraph

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file vcsgraph-0.3.2-cp313-cp313-manylinux_2_28_x86_64.whl.

File metadata

File hashes

Hashes for vcsgraph-0.3.2-cp313-cp313-manylinux_2_28_x86_64.whl
Algorithm Hash digest
SHA256 88031e5bcb0b00f2b138de406fb5a3b756fd3c107fb1b5062d01c7de38b94bb1
MD5 401bf4e19c15326dcf4580203d79a96e
BLAKE2b-256 17377d409457c63cac370109c0071f713f5588c95c5161108e3a93436c65bd4f

See more details on using hashes here.

Provenance

The following attestation bundles were made for vcsgraph-0.3.2-cp313-cp313-manylinux_2_28_x86_64.whl:

Publisher: wheels.yaml on breezy-team/vcsgraph

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file vcsgraph-0.3.2-cp313-cp313-manylinux_2_28_aarch64.whl.

File metadata

File hashes

Hashes for vcsgraph-0.3.2-cp313-cp313-manylinux_2_28_aarch64.whl
Algorithm Hash digest
SHA256 ce42bb6cf1cbe98fc6902e32722e1e5dc62d9442969875a51bce98556acab123
MD5 d043b86f74c98654f2dfa66d81a7ed85
BLAKE2b-256 ba4a9bd8194f14bbb17e4be68fc35b854d2c5943d9558cae42bf692ee321d1d9

See more details on using hashes here.

Provenance

The following attestation bundles were made for vcsgraph-0.3.2-cp313-cp313-manylinux_2_28_aarch64.whl:

Publisher: wheels.yaml on breezy-team/vcsgraph

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file vcsgraph-0.3.2-cp312-cp312-manylinux_2_28_x86_64.whl.

File metadata

File hashes

Hashes for vcsgraph-0.3.2-cp312-cp312-manylinux_2_28_x86_64.whl
Algorithm Hash digest
SHA256 7148a038831136ffe0211ba71387d459fefc3f9bccf496affc92f481112b57d9
MD5 5ae151fe4bd76c008cd9fc58e0de72b0
BLAKE2b-256 c1209f66d99d8611572db6280013a3ae4acbfb50d7668fd789f139d696bc4b94

See more details on using hashes here.

Provenance

The following attestation bundles were made for vcsgraph-0.3.2-cp312-cp312-manylinux_2_28_x86_64.whl:

Publisher: wheels.yaml on breezy-team/vcsgraph

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file vcsgraph-0.3.2-cp312-cp312-manylinux_2_28_aarch64.whl.

File metadata

File hashes

Hashes for vcsgraph-0.3.2-cp312-cp312-manylinux_2_28_aarch64.whl
Algorithm Hash digest
SHA256 0aa0de480fb694f516180138b906c89363f8d84b1d5527b4a4718b7f3d93c437
MD5 ac903fa49cd27210a076e966a7df8e7c
BLAKE2b-256 14f8456731e85f795ac2067bb0b2a4233d84be8d3f820c8779ffd3aad5cab378

See more details on using hashes here.

Provenance

The following attestation bundles were made for vcsgraph-0.3.2-cp312-cp312-manylinux_2_28_aarch64.whl:

Publisher: wheels.yaml on breezy-team/vcsgraph

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file vcsgraph-0.3.2-cp311-cp311-manylinux_2_28_x86_64.whl.

File metadata

File hashes

Hashes for vcsgraph-0.3.2-cp311-cp311-manylinux_2_28_x86_64.whl
Algorithm Hash digest
SHA256 fd9874a3489836e2f66cc69910f3d4c358d0c867b69aa1e645acd90e18839df0
MD5 cd58b1c080c22d819f85df1fef6bc826
BLAKE2b-256 b9d4fb685b276cb1ff12d886307a82ba6d878364b79dba6ad46e2cc7d98a8eba

See more details on using hashes here.

Provenance

The following attestation bundles were made for vcsgraph-0.3.2-cp311-cp311-manylinux_2_28_x86_64.whl:

Publisher: wheels.yaml on breezy-team/vcsgraph

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file vcsgraph-0.3.2-cp311-cp311-manylinux_2_28_aarch64.whl.

File metadata

File hashes

Hashes for vcsgraph-0.3.2-cp311-cp311-manylinux_2_28_aarch64.whl
Algorithm Hash digest
SHA256 8c7b17c5a142310fcf7189afd947d9c6939020e688b32c9343862aba32c6214b
MD5 319e046584b035f6243729eb3f2a4bd5
BLAKE2b-256 30d4bc024931540422989c16b4f8b123e27c911edb8b32fdc777f0657fa0d28b

See more details on using hashes here.

Provenance

The following attestation bundles were made for vcsgraph-0.3.2-cp311-cp311-manylinux_2_28_aarch64.whl:

Publisher: wheels.yaml on breezy-team/vcsgraph

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file vcsgraph-0.3.2-cp310-cp310-manylinux_2_28_x86_64.whl.

File metadata

File hashes

Hashes for vcsgraph-0.3.2-cp310-cp310-manylinux_2_28_x86_64.whl
Algorithm Hash digest
SHA256 9d23279f1cbf776b53c9e4b6fad86a3188ce775c6bdbfd552a8ad9efc7cc81bd
MD5 a40c26b1859519314761a23748c077af
BLAKE2b-256 1ef0c573562988efeb9aa5a10b3b8c60e788d405ddf85d4c5c283cd09624f896

See more details on using hashes here.

Provenance

The following attestation bundles were made for vcsgraph-0.3.2-cp310-cp310-manylinux_2_28_x86_64.whl:

Publisher: wheels.yaml on breezy-team/vcsgraph

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file vcsgraph-0.3.2-cp310-cp310-manylinux_2_28_aarch64.whl.

File metadata

File hashes

Hashes for vcsgraph-0.3.2-cp310-cp310-manylinux_2_28_aarch64.whl
Algorithm Hash digest
SHA256 bf453d9feffd55488432ebf4407a01930939b78d138172402a3bb4c5b8054a40
MD5 598004ed7fb54d96a6d6bb64d2c01eb9
BLAKE2b-256 5a9d51e0a83824c03b2ba41d8fc5ac72f123b2478105ce232a7c089d8106467b

See more details on using hashes here.

Provenance

The following attestation bundles were made for vcsgraph-0.3.2-cp310-cp310-manylinux_2_28_aarch64.whl:

Publisher: wheels.yaml on breezy-team/vcsgraph

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

Supported by

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