Logarithma

git clone https://github.com/softdevcan/logarithma.git
cd logarithma
pip install -e ".[dev,viz]"

import logarithma as lg
import networkx as nx

# Build a weighted graph
G = nx.Graph()
G.add_edge('A', 'B', weight=4)
G.add_edge('A', 'C', weight=2)
G.add_edge('B', 'C', weight=1)
G.add_edge('B', 'D', weight=5)
G.add_edge('C', 'D', weight=8)

# Dijkstra — shortest distances from A
distances = lg.dijkstra(G, 'A')
print(distances)
# {'A': 0, 'B': 3, 'C': 2, 'D': 8}

# A* — point-to-point with heuristic
result = lg.astar(G, 'A', 'D')
print(result['distance'])  # 8
print(result['path'])      # ['A', 'C', 'B', 'D']

# Bellman-Ford — supports negative weights
DG = nx.DiGraph()
DG.add_edge('X', 'Y', weight=4)
DG.add_edge('Y', 'Z', weight=-2)
result = lg.bellman_ford(DG, 'X')
print(result['distances'])  # {'X': 0, 'Y': 4, 'Z': 2}

# BFS traversal
visited = lg.bfs(G, 'A')
print(visited)  # {'A': 0, 'B': 1, 'C': 1, 'D': 2}

# Kruskal MST
mst = lg.kruskal_mst(G)
print(mst['total_weight'])   # minimum spanning tree weight

# Max Flow
DG = nx.DiGraph()
DG.add_edge('S', 'A', capacity=10)
DG.add_edge('A', 'T', capacity=10)
flow = lg.max_flow(DG, 'S', 'T')
print(flow['max_flow_value'])  # 10

# Tarjan SCC
DG2 = nx.DiGraph([('A','B'), ('B','C'), ('C','A')])
sccs = lg.tarjan_scc(DG2)
print(sccs)   # [['A', 'B', 'C']]

# Floyd-Warshall — all-pairs shortest paths
result = lg.floyd_warshall(G)
print(result['distances']['A']['D'])   # shortest distance A→D

# Johnson's — all-pairs for sparse graphs
result = lg.johnson(G)
print(result['distances']['A']['D'])   # same result, faster on sparse graphs

import logarithma as lg
import networkx as nx

G = nx.Graph()
G.add_edge('A', 'B', weight=4)
G.add_edge('A', 'C', weight=2)
G.add_edge('B', 'C', weight=1)
G.add_edge('B', 'D', weight=5)

distances = lg.dijkstra(G, 'A')
# {'A': 0, 'C': 2, 'B': 3, 'D': 8}

# Works with directed graphs too
DG = nx.DiGraph()
DG.add_edge('A', 'B', weight=1)
DG.add_edge('B', 'C', weight=2)
distances = lg.dijkstra(DG, 'A')
# {'A': 0, 'B': 1, 'C': 3}

result = lg.dijkstra_with_path(G, 'A', 'D')
print(result['distances']['D'])  # 8
print(result['paths']['D'])      # ['A', 'C', 'B', 'D']

# All paths from source
result = lg.dijkstra_with_path(G, 'A')
for node, path in result['paths'].items():
    print(f"{node}: {path}")

from logarithma import astar, euclidean_heuristic, manhattan_heuristic

# ── Euclidean heuristic (2D coordinate graphs) ──────────────────
G = nx.Graph()
pos = {'A': (0, 0), 'B': (3, 0), 'C': (3, 4), 'D': (6, 4)}
G.add_edge('A', 'B', weight=3)
G.add_edge('B', 'C', weight=4)
G.add_edge('A', 'C', weight=10)
G.add_edge('C', 'D', weight=3)

h = euclidean_heuristic(pos)
result = astar(G, 'A', 'D', heuristic=h)
print(result['distance'])  # 10
print(result['path'])      # ['A', 'B', 'C', 'D']

# ── Manhattan heuristic (grid graphs) ──────────────────────────
G_grid = nx.grid_2d_graph(5, 5)
for u, v in G_grid.edges():
    G_grid[u][v]['weight'] = 1
pos_grid = {node: (node[1], node[0]) for node in G_grid.nodes()}

h_manhattan = manhattan_heuristic(pos_grid)
result = astar(G_grid, (0, 0), (4, 4), heuristic=h_manhattan)
print(result['distance'])  # 8
print(result['path'])      # [(0,0), (0,1), ..., (4,4)]

# ── No heuristic → equivalent to Dijkstra ──────────────────────
result = astar(G, 'A', 'D')  # heuristic defaults to zero

from logarithma import astar, haversine_heuristic

# lat/lon coordinates
cities = {
    'Istanbul': (41.008, 28.978),
    'Ankara':   (39.933, 32.859),
    'Izmir':    (38.419, 27.128),
}
G = nx.Graph()
G.add_edge('Istanbul', 'Ankara', weight=450)   # km
G.add_edge('Ankara',   'Izmir',  weight=590)
G.add_edge('Istanbul', 'Izmir',  weight=480)

h = haversine_heuristic(cities)
result = astar(G, 'Istanbul', 'Izmir', heuristic=h)
print(result['distance'])  # 480  (direct is cheaper)
print(result['path'])      # ['Istanbul', 'Izmir']

from logarithma import astar_with_stats, euclidean_heuristic, zero_heuristic

# Zero heuristic (= Dijkstra)
r_zero = astar_with_stats(G_grid, (0,0), (4,4), heuristic=zero_heuristic)
print(r_zero['nodes_expanded'])   # e.g. 25 — visits all nodes

# Euclidean heuristic
r_euc = astar_with_stats(G_grid, (0,0), (4,4), heuristic=euclidean_heuristic(pos_grid))
print(r_euc['nodes_expanded'])    # e.g. 9 — much fewer nodes visited

from logarithma import bellman_ford, NegativeCycleError
import networkx as nx

# ── Graph with negative edge (no cycle) ────────────────────────
G = nx.DiGraph()
G.add_edge('A', 'B', weight=4)
G.add_edge('B', 'C', weight=-3)   # negative but no cycle
G.add_edge('A', 'C', weight=5)
G.add_edge('C', 'D', weight=1)

result = bellman_ford(G, 'A')
print(result['distances'])
# {'A': 0, 'B': 4, 'C': 1, 'D': 2}
# A→B=4, then B→C: 4+(-3)=1, C→D: 1+1=2

# ── Negative cycle detection ────────────────────────────────────
G_cycle = nx.DiGraph()
G_cycle.add_edge('A', 'B', weight=1)
G_cycle.add_edge('B', 'C', weight=-3)
G_cycle.add_edge('C', 'A', weight=1)   # total cycle weight: -1

try:
    bellman_ford(G_cycle, 'A')
except NegativeCycleError as e:
    print("Negative cycle detected!")
    print("Cycle:", e.cycle)   # ['A', 'B', 'C', 'A']

from logarithma import bellman_ford_path

result = bellman_ford_path(G, 'A', 'D')
print(result['distance'])  # 2
print(result['path'])      # ['A', 'B', 'C', 'D']

# Arbitrage detection example
exchange = nx.DiGraph()
# Negative log-rates as weights: buy low, sell high
exchange.add_edge('USD', 'EUR', weight=-0.05)
exchange.add_edge('EUR', 'GBP', weight=-0.12)
exchange.add_edge('GBP', 'USD', weight=-0.04)
try:
    bellman_ford(exchange, 'USD')
except NegativeCycleError:
    print("Arbitrage opportunity detected!")

from logarithma import bidirectional_dijkstra
import networkx as nx

# ── Large road network ─────────────────────────────────────────
G = nx.grid_2d_graph(100, 100)  # 10,000 nodes
for u, v in G.edges():
    G[u][v]['weight'] = 1

result = bidirectional_dijkstra(G, (0, 0), (99, 99))
print(result['distance'])  # 198
print(result['path'][:4])  # [(0,0), (0,1), (0,2), ...]

# ── Directed graph ─────────────────────────────────────────────
DG = nx.DiGraph()
DG.add_edge('S', 'A', weight=1)
DG.add_edge('A', 'B', weight=2)
DG.add_edge('S', 'B', weight=10)   # longer direct path
DG.add_edge('B', 'T', weight=1)

result = bidirectional_dijkstra(DG, 'S', 'T')
print(result['distance'])  # 4  (S→A→B→T)
print(result['path'])      # ['S', 'A', 'B', 'T']

# ── Unreachable target ─────────────────────────────────────────
result = bidirectional_dijkstra(DG, 'T', 'S')  # no reverse path
print(result['distance'])  # inf
print(result['path'])      # []

from logarithma import bfs, bfs_path
import networkx as nx

G = nx.Graph()
G.add_edges_from([('A','B'), ('B','C'), ('A','D'), ('D','E')])

# Distances (hop count) from A
distances = bfs(G, 'A')
# {'A': 0, 'B': 1, 'D': 1, 'C': 2, 'E': 2}

# Path to a target
result = bfs_path(G, 'A', 'E')
print(result['distances']['E'])  # 2
print(result['paths']['E'])      # ['A', 'D', 'E']

from logarithma import dfs, dfs_path, detect_cycle
import networkx as nx

G = nx.Graph()
G.add_edges_from([('A','B'), ('B','C'), ('C','D'), ('A','D')])

# DFS traversal order
visited = dfs(G, 'A')
# e.g. ['A', 'B', 'C', 'D']

# Iterative mode
visited = dfs(G, 'A', mode='iterative')

# Find any path (not necessarily shortest)
path = dfs_path(G, 'A', 'D')
# ['A', 'D']   (direct edge found first)

# Cycle detection
has_cycle, cycle = detect_cycle(G)
print(has_cycle)  # True  (A-B-C-D-A)
print(cycle)      # ['A', 'B', 'C', 'D', 'A']

# Directed graph
DG = nx.DiGraph()
DG.add_edges_from([('A','B'), ('B','C')])
has_cycle, cycle = detect_cycle(DG)
print(has_cycle)  # False

import logarithma as lg
import networkx as nx

G = nx.Graph()
G.add_edge('A', 'B', weight=4)
G.add_edge('A', 'C', weight=2)
G.add_edge('B', 'C', weight=1)
G.add_edge('B', 'D', weight=5)
G.add_edge('C', 'D', weight=8)
G.add_edge('C', 'E', weight=10)
G.add_edge('D', 'E', weight=2)

result = lg.kruskal_mst(G)
print(result['total_weight'])   # minimum total weight
print(result['edges'])          # list of (u, v, weight) tuples
print(result['mst_graph'])      # NetworkX Graph of the MST

# Error on directed graphs
from logarithma import UndirectedGraphRequiredError
try:
    lg.kruskal_mst(nx.DiGraph())
except UndirectedGraphRequiredError as e:
    print(e)

result = lg.prim_mst(G, start='A')
print(result['total_weight'])   # same as Kruskal on same graph
print(result['edges'])          # list of (u, v, weight) tuples

# start=None → random start node
result = lg.prim_mst(G)

import logarithma as lg
import networkx as nx

G = nx.DiGraph()
G.add_edge('S', 'A', capacity=10)
G.add_edge('S', 'B', capacity=10)
G.add_edge('A', 'C', capacity=10)
G.add_edge('B', 'C', capacity=10)
G.add_edge('A', 'T', capacity=10)
G.add_edge('C', 'T', capacity=10)

result = lg.max_flow(G, 'S', 'T')
print(result['max_flow_value'])    # 20
print(result['flow_dict'])         # {u: {v: flow_amount, ...}, ...}
print(result['method'])            # 'edmonds_karp'

# Custom capacity attribute name
G2 = nx.DiGraph()
G2.add_edge('X', 'Y', cap=5)
result = lg.max_flow(G2, 'X', 'Y', capacity='cap')

import logarithma as lg
import networkx as nx

DG = nx.DiGraph()
DG.add_edges_from([('A','B'), ('B','C'), ('C','A'),   # SCC 1
                   ('C','D'), ('D','E'), ('E','D')])   # SCC 2 (D-E)

sccs = lg.tarjan_scc(DG)
print(sccs)   # [['A', 'B', 'C'], ['D', 'E']]

# Condensation DAG — each SCC as a single node
result = lg.tarjan_scc(DG)
for i, scc in enumerate(result):
    print(f"SCC {i}: {scc}")

from logarithma import topological_sort, NotDAGError
import networkx as nx

DAG = nx.DiGraph()
DAG.add_edges_from([('compile', 'link'), ('link', 'test'),
                    ('compile', 'lint'), ('lint', 'test')])

order = topological_sort(DAG)
print(order)   # e.g. ['compile', 'lint', 'link', 'test']

# Kahn's algorithm variant
order = topological_sort(DAG, method='kahn')

# Raises on cyclic graph
G_cycle = nx.DiGraph([('A','B'), ('B','C'), ('C','A')])
try:
    topological_sort(G_cycle)
except NotDAGError as e:
    print("Cycle found:", e.cycle)

import logarithma as lg
import networkx as nx

# ── Dense graph — all-pairs distances ─────────────────────────
G = nx.DiGraph()
G.add_edge('A', 'B', weight=3)
G.add_edge('A', 'C', weight=8)
G.add_edge('B', 'C', weight=2)
G.add_edge('C', 'D', weight=1)
G.add_edge('B', 'D', weight=7)

result = lg.floyd_warshall(G)

# Distance from A to D: A→B(3)→C(2)→D(1) = 6
print(result['distances']['A']['D'])   # 6.0

# Full distance matrix
for u in G.nodes():
    for v in G.nodes():
        d = result['distances'][u][v]
        print(f"  {u}→{v}: {d}")

# ── Negative weights (no cycle) ───────────────────────────────
G2 = nx.DiGraph()
G2.add_edge('X', 'Y', weight=4)
G2.add_edge('Y', 'Z', weight=-3)   # negative edge, no cycle
G2.add_edge('X', 'Z', weight=5)

result = lg.floyd_warshall(G2)
print(result['distances']['X']['Z'])   # 1  (X→Y→Z: 4+(-3)=1)

# ── Negative cycle detection ──────────────────────────────────
from logarithma import NegativeCycleError

G3 = nx.DiGraph()
G3.add_edge('A', 'B', weight=1)
G3.add_edge('B', 'C', weight=-3)
G3.add_edge('C', 'A', weight=1)   # cycle total: -1

try:
    lg.floyd_warshall(G3)
except NegativeCycleError:
    print("Negative cycle detected!")

path = lg.floyd_warshall_path(G, 'A', 'D')
print(path)   # ['A', 'B', 'C', 'D']

# Unreachable target → empty list
path = lg.floyd_warshall_path(G, 'D', 'A')
print(path)   # []

import logarithma as lg
import networkx as nx

# ── Sparse graph with negative edges ──────────────────────────
G = nx.DiGraph()
G.add_edge('A', 'B', weight=4)
G.add_edge('A', 'C', weight=2)
G.add_edge('B', 'C', weight=-3)   # negative edge
G.add_edge('C', 'D', weight=1)
G.add_edge('D', 'B', weight=2)

result = lg.johnson(G)

# A→C: direct=2, via B=4+(-3)=1 → shortest is 1
print(result['distances']['A']['C'])   # 1.0

# All-pairs
for src in G.nodes():
    for tgt in G.nodes():
        d = result['distances'][src][tgt]
        print(f"  {src}→{tgt}: {d}")

# ── Negative cycle detection ──────────────────────────────────
from logarithma import NegativeCycleError

G2 = nx.DiGraph()
G2.add_edge('X', 'Y', weight=-1)
G2.add_edge('Y', 'X', weight=-1)   # 2-node negative cycle

try:
    lg.johnson(G2)
except NegativeCycleError:
    print("Negative cycle detected!")

path = lg.johnson_path(G, 'A', 'D')
print(path)   # ['A', 'B', 'C', 'D']

import logarithma as lg
import networkx as nx

G = nx.DiGraph()
G.add_edge('s', 'A', weight=2)
G.add_edge('s', 'B', weight=5)
G.add_edge('A', 'C', weight=1)
G.add_edge('B', 'C', weight=2)

distances = lg.breaking_barrier_sssp(G, 's')
print(distances)
# {'s': 0, 'A': 2, 'B': 5, 'C': 3}

# Results match Dijkstra — verify on any graph
dijkstra_dist = lg.dijkstra(G, 's')
assert distances == dijkstra_dist

# Install Cython and compile extensions
pip install "logarithma[fast]"
python setup_ext.py build_ext --inplace

from logarithma.utils import (
    generate_random_graph,
    generate_grid_graph,
    generate_scale_free_graph,
    generate_tree_graph,
)

# Erdős-Rényi random graph with weights
G = generate_random_graph(n=100, edge_prob=0.1, weighted=True, seed=42)

# 5×5 grid graph
G_grid = generate_grid_graph(rows=5, cols=5)

# Barabási-Albert scale-free graph (social network model)
G_sf = generate_scale_free_graph(n=200, m=3)

# Random tree
G_tree = generate_tree_graph(n=50)

from logarithma.utils import is_connected, is_dag, has_negative_weights, validate_graph

G = generate_random_graph(50, 0.1)

print(is_connected(G))           # True / False
print(is_dag(nx.DiGraph(G)))     # True if directed acyclic
print(has_negative_weights(G))   # True if any edge weight < 0
print(is_bipartite(G))           # True if graph is bipartite

# Full validation report
report = validate_graph(G)
print(report)

from logarithma.utils import graph_summary, graph_density, diameter

G = generate_random_graph(100, 0.1, weighted=True)

# Quick summary
summary = graph_summary(G)
print(summary)
# {'nodes': 100, 'edges': 497, 'density': 0.1003,
#  'avg_degree': 9.94, 'is_connected': True, ...}

print(graph_density(G))   # 0.1003
print(diameter(G))        # e.g. 4

from logarithma.utils import (
    to_adjacency_matrix, from_adjacency_matrix,
    to_edge_list, from_edge_list,
)
import numpy as np

# Graph → adjacency matrix
matrix = to_adjacency_matrix(G)   # numpy array

# Adjacency matrix → Graph
G2 = from_adjacency_matrix(matrix)

# Graph → edge list
edges = to_edge_list(G)
# [(0, 1, 2.3), (0, 5, 1.7), ...]

# Edge list → Graph
G3 = from_edge_list(edges)