[Networkit] Major update: Directed graphs

Christian Staudt christian.staudt at kit.edu
Fri Jun 20 13:44:35 CEST 2014

The dgraph branch has been merged into the Dev branch. If no problems appear, NetworKit 3.2 will support directed graphs too. Thanks to Klara and Marvin for adding this feature.


Am 17.06.2014 um 13:15 schrieb Christian Staudt <christian.staudt at kit.edu>:

> Dear NetworKit developers,
> Klara Reichard and Marvin Ritter have contributed a major new feature, namely support for directed graphs. The NetworKit.Graph class can now represent a directed graph if the appropriate parameter is passed at construction. The update also comes with various cleanups and improvements to the graph data structure (see the changelog below).
> The update is currently in the separate branch:
> 	dgraph
> It has passed my tests so far, but to be sure I’d like to conduct a short „beta test“: 
> 	If you have time, please compile, test and review the branch.
> I would like to merge this into the Dev branch very soon if possible. If all goes well, this will be included in the upcoming release NetworKit 3.2. 
> Best,
> Chris
> DGraph Changelog
> moved Graph typedefs (count, node, edgeweight, ...) to Globals.h (there were some redundant typedefs and Globals.h the right place to define types used by the whole framework)
> cleanup up includes for many files (several files depended on the includes made in Graph.h which are no longer required there), also moving includes to the cpp files when possible increases the compile time
> added unsigned to many integere literals in test case to reduce the number of warnings during compilation
> little stuff (e.g. PageRank now takes a _const_ Graph& as input)
> added isDirected() and the constructor parameter directed to the Python interface
> added CommunityDetectiongBenchmark
> removed the following methods from Graph interface
> node mergeEdge() (moved to CNM)
> minDegree(), argminDegree(), maxDegree(), argmaxDegree() (never used, similar methods exist in GraphProperties)
> void forNodes(C condition, L handle) (because it's implementation was identical with forNodesWhile)
> void breadthFirstNodesFrom(node r, std::vector<int>& marked, L handle)
> void breadthFirstEdgesFrom(node r, L handle)
> forEdgesOfInDegreeIncreasingOrder
> all non-const versions of the iterator methods
> added the following methods to Graph interface
> Graph(const Graph& G, bool weighted, bool directed) (copy constructor that lets you change weighted and directed for the copy)
> std::string typ()
> void shrinkToFit()
> bool isDirected()
> std::vector< std::pair<node, node> > randomEdges(count nr)
> void BFSEdgesfrom(node r, L handle)
> void DFSEdgesfrom(node r, L handle)
> count degreeIn(node u)
> count degreeOut(node u)
> void forInNeighborsOf(node u, L handle)
> void forWeightedInNeighborsOf(node u, L handle)
> void forInEdgesOf(node u, L handle)
> void forWeightedInEdgesOf(node u, L handle)
> (for undirected graph in in-methods to the same as their normal versions and degreeOut as just an alias for degree)
> call shrinkToFit in graph generators
> call shrinkToFit in graph readers
> wrote a benckmark to show the benefit of shrinkToFit (20-30% less memory and very little time compared to graph generation/reading)
> go back to commit a7ec412c276f, Graph had a method getApproximatedMemoryUsage() and in src/cpp/graph/test was GraphMemoryBenchmark testing both generators and readers
> complete rewrite of GraphGTest with much more test cases and testing everything for all 4 types (weighted/directed combinations)
> added a python script for continous testing (use: "./scripts/continuous_scripts.py GraphGTest")
> <signature.asc><ATT00001.c>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20140620/1ab7c43c/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20140620/1ab7c43c/attachment.sig>

More information about the NetworKit mailing list