|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectit.unimi.dsi.webgraph.ArrayListMutableGraph
public class ArrayListMutableGraph
A very simple mutable graph class based on IntArrayList
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)
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 | |
---|---|
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 to immutableView() . |
protected long |
m
Current number of arcs. |
protected int |
modificationCount
The current modification count. |
protected int |
n
Current number of nodes. |
protected IntArrayList[] |
successors
Current list of successor lists. |
Constructor Summary | |
---|---|
ArrayListMutableGraph()
Creates a new empty mutable graph. |
|
ArrayListMutableGraph(ImmutableGraph g)
Creates a new mutable graph copying a given immutable 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. |
Method Summary | |
---|---|
void |
addArc(int x,
int y)
Adds the given arc. |
void |
addNodes(int numNewNodes)
Adds the given number of nodes, numbering them from numNodes() onwards. |
protected void |
ensureNode(int x)
Guarantees that a node index is valid. |
boolean |
equals(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)
|
IntIterator |
successors(int x)
|
String |
toString()
|
Methods inherited from class java.lang.Object |
---|
clone, finalize, getClass, notify, notifyAll, wait, wait, wait |
Field Detail |
---|
protected int n
protected long m
protected IntArrayList[] successors
n
.
protected it.unimi.dsi.webgraph.ArrayListMutableGraph.ImmutableView immutableView
protected int modificationCount
protected int lastModificationCount
immutableView()
.
Constructor Detail |
---|
public ArrayListMutableGraph()
public ArrayListMutableGraph(int numNodes)
numNodes
- the number of nodes in the graph.public ArrayListMutableGraph(int numNodes, int[][] arc)
numNodes
- the number of nodes in the graph.arc
- an array of arrays of length 2, specifying the arcs; no sanity checks are performed..public ArrayListMutableGraph(ImmutableGraph g)
This method will not invoke ImmutableGraph.numNodes()
, but rather just create a NodeIterator
and exhaust it.
g
- an immutable graph.public ArrayListMutableGraph(int numNodes, Transform.ArcFilter arcFilter)
numNodes
- the number of nodes in the graph.arcFilter
- an arc filter which will specify which arcs go into the graph.Method Detail |
---|
protected void ensureNode(int x)
x
- a node index.public static ArrayListMutableGraph newDirectedCycle(int numNodes)
numNodes
- the number of nodes in the cycle.public static ArrayListMutableGraph newBidirectionalCycle(int numNodes)
numNodes
- the number of nodes in the cycle.public static ArrayListMutableGraph newCompleteGraph(int numNodes, boolean loops)
numNodes
- the number of nodes in the graph.loops
- true if you want loops, too.public static ArrayListMutableGraph newCompleteBinaryIntree(int height)
height
- the height of the tree (0 for the root only).public static ArrayListMutableGraph newCompleteBinaryOuttree(int height)
height
- the height of the tree (0 for the root only).public ImmutableGraph immutableView()
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.
public int numNodes()
public int outdegree(int x)
public long numArcs()
public int[] successorArray(int x)
public IntIterator successors(int x)
public void addNodes(int numNewNodes)
numNodes()
onwards. The new nodes have no successors.
numNewNodes
- the number of new nodes.public void removeNode(int x)
x
- the node to be removed.public void addArc(int x, int y)
x
- the start of the arc.y
- the end of the arc.public void removeArc(int x, int y)
x
- the start of the arc.y
- the end of the arc.public boolean equals(Object o)
equals
in class Object
o
.public int hashCode()
hashCode
in class Object
public String toString()
toString
in class Object
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |