import { Relation } from "./index.js";
import { int, nat } from "./primitives.js";
export type Vertex = int;
/**
 * This class implements directed graphs:
 * * Vertices are represented as integers.
 * * All edges are directed, and there are no multi-edges.
 */
export declare class Digraph {
    #private;
    constructor();
    clone(): Digraph;
    insert(vertex: Vertex): boolean;
    delete(vertex: Vertex): boolean;
    hasVertex(vertex: Vertex): boolean;
    hasEdge(from: Vertex, to: Vertex): boolean;
    connect(from: Vertex, to: Vertex): boolean;
    disconnect(from: Vertex, to: Vertex): boolean;
    get vertices(): Iterable<Vertex>;
    outgoing(vertex: Vertex): Iterable<Vertex>;
    countOutgoing(vertex: Vertex): nat;
    get isEmpty(): boolean;
    /** The number of vertices of this graph */
    get vertexCount(): nat;
    /** The number of edges of this graph */
    get edgeCount(): nat;
    /** The number of edges and vertices of this graph */
    get size(): nat;
}
export declare function printGraph(graph: Digraph, label?: (v: Vertex) => string, println?: (s: string) => void): void;
export type DFSNode = {
    parent: Vertex | null;
    discovered: nat;
    finished: nat;
};
export declare function depthFirstSearch(graph: Digraph, vertices?: Iterable<Vertex>): Map<Vertex, DFSNode>;
export declare function forestOfDFS(dfs: Map<Vertex, DFSNode>): Digraph;
export declare function depthFirstSearchForest(graph: Digraph, vertices?: Iterable<Vertex>): Digraph;
export declare function transposeDigraph(graph: Digraph): Digraph;
export declare function symmetricClosure(graph: Digraph): Digraph;
export declare function reachableFrom(graph: Digraph, start: Iterable<Vertex>): Set<Vertex>;
export declare function closureFrom(graph: Digraph, start: Iterable<Vertex>): Set<Vertex>;
export declare function transitiveClosure(graph: Digraph): Digraph;
/**
 * Assigns to each vertex V of the graph a unique index S(V) such that 0 ≤ S(V) < graph.vertexCount.
 * If the graph is acyclic, and if there is an edge from A to B in the graph with A ≠ B, then S(A) < S(B).
 */
export declare function topologicalSort(graph: Digraph, vertices?: Iterable<Vertex>): Map<Vertex, nat>;
export declare function backEdgesOfTopologicalSort(graph: Digraph, topsort: Map<Vertex, nat>): Digraph;
/**
 * Orders the vertices of a directed graph by finishing times, later times appear at higher array indices.
 */
export declare function topologicalSortByFinish(graph: Digraph, vertices?: Iterable<Vertex>): Vertex[];
export declare function weaklyConnectedComponents(graph: Digraph): Set<Vertex>[];
export declare function stronglyConnectedComponents(graph: Digraph): Set<Vertex>[];
export declare function sourceVertices(graph: Digraph): Set<Vertex>;
export declare function sinkVertices(graph: Digraph): Set<Vertex>;
export declare function KahnTopologicalSortDepthFirstWithCompare(graph: Digraph, compare: (x: Vertex, y: Vertex) => number): {
    sorted: Vertex[];
    remaining_transposed: Digraph;
};
export declare function KahnTopologicalSortDepthFirst(graph: Digraph): {
    sorted: Vertex[];
    remaining_transposed: Digraph;
};
export declare function transitiveReductionAndClosureOfDAG(graph: Digraph): {
    reduction: Digraph;
    closure: Digraph;
};
export declare function isSubgraph(sub: Digraph, g: Digraph): boolean;
export declare function compareGraphs(g: Digraph, h: Digraph): Relation;
export declare function mapVertices(g: Digraph, f: (v: Vertex) => Vertex): Digraph;