86 lines
2.1 KiB
Java
86 lines
2.1 KiB
Java
import java.util.*;
|
|
|
|
/**
|
|
* The DirectedMultiGraph class is a structure to store a non-weighted
|
|
* graph of nodes named 0 through N-1.
|
|
* The implementation uses an adjacency-lists representation.
|
|
* @author Diogo Peralta Cordeiro <diogo@fc.up.pt>
|
|
*/
|
|
public class
|
|
DirectedMultiGraph
|
|
{
|
|
private final List<LinkedList<Integer>> edges;
|
|
public final int[] out_degree, in_degree;
|
|
public int n_nodes, n_edges; // N, #Edges, respectively
|
|
|
|
// O(n) to construct the structure
|
|
public
|
|
DirectedMultiGraph (int n_nodes)
|
|
{
|
|
this.n_nodes = n_nodes;
|
|
this.n_edges = 0;
|
|
this.edges = new ArrayList<>(n_nodes);
|
|
this.out_degree = new int[n_nodes];
|
|
this.in_degree = new int[n_nodes];
|
|
for (int i = 0; i < n_nodes; ++i)
|
|
{
|
|
this.edges.add(i, new LinkedList<>());
|
|
}
|
|
}
|
|
|
|
// O(1) to get the adjacency-list for a node
|
|
public LinkedList<Integer>
|
|
edges (int u)
|
|
{
|
|
return this.edges.get(u);
|
|
}
|
|
|
|
// O(1) to get the first adjacency of a node
|
|
public int
|
|
first_edge (int u)
|
|
{
|
|
return this.edges.get(u).getFirst();
|
|
}
|
|
|
|
// O(1) to add an adjacency
|
|
public final void
|
|
link_first (int u, int w)
|
|
{
|
|
// If we don't want a Multi-graph and can't avoid
|
|
// duplicate links from the outside, uncomment the following
|
|
// line
|
|
//if (node_links(u).contains(w)) return;
|
|
this.edges(u).addFirst(w);
|
|
++this.out_degree[u];
|
|
++this.in_degree[w];
|
|
++this.n_edges;
|
|
}
|
|
|
|
// O(1) to remove an adjacency
|
|
public void
|
|
unlink_first (int u)
|
|
{
|
|
try
|
|
{
|
|
int w = this.edges(u).removeFirst();
|
|
--this.out_degree[u];
|
|
--this.in_degree[w];
|
|
--this.n_edges;
|
|
}
|
|
catch (NoSuchElementException e)
|
|
{
|
|
// void.
|
|
}
|
|
}
|
|
|
|
// Convenience: In case the requester needs to hold such type of information about the nodes
|
|
public boolean[] seen;
|
|
public
|
|
DirectedMultiGraph (int n_nodes, boolean have_seen)
|
|
{
|
|
this(n_nodes);
|
|
if (have_seen)
|
|
seen = new boolean[n_nodes];
|
|
}
|
|
}
|