cl.cromer.estructuras

## Class Grafo.Dirigido<T>

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

Enclosing class:
  Grafo

    public static final class Grafo.Dirigido<T>
    extends java.lang.Object

### Field Summary

Fields
`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

### Method Summary

All Methods Instance Methods Concrete Methods
`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`