[Networkit] Major update: Directed graphs

Christian Staudt christian.staudt at kit.edu
Tue Jun 17 13:15:07 CEST 2014


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")

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20140617/e44558de/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/20140617/e44558de/attachment.sig>


More information about the NetworKit mailing list