import { DirectedGraph } from "./directedGraph";
/**
 * # DirectedAcyclicGraph
 *
 * A DirectedAcyclicGraph is builds on a [[`DirectedGraph`]] but enforces acyclicality. You cannot add an edge to a DirectedAcyclicGraph that would create a cycle.
 *
 * @typeParam Node `Node` is the node type of the graph. Nodes can be anything in all the included examples they are simple objects.
 * @typeParam Edge `Edge` is the edge type of the graph. Edges can be of any type, but must be truethy and by default they are `true` which is a simple boolean.
 * @typeParam NodeId `NodeId` is the identity type of the node, by default it is a `unknown`, though most will use `string` or `number`.
 * @typeParam EdgeId `EdgeId` is the identity type of the edge, by default it is a `unknown`, though most will use `string` or `number`.
 */
export declare class DirectedAcyclicGraph<Node, Edge = true, NodeId = unknown, EdgeId = unknown> extends DirectedGraph<Node, Edge, NodeId, EdgeId> {
    private _topologicallySortedNodes?;
    /**
     * Converts an existing directed graph into a directed acyclic graph.
     * Throws a {@linkcode CycleError} if the graph attempting to be converted contains a cycle.
     * @param graph The source directed graph to convert into a DAG
     */
    static fromDirectedGraph<Node, Edge, NodeId, EdgeId>(graph: DirectedGraph<Node, Edge, NodeId, EdgeId>): DirectedAcyclicGraph<Node, Edge, NodeId, EdgeId>;
    /**
     * Adds an edge to the graph similarly to [[`DirectedGraph.addEdge`]] but maintains correctness of the acyclic graph.
     * Thows a [[`CycleError`]] if adding the requested edge would create a cycle.
     * Adding an edge invalidates the cache of topologically sorted nodes, rather than updating it.
     *
     * @param sourceNodeIdentity The identity string of the node the edge should run from.
     * @param targetNodeIdentity The identity string of the node the edge should run to.
     * @param edge The edge to add to the graph. If not provided it defaults to `true`.
     */
    addEdge(sourceNodeIdentity: NodeId, targetNodeIdentity: NodeId, edge?: Edge): EdgeId;
    /**
     * Inserts a node into the graph and maintains topologic sort cache by prepending the node
     * (since all newly created nodes have an [[ indegreeOfNode | indegree ]] of zero.)
     *
     * @param node The node to insert
     */
    insert(node: Node): NodeId;
    /**
     * Topologically sort the nodes using Kahn's algorithm. Uses a cache which means that repeated calls should be O(1) after the first call.
     * Non-cached calls are potentially expensive, Kahn's algorithim is O(|EdgeCount| + |NodeCount|).
     * There may be more than one valid topological sort order for a single graph,
     * so just because two graphs are the same does not mean that order of the resultant arrays will be.
     *
     * @returns An array of nodes sorted by the topological order.
     */
    topologicallySortedNodes(): Node[];
    /**
     * Given a starting node this returns a new [[`DirectedA`]] containing all the nodes that can be reached.
     * Throws a [[`NodeDoesntExistError`]] if the start node does not exist.
     *
     * @param startNodeIdentity The string identity of the node from which the subgraph search should start.
     */
    getSubGraphStartingFrom(startNodeIdentity: NodeId): DirectedAcyclicGraph<Node, Edge, NodeId, EdgeId>;
    /**
     * Deletes an edge between two nodes in the graph.
     * Throws a [[`NodeDoesNotExistsError`]] if either of the nodes do not exist.
     *
     * @param sourceNodeIdentity The identity of the source node
     * @param targetNodeIdentity The identity of the target node
     * @param edgeIdentity The identity of the edge to be deleted. If not provided, all edges between the two nodes will be deleted.
     */
    removeEdge(sourceNodeIdentity: NodeId, targetNodeIdentity: NodeId, edgeIdentity?: EdgeId): void;
    /**
     * Deletes a node from the graph, along with any edges associated with it.
     * Throws a [[`NodeDoesNotExistsError`]] if the node does not exist.
     *
     * @param nodeIdentity The identity of the node to be deleted.
     */
    remove(nodeIdentity: NodeId): void;
}
//# sourceMappingURL=directedAcyclicGraph.d.ts.map