Grafo.Dirigido

java.lang.Object
- cl.cromer.estructuras.Grafo.Dirigido<T>

Enclosing class:

Grafo
```
public static final class Grafo.Dirigido<T>
extends java.lang.Object
```
JBoss, Home of Professional Open Source Copyright 2006, Red Hat Middleware LLC, and individual contributors by the @authors tag. See the copyright.txt in the distribution for a full listing of individual contributors. This is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this software; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA, or see the FSF site: http://www.fsf.org.

Field Summary

Fields
Modifier and Type	Field and Description
`private java.util.List<Grafo.Edge<T>>`	`edges` Vector of edges in the graph
`private Grafo.Vertex<T>`	`rootVertex` The vertex identified as the root of the graph
`private java.util.List<Grafo.Vertex<T>>`	`verticies` Vector of graph verticies
`static int`	`VISIT_COLOR_BLACK` Color used to mark nodes after descendants are completely visited
`static int`	`VISIT_COLOR_GREY` Color used to mark nodes as they are first visited in DFS order
`static int`	`VISIT_COLOR_WHITE` Color used to mark unvisited nodes

Constructor Summary

Constructors
Constructor and Description

Dirigido()
Construct a new graph without any vertices or edges

Constructors
Constructor and Description
`Dirigido()` Construct a new graph without any vertices or edges

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`boolean`	`addEdge(Grafo.Vertex<T> from, Grafo.Vertex<T> to, int cost)` Insert a directed, weighted Edge into the graph.
`boolean`	`addVertex(Grafo.Vertex<T> v)` Add a vertex to the graph
`void`	`breadthFirstSearch(Grafo.Vertex<T> v, Grafo.Visitor<T> visitor)` Perform a breadth first search of this graph, starting at v.
`<E extends java.lang.Exception> void`	`breadthFirstSearch(Grafo.Vertex<T> v, Grafo.VisitorEX<T,E> visitor)` Perform a breadth first search of this graph, starting at v.
`void`	`clearEdges()` Clear the mark state of all edges in the graph by calling clearMark() on all edges.
`void`	`clearMark()` Clear the mark state of all verticies in the graph by calling clearMark() on all verticies.
`<E extends java.lang.Exception> void`	`depthFirstSearch(Grafo.Vertex<T> v, Grafo.VisitorEX<T,E> visitor)` Perform a depth first serach using recursion.
`void`	`dfsSpanningTree(Grafo.Vertex<T> v, Grafo.DFSVisitor<T> visitor)` Find the spanning tree using a DFS starting from v.
`Grafo.Edge<T>[]`	`findCycles()` Search the graph for cycles.
`Grafo.Vertex<T>`	`findVertexByData(T data, java.util.Comparator<T> compare)` Search the verticies for one with data.
`Grafo.Vertex<T>`	`findVertexByName(java.lang.String name)` Search the verticies for one with name.
`java.util.List<Grafo.Edge<T>>`	`getEdges()` Get the graph edges
`Grafo.Vertex<T>`	`getRootVertex()` Get the root vertex
`Grafo.Vertex<T>`	`getVertex(int n)` Get the given Vertex.
`java.util.List<Grafo.Vertex<T>>`	`getVerticies()` Get the graph verticies
`boolean`	`insertBiEdge(Grafo.Vertex<T> from, Grafo.Vertex<T> to, int cost)` Insert a bidirectional Edge in the graph
`boolean`	`isEmpty()` Are there any verticies in the graph
`boolean`	`removeEdge(Grafo.Vertex<T> from, Grafo.Vertex<T> to)` Remove an Edge from the graph
`boolean`	`removeVertex(Grafo.Vertex<T> v)` Remove a vertex from the graph
`void`	`setRootVertex(Grafo.Vertex<T> root)` Set a root vertex.
`int`	`size()` Get the vertex count.
`java.lang.String`	`toString()`
`private void`	`visit(Grafo.Vertex<T> v, java.util.ArrayList<Grafo.Edge<T>> cycleEdges)`

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

- Field Detail
  - VISIT_COLOR_WHITE
```
public static final int VISIT_COLOR_WHITE
```
    Color used to mark unvisited nodes
    
    See Also:
    
    Constant Field Values
  - VISIT_COLOR_GREY
```
public static final int VISIT_COLOR_GREY
```
    Color used to mark nodes as they are first visited in DFS order
    
    See Also:
    
    Constant Field Values
  - VISIT_COLOR_BLACK
```
public static final int VISIT_COLOR_BLACK
```
    Color used to mark nodes after descendants are completely visited
    
    See Also:
    
    Constant Field Values
  - verticies
```
private java.util.List<Grafo.Vertex<T>> verticies
```
    Vector of graph verticies
  - edges
```
private java.util.List<Grafo.Edge<T>> edges
```
    Vector of edges in the graph
  - rootVertex
```
private Grafo.Vertex<T> rootVertex
```
    The vertex identified as the root of the graph
- Constructor Detail
  - Dirigido
```
public Dirigido()
```
    Construct a new graph without any vertices or edges
- Method Detail
  - isEmpty
```
public boolean isEmpty()
```
    Are there any verticies in the graph
    
    Returns:
    
    true if there are no verticies in the graph
  - addVertex
```
public boolean addVertex(Grafo.Vertex<T> v)
```
    Add a vertex to the graph
    
    Parameters:
    
    v - the Vertex to add
    
    Returns:
    
    true if the vertex was added, false if it was already in the graph.
  - size
```
public int size()
```
    Get the vertex count.
    
    Returns:
    
    the number of verticies in the graph.
  - getRootVertex
```
public Grafo.Vertex<T> getRootVertex()
```
    Get the root vertex
    
    Returns:
    
    the root vertex if one is set, null if no vertex has been set as the root.
  - setRootVertex
```
public void setRootVertex(Grafo.Vertex<T> root)
```
    Set a root vertex. If root does no exist in the graph it is added.
    
    Parameters:
    
    root - - the vertex to set as the root and optionally add if it does not exist in the graph.
  - getVertex
```
public Grafo.Vertex<T> getVertex(int n)
```
    Get the given Vertex.
    
    Parameters:
    
    n - the index [0, size()-1] of the Vertex to access
    
    Returns:
    
    the nth Vertex
  - getVerticies
```
public java.util.List<Grafo.Vertex<T>> getVerticies()
```
    Get the graph verticies
    
    Returns:
    
    the graph verticies
  - addEdge
```
public boolean addEdge(Grafo.Vertex<T> from,
                       Grafo.Vertex<T> to,
                       int cost)
                throws java.lang.IllegalArgumentException
```
    Insert a directed, weighted Edge into the graph.
    
    Parameters:
    
    from - - the Edge starting vertex
    
    to - - the Edge ending vertex
    
    cost - - the Edge weight/cost
    
    Returns:
    
    true if the Edge was added, false if from already has this Edge
    
    Throws:
    
    java.lang.IllegalArgumentException - if from/to are not verticies in the graph
  - insertBiEdge
```
public boolean insertBiEdge(Grafo.Vertex<T> from,
                            Grafo.Vertex<T> to,
                            int cost)
                     throws java.lang.IllegalArgumentException
```
    Insert a bidirectional Edge in the graph
    
    Parameters:
    
    from - - the Edge starting vertex
    
    to - - the Edge ending vertex
    
    cost - - the Edge weight/cost
    
    Returns:
    
    true if edges between both nodes were added, false otherwise
    
    Throws:
    
    java.lang.IllegalArgumentException - if from/to are not verticies in the graph
  - getEdges
```
public java.util.List<Grafo.Edge<T>> getEdges()
```
    Get the graph edges
    
    Returns:
    
    the graph edges
  - removeVertex
```
public boolean removeVertex(Grafo.Vertex<T> v)
```
    Remove a vertex from the graph
    
    Parameters:
    
    v - the Vertex to remove
    
    Returns:
    
    true if the Vertex was removed
  - removeEdge
```
public boolean removeEdge(Grafo.Vertex<T> from,
                          Grafo.Vertex<T> to)
```
    Remove an Edge from the graph
    
    Parameters:
    
    from - - the Edge starting vertex
    
    to - - the Edge ending vertex
    
    Returns:
    
    true if the Edge exists, false otherwise
  - clearMark
```
public void clearMark()
```
    Clear the mark state of all verticies in the graph by calling clearMark() on all verticies.
    
    See Also:
    
    Grafo.Vertex.clearMark()
  - clearEdges
```
public void clearEdges()
```
    Clear the mark state of all edges in the graph by calling clearMark() on all edges.
  - depthFirstSearch
```
public <E extends java.lang.Exception> void depthFirstSearch(Grafo.Vertex<T> v,
                                                             Grafo.VisitorEX<T,E> visitor)
                                                      throws E extends java.lang.Exception
```
    Perform a depth first serach using recursion.
    
    Type Parameters:
    
    E - Exception
    
    Parameters:
    
    v - - the Vertex to start the search from
    
    visitor - - the vistor to inform prior to
    
    Throws:
    
    E - if visitor.visit throws an exception
    
    E extends java.lang.Exception
  - breadthFirstSearch
```
public void breadthFirstSearch(Grafo.Vertex<T> v,
                               Grafo.Visitor<T> visitor)
```
    Perform a breadth first search of this graph, starting at v.
    
    Parameters:
    
    v - - the search starting point
    
    visitor - - the vistor whose vist method is called prior to visting a vertex.
  - breadthFirstSearch
```
public <E extends java.lang.Exception> void breadthFirstSearch(Grafo.Vertex<T> v,
                                                               Grafo.VisitorEX<T,E> visitor)
                                                        throws E extends java.lang.Exception
```
    Perform a breadth first search of this graph, starting at v. The vist may be cut short if visitor throws an exception during a vist callback.
    
    Type Parameters:
    
    E - - exception
    
    Parameters:
    
    v - - the search starting point
    
    visitor - - the vistor whose vist method is called prior to visting a vertex.
    
    Throws:
    
    E - if vistor.visit throws an exception
    
    E extends java.lang.Exception
  - dfsSpanningTree
```
public void dfsSpanningTree(Grafo.Vertex<T> v,
                            Grafo.DFSVisitor<T> visitor)
```
    Find the spanning tree using a DFS starting from v.
    
    Parameters:
    
    v - - the vertex to start the search from
    
    visitor - - visitor invoked after each vertex is visited and an edge is added to the tree.
  - findVertexByName
```
public Grafo.Vertex<T> findVertexByName(java.lang.String name)
```
    Search the verticies for one with name.
    
    Parameters:
    
    name - - the vertex name
    
    Returns:
    
    the first vertex with a matching name, null if no matches are found
  - findVertexByData
```
public Grafo.Vertex<T> findVertexByData(T data,
                                        java.util.Comparator<T> compare)
```
    Search the verticies for one with data.
    
    Parameters:
    
    data - - the vertex data to match
    
    compare - - the comparator to perform the match
    
    Returns:
    
    the first vertex with a matching data, null if no matches are found
  - findCycles
```
public Grafo.Edge<T>[] findCycles()
```
    Search the graph for cycles. In order to detect cycles, we use a modified depth first search called a colored DFS. All nodes are initially marked white. When a node is encountered, it is marked grey, and when its descendants are completely visited, it is marked black. If a grey node is ever encountered, then there is a cycle.
    
    Returns:
    
    the edges that form cycles in the graph. The array will be empty if there are no cycles.
  - visit
```
private void visit(Grafo.Vertex<T> v,
                   java.util.ArrayList<Grafo.Edge<T>> cycleEdges)
```
  - toString
```
public java.lang.String toString()
```
    Overrides:
    
    toString in class java.lang.Object

Class Grafo.Dirigido<T>

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

VISIT_COLOR_WHITE

VISIT_COLOR_GREY

VISIT_COLOR_BLACK

verticies

edges

rootVertex

Constructor Detail

Dirigido

Method Detail

isEmpty

addVertex

size

getRootVertex

setRootVertex

getVertex

getVerticies

addEdge

insertBiEdge

getEdges

removeVertex

removeEdge

clearMark

clearEdges

depthFirstSearch

breadthFirstSearch

breadthFirstSearch

dfsSpanningTree

findVertexByName

findVertexByData

findCycles

visit

toString