@ai-on-browser/data-analysis-models
    Preparing search index...

    Class Graph

    Graph class

    Index

    Constructors

    constructor

    Accessors

    edges nodes order size

    Methods

    _mincutKargersStein0 _stNumbering addEdge addNode adjacencies adjacencyList adjacencyMatrix articulations articulationsEachNodes articulationsLowLink biconnectedComponents bisectionSpectral bridges bridgesLowLink cartesianProduct center chromaticIndex chromaticNumber chromaticNumberWelchPowell clearEdges clearNodes cleaving clique complement components contraction copy cut degree degreeMatrix diameter disjointUnion eccentricity getEdges getNode girth hamiltonianCycle hamiltonianPath hamiltonianPathDynamicProgramming hasCycle hasCycleDFS hasCycleEachNodes inducedSub isBiconnected isBipartite isComplete isConnected isDAG isDirected isEdgeless isEulerian isForest isHamiltonian isMixed isNull isomorphism isomorphismUllmann isomorphismVF2 isOriented isPlainer isPlainerAddEdge isPlainerAddVertex isRegular isSemiEulerian isSemiHamiltonian isSeparable isSimple isSymmetric isTree isUndirected isWeighted laplacianMatrix lexicographicProduct line mincut mincutBruteForce mincutKargers mincutKargersStein mincutStoerWagner minimumSpanningTree minimumSpanningTreeBoruvka minimumSpanningTreeKruskal minimumSpanningTreePrim radius removeEdges removeNode shortestPath shortestPathBellmanFord shortestPathBreadthFirstSearch shortestPathDijkstra shortestPathFloydWarshall strongProduct subdivision substitution tensorProduct toDot toSimple toString toUndirected complete completeBipartite cycle fromAdjacency fromName wheel windmill

    Constructors

    • Parameters

      • Optionalnodes: number | unknown[]

        Number of nodes or values of nodes

      • Optionaledges: (
            | [number, number]
            | {
                "0"?: number;
                "1"?: number;
                direct?: boolean;
                from?: number;
                to?: number;
                value?: unknown;
            }
            | Edge
        )[]

        Edges

      Returns Graph

    Accessors

    • get edges(): Edge[]

      Edges

      Returns Edge[]

    • get nodes(): unknown[]

      Nodes

      Returns unknown[]

    • get order(): number

      Number of nodes

      Returns number

    • get size(): number

      Number of edges

      Returns number

    Methods

    _mincutKargersStein0

    • _mincutKargersStein0(amat: any, nodes: any, minv: any): any

      Parameters

      • amat: any
      • nodes: any
      • minv: any

      Returns any

    _stNumbering

    • _stNumbering(s?: number, t?: any): number[]

      Parameters

      • Optionals: number
      • Optionalt: any

      Returns number[]

    • Add the edge.

      Parameters

      • from: number

        Index of the starting node of the edge

      • to: number

        Index of the end node of the edge

      • Optionalvalue: unknown

        Value of the edge

      • Optionaldirect: boolean

        true if the edge is direct

      Returns void

    • Add the node.

      Parameters

      • Optionalvalue: unknown

        Value of the node

      Returns void

    • Return indexes of adjacency nodes.

      Parameters

      • k: number

        Index of target node

      • Optionalundirect: boolean

        Check undirected edges

      • Optionaldirect: boolean | "in" | "out"

        Check directed edges

      Returns number[]

      Indexes of adjacency nodes

    • Return indexes of adjacency nodes.

      Parameters

      • k: number

        Index of target node

      • direct: "in" | "out"

        Check only directed edges

      Returns number[]

      Indexes of adjacency nodes

    • Returns adjacency list

      Parameters

      • Optionaldirect: "in" | "out" | "both"

        Indegree or outdegree

      Returns number[][]

      Adjacency list

    • Returns adjacency matrix

      Returns number[][]

      Adjacency matrix

    • Returns indexes of articulation (cut) nodes.

      Returns number[]

      Indexes of articulation nodes

    • Returns indexes of articulation (cut) nodes with checking each node.

      Returns number[]

      Indexes of articulation nodes

    • Returns indexes of articulation (cut) nodes with checking lowlinks.

      Returns number[]

      Indexes of articulation nodes

    • Returns indexes of each biconnected components.

      Returns number[][]

      Indexes of each biconnected components

    • Returns bisection cut.

      Returns [number, number[][]]

      Cut value and subset nodes

    • Returns edges of bridge.

      Returns Edge[]

      Bridge edges

    • Returns edges of bridge with checking lowlinks.

      Returns Edge[]

      Bridge edges

    • Take the cartesian product of this graph and other graph.

      Parameters

      Returns Graph

      Cartesian producted graph

    • Returns indexes of center of this graph.

      Returns number[]

      Indexes of center

    • Returns chromatic index of this graph.

      Returns number

      Chromatic index

    • Returns chromatic number of this graph.

      Returns number

      Chromatic number

    • Returns chromatic number of this graph with Welch-Powell algorithm.

      Returns number

      Chromatic number

    • Remove all edges.

      Returns void

    • Remove all nodes.

      Returns void

    • Cleave the node.

      Parameters

      • a: number

        Index of node

      Returns void

    • Returns index of all cliques.

      Returns number[][][]

      Index of cliques

    • Returns index of cliques.

      Parameters

      • k: number

        Size of clique

      Returns number[][]

      Index of cliques

    • Returns complement graph.

      Returns Graph

      Complement graph

    • Returns indexes of each components.

      Returns number[][]

      Indexes of each components

    • Contract this graph.

      Parameters

      • a: number

        Index of node

      • b: number

        Index of node

      Returns void

    • Returns a copy of this graph.

      Returns Graph

      Copied grpah

    • Returns cut size.

      Parameters

      • s: number[]

        Subset

      • t: number[]

        Subset

      Returns number

      Cut size

    • Return degree of the node.

      Parameters

      • k: number

        Index of target node

      • Optionalundirect: boolean

        Count undirected edges

      • Optionaldirect: boolean | "in" | "out"

        Count directed edges

      Returns number

      Degree of the node

    • Return degree of the node.

      Parameters

      • k: number

        Index of target node

      • direct: "in" | "out"

        Count only directed edges.

      Returns number

      Degree of the node

    • Returns degree matrix.

      Parameters

      • Optionaldirect: "in" | "out" | "both"

        Indegree or outdegree

      Returns number[][]

      Degree matrix

    • Returns diameter of this graph.

      Returns number

      Diameter

    • Take the disjoint union of this graph and other graph.

      Parameters

      Returns void

    • Returns eccentricity at k of this graph.

      Parameters

      • k: number

        Index of target node

      Returns number

      Eccentricity

    • Returns the edges.

      Parameters

      • from: number

        Index of the starting node of the edge

      • to: number

        Index of the end node of the edge

      • Optionalundirect: boolean

        Get undirected edges or not

      • Optionaldirect: boolean | "forward" | "backward"

        Get directed edges or not

      Returns Edge[]

      Edges between from and to

    • Returns the edges.

      Parameters

      • from: number

        Index of the starting node of the edge

      • to: number

        Index of the end node of the edge

      • direct: "forward" | "backward"

        Get only directed edges

      Returns Edge[]

      Edges between from and to

    • Returns the node value.

      Parameters

      • k: number

        Index of the node

      Returns unknown

      Node value

    • Returns the node value.

      Parameters

      • Optionalk: number[]

        Index of the node

      Returns unknown[]

      Node value

    • Returns girth of this graph.

      Returns number

      Girth

    • Returns Hamiltonian cycle

      Returns number[][]

      Hamiltonian cycle

    • Returns Hamiltonian path

      Parameters

      • Optionalfrom: number

        Index of start node

      Returns number[][]

      Hamiltonian path

    • Returns Hamiltonian path with dynamic programming

      Parameters

      • Optionalfrom: number

        Index of start node

      Returns number[][]

      Hamiltonian path

    • Returns if this has cycle or not.

      Returns boolean

      true if this has cycle

    • Returns if this has cycle or not with depth-first search.

      Returns boolean

      true if this has cycle

    • Returns if this has cycle or not with checking each node.

      Returns boolean

      true if this has cycle

    • Returns induced sub graph.

      Parameters

      • k: number[]

        Selected indexes

      Returns Graph

      Induced sub graph

    • Returns if this is biconnected graph or not.

      Returns boolean

      true if this is biconnected graph

    • Returns if this is bipartite graph or not.

      Returns boolean

      true if this is bipartite graph

    • Returns if this is complete graph or not.

      Returns boolean

      true if this is complete graph

    • Returns if this is connected graph or not.

      Returns boolean

      true if this is connected graph

    • Returns if this is directed acyclic graph or not.

      Returns boolean

      true if this is directed acyclic graph

    • Returns if this is directed graph or not.

      Returns boolean

      true if this is directed graph

    • Returns if this is edgeless graph or not.

      Returns boolean

      true if this is edgeless graph

    • Returns if this is Eulerian graph or not.

      Returns boolean

      true if this is Eulerian graph

    • Returns if this is forest or not.

      Returns boolean

      true if this is forest

    • Returns if this is Hamiltonian graph or not.

      Returns boolean

      true if this is Hamiltonian graph

    • Returns if this is mixed graph or not.

      Returns boolean

      true if this is mixed graph

    • Returns if this is null graph or not.

      Returns boolean

      true if this is null graph

    • Returns (sub) graph isomorphism maps from 'g' to this (sub) graph.

      Parameters

      Returns number[][]

      Isomorphism maps from 'g' to this (sub) graph

    • Returns (sub) graph isomorphism maps from 'g' to this (sub) graph with Ullmann algorithm.

      Parameters

      Returns number[][]

      Isomorphism maps from 'g' to this (sub) graph

    • Returns (sub) graph isomorphism maps from 'g' to this (sub) graph with VF2 algorithm.

      Parameters

      Returns number[][]

      Isomorphism maps from 'g' to this (sub) graph

    • Returns if this is oriented graph or not.

      Returns boolean

      true if this is oriented graph

    • Returns if this is plainer graph or not.

      Returns boolean

      true if this is plainer graph

    • Returns if this is plainer graph or not with add-path algorithm.

      On the Cutting Edge: Simplified O(n) Planarity by Edge Addition https://xuzijian629.hatenablog.com/entry/2019/12/14/163726

      Returns boolean

      true if this is plainer graph

    • Returns if this is plainer graph or not with add-vertex algorithm.

      Hopcroft, J. and Tarjan, R. "Efficient Planarity Testing", J. ACM, Vol. 21, No. 4, pp. 549-568 (1974) 西関 隆夫. "32. グラフの平面性判定法", 情報処理, Vol. 24, No. 4, pp. 521-528 (1983) K. S. Booth, "Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ-Tree Algorithms", Journal of computer and system sciences, 13, pp. 335-379 (1976)

      Returns boolean

      true if this is plainer graph

    • Returns if this is regular graph or not.

      Parameters

      • Optionaln: number

        Degree of vertices

      Returns boolean

      true if this is regular graph

    • Returns if this is semi-Eulerian graph or not.

      Returns boolean

      true if this is semi-Eulerian graph

    • Returns if this is semi-Hamiltonian graph or not.

      Returns boolean

      true if this is semi-Hamiltonian graph

    • Returns if this is separable graph or not.

      Returns boolean

      true if this is separable graph

    • Returns if this is simple graph or not.

      Returns boolean

      true if this is simple graph

    • Returns if this is symmetric graph or not.

      Returns boolean

      true if this is symmetric graph

    • Returns if this is tree or not.

      Returns boolean

      true if this is tree

    • Returns if this is undirected graph or not.

      Returns boolean

      true if this is undirected graph

    • Returns if this is weighted graph or not.

      Returns boolean

      true if this is weighted graph

    • Returns laplacian matrix.

      Returns number[][]

      Laplacian matrix

    • Take the lexicographic product of this graph and other graph.

      Parameters

      Returns Graph

      Lexicographic producted graph

    • Returns line graph.

      Returns Graph

      Line graph

    • Returns minimum cut.

      Parameters

      • Optionalminv: number

        Minimum number for subset

      Returns [number, number[][]]

      Cut value and subset nodes

    • Returns minimum cut.

      Parameters

      • Optionalminv: number

        Minimum number for subset

      Returns [number, number[][]]

      Cut value and subset nodes

    • Returns minimum cut.

      Parameters

      • Optionalminv: number

        Minimum number for subset

      • Optionaltrials: number

        Trial count

      Returns [number, number[][]]

      Cut value and subset nodes

    • Returns minimum cut.

      Parameters

      • Optionalminv: number

        Minimum number for subset

      • Optionaltrials: number

        Trial count

      Returns [number, number[][]]

      Cut value and subset nodes

    • Returns minimum cut.

      Parameters

      • Optionalminv: number

        Minimum number for subset

      • Optionalstartnode: number

        Start node index

      Returns [number, number[][]]

      Cut value and subset nodes

    • Returns minimum spanning tree.

      Returns Graph

      Minimum spanning tree

    • Returns minimum spanning tree with Borůvka's algorithm.

      Returns Graph

      Minimum spanning tree

    • Returns minimum spanning tree with Kruskal's algorithm.

      Returns Graph

      Minimum spanning tree

    • Returns minimum spanning tree with Prim's algorithm.

      Returns Graph

      Minimum spanning tree

    • Returns radius of this graph.

      Returns number

      Radius

    • Remove the edges.

      Parameters

      • from: number

        Index of the starting node of the edge

      • to: number

        Index of the end node of the edge

      • Optionaldirect: boolean

        null to remove direct and undirect edges, true to remove only direct edges, false to remove only undirect edges.

      Returns void

    • Remove the node.

      Parameters

      • k: number

        Index of the node

      Returns void

    • Returns shortest path.

      Parameters

      • Optionalfrom: null

        Index of start nodes

      Returns { length: number; path: number[] }[][]

      Shortest length and path for all nodes

    • Returns shortest path.

      Parameters

      • from: number

        Index of start nodes

      Returns { length: number; path: number[]; prev: number }[]

      Shortest length and path for all nodes

    • Returns shortest path with Bellman–Ford algorithm.

      Parameters

      • from: number

        Index of start node

      Returns { length: number; path: number[]; prev: number }[]

      Shortest length and path for all nodes

    • Returns shortest path with breadth first search algorithm.

      Parameters

      • from: number

        Index of start node

      Returns { length: number; path: number[]; prev: number }[]

      Shortest length and path for all nodes

    • Returns shortest path with Dijkstra's algorithm.

      Parameters

      • from: number

        Index of start node

      Returns { length: number; path: number[]; prev: number }[]

      Shortest length and path for all nodes

    • Returns shortest path with Floyd–Warshall algorithm.

      Returns { length: number; path: number[] }[][]

      Shortest length and path for all nodes

    • Take the strong product of this graph and other graph.

      Parameters

      Returns Graph

      Strong producted graph

    • Subdivision this graph.

      Parameters

      • a: number

        Index of node

      • b: number

        Index of node

      Returns void

    • Substitute other graph at the node.

      Parameters

      • k: number

        Index of the node

      • g: Graph

        Other graph

      Returns void

    • Take the tensor product of this graph and other graph.

      Parameters

      Returns Graph

      Tensor producted graph

    • Returns a string of DOT format.

      Returns string

      String of DOT format

    • Returns a graph with multiple edges and loops removed.

      Returns Graph

      Simple graph

    • Returns a string represented this graph.

      Returns string

      String represented this graph

    • Returns graph of directed edges converted to undirected.

      Returns Graph

      Undirected graph

    • Returns complete graph.

      Parameters

      • n: number

        Size of the graph

      Returns Graph

      Complete graph

    • Returns complete bipartite graph.

      Parameters

      • n: number

        Size of the first group

      • m: number

        Size of the second group

      Returns Graph

      Complete bipartite graph

    • Returns cycle graph.

      Parameters

      • n: number

        Size of the graph

      • Optionaldirect: boolean

        Direct graph or not

      Returns Graph

      Cycle graph

    • Returns graph from adjacency matrix.

      Parameters

      • mat: number[][] | boolean[][]

        Adjacency matrix

      Returns Graph

      Graph from adjacency matrix

    • Returns named graph

      Parameters

      • name:
            | "balaban 10 cage"
            | "bidiakis cube"
            | "biggs smith"
            | "brinkmann"
            | "bull"
            | "butterfly"
            | "chvatal"
            | "clebsch"
            | "coxeter"
            | "desargues"
            | "diamond"
            | "durer"
            | "errera"
            | "folkman"
            | "foster"
            | "franklin"
            | "frucht"
            | "goldner-harary"
            | "golomb"
            | "gray"
            | "grotzsch"
            | "harries"
            | "heawood"
            | "herschel"
            | "hoffman"
            | "holt"
            | "kittell"
            | "markstrom"
            | "mcgee"
            | "meredith"
            | "mobius kantor"
            | "moser spindle"
            | "nauru"
            | "pappus"
            | "petersen"
            | "poussin"
            | "robertson"
            | "shrikhande"
            | "sousselier"
            | "sylvester"
            | "tutte"
            | "tutte coxeter"
            | "wagner"
            | "wells"

        Name of the graph

      Returns Graph

      Named graph

    • Returns wheel graph.

      Parameters

      • n: number

        Size of the graph

      Returns Graph

      Wheel graph

    • Returns windmill graph.

      Parameters

      • k: number

        Size of the sub complete graph

      • n: number

        Number of the sub complete graph

      Returns Graph

      Windmill graph

    Settings

    Member Visibility

    On This Page

    Constructors
    Accessors
    Methods
    _mincutKargersStein0_stNumberingaddEdgeaddNodeadjacenciesadjacencyListadjacencyMatrixarticulationsarticulationsEachNodesarticulationsLowLinkbiconnectedComponentsbisectionSpectralbridgesbridgesLowLinkcartesianProductcenterchromaticIndexchromaticNumberchromaticNumberWelchPowellclearEdgesclearNodescleavingcliquecomplementcomponentscontractioncopycutdegreedegreeMatrixdiameterdisjointUnioneccentricitygetEdgesgetNodegirthhamiltonianCyclehamiltonianPathhamiltonianPathDynamicProgramminghasCyclehasCycleDFShasCycleEachNodesinducedSubisBiconnectedisBipartiteisCompleteisConnectedisDAGisDirectedisEdgelessisEulerianisForestisHamiltonianisMixedisNullisomorphismisomorphismUllmannisomorphismVF2isOrientedisPlainerisPlainerAddEdgeisPlainerAddVertexisRegularisSemiEulerianisSemiHamiltonianisSeparableisSimpleisSymmetricisTreeisUndirectedisWeightedlaplacianMatrixlexicographicProductlinemincutmincutBruteForcemincutKargersmincutKargersSteinmincutStoerWagnerminimumSpanningTreeminimumSpanningTreeBoruvkaminimumSpanningTreeKruskalminimumSpanningTreePrimradiusremoveEdgesremoveNodeshortestPathshortestPathBellmanFordshortestPathBreadthFirstSearchshortestPathDijkstrashortestPathFloydWarshallstrongProductsubdivisionsubstitutiontensorProducttoDottoSimpletoStringtoUndirectedcompletecompleteBipartitecyclefromAdjacencyfromNamewheelwindmill