com.mindfusion.graphs
Class Graph

java.lang.Object
  com.mindfusion.graphs.Graph

Direct Known Subclasses:

DualGraph

public class Graph
extends java.lang.Object

Field Summary

java.util.HashMap<Edge,Edge>	edgeCopyToOrigMap
java.util.HashMap<Edge,Edge>	edgeOrigToCopyMap
protected java.util.ArrayList<Edge>	edges
int[]	searchOrder
java.util.HashMap<Vertex,Vertex>	vertexCopyToOrigMap
java.util.HashMap<Vertex,Vertex>	vertexOrigToCopyMap
protected java.util.ArrayList<Vertex>	vertices

Constructor Summary

Graph()

Graph(Graph graph, boolean saveMapping)

Method Summary

void	AddEdge(Edge edge)
Edge	AddEdge(Vertex origin, Vertex destination)
void	AddVertexAndOutEdges(Vertex vertex)
void	ConvertToStGraph(java.util.ArrayList<Edge> reversedEdges)
void	DepthFirstSearch()
java.util.ArrayList<Vertex>	FindShortestPath(Set<Vertex> originSet, Set<Vertex> destSet)
java.util.ArrayList<Vertex>	FindShortestPath(Vertex v1, Set<Vertex> destSet)
java.util.ArrayList<Vertex>	FindShortestPath(Vertex v1, Vertex v2)
Graph[]	GetBiconnectedComponents()
Graph[]	GetBiconnectedComponents(boolean saveMapping)
Graph[]	GetConnectedComponents()
Graph[]	GetConnectedComponentsQuickFind()
Graph[]	GetConnectedComponentsQuickUnion()
DualGraph	GetDualGraph(boolean cacheIncidentFaces)
Graph[]	GetEdgeConnectedComponents()
java.util.ArrayList<Edge>	getEdges()
Embedding	GetPlanarEmbedding()
Graph	GetPlanarSubgraph(java.util.ArrayList<Edge> edgesToDelete)
java.util.ArrayList<Vertex>	GetStNumbering()
java.util.ArrayList<Vertex>	getVertices()
float[]	GetWeightedTopologicalNumbering()
float[]	GetWeightedTopologicalNumbering(float minNumber)
float[]	GetWeightedTopologicalNumbering(int[] tsort, float minNumber)
boolean	IsPlanar()
java.util.ArrayList<Edge>	MakeAcyclic()
java.util.ArrayList<Edge>	MakeBiconnected()
Graph	Planarize(java.util.HashMap<Edge,java.util.ArrayList<Edge>> edgeToDummyEdgesMap)
void	RemoveAllEdges()
void	RemoveEdge(Edge e)
static void	reverse(int[] b)
java.util.HashMap<Vertex,Graph>	SplitToMaxDegree(int maxDegree)
Graph	SplitToMaxDegree(Vertex vertex, int maxDegree)
int[]	TopologicalSort()
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

vertices

protected java.util.ArrayList<Vertex> vertices

edges

protected java.util.ArrayList<Edge> edges

searchOrder

public int[] searchOrder

vertexCopyToOrigMap

public java.util.HashMap<Vertex,Vertex> vertexCopyToOrigMap

edgeCopyToOrigMap

public java.util.HashMap<Edge,Edge> edgeCopyToOrigMap

vertexOrigToCopyMap

public java.util.HashMap<Vertex,Vertex> vertexOrigToCopyMap

edgeOrigToCopyMap

public java.util.HashMap<Edge,Edge> edgeOrigToCopyMap

Constructor Detail

Graph

public Graph()

Graph

public Graph(Graph graph,
             boolean saveMapping)

Method Detail

AddEdge

public Edge AddEdge(Vertex origin,
                    Vertex destination)

AddEdge

public void AddEdge(Edge edge)

RemoveAllEdges

public void RemoveAllEdges()

GetConnectedComponents

public Graph[] GetConnectedComponents()

GetEdgeConnectedComponents

public Graph[] GetEdgeConnectedComponents()

GetBiconnectedComponents

public Graph[] GetBiconnectedComponents()

GetBiconnectedComponents

public Graph[] GetBiconnectedComponents(boolean saveMapping)

MakeBiconnected

public java.util.ArrayList<Edge> MakeBiconnected()

GetConnectedComponentsQuickFind

public Graph[] GetConnectedComponentsQuickFind()

GetConnectedComponentsQuickUnion

public Graph[] GetConnectedComponentsQuickUnion()

DepthFirstSearch

public void DepthFirstSearch()

GetStNumbering

public java.util.ArrayList<Vertex> GetStNumbering()

ConvertToStGraph

public void ConvertToStGraph(java.util.ArrayList<Edge> reversedEdges)

IsPlanar

public boolean IsPlanar()

GetPlanarEmbedding

public Embedding GetPlanarEmbedding()

GetPlanarSubgraph

public Graph GetPlanarSubgraph(java.util.ArrayList<Edge> edgesToDelete)

Planarize

public Graph Planarize(java.util.HashMap<Edge,java.util.ArrayList<Edge>> edgeToDummyEdgesMap)

RemoveEdge

public void RemoveEdge(Edge e)

FindShortestPath

public java.util.ArrayList<Vertex> FindShortestPath(Vertex v1,
                                                    Vertex v2)

FindShortestPath

public java.util.ArrayList<Vertex> FindShortestPath(Vertex v1,
                                                    Set<Vertex> destSet)

FindShortestPath

public java.util.ArrayList<Vertex> FindShortestPath(Set<Vertex> originSet,
                                                    Set<Vertex> destSet)

GetDualGraph

public DualGraph GetDualGraph(boolean cacheIncidentFaces)

TopologicalSort

public int[] TopologicalSort()

reverse

public static void reverse(int[] b)

GetWeightedTopologicalNumbering

public float[] GetWeightedTopologicalNumbering()

GetWeightedTopologicalNumbering

public float[] GetWeightedTopologicalNumbering(float minNumber)

GetWeightedTopologicalNumbering

public float[] GetWeightedTopologicalNumbering(int[] tsort,
                                               float minNumber)

SplitToMaxDegree

public java.util.HashMap<Vertex,Graph> SplitToMaxDegree(int maxDegree)

SplitToMaxDegree

public Graph SplitToMaxDegree(Vertex vertex,
                              int maxDegree)

MakeAcyclic

public java.util.ArrayList<Edge> MakeAcyclic()

AddVertexAndOutEdges

public void AddVertexAndOutEdges(Vertex vertex)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

getVertices

public java.util.ArrayList<Vertex> getVertices()

getEdges

public java.util.ArrayList<Edge> getEdges()