Skip to main content

A Python package to find the shortest path in a graph using Ant Colony Optimization (ACO)

Project description

Ant Colony Optimization

Develop Deploy PyPi version Downloads

A Python package to find the shortest path in a graph using Ant Colony Optimization (ACO).

➡️ Check out my Medium article for a detailed walkthrough 🚀

The Ant colony Optimization algorithm is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs (source).

This implementation of the ACO algorithm uses the NetworkX graph environment.

🏁 Getting Started

To install the package directly from PyPi:

$ pip install aco_routing

🎈 Usage

Check out: example.py

Import all the dependencies:

from aco_routing import ACO
import networkx as nx

Create a NetworkX.Graph object with nodes and edges:

G = nx.DiGraph()

G.add_edge("A", "B", cost=2)
G.add_edge("B", "C", cost=2)
G.add_edge("A", "H", cost=2)
G.add_edge("H", "G", cost=2)
G.add_edge("C", "F", cost=1)
G.add_edge("F", "G", cost=1)
G.add_edge("G", "F", cost=1)
G.add_edge("F", "C", cost=1)
G.add_edge("C", "D", cost=10)
G.add_edge("E", "D", cost=2)
G.add_edge("G", "E", cost=2)

Use ACO to find the shortest path and cost between the source and destination:

aco = ACO(G, ant_max_steps=100, num_iterations=100, ant_random_spawn=True)

aco_path, aco_cost = aco.find_shortest_path(
    source="A",
    destination="D",
    num_ants=100,
)

Output:

ACO path: A -> H -> G -> E -> D
ACO path cost: 8.0

📦 Contents

Ant

aco_routing.Ant

  • An Ant that traverses the graph.

ACO

aco_routing.ACO

  • The traditional Ant Colony Optimization algorithm that spawns ants at various nodes in the graph and finds the shortest path between the specified source and destination (pseudo code).

Contributing

  • Post any issues and suggestions on the GitHub issues page.
  • To contribute, fork the project and then create a pull request back to master.

Project details


Download files

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

Source Distribution

aco_routing-1.1.1.tar.gz (7.6 kB view details)

Uploaded Source

Built Distribution

aco_routing-1.1.1-py3-none-any.whl (8.5 kB view details)

Uploaded Python 3

File details

Details for the file aco_routing-1.1.1.tar.gz.

File metadata

  • Download URL: aco_routing-1.1.1.tar.gz
  • Upload date:
  • Size: 7.6 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/5.1.0 CPython/3.8.18

File hashes

Hashes for aco_routing-1.1.1.tar.gz
Algorithm Hash digest
SHA256 d0a6dc14e7c1c05f55a77b885b1c6f227d61d5d49925778a391e089aea59cdd5
MD5 02f252b1448b4a1e1fbd8d128700d3a5
BLAKE2b-256 80c7a0d2936d1e06952975607cc69a9d516214665d0f49017868a30d818e9324

See more details on using hashes here.

File details

Details for the file aco_routing-1.1.1-py3-none-any.whl.

File metadata

  • Download URL: aco_routing-1.1.1-py3-none-any.whl
  • Upload date:
  • Size: 8.5 kB
  • Tags: Python 3
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/5.1.0 CPython/3.8.18

File hashes

Hashes for aco_routing-1.1.1-py3-none-any.whl
Algorithm Hash digest
SHA256 c79e5b21829830c49cbb064b47c42d86124a057a0e66ed81fdcbf91114236a0b
MD5 c74825f54e89acadaaccad940c6e0a9d
BLAKE2b-256 ba456163a00ce560bbfefd7bdea051987c999ad24f2a8c5292029ad0c4907f77

See more details on using hashes here.

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