Class ArrayListMutableGraph
- java.lang.Object
-
- it.unimi.dsi.webgraph.ArrayListMutableGraph
-
public class ArrayListMutableGraph extends java.lang.Object
A very simple mutable graph class based onIntArrayList
s.When creating examples for test cases or everyday usage, this class offers practical constructors. For instance, a 3-cycle is easily built as
new ArrayListMutableGraph(3, new int[][] { { 0, 1 }, { 1, 2 }, { 2, 0 } })
Moreover, methods like
addNodes(int)
andaddArc(int, int)
allow to change the graph structure after construction, and several static factory methods provides ready-made common graphs (see, e.g.,newCompleteBinaryIntree(int)
).A mutable graph is not an
ImmutableGraph
. However, it is possible to obtain an immutable view of a mutable graph. The view is valid until the exposed mutable graph is modified. A modification counter is used to cause a fail-fast behaviour in case the immutable view is used after modifications.Warning: obtaining a
NodeIterator
and using it while modifying the graph will lead to unpredictable results.
-
-
Field Summary
Fields Modifier and Type Field Description protected it.unimi.dsi.webgraph.ArrayListMutableGraph.ImmutableView
immutableView
A cached copy of the immutable view, if it has ever been requested.protected int
lastModificationCount
The modification count at the last call toimmutableView()
.protected long
m
Current number of arcs.protected int
modificationCount
The current modification count.protected int
n
Current number of nodes.protected it.unimi.dsi.fastutil.ints.IntArrayList[]
successors
Current list of successor lists.
-
Constructor Summary
Constructors Constructor Description ArrayListMutableGraph()
Creates a new empty mutable graph.ArrayListMutableGraph(int numNodes)
Creates a new disconnected mutable graph with specified number of nodes.ArrayListMutableGraph(int numNodes, int[][] arc)
Creates a new mutable graph using a given number of nodes and a given list of arcs.ArrayListMutableGraph(int numNodes, Transform.ArcFilter arcFilter)
Creates a new mutable graph using a given number of nodes and a given arc filter.ArrayListMutableGraph(ImmutableGraph g)
Creates a new mutable graph copying a given immutable graph.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
addArc(int x, int y)
Adds the given arc.void
addNodes(int numNewNodes)
Adds the given number of nodes, numbering them fromnumNodes()
onwards.protected void
ensureNode(int x)
Guarantees that a node index is valid.boolean
equals(java.lang.Object o)
Compare this mutable graph to another object.int
hashCode()
Returns a hash code for this mutable graph.ImmutableGraph
immutableView()
Returns an immutable view of this mutable graph.static ArrayListMutableGraph
newBidirectionalCycle(int numNodes)
Returns a new mutable graph containing a bidirectional cycle.static ArrayListMutableGraph
newCompleteBinaryIntree(int height)
Returns a new mutable graph containing a complete binary in-tree of given height.static ArrayListMutableGraph
newCompleteBinaryOuttree(int height)
Returns a new mutable graph containing a complete binary out-tree of given height.static ArrayListMutableGraph
newCompleteGraph(int numNodes, boolean loops)
Returns a new mutable graph containing a complete graph.static ArrayListMutableGraph
newDirectedCycle(int numNodes)
Returns a new mutable graph containing a directed cycle.long
numArcs()
int
numNodes()
int
outdegree(int x)
void
removeArc(int x, int y)
Removes the given arc.void
removeNode(int x)
Removes the given node.int[]
successorArray(int x)
it.unimi.dsi.fastutil.ints.IntIterator
successors(int x)
java.lang.String
toString()
-
-
-
Field Detail
-
n
protected int n
Current number of nodes.
-
m
protected long m
Current number of arcs.
-
successors
protected it.unimi.dsi.fastutil.ints.IntArrayList[] successors
Current list of successor lists. The backing array might be longer thann
.
-
immutableView
protected it.unimi.dsi.webgraph.ArrayListMutableGraph.ImmutableView immutableView
A cached copy of the immutable view, if it has ever been requested.
-
modificationCount
protected int modificationCount
The current modification count.
-
lastModificationCount
protected int lastModificationCount
The modification count at the last call toimmutableView()
.
-
-
Constructor Detail
-
ArrayListMutableGraph
public ArrayListMutableGraph()
Creates a new empty mutable graph.
-
ArrayListMutableGraph
public ArrayListMutableGraph(int numNodes)
Creates a new disconnected mutable graph with specified number of nodes.- Parameters:
numNodes
- the number of nodes in the graph.
-
ArrayListMutableGraph
public ArrayListMutableGraph(int numNodes, int[][] arc)
Creates a new mutable graph using a given number of nodes and a given list of arcs.- Parameters:
numNodes
- the number of nodes in the graph.arc
- an array of arrays of length 2, specifying the arcs; no sanity checks are performed..
-
ArrayListMutableGraph
public ArrayListMutableGraph(ImmutableGraph g)
Creates a new mutable graph copying a given immutable graph.This method will not invoke
ImmutableGraph.numNodes()
, but rather just create aNodeIterator
and exhaust it.- Parameters:
g
- an immutable graph.
-
ArrayListMutableGraph
public ArrayListMutableGraph(int numNodes, Transform.ArcFilter arcFilter)
Creates a new mutable graph using a given number of nodes and a given arc filter.- Parameters:
numNodes
- the number of nodes in the graph.arcFilter
- an arc filter which will specify which arcs go into the graph.
-
-
Method Detail
-
ensureNode
protected void ensureNode(int x)
Guarantees that a node index is valid.- Parameters:
x
- a node index.
-
newDirectedCycle
public static ArrayListMutableGraph newDirectedCycle(int numNodes)
Returns a new mutable graph containing a directed cycle.- Parameters:
numNodes
- the number of nodes in the cycle.
-
newBidirectionalCycle
public static ArrayListMutableGraph newBidirectionalCycle(int numNodes)
Returns a new mutable graph containing a bidirectional cycle.- Parameters:
numNodes
- the number of nodes in the cycle.
-
newCompleteGraph
public static ArrayListMutableGraph newCompleteGraph(int numNodes, boolean loops)
Returns a new mutable graph containing a complete graph.- Parameters:
numNodes
- the number of nodes in the graph.loops
- true if you want loops, too.
-
newCompleteBinaryIntree
public static ArrayListMutableGraph newCompleteBinaryIntree(int height)
Returns a new mutable graph containing a complete binary in-tree of given height. Warning: starting from version 1.7, the spurious loop at the root has been removed.- Parameters:
height
- the height of the tree (0 for the root only).
-
newCompleteBinaryOuttree
public static ArrayListMutableGraph newCompleteBinaryOuttree(int height)
Returns a new mutable graph containing a complete binary out-tree of given height. Warning: starting from version 1.7, the spurious loop at the root has been removed.- Parameters:
height
- the height of the tree (0 for the root only).
-
immutableView
public ImmutableGraph immutableView()
Returns an immutable view of this mutable graph.The view can be used until this mutable graph is modified. Attempt to use the view after modifying this mutable graph will cause a
ConcurrentModificationException
. After modification, a new call to this method will return a new immutable view.- Returns:
- an immutable view of this mutable graph.
-
numNodes
public int numNodes()
-
outdegree
public int outdegree(int x)
-
numArcs
public long numArcs()
-
successorArray
public int[] successorArray(int x)
-
successors
public it.unimi.dsi.fastutil.ints.IntIterator successors(int x)
-
addNodes
public void addNodes(int numNewNodes)
Adds the given number of nodes, numbering them fromnumNodes()
onwards. The new nodes have no successors.- Parameters:
numNewNodes
- the number of new nodes.
-
removeNode
public void removeNode(int x)
Removes the given node. All arcs incident on the node are removed, too.- Parameters:
x
- the node to be removed.
-
addArc
public void addArc(int x, int y)
Adds the given arc.- Parameters:
x
- the start of the arc.y
- the end of the arc.
-
removeArc
public void removeArc(int x, int y)
Removes the given arc.- Parameters:
x
- the start of the arc.y
- the end of the arc.
-
equals
public boolean equals(java.lang.Object o)
Compare this mutable graph to another object.- Overrides:
equals
in classjava.lang.Object
- Returns:
- true iff the given object is a mutable graph the same size, and
the successor list of every node of this graph is equal to the successor list of the corresponding node of
o
.
-
hashCode
public int hashCode()
Returns a hash code for this mutable graph.- Overrides:
hashCode
in classjava.lang.Object
- Returns:
- a hash code for this mutable graph.
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-