Package com.mxgraph.analysis
Class mxTraversal
java.lang.Object
com.mxgraph.analysis.mxTraversal
Implements a collection of utility methods for traversing the
graph structure. This does not include tree traversal methods.
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionbellmanFord
(mxAnalysisGraph aGraph, Object startVertex) Implements the Bellman-Ford shortest path from startVertex to all vertices.static void
bfs
(mxAnalysisGraph aGraph, Object startVertex, mxGraph.mxICellVisitor visitor) Implements a recursive breadth first search starting from the specified cell.private static void
bfsRec
(mxAnalysisGraph aGraph, Set<Object> queued, LinkedList<Object[]> queue, mxGraph.mxICellVisitor visitor) Core recursive BFS - for internal usestatic void
dfs
(mxAnalysisGraph aGraph, Object startVertex, mxGraph.mxICellVisitor visitor) Implements a recursive depth first search starting from the specified cell.private static void
dfsRec
(mxAnalysisGraph aGraph, Object cell, Object edge, Set<Object> seen, mxGraph.mxICellVisitor visitor) Core recursive DFS - for internal usestatic void
dijkstra
(mxAnalysisGraph aGraph, Object startVertex, Object endVertex, mxGraph.mxICellVisitor visitor) Implements the Dijkstra's shortest path from startVertex to endVertex.floydRoyWarshall
(mxAnalysisGraph aGraph) Implements the Floyd-Roy-Warshall (aka WFI) shortest path algorithm between all vertices.static Object[]
getWFIPath
(mxAnalysisGraph aGraph, ArrayList<Object[][]> FWIresult, Object startVertex, Object targetVertex) This method helps the user to get the desired data from the result of the Floyd-Roy-Warshall algorithm.getWFIPathRec
(mxAnalysisGraph aGraph, Object[][] paths, Object startVertex, Object targetVertex, ArrayList<Object> currPath, mxCostFunction cf, mxGraphView view) Helper method for getWFIPath - for internal useprivate static Double[][]
initializeWeight
(mxAnalysisGraph aGraph, Object[] nodes, Object[] edges, Map<Object, Integer> indexMap) A helper function for the Floyd-Roy-Warshall algorithm - for internal use
-
Constructor Details
-
mxTraversal
public mxTraversal()
-
-
Method Details
-
dfs
Implements a recursive depth first search starting from the specified cell. Process on the cell is performing by the visitor class passed in. The visitor has access to the current cell and the edge traversed to find this cell. Every cell is processed once only.mxTraversal.bfs(analysisGraph, startVertex, new mxICellVisitor() { public boolean visit(Object vertex, Object edge) { // perform your processing on each cell here return false; } });
- Parameters:
aGraph
- the graphstartVertex
-visitor
-
-
dfsRec
private static void dfsRec(mxAnalysisGraph aGraph, Object cell, Object edge, Set<Object> seen, mxGraph.mxICellVisitor visitor) Core recursive DFS - for internal use- Parameters:
aGraph
-cell
-edge
-seen
-visitor
-
-
bfs
Implements a recursive breadth first search starting from the specified cell. Process on the cell is performing by the visitor class passed in. The visitor has access to the current cell and the edge traversed to find this cell. Every cell is processed once only.mxTraversal.bfs(analysisGraph, startVertex, new mxICellVisitor() { public boolean visit(Object vertex, Object edge) { // perform your processing on each cell here return false; } });
- Parameters:
aGraph
- the graphstartVertex
-visitor
-
-
bfsRec
private static void bfsRec(mxAnalysisGraph aGraph, Set<Object> queued, LinkedList<Object[]> queue, mxGraph.mxICellVisitor visitor) Core recursive BFS - for internal use- Parameters:
aGraph
-queued
-queue
-visitor
-
-
dijkstra
public static void dijkstra(mxAnalysisGraph aGraph, Object startVertex, Object endVertex, mxGraph.mxICellVisitor visitor) throws StructuralException Implements the Dijkstra's shortest path from startVertex to endVertex. Process on the cell is performing by the visitor class passed in. The visitor has access to the current cell and the edge traversed to find this cell. Every cell is processed once only.mxTraversal.dijkstra(analysisGraph, startVertex, endVertex, new mxICellVisitor() { public boolean visit(Object vertex, Object edge) { // perform your processing on each cell here return false; } });
- Parameters:
aGraph
-startVertex
-endVertex
-visitor
-- Throws:
StructuralException
- - The current Dijkstra algorithm only works for connected graphs
-
bellmanFord
public static List<Map<Object,Object>> bellmanFord(mxAnalysisGraph aGraph, Object startVertex) throws StructuralException Implements the Bellman-Ford shortest path from startVertex to all vertices.- Parameters:
aGraph
-startVertex
-- Returns:
- a List where List(0) is the distance map and List(1) is the parent map. See the example in GraphConfigDialog.java
- Throws:
StructuralException
- - The Bellman-Ford algorithm only works for graphs without negative cycles
-
floydRoyWarshall
public static ArrayList<Object[][]> floydRoyWarshall(mxAnalysisGraph aGraph) throws StructuralException Implements the Floyd-Roy-Warshall (aka WFI) shortest path algorithm between all vertices.- Parameters:
aGraph
-- Returns:
- an ArrayList where ArrayList(0) is the distance map and List(1) is the path map. See the example in GraphConfigDialog.java
- Throws:
StructuralException
- - The Floyd-Roy-Warshall algorithm only works for graphs without negative cycles
-
initializeWeight
private static Double[][] initializeWeight(mxAnalysisGraph aGraph, Object[] nodes, Object[] edges, Map<Object, Integer> indexMap) A helper function for the Floyd-Roy-Warshall algorithm - for internal use- Parameters:
aGraph
-nodes
-edges
-indexMap
-- Returns:
-
getWFIPath
public static Object[] getWFIPath(mxAnalysisGraph aGraph, ArrayList<Object[][]> FWIresult, Object startVertex, Object targetVertex) throws StructuralException This method helps the user to get the desired data from the result of the Floyd-Roy-Warshall algorithm.- Parameters:
aGraph
-FWIresult
- - the result of the Floyd-Roy-Warhall algorithmstartVertex
-targetVertex
-- Returns:
- returns the shortest path from startVertex to endVertex
- Throws:
StructuralException
- - The Floyd-Roy-Warshall algorithm only works for graphs without negative cycles
-
getWFIPathRec
private static ArrayList<Object> getWFIPathRec(mxAnalysisGraph aGraph, Object[][] paths, Object startVertex, Object targetVertex, ArrayList<Object> currPath, mxCostFunction cf, mxGraphView view) throws StructuralException Helper method for getWFIPath - for internal use- Parameters:
aGraph
-paths
-startVertex
-targetVertex
-currPath
-cf
-view
-- Returns:
- Throws:
StructuralException
-