public class AdjacencyListGraph
extends java.lang.Object
Modifier and Type | Field and Description |
---|---|
java.util.HashMap<Edge,java.lang.Integer> |
edges
the edges of the graph, stored in a hash map as pairs of nodes
|
java.util.ArrayList<Node> |
neighbors
for each node, store the list of neighbors
|
Constructor and Description |
---|
AdjacencyListGraph()
Initialize an empty graph
|
Modifier and Type | Method and Description |
---|---|
void |
addEdge(Node a,
Node b)
Add an edge between two nodes
|
void |
addNode(Node v)
Add a new node to the graph.
|
boolean |
adjacent(Node a,
Node b)
Check whether two nodes are adjacent (slow implementation, without hash maps)
|
int |
degree(Node v)
Return the degree of a node
|
java.util.List<Node> |
findConnectedComponent(Node v)
Compute and return the connected component containing the vertex v
It performs a DFS visit of the graph starting from vertex v
|
int |
getEdgeIndex(Node a,
Node b)
Return the index of the edge having extremities (a, b) if any.
|
int[] |
getIndices()
Return an array storing all vertex indices, according to the order of vertices
|
java.util.Collection<Node> |
getNeighbors(Node v) |
Node |
getNode(int index)
Return the node given its index (between [0..n-1])
|
java.lang.String |
info()
Return a string containing informations and parameters of the graph
|
boolean |
isConnected()
Check whether the graph is connected
Remark: the graph is assumed to be undirected
|
int |
maxVertexIndex()
Compute the maximum vertex index of the graph (a non negative number)
Remark: vertices are allowed to have indices between 0..infty
This is required when graphs are dynamic: vertices can be removed
|
int |
minVertexIndex()
Compute the minimum vertex index of the graph (a non negative number)
Remark: vertices are allowed to have indices between 0..infty
This is required when graphs are dynamic: vertices can be removed
|
void |
removeEdge(Node a,
Node b)
Remove the edge between two nodes
|
void |
removeNode(Node v) |
int |
sizeEdges()
Return the number of arcs
Remark: arcs are not counted twice
|
int |
sizeVertices()
Return the number of nodes
|
public java.util.ArrayList<Node> neighbors
public java.util.HashMap<Edge,java.lang.Integer> edges
public void addNode(Node v)
public int getEdgeIndex(Node a, Node b)
public Node getNode(int index)
public void removeNode(Node v)
public boolean adjacent(Node a, Node b)
public int degree(Node v)
public int sizeVertices()
public int sizeEdges()
public int[] getIndices()
public java.util.List<Node> findConnectedComponent(Node v)
Remark: the graph is assumed to be undirected
v
- the starting nodepublic boolean isConnected()
public int minVertexIndex()
public int maxVertexIndex()
public java.lang.String info()