Graph

java.lang.Object
- graph.elements.Graph<V,E>

Type Parameters:

V - The vertex type

E - The edge type

Direct Known Subclasses:

AbstractTree, BCTree, Block, DFSTree, GraphCopy, PQTree, Skeleton, SplitComponent, STDualGraph
```
public class Graph<V extends Vertex,E extends Edge<V>>
extends java.lang.Object
```
/** A graph consisting of a set of vertices of type V and a set of edges of type E.

Author:

Renata

Constructor Summary

Constructors
Constructor and Description
`Graph()` Creates a graph by creating empty lists of edges, vertices and other properties By default, the graph is undirected
`Graph(boolean directed)` Creates a directed or undirected graph, depending on the provided parameter value
`Graph(java.util.List<V> vertices, java.util.List<E> edges)`

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`addEdge(E... edge)`
`void`	`addVertex(V... vert)`
`void`	`addVertex(V v)` Add one vertex to the graph
`void`	`addVertexBeginning(V v)` Adds vertex as to the graph before any other vertex
`int[][]`	`adjacencyMatrix()` Calculates the adjacency matrix of the graph
`java.util.List<E>`	`adjacentEdges(V v)`
`java.util.List<V>`	`adjacentVertices(V v)` All vertices adjacent to the given one
`java.util.LinkedList<E>`	`allEdges(V v)` All edges leaving or entering the given vertex
`E`	`edgeBetween(V v1, V v2)` Checks if there is an edge between the two given graph vertices and return is it if exists
`java.util.List<E>`	`edgeesBetween(V v1, V v2)` Returns all edges between vertices v1 and v2
`java.util.List<E>`	`edgesBetween(java.util.List<V> vertices)` Finds all edges between certain vertices
`boolean`	`equals(java.lang.Object obj)`
`java.util.Map<V,java.util.List<E>>`	`getAdjacentLists()`
`java.util.List<E>`	`getAllSelfLoopEdges()` All edges which connect one vertex to itself - loops
`java.util.List<V>`	`getAllSinks()` Finds all sinks in the graph
`java.util.List<V>`	`getAllSources()` Finds all sources in the graph
`java.util.List<E>`	`getEdges()`
`java.util.List<V>`	`getTreeLeaves(V root)`
`V`	`getVertexByContent(java.lang.Object content)` Return a vertex with the provided content
`java.util.List<V>`	`getVertices()`
`int`	`graphMaxDegree()` Max vertex degree
`boolean`	`hasEdge(V v1, V v2)` Checks if vertices v1 and v2 are connected i.e.
`int`	`hashCode()`
`boolean`	`hasSelfLoopEdges()` Checks if graph has loops
`boolean`	`hasVertex(V v)` Checks if the graph contains a certain vertex
`int`	`inDegree(V v)` In degree of the given vertex
`java.util.List<E>`	`inEdges(V v)` All edges entering v
`boolean`	`isBiconnected()` Checks if a graph is biconnected.
`boolean`	`isConnected()` Checks is graph is connected
`boolean`	`isConnected(java.util.List<V> excluding)` Checks is graph is connected presumed that certain vertices are removed
`boolean`	`isCyclic()` Check if the graph is cyclic
`boolean`	`isDirected()`
`boolean`	`isRing()` Check if the graph is a ring
`boolean`	`isSimple()` Checks if graph is simple
`boolean`	`isSink(V v)` Checks if vertex is a sink (vertex with no outgoing edges)
`boolean`	`isSource(V v)` Checks if vertex is a source (vertex with no incoming edges)
`boolean`	`isTree()` Check if the graph is a tree
`java.util.List<Graph<V,E>>`	`listBiconnectedComponents()` Finds all biconnected components of the graph
`java.util.List<V>`	`listCutVertices()` Finds all cut vertices of a graph
`java.util.List<java.util.List<E>>`	`listMultiEdges()` Finds all multiedges of the graph
`int`	`outDegree(V v)` Out degree of the given node
`java.util.List<E>`	`outEdges(V v)` All edges leaving v
`void`	`printAdjacencyMatrix()` Prints adjacency matrix
`void`	`removeEdge(E e)` Removes an edge from the graph and updates all relevants structures
`void`	`removeVertex(V v)` Removes a vertex from the graph, thus updating all relevant structures and also removing the edges it was a part of
`void`	`setDirected(boolean directed)`
`void`	`setEdges(java.util.List<E> edges)`
`void`	`setVertices(java.util.List<V> vertices)`
`Graph<V,E>`	`subgraph(java.util.List<V> subgraphVertices)` Creates a subgraph of the graph containing the given vertices
`java.lang.String`	`toString()`
`int`	`vertexDegree(V v)` Number of edges entering or leaving v

Methods inherited from class java.lang.Object
getClass, notify, notifyAll, wait, wait, wait

- Constructor Detail
  - Graph
```
public Graph()
```
    Creates a graph by creating empty lists of edges, vertices and other properties By default, the graph is undirected
  - Graph
```
public Graph(java.util.List<V> vertices,
             java.util.List<E> edges)
```
  - Graph
```
public Graph(boolean directed)
```
    Creates a directed or undirected graph, depending on the provided parameter value
    
    Parameters:
    
    directed - true if the graph should be directed, false otherwise
- Method Detail
  - hasVertex
```
public boolean hasVertex(V v)
```
    Checks if the graph contains a certain vertex
    
    Parameters:
    
    v - Vertex
    
    Returns:
    
    true if the graph contains v, false otherwise
  - addVertex
```
public void addVertex(V... vert)
```
  - addVertex
```
public void addVertex(V v)
```
    Add one vertex to the graph
    
    Parameters:
    
    v - Vertex to add
  - addVertexBeginning
```
public void addVertexBeginning(V v)
```
    Adds vertex as to the graph before any other vertex
    
    Parameters:
    
    v - Vertex to add
  - removeVertex
```
public void removeVertex(V v)
```
    Removes a vertex from the graph, thus updating all relevant structures and also removing the edges it was a part of
    
    Parameters:
    
    v - Vertex to remove
  - addEdge
```
public void addEdge(E... edge)
```
  - hasEdge
```
public boolean hasEdge(V v1,
                       V v2)
```
    Checks if vertices v1 and v2 are connected i.e. if there is an edge between them
    
    Parameters:
    
    v1 - Source vertex
    
    v2 - Destination vertex
    
    Returns:
    
    true if there is and edge between v1 and v2, otherwise false
  - edgeesBetween
```
public java.util.List<E> edgeesBetween(V v1,
                                       V v2)
```
    Returns all edges between vertices v1 and v2
    
    Parameters:
    
    v1 - Source vertex
    
    v2 - Destination vertex
    
    Returns:
    
    All edges between v1 and v2
  - edgeBetween
```
public E edgeBetween(V v1,
                     V v2)
```
    Checks if there is an edge between the two given graph vertices and return is it if exists
    
    Parameters:
    
    v1 - The first vertex
    
    v2 - The second vertex
    
    Returns:
    
    Edge between v1 and v2 if it exists, @{code null} otherwise
  - removeEdge
```
public void removeEdge(E e)
```
    Removes an edge from the graph and updates all relevants structures
    
    Parameters:
    
    e - Edge to be removed
  - adjacentEdges
```
public java.util.List<E> adjacentEdges(V v)
```
  - outEdges
```
public java.util.List<E> outEdges(V v)
```
    All edges leaving v
    
    Parameters:
    
    v - Vertex
    
    Returns:
    
    A list of all edges leaving graph vertex v
  - adjacentVertices
```
public java.util.List<V> adjacentVertices(V v)
```
    All vertices adjacent to the given one
    
    Parameters:
    
    v - Vertex
    
    Returns:
    
    A list of all vertices adjacent to graph vertex v
  - outDegree
```
public int outDegree(V v)
```
    Out degree of the given node
    
    Parameters:
    
    v - Vertex
    
    Returns:
    
    Out degree of v
  - inEdges
```
public java.util.List<E> inEdges(V v)
```
    All edges entering v
    
    Parameters:
    
    v - Vertex
    
    Returns:
    
    A list of all edges entering vertex v
  - inDegree
```
public int inDegree(V v)
```
    In degree of the given vertex
    
    Parameters:
    
    v - Vertex
    
    Returns:
    
    In degree of vertex v
  - isSource
```
public boolean isSource(V v)
```
    Checks if vertex is a source (vertex with no incoming edges)
    
    Parameters:
    
    v - Vertex
    
    Returns:
    
    true if vertex v is a source, false otherwise
  - isSink
```
public boolean isSink(V v)
```
    Checks if vertex is a sink (vertex with no outgoing edges)
    
    Parameters:
    
    v - Vertex
    
    Returns:
    
    true if vertex v is a sink, false otherwise
  - allEdges
```
public java.util.LinkedList<E> allEdges(V v)
```
    All edges leaving or entering the given vertex
    
    Parameters:
    
    v - Vertex
    
    Returns:
    
    A list of all edges leaving or entering v
  - edgesBetween
```
public java.util.List<E> edgesBetween(java.util.List<V> vertices)
```
    Finds all edges between certain vertices
    
    Parameters:
    
    vertices - A list of vertices
    
    Returns:
    
    A list of edges between vertices belonging to the vertices list
  - getAllSelfLoopEdges
```
public java.util.List<E> getAllSelfLoopEdges()
```
    All edges which connect one vertex to itself - loops
    
    Returns:
    
    A list of loops
  - hasSelfLoopEdges
```
public boolean hasSelfLoopEdges()
```
    Checks if graph has loops
    
    Returns:
    
    true if the graph has loops, false otherwise
  - isSimple
```
public boolean isSimple()
```
    Checks if graph is simple
    
    Returns:
    
    true if the graph is simple, false otherwise
  - vertexDegree
```
public int vertexDegree(V v)
```
    Number of edges entering or leaving v
    
    Parameters:
    
    v - Vertex
    
    Returns:
    
    Vertex degree of v
  - graphMaxDegree
```
public int graphMaxDegree()
```
    Max vertex degree
    
    Returns:
    
    Maximum degree of any of the graph vertices
  - isConnected
```
public boolean isConnected()
```
    Checks is graph is connected
    
    Returns:
    
    true if the graph is connected, false otherwise
  - isTree
```
public boolean isTree()
```
    Check if the graph is a tree
    
    Returns:
    
    true if the graph is a tree, false otherwise
  - getTreeLeaves
```
public java.util.List<V> getTreeLeaves(V root)
```
    Parameters:
    
    root - Root of the tree
    
    Returns:
    
    list of vertices which are tree leaves (presuming that the graph is a tree)
  - isConnected
```
public boolean isConnected(java.util.List<V> excluding)
```
    Checks is graph is connected presumed that certain vertices are removed
    
    Parameters:
    
    excluding - Vertices without whom the graph should still be connected
    
    Returns:
    
    true if the graph without vertices belonging to excluding is connected, false otherwise
  - isCyclic
```
public boolean isCyclic()
```
    Check if the graph is cyclic
    
    Returns:
    
    true if the graph is a tree, false otherwise
  - getAllSinks
```
public java.util.List<V> getAllSinks()
```
    Finds all sinks in the graph
    
    Returns:
    
    A list of sinks
  - getAllSources
```
public java.util.List<V> getAllSources()
```
    Finds all sources in the graph
    
    Returns:
    
    A list of sources
  - listMultiEdges
```
public java.util.List<java.util.List<E>> listMultiEdges()
```
    Finds all multiedges of the graph
    
    Returns:
    
    All multiedges. Group so that all edges between the same two vertices are in a separate list, which is then added to the another list which is returned
  - isRing
```
public boolean isRing()
```
    Check if the graph is a ring
    
    Returns:
    
    true if the graph is a tree, false otherwise
  - isBiconnected
```
public boolean isBiconnected()
```
    Checks if a graph is biconnected. A graph is biconnected if and only if any vertex is deleted, the graph remains connected.
    
    Returns:
    
    true if graph is biconnected, otherwise false
  - listCutVertices
```
public java.util.List<V> listCutVertices()
```
    Finds all cut vertices of a graph
    
    Returns:
    
    A list of graph's cut vertices
  - listBiconnectedComponents
```
public java.util.List<Graph<V,E>> listBiconnectedComponents()
```
    Finds all biconnected components of the graph
    
    Returns:
    
    A list of graph's biconnected components
  - subgraph
```
public Graph<V,E> subgraph(java.util.List<V> subgraphVertices)
```
    Creates a subgraph of the graph containing the given vertices
    
    Parameters:
    
    subgraphVertices - Vertices that should be in the subgraph
    
    Returns:
    
    Subgraph containing vertices @{code subgraphVertices}
  - adjacencyMatrix
```
public int[][] adjacencyMatrix()
```
    Calculates the adjacency matrix of the graph
    
    Returns:
    
    Adjacency matrix
  - printAdjacencyMatrix
```
public void printAdjacencyMatrix()
```
    Prints adjacency matrix
  - getVertexByContent
```
public V getVertexByContent(java.lang.Object content)
```
    Return a vertex with the provided content
    
    Parameters:
    
    content - Searched content
    
    Returns:
    
    A vertex whose content is @{code content}
  - getVertices
```
public java.util.List<V> getVertices()
```
    Returns:
    
    Graph's vertices
  - setVertices
```
public void setVertices(java.util.List<V> vertices)
```
    Parameters:
    
    vertices - Vertices to set
  - getEdges
```
public java.util.List<E> getEdges()
```
    Returns:
    
    Graph's edges
  - setEdges
```
public void setEdges(java.util.List<E> edges)
```
    Parameters:
    
    edges - Edges to set
  - isDirected
```
public boolean isDirected()
```
    Returns:
    
    true if graph is directed, false otherwise
  - setDirected
```
public void setDirected(boolean directed)
```
    Parameters:
    
    directed - Value of directed property to set
  - toString
```
public java.lang.String toString()
```
    Overrides:
    
    toString in class java.lang.Object
  - hashCode
```
public int hashCode()
```
    Overrides:
    
    hashCode in class java.lang.Object
  - equals
```
public boolean equals(java.lang.Object obj)
```
    Overrides:
    
    equals in class java.lang.Object
  - getAdjacentLists
```
public java.util.Map<V,java.util.List<E>> getAdjacentLists()
```
    Returns:
    
    the adjacentLists

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

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

Graph

Graph

Graph

Method Detail

hasVertex

addVertex

addVertex

addVertexBeginning

removeVertex

addEdge

hasEdge

edgeesBetween

edgeBetween

removeEdge

adjacentEdges

outEdges

adjacentVertices

outDegree

inEdges

inDegree

isSource

isSink

allEdges

edgesBetween

getAllSelfLoopEdges

hasSelfLoopEdges

isSimple

vertexDegree

graphMaxDegree

isConnected

isTree

getTreeLeaves

isConnected

isCyclic

getAllSinks

getAllSources

listMultiEdges

isRing

isBiconnected

listCutVertices

listBiconnectedComponents

subgraph

adjacencyMatrix

printAdjacencyMatrix

getVertexByContent

getVertices

setVertices

getEdges

setEdges

isDirected

setDirected

toString

hashCode

equals

getAdjacentLists