Class ArrayListMutableGraph
IntArrayLists.
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) and addArc(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
FieldsModifier and TypeFieldDescriptionprotected it.unimi.dsi.webgraph.ArrayListMutableGraph.ImmutableViewA cached copy of the immutable view, if it has ever been requested.protected intThe modification count at the last call toimmutableView().protected longCurrent number of arcs.protected intThe current modification count.protected intCurrent number of nodes.protected it.unimi.dsi.fastutil.ints.IntArrayList[]Current list of successor lists. -
Constructor Summary
ConstructorsConstructorDescriptionCreates 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.Creates a new mutable graph copying a given immutable graph. -
Method Summary
Modifier and TypeMethodDescriptionvoidaddArc(int x, int y) Adds the given arc.voidaddNodes(int numNewNodes) Adds the given number of nodes, numbering them fromnumNodes()onwards.protected voidensureNode(int x) Guarantees that a node index is valid.booleanCompare this mutable graph to another object.inthashCode()Returns a hash code for this mutable graph.Returns an immutable view of this mutable graph.static ArrayListMutableGraphnewBidirectionalCycle(int numNodes) Returns a new mutable graph containing a bidirectional cycle.static ArrayListMutableGraphnewCompleteBinaryIntree(int height) Returns a new mutable graph containing a complete binary in-tree of given height.static ArrayListMutableGraphnewCompleteBinaryOuttree(int height) Returns a new mutable graph containing a complete binary out-tree of given height.static ArrayListMutableGraphnewCompleteGraph(int numNodes, boolean loops) Returns a new mutable graph containing a complete graph.static ArrayListMutableGraphnewDirectedCycle(int numNodes) Returns a new mutable graph containing a directed cycle.longnumArcs()intnumNodes()intoutdegree(int x) voidremoveArc(int x, int y) Removes the given arc.voidremoveNode(int x) Removes the given node.int[]successorArray(int x) it.unimi.dsi.fastutil.ints.IntIteratorsuccessors(int x) toString()
-
Field Details
-
n
protected int nCurrent number of nodes. -
m
protected long mCurrent number of arcs. -
successors
protected it.unimi.dsi.fastutil.ints.IntArrayList[] successorsCurrent list of successor lists. The backing array might be longer thann. -
immutableView
protected it.unimi.dsi.webgraph.ArrayListMutableGraph.ImmutableView immutableViewA cached copy of the immutable view, if it has ever been requested. -
modificationCount
protected int modificationCountThe current modification count. -
lastModificationCount
protected int lastModificationCountThe modification count at the last call toimmutableView().
-
-
Constructor Details
-
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
Creates a new mutable graph copying a given immutable graph.This method will not invoke
ImmutableGraph.numNodes(), but rather just create aNodeIteratorand exhaust it.- Parameters:
g- an immutable graph.
-
ArrayListMutableGraph
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 Details
-
ensureNode
protected void ensureNode(int x) Guarantees that a node index is valid.- Parameters:
x- a node index.
-
newDirectedCycle
Returns a new mutable graph containing a directed cycle.- Parameters:
numNodes- the number of nodes in the cycle.
-
newBidirectionalCycle
Returns a new mutable graph containing a bidirectional cycle.- Parameters:
numNodes- the number of nodes in the cycle.
-
newCompleteGraph
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
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
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
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
Compare this mutable graph to another object. -
hashCode
public int hashCode()Returns a hash code for this mutable graph. -
toString
-