[Networkit] Read simple edgelist

Maximilian Vogel maximilian.vogel at student.kit.edu
Wed Nov 25 22:13:39 CET 2015


Hi,

I was about to mention APSP as well. Under Python it can be found under 
dynamic.APSP (for whatever reason it is placed there...). As you 
mentioned, it would be more efficient to utilize a BFS instead of 
Dijkstra for unweighted graphs.

For your application, Jerome, it depends on how many distances you are 
interested in. Currently, I suggest to use graph.BFS. Two options 
currently seem applicable:
bfs = graph.BFS(G, source, storePaths=False, storeStack=False).run() 
will run a BFS from the specified source node. Storing the number of 
paths or the stack of nodes in the order in which they are processed is 
not important for your application. With bfs.distance(target) you can 
retrieve the distance from previously specified source for any node.
bfs = graph.BFS(G, source, storePaths=False, storeStack=False, t1).run() 
will run a BFS from the specified source until the specified target node 
t1 has been reached. Depending on the target, this may reduce the 
running time for individual searches, however if you are interested in 
multiple distances from the specified source (e.g. (source, t1), 
(source, t2), (source, t3), it is not guarenteed, that these have been 
found aswell and additional searches for t2 and t3 are likely to be 
necessary.

I hope this helps.
Max


On 25.11.2015 21:39, Dominik Kiefer wrote:
> Hey,
>
> APSP
> https://algohub.iti.kit.edu/parco/NetworKit/NetworKit/files/9c37fb4c04be9e5f3b162f52ea66e9473d756a72/networkit/cpp/graph/APSP.h
> https://algohub.iti.kit.edu/parco/NetworKit/NetworKit/files/9c37fb4c04be9e5f3b162f52ea66e9473d756a72/networkit/cpp/graph/APSP.cpp
> It does exist, status of code is unknown to me. Differentiating betweend
> the unweighted/ weighted case might be advisable?! As a reference:
> https://algohub.iti.kit.edu/parco/NetworKit/NetworKit/files/9c37fb4c04be9e5f3b162f52ea66e9473d756a72/networkit/cpp/centrality/Closeness.cpp#L42
>
> Regards,
> Dominik
>
> Am 24.11.2015 um 02:20 schrieb Christian Staudt:
>> Hi Jerome,
>> you’ll get the shortest-path distances between all pairs of nodes by
>> running an instance of graph.BFS from each node and asking for them
>> through graph.BFS.getDistances. I think there’s no other
>> all-pair-shortest-path method for unweighted graphs (or is there?).
>>
>> If I understood it correctly, the rest seems like a data munging
>> problem that is somewhat outside of the scope of the networkit core.
>> Do you know the pandas library (http://pandas.pydata.org)? For working
>> with tabular data, I suggest familiarizing yourself with it.
>>
>> Best,
>> Chris
>>
>>
>> On 23 Nov 2015, at 17:55, Jérôme Deschênes <jeromedesch at gmail.com
>> <mailto:jeromedesch at gmail.com>> wrote:
>>
>>> Hi again,
>>>
>>> I have a new (not so hard) problem but I am struggling a bit with it.
>>>
>>> I have a new edgelist but this time in this form (starting at zero
>>> and with continuous numbering of nodes):
>>>
>>> 0 1
>>> 0 4
>>> 2 3
>>> 2 8
>>> ... ...
>>>
>>> I want to measure the distance between specific nodes. I have another
>>> file with the list of wanted distances:
>>>
>>> 0 15
>>> 0 172
>>> 0 23
>>> 1 55
>>> 1 74
>>> 1 198
>>> 1 534
>>> ,,, ,,,
>>>
>>> I naturally want to get the results in a file with the two columns of
>>> the nodes of the desired distances and a third column with the distances.
>>>
>>> 0 15 2
>>> 0 172 5
>>> 0 23 10
>>> 1 55 6
>>> 1 74 4
>>> 1 198 7
>>> 1 534 24
>>> ,,, ,,, ...
>>>
>>> What is the best way to do that using networkit.distance?
>>>
>>> Thank you.
>>>
>>> Jerome
>>>
>>>
>>> 2015-10-07 16:22 GMT-04:00 Jérôme Deschênes <jeromedesch at gmail.com
>>> <mailto:jeromedesch at gmail.com>>:
>>>
>>>      Thanks again Max.
>>>
>>>      Nice module.
>>>
>>>      Just wanted to update you on the fact that the csv file is
>>>      created and work as intended when imported in STATA and in SAS.
>>>      However the file itself is not perfectly formatted: single lines
>>>      of data are split among multiple lines.
>>>
>>>      On any given line, it would look like this:
>>>
>>>      old_id, cent1
>>>      ,cent2
>>>
>>>      But, as said, it doesn't matter as other programs are able to
>>>      read those csv as it.
>>>
>>>      Jerome
>>>
>>>
>>>      2015-10-02 16:01 GMT-04:00 Christian Staudt
>>>      <christian.staudt at kit.edu <mailto:christian.staudt at kit.edu>>:
>>>
>>>
>>>          On 02 Oct 2015, at 20:26, Maximilian Vogel
>>>          <maximilian.vogel at student.kit.edu
>>>          <mailto:maximilian.vogel at student.kit.edu>> wrote:
>>>
>>>>          # ...
>>>>          # if you want a header row, describing the contents
>>>>          helper.exportNodeValues("your_file.csv", mapping, results,
>>>>          ["betweenness","degree"])
>>>>          # else this is sufficient
>>>>          helper.exportNodeValues("your_file.csv", mapping, results)
>>>>
>>>>          You can also specifiy a different than the
>>>>          default delimiter=','. This should then produce the file in
>>>>          the desired format.
>>>>
>>>>          I hope this helps,
>>>>          Max
>>>          We should probably integrate your helper.py code into the
>>>          project.
>>>          Chris
>>>
>>>          _______________________________________________
>>>          NetworKit mailing list
>>>          NetworKit at ira.uni-karlsruhe.de
>>>          <mailto:NetworKit at ira.uni-karlsruhe.de>
>>>          https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
>>>
>>>
>>>
>>> _______________________________________________
>>> NetworKit mailing list
>>> NetworKit at ira.uni-karlsruhe.de <mailto:NetworKit at ira.uni-karlsruhe.de>
>>> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
>>
>>
>> _______________________________________________
>> NetworKit mailing list
>> NetworKit at ira.uni-karlsruhe.de
>> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
>
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit




More information about the NetworKit mailing list