js-incremental-cycle-detect
Options
All
  • Public
  • Public/Protected
  • All
Menu

Generic graph data structure similar to CommonAdapter. It additionally supports multiple edges between two vertices. An edge is identified by its label. Labels are compared by a Map, ie. ===.


// Type of the data we want to use as vertices.
interface Vertex {
  id: number;
  name: string;
  // ...
}

// Create a new graph.
const graph = MultiGraphAdapter.create<Vertex, string>();

// Add some vertices and edges.
const v1 = {id: 1, name: "foo"};
const v2 = {id: 2, name: "bar"};
const v3 = {id: 2, name: "baz"};

graph.addVertex(v1);
graph.addVertex(v2);
graph.addVertex(v3);

graph.addEdge(v1, v2, "Some edge data", "Label1");
// Another edge from v1 to v2, but with a different label.
graph.addEdge(v1, v2, "More edge data", "Label2");
graph.addEdge(v2, v3, "Even more data, "Label3");

// Fetch the data associated with the edge.
graph.getEdgeData(v1, v2, "Label1"); // => "Some edge data"
graph.getEdgeData(v1, v2, "Label2"); // => "More edge data"
graph.getEdgeData(v1, v2, "no-such-label"); // => undefined

// This edge would create cycle.
graph.addEdge(v3, v1); // => false
graph.hasEdge(v3, v1); // => false

graph.deleteEdge(v1, v2, "Label2");
// There is still an edge left between v1 and v2, so this would create a cycle.
graph.addEdge(v3, v1) // => false;

graph.deleteEdge(v1, v2, "Label1");
graph.addEdge(v3, v1) // true;
see

CommonAdapter

see

CommonAdapter

Type parameters

  • TVertex

    Type of the vertices of this graph.

  • TEdgeData

    Type of the data associated with edges.

  • TEdgeLabel

    Type of the label used to distiniguish different between edges with the same source and target vertex.

Hierarchy

  • MultiGraphAdapter

Implements

Index

Methods

Methods

addEdge

addLabeledEdge

  • addLabeledEdge(from: TVertex, to: TVertex, label: Maybe<TEdgeLabel>, data?: TEdgeData): boolean

addVertex

  • addVertex(vertex: TVertex): boolean

canAddEdge

  • canAddEdge(from: TVertex, to: TVertex, label?: TEdgeLabel): boolean

canContractEdge

  • canContractEdge(from: TVertex, to: TVertex): boolean

canContractLabeledEdge

  • canContractLabeledEdge(from: TVertex, to: TVertex, label?: TEdgeLabel): boolean

  • This check if a specific labeled edge between the given vertices can be contracted. Note that cycles are not allowed, so if there exists more than one edge between the given vertices, the contraction cannot be performed as that would create a cycle.

    Parameters

    • from: TVertex

      Source vertex of the edge.

    • to: TVertex

      Target vertex of the edge.

    • Optional label: TEdgeLabel

      Label of the edge to be deleted.

    Returns boolean

    true iff the edge can be contracted, false otherwise.

canContractOneEdge

  • canContractOneEdge(from: TVertex, to: TVertex): boolean

  • This check if a single labeled edge between the given vertices can be contracted. Note that cycles are not allowed, so if there exists more than one edge between the given vertices, the contraction cannot be performed as that would create a cycle.

    Parameters

    • from: TVertex

      Source vertex of the edge.

    • to: TVertex

      Target vertex of the edge.

    Returns boolean

    true iff the edge can be contracted, false otherwise.

clone

  • clone(vertexCloner?: UnaryOperator<TVertex>, edgeDataCloner?: UnaryOperator<TEdgeData>, labelCloner?: UnaryOperator<TEdgeLabel>): MultiGraphAdapter<TVertex, TEdgeData, TEdgeLabel>

  • Parameters

    • Optional vertexCloner: UnaryOperator<TVertex>
    • Optional edgeDataCloner: UnaryOperator<TEdgeData>
    • Optional labelCloner: UnaryOperator<TEdgeLabel>

    Returns MultiGraphAdapter<TVertex, TEdgeData, TEdgeLabel>

contractEdge

  • contractEdge(from: TVertex, to: TVertex, vertexMerger?: BinaryOperator<TVertex>, edgeMerger?: BinaryOperator<TEdgeData>): boolean

  • This contracts two vertices, ie. all edges between the given vertices.

    see

    MultiGraphAdapter#contractLabeledEdge

    Parameters

    • from: TVertex
    • to: TVertex
    • Optional vertexMerger: BinaryOperator<TVertex>
    • Optional edgeMerger: BinaryOperator<TEdgeData>

    Returns boolean

contractLabeledEdge

  • contractLabeledEdge(from: TVertex, to: TVertex, label?: TEdgeLabel, vertexMerger?: BinaryOperator<TVertex>, edgeMerger?: BinaryOperator<TEdgeData>): boolean

  • This contract a specific labeled edge between the given vertices. Note that cycles are not allowed, so if there exists more than one edge between the given vertices, the contraction cannot be performed as that would create a cycle.

    throws

    If vertex merger returns a vertex that is already contained in the graph.

    see

    MultiGraphAdapter#contractEdge

    Parameters

    • from: TVertex

      Source vertex of the edge.

    • to: TVertex

      Target vertex of the edge.

    • Optional label: TEdgeLabel

      Label of the edge to be deleted.

    • Optional vertexMerger: BinaryOperator<TVertex>

      The vertex that replaces the two old vertices. If not given, defaults to from.

    • Optional edgeMerger: BinaryOperator<TEdgeData>

    Returns boolean

    true iff the edge was contracted.

deleteEdge

  • deleteEdge(from: TVertex, to: TVertex, label?: TEdgeLabel): boolean

deleteLabeledEdge

  • deleteLabeledEdge(from: TVertex, to: TVertex, label: Maybe<TEdgeLabel>): boolean

  • Deletes the edges with the given label, which may be undefined.

    Parameters

    • from: TVertex

      Source vertex of the edge.

    • to: TVertex

      Target vertex of the edge.

    • label: Maybe<TEdgeLabel>

      Label of the edge.

    Returns boolean

    true iff an edge was deleted.

deleteVertex

  • deleteVertex(vertex: TVertex): boolean

  • Deletes a vertex from the graph; and all incident egdes.

    Parameters

    • vertex: TVertex

      Vertex to be deleted.

    Returns boolean

    Whether the vertex was deleted. That is, it returns false in case the given vertex was not contained in this graph.

getEdgeCount

  • getEdgeCount(): number

getEdgeCountBetween

  • getEdgeCountBetween(from: TVertex, to: TVertex): number

  • Parameters

    • from: TVertex

      Source vertex.

    • to: TVertex

      Target vertex.

    Returns number

    How many edges there are between the two vertices.

getEdgeData

  • getEdgeData(from: TVertex, to: TVertex, label?: TEdgeLabel): TEdgeData | undefined

getEdgeDataFrom

  • getEdgeDataFrom(vertex: TVertex, label?: TEdgeLabel): Iterator<TEdgeData>

getEdgeDataTo

  • getEdgeDataTo(vertex: TVertex, label?: TEdgeLabel): Iterator<TEdgeData>

getEdgeLabels

  • getEdgeLabels(from: TVertex, to: TVertex): Iterator<TEdgeLabel | undefined>

getEdges

  • getEdges(): Iterator<Pair<TVertex>>

getEdgesWithData

  • getEdgesWithData(): Iterator<Triple<TVertex, TVertex, Maybe<TEdgeData>>>

getEdgesWithDataFrom

  • getEdgesWithDataFrom(vertex: TVertex, label?: TEdgeLabel): Iterator<Pair<TVertex, Maybe<TEdgeData>>>

  • If a label is given, restricts the returned result to edges with that label.

    see

    CommonAdapter#getEdgesWithDataFrom

    Parameters

    Returns Iterator<Pair<TVertex, Maybe<TEdgeData>>>

getEdgesWithDataTo

  • getEdgesWithDataTo(vertex: TVertex, label?: TEdgeLabel): Iterator<Pair<TVertex, Maybe<TEdgeData>>>

  • If a label is given, restricts the returned result to edges with that label.

    see

    CommonAdapter#getEdgesWithDataTo

    Parameters

    Returns Iterator<Pair<TVertex, Maybe<TEdgeData>>>

getLabeledEdgeCount

  • getLabeledEdgeCount(): number

  • This returns the number of all edges, ie. including multiple edges between the same vertices.

    Returns number

    The number of edges in this graph, counting each multiple edge.

getLabeledEdges

  • getLabeledEdges(): Iterator<Triple<TVertex, TVertex, Maybe<TEdgeLabel>>>

  • Similar to MultiGraphAdapter#getEdges, but returns all edges between the vertices.

    Returns Iterator<Triple<TVertex, TVertex, Maybe<TEdgeLabel>>>

    All edges between the vertices. An edge is identified by its source vertex, its target vertex and its label.

getLabeledEdgesWithData

  • getLabeledEdgesWithData(): Iterator<Quadruple<TVertex, TVertex, Maybe<TEdgeData>, Maybe<TEdgeLabel>>>

  • Returns Iterator<Quadruple<TVertex, TVertex, Maybe<TEdgeData>, Maybe<TEdgeLabel>>>

getOrder

  • getOrder(vertex: TVertex): number

getPredecessorsOf

  • getPredecessorsOf(vertex: TVertex, label?: TEdgeLabel): Iterator<TVertex>

  • If a label is given, only returns predecessors connected to this vertex by an edge with the given label.

    see

    CommonAdapter#getPredecessorsOf

    Parameters

    Returns Iterator<TVertex>

getSuccessorsOf

  • getSuccessorsOf(vertex: TVertex, label?: TEdgeLabel): Iterator<TVertex>

  • If a label is given, only returns successors connected to this vertex by an edge with the given label.

    see

    CommonAdapter#getSuccessorsOf

    Parameters

    Returns Iterator<TVertex>

getVertexCount

  • getVertexCount(): number

getVertices

  • getVertices(): Iterator<TVertex>

hasEdge

  • hasEdge(from: TVertex, to: TVertex, label?: TEdgeLabel): boolean

  • If no label is given, returns true iff an edge with any label exists between the two given vertices. Otherwise, returns true iff an edge with the given label exists.

    see

    CommonAdapter#hasEdge

    Parameters

    • from: TVertex
    • to: TVertex
    • Optional label: TEdgeLabel

    Returns boolean

hasLabeledEdge

  • hasLabeledEdge(from: TVertex, to: TVertex, label: TEdgeLabel | undefined): boolean

  • Similar to MultiGraphAdapter#hasEdge, but if undefined is given for the label, checks whether an edge with an undefined label exists.

    Parameters

    • from: TVertex

      Source vertex of the edge.

    • to: TVertex

      Target vertex of the edge.

    • label: TEdgeLabel | undefined

      Label the edge must have.

    Returns boolean

    Whether this graph contains an edge form the given source to the target with the given label.

hasVertex

  • hasVertex(vertex: TVertex): boolean

isReachable

  • isReachable(source: TVertex, target: TVertex): boolean

map

  • map<TClonedVertex, TClonedEdgeData>(vertexMapper: TypedFunction<TVertex, TClonedVertex>, edgeDataMapper: TypedFunction<TEdgeData, TClonedEdgeData>): MultiGraphAdapter<TClonedVertex, TClonedEdgeData, TEdgeLabel>

  • Type parameters

    • TClonedVertex

    • TClonedEdgeData

    Parameters

    • vertexMapper: TypedFunction<TVertex, TClonedVertex>
    • edgeDataMapper: TypedFunction<TEdgeData, TClonedEdgeData>

    Returns MultiGraphAdapter<TClonedVertex, TClonedEdgeData, TEdgeLabel>

mapLabeled

  • mapLabeled<TClonedVertex, TClonedEdgeData, TClonedEdgeLabel>(vertexMapper: TypedFunction<TVertex, TClonedVertex>, edgeDataMapper: TypedFunction<TEdgeData, TClonedEdgeData>, labelMapper: TypedFunction<TEdgeLabel, TClonedEdgeLabel>): MultiGraphAdapter<TClonedVertex, TClonedEdgeData, TClonedEdgeLabel>

  • Creates an independent copy of this graph data structure and maps each vertex and edge datum to a new vertex and edge datum and edge label. Further changes to this graph are not reflected in the returned copy, and vice-versa.

    Type parameters

    • TClonedVertex

      Type of the mapped vertices.

    • TClonedEdgeData

      Type of the cloned edge data.

    • TClonedEdgeLabel

      Type of the cloned edge label.

    Parameters

    • vertexMapper: TypedFunction<TVertex, TClonedVertex>

      Mapping function that takes a vertex and returns a mapped copy of it.

    • edgeDataMapper: TypedFunction<TEdgeData, TClonedEdgeData>

      Mapping function that takes an edge datum and returns a mapped copy of it.

    • labelMapper: TypedFunction<TEdgeLabel, TClonedEdgeLabel>

      Mapping function that takes a label and returns a mapped copy of it.

    Returns MultiGraphAdapter<TClonedVertex, TClonedEdgeData, TClonedEdgeLabel>

    A mapped copy of this graph.

setEdgeData

  • setEdgeData(from: TVertex, to: TVertex, data: TEdgeData | undefined, label?: TEdgeLabel): boolean

supportsOrder

  • supportsOrder(): boolean

Static create

  • Creates a new graph adapter with the given options.

    see

    {@link CommonAdapterOptions}

    Type parameters

    • TVertex

      Type of the vertices of this graph.

    • TEdgeData

      Type of the data associated with edges.

    • TEdgeLabel

      Type of the label used to distiniguish different between edges with the same source and target vertex.

    Parameters

    • Default value options: Partial<MultiGraphAdapterOptions<TVertex, TEdgeData, TEdgeLabel>> = {}

      Options for configuring this instance.

    Returns MultiGraphAdapter<TVertex, TEdgeData, TEdgeLabel>

Legend

  • Module
  • Object literal
  • Variable
  • Function
  • Function with type parameter
  • Index signature
  • Type alias
  • Enumeration
  • Enumeration member
  • Property
  • Method
  • Interface
  • Interface with type parameter
  • Constructor
  • Property
  • Method
  • Index signature
  • Class
  • Class with type parameter
  • Constructor
  • Property
  • Method
  • Accessor
  • Index signature
  • Inherited constructor
  • Inherited property
  • Inherited method
  • Inherited accessor
  • Protected property
  • Protected method
  • Protected accessor
  • Private property
  • Private method
  • Private accessor
  • Static property
  • Static method

Generated using TypeDoc