import { EventEmitter } from "../events/EventEmitter";
/**
 * # Graph
 *
 * A `Graph` is is a simple undirected graph. On it's own it isn't too useful but it forms the basic functionality for the [[`DirectedGraph`]] and [[`DirectedAcyclicGraph`]].
 *
 * ## Creating a Graph
 *
 * You can create a graph to contain any type of node, for example:
 *
 * ```typescript
 * type NodeType = { a: Number, b: string }
 * const graph = new Graph<NodeType>()
 *
 * // Add a node of the defined type
 * const node: string = graph.insert({ a: 10, b: 'string' })
 *
 * // Get the node back
 * const nodeValue: NodeType | undefined = graph.getNode(node);
 * ```
 *
 * ### Defining a custom node identity
 *
 * When you create a graph you likely want to create include a custom `nodeIdentity` function.
 * This function tells the graph how to uniquely identify nodes in a graph,
 * default is to simply use an [[hash]] which means that functionality like [[`replace`]] will not work.
 *
 * ```typescript
 * type NodeType = { count: number, name: string }
 * const graph = new Graph<NodeType>((n) => n.name)
 *
 * // Add a node
 * graph.insert({ count: 5, name: 'node1' })
 * // This will throw an error even though `count` is different because they share a name.
 * graph.insert({ count: 20, name: 'node1' })
 * ```
 *
 * ### Adding an edge
 *
 * Graphs without edges aren't very useful. Inserting edges is done using the node identity string returned by the node identity function.
 *
 * ```typescript
 * const node1: string = graph.insert({ count: 5, name: 'node1' })
 * const node2: string = graph.insert({ count: 20, name: 'node2' })
 *
 * graph.addEdge(node1, node2)
 *
 * // This will throw an error since there is no node with the later name.
 * graph.addEdge(node1, 'not a real node')
 * ```
 *
 * In an undirected graph the order in which you input the node names doesn't matter,
 * but in directed graphs the "from node" comes first and the "to node" will come second.
 *
 * ### Replacing a node
 *
 * If a node already exists you can update it using [[`replace`]]. `nodeIdentity(newNode)` must be equal to `nodeIdentity(oldNode)`.
 *
 * ```typescript
 * const node1: string = graph.insert({ count: 5, name: 'node1' })
 * const node2: string = graph.insert({ count: 20, name: 'node2' })
 *
 * // This will work because the name has not changed.
 * graph.replace({ count: 15, name: 'node1' })
 *
 * // This will not work because the name has changed.
 * graph.replace({ count: 20, name: 'node3' })
 * ```
 *
 * [[`replace`]] will throw a [[`NodeDoesntExistError`]] exception if you are trying to replace a node that is missing from the graph.
 *
 * ### Upsert
 *
 * Often you will want to create a node node if it doesn't exist and update it does. This can be achieved using [[`upsert`]].
 *
 * ```typescript
 * const node1: string = graph.insert({ count: 5, name: 'node1' })
 *
 * // Both of these will work, the first updating node1 and the second creating a node.
 * const node2: string = graph.upsert({ count: 15, name: 'node1' })
 * const node3: string = graph.upsert({ count: 25, name: 'node3' })
 * ```
 *
 * [[`upsert`]] always return the node identity string of the inserted or updated node. At presented there is no way to tell if the node was created or updated.
 *
 * @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 type AdjacencyValue<Edge> = null | Array<Edge>;
export type AdjacencyMatrix<Edge> = Array<Array<AdjacencyValue<Edge>>>;
/**
 * Events that can be emitted by the TaskGraph
 */
export type GraphEvents<NodeId, EdgeId> = keyof GraphEventListeners<NodeId, EdgeId>;
export type GraphEventListeners<NodeId, EdgeId> = {
    "node-added": (node: NodeId) => void;
    "node-removed": (node: NodeId) => void;
    "node-replaced": (node: NodeId) => void;
    "edge-added": (edge: EdgeId) => void;
    "edge-removed": (edge: EdgeId) => void;
    "edge-replaced": (edge: EdgeId) => void;
};
export type GraphEventListener<NodeId, EdgeId, Event extends GraphEvents<NodeId, EdgeId>> = GraphEventListeners<NodeId, EdgeId>[Event];
export type GraphEventParameters<NodeId, EdgeId, Event extends GraphEvents<NodeId, EdgeId>> = Parameters<GraphEventListeners<NodeId, EdgeId>[Event]>;
export declare class Graph<Node, Edge = true, NodeId = unknown, EdgeId = unknown> {
    protected nodes: Map<NodeId, Node>;
    protected adjacency: AdjacencyMatrix<Edge>;
    protected nodeIdentity: (t: Node) => NodeId;
    protected edgeIdentity: (t: Edge, n1: NodeId, n2: NodeId) => EdgeId;
    /** O(1) lookup of node identity → adjacency matrix index. */
    protected nodeIndexMap: Map<NodeId, number>;
    constructor(nodeIdentity: (node: Node) => NodeId, edgeIdentity: (edge: Edge, node1Identity: NodeId, node2Identit: NodeId) => EdgeId);
    /** Returns the adjacency matrix index for a node, or -1 if not found. */
    protected getNodeIndex(nodeIdentity: NodeId): number;
    events: EventEmitter<GraphEventListeners<NodeId, EdgeId>>;
    on<Event extends GraphEvents<NodeId, EdgeId>>(name: Event, fn: GraphEventListener<NodeId, EdgeId, Event>): void;
    off<Event extends GraphEvents<NodeId, EdgeId>>(name: Event, fn: GraphEventListener<NodeId, EdgeId, Event>): void;
    emit<Event extends GraphEvents<NodeId, EdgeId>>(name: Event, ...args: Parameters<GraphEventListener<NodeId, EdgeId, Event>>): void;
    /**
     * Add a node to the graph if it doesn't already exist. If it does, throw a [[`NodeAlreadyExistsError`]].
     *
     * @param node The node to be added
     * @returns A `string` that is the identity of the newly inserted node. This is created by applying the [[constructor | `nodeIdentity`]].
     */
    insert(node: Node): NodeId;
    /**
     * This replaces an existing node in the graph with an updated version.
     * Throws a [[`NodeDoesNotExistsError`]] if no node with the same identity already exists.
     *
     * __Caveat_:_ The default identity function means that this will never work since if the node changes it will have a different [[`hash`]].
     *
     * @param node The new node that is replacing the old one.
     */
    replace(node: Node): void;
    /**
     * This essentially combines the behavior of [[`insert`]] and [[`replace`]].
     * If the node doesn't exist, create it. If the node already exists, replace it with the updated version.
     *
     * @param node The node to insert or update
     * @returns The identity string of the node inserted or updated.
     */
    upsert(node: Node): NodeId;
    /**
     * Create an edge between two nodes in the graph.
     * Throws a [[`NodeDoesNotExistsError`]] if no either of the nodes you are attempting to connect do not exist.
     *
     * @param node1Identity The first node to connect (in [[`DirectedGraph`]]s and [[`DirectedAcyclicGraph`]]s this is the `source` node.)
     * @param node2Identity The second node to connect (in [[`DirectedGraph`]]s and [[`DirectedAcyclicGraph`]]s this is the `target` node)
     * @param edge The edge to be added. By default this is `true` but it can be any type.
     */
    addEdge(node1Identity: NodeId, node2Identity: NodeId, edge?: Edge): EdgeId;
    /**
     * This simply returns all the nodes stored in the graph
     *
     * @param compareFunc An optional function that indicates the sort order of the returned array
     */
    getNodes(compareFunc?: (a: Node, b: Node) => number): Node[];
    /**
     * Returns a specific node given the node identity returned from the [[`insert`]] function
     */
    getNode(nodeIdentity: NodeId): Node | undefined;
    /**
     * Returns true if the node exists in the graph.
     */
    hasNode(nodeIdentity: NodeId): boolean;
    /**
     * Returns all edges in the graph as an array of tuples.
     */
    getEdges(): Array<[node1Identity: NodeId, node2Identity: NodeId, edge: Edge]>;
    /**
     * Returns the out edges for a specific node.
     */
    outEdges(node1Identity: NodeId): Array<[node1Identity: NodeId, node2Identity: NodeId, edge: Edge]>;
    /**
     * Returns the in edges for a specific node.
     */
    inEdges(node2Identity: NodeId): Array<[node1Identity: NodeId, node2Identity: NodeId, edge: Edge]>;
    /**
     * Returns the edges for a specific node.
     */
    nodeEdges(nodeIdentity: NodeId): Array<[node1Identity: NodeId, node2Identity: NodeId, edge: Edge]>;
    /**
     * Deletes an edge between two nodes in the graph.
     * Throws a [[`NodeDoesNotExistsError`]] if either of the nodes do not exist.
     *
     * @param node1Identity The identity of the first node (in [[`DirectedGraph`]]s and [[`DirectedAcyclicGraph`]]s this is the `from` node.)
     * @param node2Identity The identity of the second node (in [[`DirectedGraph`]]s and [[`DirectedAcyclicGraph`]]s this is the `to` node)
     * @param edgeIdentity The identity of the edge to be deleted. If not provided, all edges between the two nodes will be deleted.
     */
    removeEdge(node1Identity: NodeId, node2Identity: 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;
    /**
     * @alias remove
     */
    removeNode(nodeIdentity: NodeId): void;
    /**
     * @alias insert
     */
    addNode(node: Node): NodeId;
    /**
     * Add nodes in bulk
     */
    addNodes(nodes: Node[]): NodeId[];
    /**
     * Add edges
     * @param edges An array of tuples, each tuple containing the identity of the source node, the identity of the target node, and the edge to add.
     */
    addEdges(edges: Array<[node1Identity: NodeId, node2Identity: NodeId, edge?: Edge | undefined]>): EdgeId[];
}
//# sourceMappingURL=graph.d.ts.map