com.mxgraph.analysis

## Class mxGraphAnalysis

- java.lang.Object
- - com.mxgraph.analysis.mxGraphAnalysis

-     public class mxGraphAnalysis
      extends java.lang.Object

  A singleton class that provides algorithms for graphs. Assume these variables for the following examples:
  `mxICostFunction cf = mxDistanceCostFunction(); Object[] v = graph.getChildVertices(graph.getDefaultParent()); Object[] e = graph.getChildEdges(graph.getDefaultParent()); mxGraphAnalysis mga = mxGraphAnalysis.getInstance();`

  ### Shortest Path (Dijkstra)

  For example, to find the shortest path between the first and the second selected cell in a graph use the following code:
  `Object[] path = mga.getShortestPath(graph, from, to, cf, v.length, true);`

  ### Minimum Spanning Tree

  This algorithm finds the set of edges with the minimal length that connect all vertices. This algorithm can be used as follows:

  ##### Prim

  `mga.getMinimumSpanningTree(graph, v, cf, true))`

  ##### Kruskal

  `mga.getMinimumSpanningTree(graph, v, e, cf))`

  ### Connection Components

  The union find may be used as follows to determine whether two cells are connected: `boolean connected = uf.differ(vertex1, vertex2)`.
  See Also:
    `mxICostFunction`

- - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected static mxGraphAnalysis` | `instance` Holds the shared instance of this class.

  - ### Constructor Summary

    Constructors
    Modifier | Constructor and Description
    --- | ---
    `protected` | `mxGraphAnalysis()`

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `protected mxFibonacciHeap` | `createPriorityQueue()` Hook for subclassers to provide a custom fibonacci heap.
    `protected mxUnionFind` | `createUnionFind(java.lang.Object[] v)` Hook for subclassers to provide a custom union find structure.
    `mxUnionFind` | `getConnectionComponents(mxGraph graph, java.lang.Object[] v, java.lang.Object[] e)` Returns a union find structure representing the connection components of G=(E,V).
    `static mxGraphAnalysis` | `getInstance()`
    `java.lang.Object[]` | `getMinimumSpanningTree(mxGraph graph, java.lang.Object[] v, mxICostFunction cf, boolean directed)` Returns the minimum spanning tree (MST) for the graph defined by G=(E,V).
    `java.lang.Object[]` | `getMinimumSpanningTree(mxGraph graph, java.lang.Object[] v, java.lang.Object[] e, mxICostFunction cf)` Returns the minimum spanning tree (MST) for the graph defined by G=(E,V).
    `java.lang.Object[]` | `getShortestPath(mxGraph graph, java.lang.Object from, java.lang.Object to, mxICostFunction cf, int steps, boolean directed)` Returns the shortest path between two cells or their descendants represented as an array of edges in order of traversal.
    `static void` | `setInstance(mxGraphAnalysis instance)` Sets the shared instance of this class.
    `mxCellState[]` | `sort(mxCellState[] states, mxICostFunction cf)` Returns a sorted set for `cells` with respect to `cf`.
    `double` | `sum(mxCellState[] states, mxICostFunction cf)` Returns the sum of all cost for `cells` with respect to `cf`.

    - ### Methods inherited from class java.lang.Object

      `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- - ### Field Detail

    - #### instance

          protected static mxGraphAnalysis instance

      Holds the shared instance of this class.

  - ### Constructor Detail

    - #### mxGraphAnalysis

          protected mxGraphAnalysis()

  - ### Method Detail

    - #### getInstance

          public static mxGraphAnalysis getInstance()

      Returns:
        Returns the sharedInstance.

    - #### setInstance

          public static void setInstance(mxGraphAnalysis instance)

      Sets the shared instance of this class.
      Parameters:
        `instance` - The instance to set.

    - #### getShortestPath

          public java.lang.Object[] getShortestPath(mxGraph graph,
                                           java.lang.Object from,
                                           java.lang.Object to,
                                           mxICostFunction cf,
                                           int steps,
                                           boolean directed)

      Returns the shortest path between two cells or their descendants represented as an array of edges in order of traversal.
      This implementation is based on the Dijkstra algorithm.
      Parameters:
        `graph` - The object that defines the graph structure
        `from` - The source cell.
        `to` - The target cell (aka sink).
        `cf` - The cost function that defines the edge length.
        `steps` - The maximum number of edges to traverse.
        `directed` - If edge directions should be taken into account.
      Returns:
        Returns the shortest path as an alternating array of vertices and edges, starting with `from` and ending with `to`.
      See Also:
        `createPriorityQueue()`

    - #### getMinimumSpanningTree

          public java.lang.Object[] getMinimumSpanningTree(mxGraph graph,
                                                  java.lang.Object[] v,
                                                  mxICostFunction cf,
                                                  boolean directed)

      Returns the minimum spanning tree (MST) for the graph defined by G=(E,V). The MST is defined as the set of all vertices with minimal lengths that forms no cycles in G.
      This implementation is based on the algorihm by Prim-Jarnik. It uses O(|E|+|V|log|V|) time when used with a Fibonacci heap and a graph whith a double linked-list datastructure, as is the case with the default implementation.
      Parameters:
        `graph` - the object that describes the graph
        `v` - the vertices of the graph
        `cf` - the cost function that defines the edge length
      Returns:
        Returns the MST as an array of edges
      See Also:
        `createPriorityQueue()`

    - #### getMinimumSpanningTree

          public java.lang.Object[] getMinimumSpanningTree(mxGraph graph,
                                                  java.lang.Object[] v,
                                                  java.lang.Object[] e,
                                                  mxICostFunction cf)

      Returns the minimum spanning tree (MST) for the graph defined by G=(E,V). The MST is defined as the set of all vertices with minimal lenths that forms no cycles in G.
      This implementation is based on the algorihm by Kruskal. It uses O(|E|log|E|)=O(|E|log|V|) time for sorting the edges, O(|V|) create sets, O(|E|) find and O(|V|) union calls on the union find structure, thus yielding no more than O(|E|log|V|) steps. For a faster implementatin
      Parameters:
        `graph` - The object that contains the graph.
        `v` - The vertices of the graph.
        `e` - The edges of the graph.
        `cf` - The cost function that defines the edge length.
      Returns:
        Returns the MST as an array of edges.
      See Also:
        `getMinimumSpanningTree(mxGraph, Object[], mxICostFunction, boolean)`, `createUnionFind(Object[])`

    - #### getConnectionComponents

          public mxUnionFind getConnectionComponents(mxGraph graph,
                                            java.lang.Object[] v,
                                            java.lang.Object[] e)

      Returns a union find structure representing the connection components of G=(E,V).
      Parameters:
        `graph` - The object that contains the graph.
        `v` - The vertices of the graph.
        `e` - The edges of the graph.
      Returns:
        Returns the connection components in G=(E,V)
      See Also:
        `createUnionFind(Object[])`

    - #### sort

          public mxCellState[] sort(mxCellState[] states,
                           mxICostFunction cf)

      Returns a sorted set for `cells` with respect to `cf`.
      Parameters:
        `states` - the cell states to sort
        `cf` - the cost function that defines the order
      Returns:
        Returns an ordered set of `cells` wrt. `cf`

    - #### sum

          public double sum(mxCellState[] states,
                   mxICostFunction cf)

      Returns the sum of all cost for `cells` with respect to `cf`.
      Parameters:
        `states` - the cell states to use for the sum
        `cf` - the cost function that defines the costs
      Returns:
        Returns the sum of all cell cost

    - #### createUnionFind

          protected mxUnionFind createUnionFind(java.lang.Object[] v)

      Hook for subclassers to provide a custom union find structure.
      Parameters:
        `v` - the array of all elements
      Returns:
        Returns a union find structure for `v`

    - #### createPriorityQueue

          protected mxFibonacciHeap createPriorityQueue()

      Hook for subclassers to provide a custom fibonacci heap.

Copyright (c) 2010 Gaudenz Alder. All rights reserved.