graph
An efficient dynamic graph implementation which supports concurrent reading and writing.
A directed graph where nodes are identified by Int ids.
A directed graph where nodes are identified by Int ids. Implementations may or may not allow multiple copies of the same edge (see their documentation). If given an invalid node id, methods call the defaultNeighbors method, which by default throws a NoSuchElementException, but this can be overridden, for example to assume that non-existant nodes simply have no neighbors.
Wraps a sequence of directed graphs to create a view of the union of their nodes and edges.
Wraps a sequence of directed graphs to create a view of the union of their nodes and edges. Graph mutations are not supported through this view, but if underlying graphs change, this view will reflect the changes.
Wraps a directed graph and a dynamic directed graph to create a dynamic graph with the union of their nodes and edges.
Wraps a directed graph and a dynamic directed graph to create a dynamic graph with the union of their nodes and edges. When edge are added, they are added to the underlying dynamic graph. Edge deletion is not supported.
Given a graph, returns an object which simply forwards all method calls to the given graph.
Given a graph, returns an object which simply forwards all method calls to the given graph. This allows classes like TransposedGraphView to only override the methods they need to override.
A graph which stores edge data in a memory mapped file.
A graph which stores edge data in a memory mapped file. There is no object overhead per node: the memory used for with both in-neighbor and out-neighbor access is 8 bytes per edge and 24 bytes per node. Loading is very fast because no parsing of text is required. Loading time is exactly the time it takes the operating system to page data from disk into memory. Nodes are numbered sequentially from 0 to maxNodeId, and when a node id greater than maxNodeId is added, empty nodes are created as needed (i.e. nodeCount == maxNodeId + 1).
If given an empty file, this class creates a new empty graph which will store new nodes and edges in that file. If a MemMappedDynamicDirectedGraph is later created from the same file, it will contain the added nodes and edges. Graphs can also converted to dynamic binary format using MemMappedDynamicDirectedGraphConverter, then loaded using this class.
Concurrent reading threads are safe, but concurrent reading and writing is not currently supported.
If parameter syncAllWrites is true, all writes are immediately written to disk during each addEdges call. If syncAllWrites is set to false, write performance will improve, but the graph may be in an inconsistent state if the OS crashes or the machine loses power.
The binary format is currently subject to change.
A graph which stores the neighbors of each node in only one direction.
A graph which stores the neighbors of each node in only one direction. As a result of a call to addEdge(u, v), neighbors(u) will contain v, but neighbors(v) won't contain u.
Parameter dataPointerPointer is a pointer to a Long value in allocator.data which this class uses to store the pointer to its data. If initializeNewGraph is true, it ignores the current value at dataPointerPointer and sets it to a new allocation; else it reads the data at dataPointerPointer to open an existing graph.
Currently does not keep track of which nodes exist, but assumes all nodes between 0 and maxNodeId exist.
Supports up to 2**32 nodes by using Integer.toUnsignedLong to interpret negative node ids as positive integers.
A graph which reads edge data from a memory mapped file.
A graph which reads edge data from a memory mapped file. There is no object overhead per node: the memory used for with both in-neighbor and out-neighbor access is 8 bytes per edge and 8 bytes per node. Loading is very fast because no parsing of text is required. Loading time is exactly the time it takes the operating system to page data from disk into memory. Nodes are numbered sequentially from 0 to nodeCount - 1 and must be a range of this form (i.e. nodeCount == maxNodeId + 1).
Graphs are converted to this format using MemoryMappedDirectedGraphConverter, then loaded using this class. When transforming a graph where nodeCount <= maxNodeId to this format, new nodes with no neighbors will be implicitly created. The binary format is currently subject to change.
The convert method converts a graph from a text file of unsorted edges "<id1><whitespace><id2>" to a binary file which can be efficiently read using MemMappedDynamicDirectedGraph.
The convert method converts a graph from a text file of unsorted edges "<id1><whitespace><id2>" to a binary file which can be efficiently read using MemMappedDynamicDirectedGraph. This can also be run from the command line; for example: sbt assembly printf "1 2\n3 4\n1 3" > input_graph.txt java -cp target/scala-2.11/tempest<current_version>.jar \ co.teapot.tempest.graph.MemMappedDynamicDirectedGraphConverter input_graph.txt output_graph.dat
Then in scala code, MemMappedDynamicDirectedGraph("output_graph.dat") will efficiently read the graph and allow for further nodes and edges to be added.
The convert method converts a graph from a text file of unsorted edges to a binary file which can be efficiently read using MemoryMappedDirectedGraph.
The convert method converts a graph from a text file of unsorted edges to a binary file which can be efficiently read using MemoryMappedDirectedGraph. This can also be run from the command line; for example: sbt assembly printf "1 2\n3 4\n1 3" > input_graph.txt java -Xmx7g -cp target/scala-2.11/bidirectional-random-walk-assembly-1.0.jar\ co.teapot.tempest.graph.MemoryMappedDirectedGraphConverter input_graph.txt output_graph.dat
Then in scala code, MemoryMappedDirectedGraph("output_graph.dat") will efficiently read the graph.
An efficient dynamic graph implementation which supports concurrent reading and writing. Locks are only used by writing threads. Nodes are stored in a ConcurrentHashMap. Multi-edges are allowed (multiple copies of an edge may exist in the graph). Node count and edge count are both available.