graph.trees.dfs

Class DFSTree<V extends Vertex,E extends Edge<V>>

java.lang.Object

graph.elements.Graph<V,E>

graph.trees.dfs.DFSTree<V,E>

Type Parameters:

V - The vertex type

E - The edge type

public class DFSTree<V extends Vertex,E extends Edge<V>>
extends Graph<V,E>

DFS tree, with methods for its creation and relevant method regarding its edges and nodes

Author:

Renata

Constructor Summary

Constructors

Constructor and Description
DFSTree(V root)
DFSTree(V root, int[] numbering, java.util.List<E> treeEdges, java.util.List<E> backEdges, java.util.List<V> vertices)

Method Summary

Modifier and Type	Method and Description
void	addTreeEdge(E e)
void	addVertex(V v, int index) Adds vertex with the provided index to the tree
java.util.List<V>	allDescendantsOf(V v, boolean includeVertex) Returns all vertices that are descendants of vertex v in the tree
java.util.LinkedList<E>	allEdges(V v) All edges leaving or entering the given vertex
java.util.List<E>	allIncomingBackEdges(V v) Finds all back edges entering the given vertex
java.util.List<E>	allOutgoingEdges(V v) Finds all edges (tree and back) leaving the given vertex
java.util.List<E>	allOutgoingTreeEdges(V v) Finds all edges starting from v and ending in a descendant of v (index of v is lower)
java.util.List<V>	directDescendantsOf(V v) Finds all direct descendants of a given vertex.
java.util.List<Path<V,E>>	findAllPathsDFS(V first, V target) Finds all paths between the given two vertices using DFS
void	formBackEdges(java.util.List<E> allEdges) Separates back edges
java.util.List<E>	getAllEdges()
java.util.List<E>	getBackEdges()
E	getHighestReturningEdge(E e) Finds the highest returning edge of a given edge
int	getIndex(V v)
V	getRoot()
java.util.List<E>	getTreeEdges()
java.util.Map<V,java.lang.Integer>	getVerticesWithIndexes()
int	highpt(E e) Finds the highpoint of the given edge The highpt of an edge (v, w) is its highest return point (or v if none exists).
int	highpt(V v) Finds the highpoint of a vertex Highpoint of a vertex is the highest DFS index of an ancestor of v reachable through a back edge from a descendant of v
E	incomingEdge(V v) Finds the incoming edge (starting from an ancestor of v (edge with lower index) and ending in v)
V	leastAncestor(V v) Vertex directly adjacent to v by a back edge that has the lowest index of all such vertices
int	lowpt(E e) Finds the lowpoint of the given edge The lowpt of an edge (v, w) is its lowest return point (or w if none exists).
int	lowpt(V v) Finds the lowpoint of a vertex The lowpoint of a vertex v, denoted by lowpt(v), is the lowest DFS index of an ancestor of v reachable through a back edge from a descendant of v
int[]	lowpts(V v) Finds both lowpt1 and lowpt2 of a vertex The lowpoint of a vertex v, denoted by lowpt(v), is the lowest DFS index of an ancestor of v reachable through a back edge from a descendant of v lowpt1 is the lowest index, lowpt2 is the second lowest
java.util.List<E>	returningEdges(E e) Finds all returning edges of a given edge Given a tree edge e = (u, v), its returning edges are those back edges that from a descendant of v (included v itself ) go to an ancestor of u different from u itself.
void	setRoot(V root)
java.lang.String	toString()
java.util.List<E>	treeEdgesBetween(V first, V target) Finds all tree edges between the given two vertices
java.util.List<V>	treePathBetween(V first, V target) Finds a tree path (presented as a list of vertices belonging to it) between the two given vertices

Methods inherited from class graph.elements.Graph

addEdge, addVertex, addVertex, addVertexBeginning, adjacencyMatrix, adjacentEdges, adjacentVertices, edgeBetween, edgeesBetween, edgesBetween, equals, getAdjacentLists, getAllSelfLoopEdges, getAllSinks, getAllSources, getEdges, getTreeLeaves, getVertexByContent, getVertices, graphMaxDegree, hasEdge, hashCode, hasSelfLoopEdges, hasVertex, inDegree, inEdges, isBiconnected, isConnected, isConnected, isCyclic, isDirected, isRing, isSimple, isSink, isSource, isTree, listBiconnectedComponents, listCutVertices, listMultiEdges, outDegree, outEdges, printAdjacencyMatrix, removeEdge, removeVertex, setDirected, setEdges, setVertices, subgraph, vertexDegree

Methods inherited from class java.lang.Object

getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

DFSTree

public DFSTree(V root)

DFSTree

public DFSTree(V root,
               int[] numbering,
               java.util.List<E> treeEdges,
               java.util.List<E> backEdges,
               java.util.List<V> vertices)

Method Detail

formBackEdges

public void formBackEdges(java.util.List<E> allEdges)

Separates back edges

Parameters:

allEdges - All edges of the tree

getIndex

public int getIndex(V v)

Parameters:

v - Vertex

Returns:

DFS index of the vertex

addVertex

public void addVertex(V v,
                      int index)

Adds vertex with the provided index to the tree

Parameters:

v - Vertex

index - Index

addTreeEdge

public void addTreeEdge(E e)

allEdges

public java.util.LinkedList<E> allEdges(V v)

Description copied from class: Graph

All edges leaving or entering the given vertex

Overrides:

allEdges in class Graph<V extends Vertex,E extends Edge<V>>

Parameters:

v - Vertex

Returns:

A list of all edges leaving or entering v

incomingEdge

public E incomingEdge(V v)

Finds the incoming edge (starting from an ancestor of v (edge with lower index) and ending in v)

Parameters:

v - Vertex

Returns:

Edge entering vertex v

allIncomingBackEdges

public java.util.List<E> allIncomingBackEdges(V v)

Finds all back edges entering the given vertex

Parameters:

v - Vertex

Returns:

A list of all back edges entering v

allOutgoingTreeEdges

public java.util.List<E> allOutgoingTreeEdges(V v)

Finds all edges starting from v and ending in a descendant of v (index of v is lower)

Parameters:

v - Vertex

Returns:

A list of all tree edges leaving v

allOutgoingEdges

public java.util.List<E> allOutgoingEdges(V v)

Finds all edges (tree and back) leaving the given vertex

Parameters:

v - Vertex

Returns:

A list of all edges leaving v

allDescendantsOf

public java.util.List<V> allDescendantsOf(V v,
                                          boolean includeVertex)

Returns all vertices that are descendants of vertex v in the tree

Parameters:

v - Vertex

includeVertex - Specifies if the vertex itself should be in the list of descendants

Returns:

A list of all descendants of v

directDescendantsOf

public java.util.List<V> directDescendantsOf(V v)

Finds all direct descendants of a given vertex. That is, those vertices directly connected with it through a tree edge, with a higher DFS index

Parameters:

v - Vertex

Returns:

List of all direct descendants of v

lowpt

public int lowpt(V v)

Finds the lowpoint of a vertex The lowpoint of a vertex v, denoted by lowpt(v), is the lowest DFS index of an ancestor of v reachable through a back edge from a descendant of v

Parameters:

v - Vertex

Returns:

lowpt of v if there are back edges leading form descendant to ancestor of v, -1 otherwise

lowpts

public int[] lowpts(V v)

Finds both lowpt1 and lowpt2 of a vertex The lowpoint of a vertex v, denoted by lowpt(v), is the lowest DFS index of an ancestor of v reachable through a back edge from a descendant of v lowpt1 is the lowest index, lowpt2 is the second lowest

Parameters:

v - Vertex

Returns:

An array whose first element is lowpt1 and the second one is lowpt2

highpt

public int highpt(V v)

Finds the highpoint of a vertex Highpoint of a vertex is the highest DFS index of an ancestor of v reachable through a back edge from a descendant of v

Parameters:

v - Vertex

Returns:

highpt of v if there are back edges leading form descendant to ancestor of v, -1 otherwise

lowpt

public int lowpt(E e)

Finds the lowpoint of the given edge The lowpt of an edge (v, w) is its lowest return point (or w if none exists).

Parameters:

e - Edge

Returns:

Lowpoint of e

highpt

public int highpt(E e)

Finds the highpoint of the given edge The highpt of an edge (v, w) is its highest return point (or v if none exists).

Parameters:

e - Edge

Returns:

Highpoint of e

returningEdges

public java.util.List<E> returningEdges(E e)

Finds all returning edges of a given edge Given a tree edge e = (u, v), its returning edges are those back edges that from a descendant of v (included v itself ) go to an ancestor of u different from u itself.

Parameters:

e - Edge

Returns:

A list of returning edges of e

getHighestReturningEdge

public E getHighestReturningEdge(E e)

Finds the highest returning edge of a given edge

Parameters:

e - Edge

Returns:

The highest returning edge of e

leastAncestor

public V leastAncestor(V v)

Vertex directly adjacent to v by a back edge that has the lowest index of all such vertices

Parameters:

v - Vertex

Returns:

Least ancestor of v if one exists, null otherwise

treeEdgesBetween

public java.util.List<E> treeEdgesBetween(V first,
                                          V target)

Finds all tree edges between the given two vertices

Parameters:

first - The source vertex

target - The target (destination) vertex

Returns:

A list of all tree edges between first and target

treePathBetween

public java.util.List<V> treePathBetween(V first,
                                         V target)

Finds a tree path (presented as a list of vertices belonging to it) between the two given vertices

Parameters:

first - The source vertex

target - The target (destination) vertex

Returns:

A tree path between first and target

findAllPathsDFS

public java.util.List<Path<V,E>> findAllPathsDFS(V first,
                                                 V target)

Finds all paths between the given two vertices using DFS

Parameters:

first - The source vertex

target - The target (destination) vertex

Returns:

A list of all paths between first and target

getRoot

public V getRoot()

Returns:

The root of the tree

setRoot

public void setRoot(V root)

Parameters:

root - Root to set

getVerticesWithIndexes

public java.util.Map<V,java.lang.Integer> getVerticesWithIndexes()

Returns:

A map of vertices and their DFS indexes

getTreeEdges

public java.util.List<E> getTreeEdges()

Returns:

A list of tree edges

getBackEdges

public java.util.List<E> getBackEdges()

Returns:

A list of back edges

getAllEdges

public java.util.List<E> getAllEdges()

Returns:

All edges

toString

public java.lang.String toString()

Overrides:

toString in class Graph<V extends Vertex,E extends Edge<V>>