NetworkX Developer Zone: Ticket Query
https://networkx.lanl.gov/trac/query?status=!closed&priority=normal&order=component
NetworkXenUSTrac 0.12.3
https://networkx.lanl.gov/trac/ticket/158
https://networkx.lanl.gov/trac/ticket/158#158: clustering (community finding) algorithmsTue, 06 May 2008 17:03:12 GMTsyzheng<p>
I'm wondering if networkx has any plan to add some clustering algorithms in the future version. Clustering/module detection is a frequently used technology in the graph analysis.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/158#changelog
https://networkx.lanl.gov/trac/ticket/190
https://networkx.lanl.gov/trac/ticket/190#190: triadic censusMon, 24 Nov 2008 18:36:43 GMTaric<p>
Triadic Cencus (triads) is a way for looking for motifs in a directed graph.
Commonly there are 16 motifs defined:
<a class="extlink" href="http://www.educa.fmf.unilj.si/datana/pub/networks/pajek/triade.pdf"><span class="icon"></span>http://www.educa.fmf.unilj.si/datana/pub/networks/pajek/triade.pdf</a>
the interface of JUNG is:
<a class="extlink" href="http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/metrics/TriadicCensus.html"><span class="icon"></span>http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/metrics/TriadicCensus.html</a>
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/190#changelog
https://networkx.lanl.gov/trac/ticket/191
https://networkx.lanl.gov/trac/ticket/191#191: Add structural holes measureMon, 24 Nov 2008 18:37:40 GMTaric<p>
Structural holes:
<a class="extlink" href="http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/metrics/StructuralHoles.html"><span class="icon"></span>http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/metrics/StructuralHoles.html</a>
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/191#changelog
https://networkx.lanl.gov/trac/ticket/200
https://networkx.lanl.gov/trac/ticket/200#200: Add depth first forest algorithmThu, 04 Dec 2008 12:47:47 GMTmurray_mintuk<p>
I needed the depth first forest of a (directed) graph. i.e. a copy of the original graph with edges labeled as one of: tree,back,forward or cross. And also the discovery/finish times and parent of each node in it's tree.
</p>
<p>
I've attached 2 files:
</p>
<p>
networkx/algorithms/traversal/dfs_forest.py (new file)
dfs_forest.diff (against trunk 1072)
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/200#changelog
https://networkx.lanl.gov/trac/ticket/206
https://networkx.lanl.gov/trac/ticket/206#206: Create C language dictofdicts structureTue, 09 Dec 2008 14:39:01 GMTaric<p>
Inheriting from dict can potentially create a more natural Python API
for Graph().
</p>
<p>
Using such a class would allow saying G[u][v]=data (currently wrong,
causes inconsistent internal data) to create a new edge and del
G[u][v] to remove an edge (also currently creates inconsistent
internal data structure).
</p>
<p>
Attached is a pure Python Graph() reference class based on inheriting
from dict that implements the NetworkX 0.99 API. It is
substantially slower (510 times) than NetworkX Graph().
</p>
<p>
A C language dictofdicts base class that implements this could
improve performance.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/206#changelog
https://networkx.lanl.gov/trac/ticket/224
https://networkx.lanl.gov/trac/ticket/224#224: Persistent graph storageSat, 07 Feb 2009 23:31:54 GMTaric<p>
The mailing list discussion at
<a class="extlink" href="http://groups.google.com/group/networkxdiscuss/browse_thread/thread/edc1b0ad6728243e"><span class="icon"></span>http://groups.google.com/group/networkxdiscuss/browse_thread/thread/edc1b0ad6728243e</a>#
suggested some ideas for persistent storage of NetworkX graphs.
</p>
<p>
Attached is an example of how to do this using shelve.
Use it like this:
</p>
<pre class="wiki">>>> G=PersistentGraph(file='graph.db')
>>> G.add_edge('a','b')
>>> del G # closes file graph.db
>>> G=PersistentGraph(file='graph.db')
>>> print G.edges()
[('b', 'a')]
</pre><p>
This version works with both writeback=True and writeback=False for the shelve.
See <a class="extlink" href="http://www.python.org/doc/2.5.2/lib/node328.html"><span class="icon"></span>http://www.python.org/doc/2.5.2/lib/node328.html</a>
for an example of the difference. For writeback=True only
a very simple modification of the Graph() class code is necssary to
use a shelve instead of dict as the underlying data structure.
For writeback=False a few methods need to be changed to handle
the persistence correctly.
</p>
<p>
There is also test (run with nosetests v) to demonstrate that it
at least passes the "smoke test".
</p>
<p>
Some drawbacks to this approach:
</p>
<p>
Only the adjacency structure is stored (as a shelve
dictofdicts)  no metadata about the graph (e.g graph type).
</p>
<p>
It is obviously slower. I didn't do any benchmarks.
</p>
<p>
Only strings are allowed as shelve keys. So nodes must be strings.
</p>
<p>
If this has decent performance it may be useful to incorporate
into NetworkX. Either as an option in the existing graph classes
or as as separate graph classes.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/224#changelog
https://networkx.lanl.gov/trac/ticket/239
https://networkx.lanl.gov/trac/ticket/239#239: Add Louvain method community detectionFri, 24 Apr 2009 14:57:15 GMTaric<p>
<a class="extlink" href="http://perso.crans.org/aynaud/communities/"><span class="icon"></span>http://perso.crans.org/aynaud/communities/</a>
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/239#changelog
https://networkx.lanl.gov/trac/ticket/245
https://networkx.lanl.gov/trac/ticket/245#245: Fast Algorithm for Finding Community StructureWed, 17 Jun 2009 04:01:35 GMTdcurtis<p>
Here is a version of the algorithm from "Finding community structure in very large networks" by Aaron Clauset, M.E.J. Newman, and Cristopher Moore.
</p>
<p>
I think there are some things I could probably do better but the algorithm is pretty intensive. If there was a maxheapq structure in Python it might save some time. Any improvements I'd love to see. It's not simple, consult the paper if you're curious why I did what I did.
</p>
<p>
One thing that I do that's somewhat crazyish is that I am building a dendrogram of the process. Thus, each node is actually a tuple containing what are supposed to be communities. In the end you'd have a single root node that is all communities as one.
</p>
<p>
The authors do provide a version of this written in C but of course they have lots of fun stuff to do because they don't have the Python datastructures. However, theirs runs faster. With that said, I did test my algorithm and it gives identical results.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/245#changelog
https://networkx.lanl.gov/trac/ticket/246
https://networkx.lanl.gov/trac/ticket/246#246: Function for calculating a graphs Q value (community structure quality)Wed, 17 Jun 2009 04:06:28 GMTdcurtis<p>
This function simply calculates the Q value for a graph based on a particular community structure. This is for undirected graphs and is based on the measure given in "Finding and evaluating community structure in networks" by Newman and Girvan.
</p>
<p>
The function takes a graph and a list of communities (given as lists) and uses that information to calculate the Q value.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/246#changelog
https://networkx.lanl.gov/trac/ticket/253
https://networkx.lanl.gov/trac/ticket/253#253: generators for subclassesWed, 29 Jul 2009 18:13:58 GMTcellison<p>
I was wondering if the generator functions could/should be modified so that they accepted a class that was used to construct the graph. This can be helpful if one wanted to generate a graph but desired that graph class was actually a subclass of DiGraph (for example).
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/253#changelog
https://networkx.lanl.gov/trac/ticket/254
https://networkx.lanl.gov/trac/ticket/254#254: Inconsistency of tickets 245 and 246Thu, 30 Jul 2009 14:41:22 GMTcomellas<p>
Modularity Q returns a different value if using fascommunity.py or qvalue.py (this is the good value, I believe)
Example:
</p>
<p>
commNetwX=communityStructureNewman(nx.heawood_graph())
print 'Q fastcommunity.py = ',commNetwX<a class="missing changeset" title="No changeset 0 in the repository">[0]</a>
print 'Q qvalue.py = ',qvalue(nx.heawood_graph(),commNetwX<a class="changeset" href="https://networkx.lanl.gov/trac/changeset/1/networkxsvnarchive" title="initial svn layout">[1]</a>)
</p>
<p>
returns
Q fastcommunity.py = 0.<a class="missing changeset" rel="nofollow" title="No changeset 231292517007 in the repository">231292517007</a>
Q qvalue.py = 0.<a class="missing changeset" rel="nofollow" title="No changeset 204081632653 in the repository">204081632653</a>
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/254#changelog
https://networkx.lanl.gov/trac/ticket/261
https://networkx.lanl.gov/trac/ticket/261#261: Cumulative nomination scheme as a centrality measureMon, 17 Aug 2009 10:54:36 GMTdheerajrav<p>
Cumulative nomination scheme, also known as CNS is a centrality measure which works on the principle of ranking a graph based on the nominations it gets.
</p>
<p>
The individuals(nodes) in a graph gets the initial nomination of 1. and at every stage, each individual(node) gets additional nominations their contacts already have( 1 is the nomination in the first stage).
Thus, the individual with more nominations will be considered more important than the contacts with only a few nominations.
</p>
<p>
The process is repeated till the growth of every individual is a constant.
</p>
<p>
I've attached the CNS code (which works for both connected and disconnected components)
</p>
<p>
Reference: Dynamical systems to define centrality in social networks by Poulin, Boily and Masse
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/261#changelog
https://networkx.lanl.gov/trac/ticket/307
https://networkx.lanl.gov/trac/ticket/307#307: Add progress callback option for long running methodsTue, 12 Jan 2010 16:16:42 GMTmidgleyf@…<p>
As discussed <a class="extlink" href="http://groups.google.com/group/networkxdiscuss/browse_thread/thread/43ef95967c97fd80/ed508f218695afd7"><span class="icon"></span>previously</a> it would be nice to have progress/status reported while long operations ran. As a bonus the operations could be cancelable.
</p>
<p>
I propose the following callback mechanism:
</p>
<ol><li>NetworkX methods that could run for a long time add a progress_callback parameter with a default value of None. For example:
</li></ol><pre class="wiki"> def closeness_centrality(G,v=None,weighted_edges=False, progress_callback=None):
...
</pre><ol start="2"><li>Callers of the methods can provide a callback function such as the following:
</li></ol><pre class="wiki"> def print_progress(message = None, fraction_complete = None)
# Just dump the progress to stdout.
print (message or "Calculating...") + ( "" if fraction_complete is None else " (%.1f%%)" % (fraction_complete * 100.0))
return True
</pre><p>
The message parameter would be a humanreadable string for display to the user. The fraction_complete parameter would be a float between 0.0 and 1.0 or None (indicating an unknown amount of progress).
</p>
<p>
The callback function would also return a boolean to indicate whether or not the method should continue.
</p>
<ol start="3"><li>The NetworkX methods should periodically call the callback with whatever progress is available. If the callback returns False then they should cease calculation and make no changes to the graph, etc. For example, closeness_centrality could add the following to its main loop:
</li></ol><pre class="wiki"> for n in G:
if callable(progress_callback):
if not progress_callback(message = "Calculating closeness centrality...", fraction_complete = float(len(closeness_centrality)) / len(G)):
return {}
</pre><p>
I have used this mechanism for a few methods on a locally modified version of NetworkX and it works well.
</p>
<p>
Remaining questions:
</p>
<ol><li>Which methods need this?
</li></ol><ol start="2"><li>How much will it impact performance? Will some methods need to throttle their feedback, e.g. update progress at most x times per second?
</li></ol>Resultshttps://networkx.lanl.gov/trac/ticket/307#changelog
https://networkx.lanl.gov/trac/ticket/309
https://networkx.lanl.gov/trac/ticket/309#309: Load Data from Open Street MapsWed, 27 Jan 2010 00:37:45 GMTabie@…<p>
it would be cool to be able to import map data from <a class="extlink" href="http://www.openstreetmap.org/"><span class="icon"></span>http://www.openstreetmap.org/</a>
</p>
<p>
I have implemented this based on BSD licensed code, and submit it for inclusion to the readwrite module of networkx.
</p>
<p>
<a class="extlink" href="http://gist.github.com/287370"><span class="icon"></span>http://gist.github.com/287370</a>
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/309#changelog
https://networkx.lanl.gov/trac/ticket/328
https://networkx.lanl.gov/trac/ticket/328#328: Speeding up double edge swapSun, 21 Mar 2010 16:13:21 GMTjoelmiller<p>
I've come across some cases where it is relatively rare for a network to remain connected after an edge swap. For the current code it will check if the entire network is still connected, which is slow. If successful, then it will do two swaps before checking if the entire network is still connected, at which point if there is a failure it will undo both swaps and start over.
</p>
<p>
There is a faster test when only one edge swap has been done. The disadvantage of testing each time is that in many cases the vast majority of swaps leave a connected network, and so it may be faster to do many swaps and then use the slower test. The existing code makes this assumption, and tries to estimate the optimal number of swaps by dynamically increasing the number as there are more successes and halving the number if there is a failure.
</p>
<p>
I have created a modified code. If the 'optimal' number of swaps appears to be small (at present <3), then it will simply check after each swap if the network is still connected. If the number gets larger it will switch to checking only after many swaps. I believe this code will always be faster than the preexisting code.
</p>
<p>
However, it may be able to make it faster by changing the cutoff between the two methods to a larger value. In fact, if we test the cpu time each time it tests whether the network is still connected, we can get a good idea of which method is faster. If the slower test takes 10 times as long, then the window should be a bit larger than 10 before we switch to that test. I haven't tried to implement that but it would probably be a significant speed up and ensure that the approach is working well for all sorts of different network types.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/328#changelog
https://networkx.lanl.gov/trac/ticket/333
https://networkx.lanl.gov/trac/ticket/333#333: edge_subgraph()Mon, 12 Apr 2010 23:59:51 GMTcellison<p>
I'm interested in adding methods for returning edgeinduced subgraphs. For my use, I definitely do not need copies at all...I need these to be views, because all I want to do is analyze the properties of these subgraphs. I'll wait to hear on <a class="closed ticket" href="https://networkx.lanl.gov/trac/ticket/314" title="defect: the function networkx.connected_component_subgraphs(G) is very slow, it ... (closed: fixed)">#314</a> before writing the code. Does this sound like something of general interest?
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/333#changelog
https://networkx.lanl.gov/trac/ticket/338
https://networkx.lanl.gov/trac/ticket/338#338: Consider views for graphsWed, 14 Apr 2010 14:38:59 GMTdschult<p>
It would be nice to have a fast way to process parts of a graph.
A view could be faster than creating the induced subgraph
because it might not have to create the whole graph structure.
Let's see if that is really true.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/338#changelog
https://networkx.lanl.gov/trac/ticket/359
https://networkx.lanl.gov/trac/ticket/359#359: Fractal Dimension of GraphsTue, 08 Jun 2010 21:11:54 GMTbedwards<p>
Two functions to calculate the fractal dimension of a Graph. References provided in the code, no unit tests yet.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/359#changelog
https://networkx.lanl.gov/trac/ticket/378
https://networkx.lanl.gov/trac/ticket/378#378: Heuristically Optimized TradeoffsTue, 27 Jul 2010 23:39:03 GMTbedwards<p>
A random graph model for heuristically optimized tradeoffs presented by Fabrikant, Koutsoupia, and Papadimitriou. Function and Test included.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/378#changelog
https://networkx.lanl.gov/trac/ticket/406
https://networkx.lanl.gov/trac/ticket/406#406: alternative mincost maxflow implementationMon, 23 Aug 2010 13:04:53 GMTmfrasca<p>
some time ago I opened ticket <a class="closed ticket" href="https://networkx.lanl.gov/trac/ticket/291" title="enhancement: mincost maxflow support (closed: fixed)">#291</a>, and in that framework I had been asked to attach my implementation. never came so far, because I never managed to log into this system again... well, now it's a lot too late, and there is a good looking implementation attached to the ticket and committed in the library, but I managed to log in and I am still very much interested in reading your comments about my solution. I looked at the one attached to <a class="closed ticket" href="https://networkx.lanl.gov/trac/ticket/291" title="enhancement: mincost maxflow support (closed: fixed)">#291</a> and I can follow mine better, but I assume readability is not the main criterium for choosing an implementation.
here it comes!
thanks for your time!
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/406#changelog
https://networkx.lanl.gov/trac/ticket/419
https://networkx.lanl.gov/trac/ticket/419#419: Coreness (core / periphery)Sun, 05 Sep 2010 20:27:31 GMTalex<p>
Implements the continuous version of coreness described by Borgatti in <a class="extlink" href="http://dx.doi.org/10.1016/S03788733(99)000192"><span class="icon"></span>http://dx.doi.org/10.1016/S03788733(99)000192</a>
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/419#changelog
https://networkx.lanl.gov/trac/ticket/422
https://networkx.lanl.gov/trac/ticket/422#422: Add Borukva's (or modified) algorithm for minimum spanning treeMon, 06 Sep 2010 20:44:47 GMTaric<p>
From
<a class="extlink" href="http://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm"><span class="icon"></span>http://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm</a>
</p>
<p>
Faster algorithms can be obtained by combining Prim's algorithm with Borůvka's. A faster randomized minimum spanning tree algorithm based in part on Borůvka's algorithm due to Karger, Klein, and Tarjan runs in expected O(E) time. The best known (deterministic) minimum spanning tree algorithm by Bernard Chazelle is also based in part on Borůvka's and runs in O(E α(V)) time, where α is the inverse of the Ackermann function. These randomized and deterministic algorithms combine steps of Borůvka's algorithm, reducing the number of components that remain to be connected, with steps of a different type that reduce the number of edges between pairs of components.
</p>
<p>
The attached code has an basic example implementation.
See code for references to original sources.
</p>
<p>
Also see <a class="source" href="https://networkx.lanl.gov/trac/browser/networkx/networkx/algorithms/tests/test_mst.py">source:networkx/networkx/algorithms/tests/test_mst.py</a> for some tests using Kruskal's algorithm which might be helpful.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/422#changelog
https://networkx.lanl.gov/trac/ticket/423
https://networkx.lanl.gov/trac/ticket/423#423: Add arrow drawing and other improvements to Matplotlib drawingMon, 06 Sep 2010 20:50:37 GMTaric<p>
Update of tickets <a class="closed ticket" href="https://networkx.lanl.gov/trac/ticket/78" title="defect: draw arrows for digraphs with matplotlib (closed: duplicate)">#78</a> and <a class="closed ticket" href="https://networkx.lanl.gov/trac/ticket/293" title="enhancement: graph weights for colormap (closed: duplicate)">#293</a> (now closed) based on new code provided on mailing list at
</p>
<p>
<a class="extlink" href="http://groups.google.com/group/networkxdiscuss/browse_thread/thread/b95fda9813fae67d?hl=en_US"><span class="icon"></span>http://groups.google.com/group/networkxdiscuss/browse_thread/thread/b95fda9813fae67d?hl=en_US</a>
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/423#changelog
https://networkx.lanl.gov/trac/ticket/425
https://networkx.lanl.gov/trac/ticket/425#425: Add Python data types as extension to GraphMLTue, 14 Sep 2010 12:28:15 GMTaric<p>
The standard GraphML specification does not have types for allbuilt in Python data types (e.g. tuple, list, dict are not known). Adding them would allow the
GraphML module to read and write them <a class="source" href="https://networkx.lanl.gov/trac/browser/networkx/networkx/readwrite/graphml.py">networkx/networkx/readwrite/graphml.py</a>
</p>
<p>
GraphML can be extended to add "complex types" to support these by defining an XML schema.
<a class="extlink" href="http://graphml.graphdrawing.org/primer/graphmlprimer.html#Complex"><span class="icon"></span>http://graphml.graphdrawing.org/primer/graphmlprimer.html#Complex</a>
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/425#changelog
https://networkx.lanl.gov/trac/ticket/426
https://networkx.lanl.gov/trac/ticket/426#426: Performance bottleneck at reading GML fileTue, 14 Sep 2010 13:01:00 GMTray dot subhasis at gmail dot com<p>
The recommended GML format takes too long to read.
Especially, when it comes to large graphs, it is way faster to generate the graph programmatically than reading a GML file (e.g.,
Number of nodes: 3560
Number of edges: 618560,
GML file size 36 MB,
</p>
<p>
on the following hardware:
</p>
<p>
model name : Intel(R) Xeon(R) CPU E5520 @ 2.27GHz
cpu MHz : 1600.000
cache size : 8192 KB
<a class="missing wiki">MemTotal?</a>: 24677040 kB
</p>
<p>
running CentOS 5.
The memory consumption is > 6 GB and time 1554.35 s, in comparison, writing the file takes 9.42645 s and constructing the graph programmatically takes 8.2 s on the same system).
</p>
<p>
Perhaps it might be improved by a little C code to do the File I/O and some cache optimization?
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/426#changelog
https://networkx.lanl.gov/trac/ticket/434
https://networkx.lanl.gov/trac/ticket/434#434: Update matplotlib drawing with arrows and other improvementsTue, 21 Sep 2010 03:27:39 GMTaric<p>
Attached is code from <a class="extlink" href="http://groups.google.com/group/networkxdiscuss/browse_thread/thread/b95fda9813fae67d"><span class="icon"></span>http://groups.google.com/group/networkxdiscuss/browse_thread/thread/b95fda9813fae67d</a> that improves the matplotlib drawing interface.
See also <a class="closed ticket" href="https://networkx.lanl.gov/trac/ticket/78" title="defect: draw arrows for digraphs with matplotlib (closed: duplicate)">#78</a> and <a class="closed ticket" href="https://networkx.lanl.gov/trac/ticket/293" title="enhancement: graph weights for colormap (closed: duplicate)">#293</a> for context.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/434#changelog
https://networkx.lanl.gov/trac/ticket/435
https://networkx.lanl.gov/trac/ticket/435#435: Structural HolesTue, 21 Sep 2010 07:12:06 GMTalex<p>
Calculates Burt's structural holes values
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/435#changelog
https://networkx.lanl.gov/trac/ticket/442
https://networkx.lanl.gov/trac/ticket/442#442: Add GraphML reader with yfiles extensions.Wed, 29 Sep 2010 04:12:30 GMTaric<p>
yWorks extends the graphml standard with extra graphics attributes,
<a class="extlink" href="http://www.yworks.com/en/products_yfiles_ep_graphml.html"><span class="icon"></span>http://www.yworks.com/en/products_yfiles_ep_graphml.html</a>
</p>
<p>
Extend the exiting graphml reader/writer <a class="source" href="https://networkx.lanl.gov/trac/browser/networkx/networkx/readwrite/graphml.py">networkx/networkx/readwrite/graphml.py</a>
to handle the extension.
</p>
<p>
See also <a class="extlink" href="http://github.com/mshelton/networkx/blob/master/scripts/stripYfiles.py"><span class="icon"></span>http://github.com/mshelton/networkx/blob/master/scripts/stripYfiles.py</a>
for removing the extensions so the file can be read by networkx.read_graphml
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/442#changelog
https://networkx.lanl.gov/trac/ticket/445
https://networkx.lanl.gov/trac/ticket/445#445: track node and edge ordersSun, 03 Oct 2010 20:21:21 GMTcellison<p>
The user can always do this, but is there any interest in storing the node/edge addition order into NetworkX?
</p>
<p>
For example, each graph class could have an attribute:
</p>
<pre class="wiki"> G._node_order
G._edge_order
</pre><p>
These attributes would be lists of the node/edge attribute dictionaries, in the order that they were added to the graph instance. Since we're not copying the attribute dictionaries, it seems like this would have a fairly small footprint.
</p>
<p>
So each graph would have something like:
</p>
<pre class="wiki"> G._nodeIndex
G._edgeIndex
</pre><p>
which are integers storing the total number of nodes/edges that have ever been put into the graph. Note: this is not the same as the total number of nodes/edges currently in the graph (since the user might delete nodes/edges).
</p>
<p>
As each node/edge is added to the graph, we store its index in the attribute dictionary. This provides for an easy lookup and way to mark the node/edge as deleted.
</p>
<pre class="wiki">>>> G = nx.Graph()
>>> G.add_edge(0,1)
>>> G[0][1]
{'index': 0}
>>> G.nodes[0]
{'index': 0}
>>> G.nodes[1]
{'index': 1}
>>> G._node_index
2
>>> G._edge_index
1
>>> G._node_order
[{'index': 0}, {'index': 1}]
>>> G._edge_order
[{'index': 0}]
>>> G.add_edge(0, 2)
>>> G.remove_node(1)
>>> G._node_order
[{'index': 0}, None, {'index': 2}]
>>> G._edge_order
[{'index': 1}]
</pre><p>
So when an node/edge is deleted, its 'index' attribute is used to mark the location in _node_order (or _edge_order) to have the value of <tt>None</tt>. Then, we could provide some methods like:
</p>
<pre class="wiki">def node_order(self):
return [n for n in self._node_order if n is not None]
</pre><p>
and similarly for edge_order.
</p>
<p>
Not sure if this is a good way to implement it, but I thought the feature might seem useful. Please comment!
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/445#changelog
https://networkx.lanl.gov/trac/ticket/455
https://networkx.lanl.gov/trac/ticket/455#455: Reimplement graphml to use SAX (and not build XML documents in memory)Mon, 01 Nov 2010 19:21:35 GMTalexsdutton<p>
I've reimplemented the readwrite.graphml API to use a SAX content handler and xml.sax.utils.XMLGenerator instead of etree. It passes the tests (so could be assumed to be a functional replacement), but may need tidying.
</p>
<p>
We'd like to use graphml for serialization but it builds the XML document in memory, which is suboptimal for very large graphs. A SAXbased implementation also seems to be much quicker.
</p>
<p>
I've attached the patch.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/455#changelog
https://networkx.lanl.gov/trac/ticket/457
https://networkx.lanl.gov/trac/ticket/457#457: Add graph class that tracks connected componentsSun, 07 Nov 2010 00:57:01 GMTaric<p>
Add a class to incrementally maintain list of connected components.
</p>
<p>
Implementation in <a class="changeset" href="https://networkx.lanl.gov/trac/changeset/1464/networkx" title="Adding class for incrementally tracking connected components.">[1464/networkx]</a>.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/457#changelog
https://networkx.lanl.gov/trac/ticket/470
https://networkx.lanl.gov/trac/ticket/470#470: Add graph sampling methods. E.g., MetropolisHastings random walk or weighted independent samplerWed, 17 Nov 2010 12:47:23 GMTmaciej.kurant@…<p>
Many reallife graphs are too big to be downloaded and analyzed in their full size. Examples are WWW or Online Social Networks. We can still learn something about such a massive graph by collecting a *sample* of its nodes, and using it to *estimate* whatever metric we are interested in.
</p>
<p>
I attach a module with common graph sampling techniques and basic estimators compatible with them. They are rather simple (though the weighted versions may be a bit tricky) and you will find them in many textbooks. I think, it would be really useful to include this module in networkx. Please, let me know what you think.
</p>
<p>
Supported sampling methods:
</p>
<ul><li>uniform_independent_node_sample
</li><li>random_walk
</li><li>metropolis_hastings_random_walk
</li><li>weighted_independent_node_sample
</li><li>weighted_random_walk
</li></ul><p>
Supported estimators:
</p>
<ul><li>estimate_size
</li><li>estimate_mean
</li></ul>Resultshttps://networkx.lanl.gov/trac/ticket/470#changelog
https://networkx.lanl.gov/trac/ticket/471
https://networkx.lanl.gov/trac/ticket/471#471: Algorithm for Degreeconstrained minimum spanning treeThu, 18 Nov 2010 01:13:23 GMTwladston@…<p>
Hey guys,
</p>
<p>
I've used networkx to write a code to find the degree constrained minimum spanning tree of a graph using this technique :
</p>
<p>
<a class="extlink" href="http://www.scielo.br/scielo.php?script=sci_arttext&pid=S010174382005000200004"><span class="icon"></span>http://www.scielo.br/scielo.php?script=sci_arttext&pid=S010174382005000200004</a>
</p>
<p>
I was wondering if there is any interest in making this code a part of networkx, so future people interested in finding the degreeconstrained, or hop constrained minimum spanning tree can save some time.
</p>
<p>
If yes, I just fork networkx from <a class="extlink" href="http://github.com/networkx/networkx"><span class="icon"></span>http://github.com/networkx/networkx</a> , apply my code, create a diff, post it here, and then you review it ?
</p>
<p>
Just to remember, finding the degreeconstrained minimum spanning tree is an NPHard problem.
</p>
<p>
Thanks, waiting for a reply!
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/471#changelog
https://networkx.lanl.gov/trac/ticket/498
https://networkx.lanl.gov/trac/ticket/498#498: double_edge_swap for directed graphsTue, 01 Feb 2011 03:26:47 GMTanonymous<p>
Currently, double_edge_swap doesn't work for <a class="missing wiki">DiGraph?</a>. I have attached the patch for degree_seq.py that should make double_edge_swap work for directed graphs.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/498#changelog
https://networkx.lanl.gov/trac/ticket/511
https://networkx.lanl.gov/trac/ticket/511#511: floydwarshall algorithm for weighted capacitated graphsFri, 25 Feb 2011 13:36:11 GMTmfrasca<p>
in the course of the analysis of <a class="needinfo ticket" href="https://networkx.lanl.gov/trac/ticket/406" title="enhancement: alternative mincost maxflow implementation (needinfo)">ticket:406</a>, I have written an implementation of the floyd_warshall algorithm, for weighted and capacitated graphs.
</p>
<p>
I don't know whether this has been added to the library since, but in case it hasn't here it is.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/511#changelog
https://networkx.lanl.gov/trac/ticket/534
https://networkx.lanl.gov/trac/ticket/534#534: Add an algorithm to detect a graph chordless cyclesWed, 06 Apr 2011 11:53:40 GMTpa.basso@…<p>
Related discussion: <a class="extlink" href="http://stackoverflow.com/questions/4022662/findallchordlesscyclesinanundirectedgraph"><span class="icon"></span>http://stackoverflow.com/questions/4022662/findallchordlesscyclesinanundirectedgraph</a>
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/534#changelog
https://networkx.lanl.gov/trac/ticket/538
https://networkx.lanl.gov/trac/ticket/538#538: Add node independent paths functionsSun, 10 Apr 2011 21:06:18 GMTjtorrents<p>
Because of the new flow based connectivity functions (<a class="new ticket" href="https://networkx.lanl.gov/trac/ticket/625" title="enhancement: Add flow based connectivity and cutsets functions (new)">#625</a>) I've changed the name for this module from <tt>node_independent_paths.py</tt> to <tt>connectivity_approx.py</tt>. I also added a new function <tt>global_vertex_connectivity_approx</tt> that uses the same logic than its flow based friend but using the White and Newman fast approximation to find node independent paths. For sparse networks, the approximation is two orders of magnitude faster. I also removed functions for single source node independent paths and all pairs node independent paths because I think that this module will be more useful as a fast approximation to vertex connectivity.
</p>
<p>
Node independent paths or disjoint vertex paths are paths between two nodes that share no nodes in common other than their starting and ending nodes. The attached implementation finds node independents paths between two nodes by computing their shortest path using BFS, marking the nodes of the path found as 'used' and then searching other shortest paths excluding the nodes marked as used until no more paths exist.
</p>
<p>
References
</p>
<p>
White, Douglas R., and Mark Newman. 2001 A Fast Algorithm for NodeIndependent Paths. Santa Fe Institute Working Paper 0107035
</p>
<p>
<a class="extlink" href="http://eclectic.ss.uci.edu/~drwhite/working.pdf"><span class="icon"></span>http://eclectic.ss.uci.edu/~drwhite/working.pdf</a>
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/538#changelog
https://networkx.lanl.gov/trac/ticket/540
https://networkx.lanl.gov/trac/ticket/540#540: Gephi read/write functions don't handle dynamic data correctly.Thu, 14 Apr 2011 01:06:55 GMTaric<p>
See
<a class="extlink" href="http://groups.google.com/group/networkxdiscuss/browse_thread/thread/6b53d6015821738e"><span class="icon"></span>http://groups.google.com/group/networkxdiscuss/browse_thread/thread/6b53d6015821738e</a>
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/540#changelog
https://networkx.lanl.gov/trac/ticket/557
https://networkx.lanl.gov/trac/ticket/557#557: Community Detection AlgorithmsFri, 20 May 2011 21:30:53 GMTbedwards<p>
This is a ticket to track the progress of community detection algorithms for Google Summer of Code 2011
</p>
<p>
Links to other info about this ticket.
</p>
<p>
proposal: <a class="extlink" href="http://cs.unm.edu/~bedwards/gsoc2.html"><span class="icon"></span>http://cs.unm.edu/~bedwards/gsoc2.html</a>
</p>
<p>
blog: <a class="extlink" href="http://gsocnetworkx.blogspot.com/"><span class="icon"></span>http://gsocnetworkx.blogspot.com/</a>
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/557#changelog
https://networkx.lanl.gov/trac/ticket/558
https://networkx.lanl.gov/trac/ticket/558#558: More Network Flow AlgorithmsMon, 23 May 2011 23:42:59 GMTputra.manggala@…<p>
This ticket is meant to follow the progress of the network flow algorithms implementation project under GSoC 2011.
</p>
<p>
The proposal to this project is here:
<a class="extlink" href="http://www.cs.mcgill.ca/~pmangg/networkx.pdf"><span class="icon"></span>http://www.cs.mcgill.ca/~pmangg/networkx.pdf</a>
</p>
<p>
The blog posts are here: <a class="extlink" href="http://deephunch.wordpress.com/"><span class="icon"></span>http://deephunch.wordpress.com/</a>
</p>
<p>
Git repository here: <a class="extlink" href="https://github.com/pmangg/networkx"><span class="icon"></span>https://github.com/pmangg/networkx</a>
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/558#changelog
https://networkx.lanl.gov/trac/ticket/565
https://networkx.lanl.gov/trac/ticket/565#565: convert.py needs be refactored and the design reconsideredSat, 04 Jun 2011 15:18:16 GMTaric<p>
convert.py is too big and should be split into modules.
The design of esp. from_dict_of_dicts() could be reconsidered to make it simpler and easier to test. See ticket <a class="closed ticket" href="https://networkx.lanl.gov/trac/ticket/564" title="defect: Error in converting from digraph to graph using Graph(Digraph()) (closed: fixed)">#564</a> for a bug that was hard to find.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/565#changelog
https://networkx.lanl.gov/trac/ticket/578
https://networkx.lanl.gov/trac/ticket/578#578: Feedback on adding Omnigraffle read supportThu, 23 Jun 2011 02:19:59 GMTsimon.knight<p>
Hello,
</p>
<p>
I have been looking at <a class="missing wiki">OmniGraffle?</a> support in NetworkX.
</p>
<p>
NetworkX does not currently support reading of graphs drawn in <a class="missing wiki">OmniGraffle?</a>. <a class="missing wiki">OmniGraffle?</a> only exports to image formats. There have been some requests in their forums to export to a graph based format (dot etc) but they have not yet been implemented.
</p>
<p>
There is a Python project  graffle2svg  which converts an Omnigraffle document into an SVG document. We could adapt this  the document reading part  for NetworkX.
</p>
<p>
I emailed the author about adapting the code for use in NetworkX, and he was ok with this.
</p>
<p>
Is something that would be of interest? Most of the heavy lifting is done in <a class="extlink" href="http://code.google.com/p/graffle2svg/source/browse/trunk/graffle2svg/main.py"><span class="icon"></span>http://code.google.com/p/graffle2svg/source/browse/trunk/graffle2svg/main.py</a>
We can discard the graphics information, we only need the part that pushes the Graffle document into a Python data structure.
</p>
<p>
This does not export back to Graffle format, however <a class="missing wiki">OmniGraffle?</a> can read graphviz dot files, so I think this is an acceptable work around.
</p>
<p>
The biggest hurdle I see is that they use xml minidom, whereas NetworkX uses <a class="missing wiki">ElementTree?</a>. Any comments on this? Should I modify it to use ET?
</p>
<p>
Any feedback is welcomed.
</p>
<p>
Cheers
Simon
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/578#changelog
https://networkx.lanl.gov/trac/ticket/581
https://networkx.lanl.gov/trac/ticket/581#581: Change methods to return iterators and retire _iter methodsSat, 25 Jun 2011 01:33:45 GMTdschult<p>
Graph class methods such as <tt>neighbors</tt>, <tt>degree</tt>, and <tt>edges</tt> return lists or dicts when it seems cleaner and more efficient to return iterators.
</p>
<p>
Currently these methods have cousin methods like <tt>edges_iter</tt> that do return iterators.. We should consider removing the <tt>_iter</tt> methods and making the others return iterators by design. Then if the user needs a list of dict they can use e.g. <tt>list(G.edges())</tt> Making the default behavior an iterator encourages efficiency.
</p>
<p>
Most methods would generate pairs (node, value) that could be used to construct a dict. It might also be useful to be able to generate just the values. Some methods like {{{G.nodes()}} would naturally just generate single values.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/581#changelog
https://networkx.lanl.gov/trac/ticket/582
https://networkx.lanl.gov/trac/ticket/582#582: Add data keyword to neighbors methodSat, 25 Jun 2011 01:39:53 GMTdschult<p>
The <tt>neighbors</tt> method could return edge data just like the <tt>edges</tt> method does. This would allow simpler code when iterating over the adjacency list of a node.
</p>
<p>
See <a class="closed ticket" href="https://networkx.lanl.gov/trac/ticket/574" title="enhancement: New method for graphs called get_edge_weight() (closed: wontfix)">#574</a> for discussion and examples.
</p>
<p>
<tt>G.neighbors(n, data=True)</tt> would return a dict keyed by neighbor node to the edge data dict connecting them.
</p>
<p>
<tt>G.neighbors_iter(n, data=True)</tt> would return an iterator of pairs (nbr,edgedata). This is similar to G.edges(n, data=True) but that iterates through (n,nbr,edgedata). This is a synonym for G[u].items()
</p>
<p>
Suggestions?
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/582#changelog
https://networkx.lanl.gov/trac/ticket/583
https://networkx.lanl.gov/trac/ticket/583#583: Add features to get_edge_data methodSat, 25 Jun 2011 02:56:44 GMTdschult<p>
The get_edge_data method should be enhanced with keyword control of what gets returned.
</p>
<p>
The motivation for this change is to make it simpler to write algorithms that access edge data, especially when handling multigraphs. See <a class="closed ticket" href="https://networkx.lanl.gov/trac/ticket/574" title="enhancement: New method for graphs called get_edge_weight() (closed: wontfix)">#574</a> for a detailed discussion and examples.
</p>
<p>
The proposed signature is:
</p>
<pre class="wiki">G.get_edge_data(u,v,key=None,data_key=None,default=1,missing=None,combine=list)
</pre><p>
Briefly, when <tt>data_key is None</tt>, this is like <tt>G.adj[u][v]</tt>.
But when <tt>data_key</tt> is specified, this is like <tt>G.adj[u][v].get(data_key, default) </tt>
</p>
<p>
If the edge doesn't exist, <tt>missing</tt> is returned.
</p>
<p>
The <tt>key</tt> and <tt>combine</tt> arguments are used only for multigraphs. If key is specified, use the same behavior on the data dict <tt>G.adj[u][v][key]</tt>. If <tt>key is None</tt> and <tt>data_key</tt> is specified, the list of values obtained is sent to the function combine, which defaults to <tt>list</tt>, but common examples would be <tt>min</tt> or <tt>sum</tt>.
</p>
<p>
This is not backward compatible since the current method uses the <tt>default</tt> keyword to supply a value when the edge does not exist instead of when the edge data key does not exist as proposed here.
</p>
<p>
Suggestions on other desired features? names for arguments? anything else?
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/583#changelog
https://networkx.lanl.gov/trac/ticket/586
https://networkx.lanl.gov/trac/ticket/586#586: Trophic Index, Initial ImplementationWed, 29 Jun 2011 17:06:14 GMTvaggi.federico@…<p>
I created a very initial implementation for the trophic index, an index used in ecological network analysis to calculate the strength of the indirect effect of a species on another species. The description of the trophic index can be found here:
</p>
<p>
Quantifying the importance of species and their interactions in a hostparasitoid community. F. Jordan, W.C. Liu and F.J.F van Veen Community Ecology, 2003.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/586#changelog
https://networkx.lanl.gov/trac/ticket/589
https://networkx.lanl.gov/trac/ticket/589#589: kcomponents approximationThu, 07 Jul 2011 15:47:00 GMTjtorrents<p>
New version of the algorithm. To run it you'll need the code for vertex connectivity approximation <a class="new ticket" href="https://networkx.lanl.gov/trac/ticket/538" title="enhancement: Add node independent paths functions (new)">#538</a>, the antigraph data structure <a class="new ticket" href="https://networkx.lanl.gov/trac/ticket/608" title="enhancement: Complement graph class for small footprint dense networks (new)">#608</a>. For accuracy tests you will also need the flow based connectivity code <a class="new ticket" href="https://networkx.lanl.gov/trac/ticket/625" title="enhancement: Add flow based connectivity and cutsets functions (new)">#625</a>
</p>
<p>
A kcomponent is a maximal subgraph that cannot be disconnected removing less
than k nodes (along with their incident edges). By Merger's theorem, this is
equivalent to a maximal subgraph in which all pairs of nodes are connected
by at least k nodeindependent paths which each run entirely within the
subgraph. Note that a kcomponent must be a subset of a (k1)component or
be a (k1)component itself. Thus, they have an inherent hiearchical structure.
Components of level k can overlap in k1 nodes.
</p>
<p>
Following White and Harary (2001) and Moody and White (2003), the cohesive
structure of a network can be conceptualized as increasingly cohesive groups
nested inside each other. Those groups can be operacionalized as the
kcomponents of the network. A common structural pattern in large networks is
an hierarchical nesting of increasingly cohesive groups at low connectivity
levels and nonoverlapping highly cohesive groups at higher connectivity levels.
</p>
<p>
Those highly cohesive groups play a key role in the diffusion of the
consequences of social interactions among actors in networks. It is usually
assumed that the transmission through the network of knowledge, influence
and resources generated by social interactions is limited to people 2 or 3
steps away from the initiator of such interactions. However, strongly cohesive
subsets of nodes allow repetition of information and reinforcement of influence
because they are characterized by multiple independent pathways that
compensate the decay effects of the transmission of knowledge,
influence and resources.
</p>
<p>
An exact solution for the computation of the complete kcomponent structure
(Moody & White, 2003) is impractical for large networks. This approximation
is based on the proposal of White and Newman (2001) of a fast approximation
for finding node independent paths (implemented in <a class="new ticket" href="https://networkx.lanl.gov/trac/ticket/538" title="enhancement: Add node independent paths functions (new)">#538</a>). It allows us to
compute the approximate kcomponent structure for moderately large networks,
in a reasonable time frame.
</p>
<p>
The algorithm consists in 6 steps:
</p>
<ol><li>kcore computation (time O(E)): Compute the core number for each node. A kcore is a maximal subgraph that contains nodes of degree k or more. The core number of a node is the largest value k of a kcore containing that node. This is a baseline for kcomponents because \kappa(G) <= \lambda(G) <= \delta(G)
</li></ol><ol start="2"><li>bicomponents computation (time O(V+E)): Compute the biconnected components of the graph. (k>2)components are a subset of (or are themselves also) a bicomponent. Besides, the exact computation is faster than the approximation because usually bicomponents are quite large. Thus we start computing the approximation for k=3. (same for tricomponents but it is not implemented in NetworkX yet)
</li></ol><ol start="3"><li>for each k from 3 to the maximum core number of a node of the graph we repeat the following steps:
</li></ol><ol start="4"><li>For each bicomponent we create a subgraph with all nodes with core level = k. Compute the connected component of the kcore sugraph (note that the kcore could be disconnected) and then compute the approximation for vertex connectivity (proposed by White and Newman (2001)) between all pairs of nodes. Implemented in ticket <a class="new ticket" href="https://networkx.lanl.gov/trac/ticket/538" title="enhancement: Add node independent paths functions (new)">#538</a>.
</li></ol><ol start="5"><li>Build an auxiliary graph with all nodes in the subgraph analyzed and edges between two nodes if the local vertex connectivity (ie number of node independent paths between them) is greater or equal than the level k of the main for loop. Note: we actually use a complement graph data structure to save memory because usually a big part of the kcore is actually a kcomponent.
</li></ol><ol start="6"><li>Each connected component of the auxiliary graph is a candidate to be a kcomponent. But we need to do a final check: we create the induced subgraph of candidate nodes from the input graph and discard any node that, in this induced subgraph, has core number less than k. The remaining nodes are assumed to be a kcomponent.
</li></ol><p>
References
</p>
<blockquote>
<p>
White, Douglas R., and Mark Newman. 2001
A Fast Algorithm for NodeIndependent Paths.
Santa Fe Institute Working Paper 0107035
<a class="extlink" href="http://eclectic.ss.uci.edu/~drwhite/working.pdf"><span class="icon"></span>http://eclectic.ss.uci.edu/~drwhite/working.pdf</a>
</p>
</blockquote>
<blockquote>
<p>
White, D. R., and F. Harary. (2001)
The cohesiveness of blocks in social networks: Node
connectivity and conditional density,
Sociological Methodology 31:30559.
<a class="extlink" href="http://eclectic.ss.uci.edu/~drwhite/smw23.PDF"><span class="icon"></span>http://eclectic.ss.uci.edu/~drwhite/smw23.PDF</a>
</p>
</blockquote>
<blockquote>
<p>
Moody, James and Douglas R. White. 2003.
Social Cohesion and Embeddedness. American Sociological Review. 68:103127
<a class="extlink" href="http://www2.asanet.org/journals/ASRFeb03MoodyWhite.pdf"><span class="icon"></span>http://www2.asanet.org/journals/ASRFeb03MoodyWhite.pdf</a>
</p>
</blockquote>
Resultshttps://networkx.lanl.gov/trac/ticket/589#changelog
https://networkx.lanl.gov/trac/ticket/593
https://networkx.lanl.gov/trac/ticket/593#593: add parallelpython example for small world factorFri, 15 Jul 2011 20:13:52 GMTjtorrents<p>
Add a simple example using parallel python to compute small world factor using a bunch of ErdösRényi random networks
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/593#changelog
https://networkx.lanl.gov/trac/ticket/594
https://networkx.lanl.gov/trac/ticket/594#594: Add example for computation in parallel for betweenness centralityFri, 15 Jul 2011 20:16:26 GMTjtorrents<p>
Add Ben's example of parallel computation for betweenness centrality using the multiprocessing module of the standard library
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/594#changelog
https://networkx.lanl.gov/trac/ticket/607
https://networkx.lanl.gov/trac/ticket/607#607: Network Simplex gives incorrect solutions on MultiDiGraphsMon, 25 Jul 2011 11:25:05 GMTarv@…<p>
When running network_simplex on a MultiDiGraph, the capacity edge attributes seem to be ignored, because the code does not appear to be written with a MultiDiGraph in mind, despite the algorithm being welldefined (seems to me) on MultiDiGraphs.
</p>
<p>
For example, lines 5556 of algorithms/flow/mincost.py:
</p>
<pre class="wiki">if (not capacity in G[r][v]
or vDemand <= G[r][v][capacity]):
</pre><p>
This condition will always fail on a MultiDiGraph, since G[r][v] refers to not a single edge dict, but a dict of edges.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/607#changelog
https://networkx.lanl.gov/trac/ticket/608
https://networkx.lanl.gov/trac/ticket/608#608: Complement graph class for small footprint dense networksMon, 25 Jul 2011 21:38:03 GMTdschult<p>
It would be nice to include a complement graph data storage class to store dense networks without using a lot of memory.
</p>
<p>
Let's start with the example from ticket <a class="new ticket" href="https://networkx.lanl.gov/trac/ticket/589" title="enhancement: kcomponents approximation (new)">#589</a> called <a class="missing wiki">AntiGraph?</a>
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/608#changelog
https://networkx.lanl.gov/trac/ticket/611
https://networkx.lanl.gov/trac/ticket/611#611: Global, nodal and local efficiency calculationFri, 29 Jul 2011 11:08:33 GMTtr332@…<p>
This is a script I've written for calculating measures of efficiency, as introduced by Latora and Marchiori(Latora V, Marchiori M (2001). Efficient behavior of smallworld networks. Phys Rev Lett 87: 198701.). I've written functions for general, nodal and local efficiency. It is written for an undirected unweighted graph.
</p>
<p>
This is my first ever script/ticket submission to any programming website! Apologies if it's not perfect, but I hope it can be developed to a point where it is useful for others.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/611#changelog
https://networkx.lanl.gov/trac/ticket/613
https://networkx.lanl.gov/trac/ticket/613#613: speed up for simple_cycles using componentsFri, 05 Aug 2011 16:54:40 GMTdschult<p>
On the discussion list, Kevin Greene said (7/22/2011):
</p>
<p>
I'm currently working on processing large graphs representing object
relations in a program.
</p>
<p>
One aspect I'm interested in is the number of cycles, and how many
nodes are present in cycles.
</p>
<p>
However, the standard nx.simple_cycles() takes a very long time on my
graphs (multiple days).
</p>
<p>
But, if I create the strongly connected components, then iterate over
all of the components, generating the cycles from them, the algorithm
is significantly faster. The 46,000 node graph that takes multiple
days with nx.simple_cycles takes about 5 minutes with my method.
</p>
<p>
I think the reason is in the simple_cycles method:
</p>
<pre class="wiki"> ordering=dict(zip(G,range(len(G))))
for s in ordering:
# Build the subgraph induced by s and following nodes in the ordering
subgraph = G.subgraph(node for node in G
if ordering[node] >= ordering[s])
# Find the strongly connected component in the subgraph
# that contains the least node according to the ordering
strongcomp = nx.strongly_connected_components(subgraph)
</pre><p>
It seems to me that this is generating the strongly connected
components far too often, which can be costly in a large graph.
</p>
<p>
Also, because of the nature of strongly connected components, no
simple cycle should exist between two distinct components. So, if
instead of
</p>
<p>
<tt>nx.simple_cycles(G) </tt>
</p>
<p>
I do
</p>
<pre class="wiki">s_components = nx.strongly_connected_components(G)
cycles = []
for s_component in s_components:
if len(s_component) == 1:
continue
else:
for cycle in nx.simple_cycles(component):
cycles.append(cycle)
</pre><p>
Is there any flaw in this? It is also much faster for the graphs I am
working on, and seems like it would be faster in general, for any
graph with at least a few strongly connected components.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/613#changelog
https://networkx.lanl.gov/trac/ticket/619
https://networkx.lanl.gov/trac/ticket/619#619: _find_entering_edge in mincost.py does not work for degenerate treesThu, 11 Aug 2011 13:11:14 GMTmichael.osullivan@…<p>
When trying to solve a network flow problem using networkx.algorithms.flow.network_simplex, I encountered a problem when a node seemed to disappear from the basis tree. I looked into the code and reaslied that the _find_entering_edge function in networkx\algorithms\flow\mincost.py did not cater for degenerate bases/trees. The function is given below with the problem indicated:
</p>
<p>
def _find_entering_edge(H, c, capacity = 'capacity'):
</p>
<blockquote>
<p>
"""Find an edge which creates a negative cost cycle in the actual
tree solution.
</p>
</blockquote>
<blockquote>
<p>
The reduced cost of every edge gives the value of the cycle
obtained by adding that edge to the tree solution. If that value is
negative, we will augment the flow in the direction indicated by
the edge. Otherwise, we will augment the flow in the reverse
direction.
</p>
</blockquote>
<blockquote>
<p>
If no edge is found, return and empty tuple. This will cause the
main loop of the algorithm to terminate.
"""
newEdge = ()
for u, v, d in H.edges_iter(data = True):
</p>
<blockquote>
<p>
if d.get('flow', 0) == 0: < if tree is degenerate then
</p>
<blockquote>
<p>
if c[(u, v)] < 0: < its flow is 0 and c[(u, v)]
</p>
<blockquote>
<p>
newEdge = (u, v) < might be < 0 by numerical error
break < so (u, v) enters when it is
</p>
</blockquote>
</blockquote>
<p>
else: < already in the tree
</p>
<blockquote>
<p>
if capacity in d:
</p>
<blockquote>
<p>
if (d.get('flow', 0) == d[capacity]
</p>
<blockquote>
<p>
and c[(u, v)] > 0):
newEdge = (u, v)
break
</p>
</blockquote>
</blockquote>
</blockquote>
</blockquote>
</blockquote>
<p>
return newEdge
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/619#changelog
https://networkx.lanl.gov/trac/ticket/621
https://networkx.lanl.gov/trac/ticket/621#621: k_path centralityFri, 12 Aug 2011 22:51:11 GMTfranckkalala<p>
<a class="extlink" href="http://research.microsoft.com/enus/projects/ldg/a03alahakoon.pdf"><span class="icon"></span>http://research.microsoft.com/enus/projects/ldg/a03alahakoon.pdf</a>
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/621#changelog
https://networkx.lanl.gov/trac/ticket/625
https://networkx.lanl.gov/trac/ticket/625#625: Add flow based connectivity and cutsets functionsSun, 21 Aug 2011 17:34:49 GMTjtorrents<p>
All these functions are build around Loïc's nice implementation of the Ford and Fulkerson algorithm for maximum flow. They should work for both directed and undirected graphs. Connectivity functions are well documented in the literature (see references and docstrings) and use the current implementation of maxflow.py. The directed case is not covered in deep in the references. The adaptation is straightforward, but it should be reviewed.
</p>
<p>
The (vertex and edge) cutset functions need a modification of the ford_fulkerson function: to compute the cutset we need the residual network after finding the maximum flow. The patch <tt>maxflow_cutset.patch</tt> adds an auxiliary function that computes the cutset, a parameter to the ford_fulkerson function to optionally return the cutset instead of the flow_dict and a new function <tt>cut_set</tt> that returns only the cutset. I wasn't able to find a proper reference for the algorithm for computing the cutset from the residual network, but it is nicely explained in (3, the part with the diagrams with yellow and blue nodes).
</p>
<p>
Global minimim cutset functions are analog to connectivity functions, so they share a lot of code. I'm not sure of the best way to integrate them, an alternative approach would be to compute always the cutset and, for connectivity functions, return its length.
</p>
<p>
Regarding names (which is always hard), I've used <tt>global_vertex_connectivity</tt> for connectivity of the whole graph and <tt>vertex_connectivity</tt> for local st connectivity. But in the case of cuts I've used <tt>minimum_vertex_cutset</tt> for a global minimum cut and <tt>minimum_st_vertex_cutset</tt> for local st minimum cuts. So, the names for cutset are ugly and long and inconsistent with connectivity ones. Suggestions are very welcome.
</p>
<p>
References
</p>
<p>
(1) AbdolHossein Esfahanian. Connectivity Algorithms.
<a class="extlink" href="http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf"><span class="icon"></span>http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf</a>
</p>
<p>
(2) Kammer, Frank and Hanjo Taubig. Graph Connectivity. in Brandes and Erlebach, 'Network Analysis: Methodological Foundations', Lecture Notes in Computer Science, Volume 3418, SpringerVerlag, 2005.
<a class="extlink" href="http://www.informatik.uniaugsburg.de/thi/personen/kammer/Graph_Connectivity.pdf"><span class="icon"></span>http://www.informatik.uniaugsburg.de/thi/personen/kammer/Graph_Connectivity.pdf</a>
</p>
<p>
(3) <a class="extlink" href="http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow"><span class="icon"></span>http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow</a>
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/625#changelog
https://networkx.lanl.gov/trac/ticket/627
https://networkx.lanl.gov/trac/ticket/627#627: Label Propagation Algorithm for community detectionSun, 28 Aug 2011 23:14:44 GMTaric<p>
From networkxdevel:http://groups.google.com/group/networkxdevel/browse_thread/thread/2751c28efef84461
</p>
<p>
Tyler Rush via googlegroups.com to networkxdevel
show details Aug 27 (1 day ago)
Hi,
</p>
<p>
I wrote an LPA community detection algorithm (based off of 'Community Detection via SemiSynchronous Label Propagation Algorithms' Cordasco and Gargano, 2011), made use of networkx, and thought I'd donate the resulting code to the networkx project. The code is attached, so do what you will with it.
</p>
<p>
Sorry that I don't have any time right now to enhance the code: incorporate it into networkx source or use other LPA methods as specified in the aforementioned paper and also the original paper, 'Near linear time algorithm to detect communities in largescale networks' by Raghavan et al.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/627#changelog
https://networkx.lanl.gov/trac/ticket/639
https://networkx.lanl.gov/trac/ticket/639#639: Mistake in computation of average neighbor degree for directed networksTue, 27 Sep 2011 11:33:57 GMTOleguer Sagarra <oleguer.sagarra@…><p>
There is a problem in the algorithm to compute the negihbor degree (and average neighbor degree) for directed networks. The thing is that as networkx is based on a dict of dicts one may follow the neighbors of a node "forward" but not "backwards", meaning that with the functions such as G.in_degree(G[n]) one lists the incoming degree of the neighbors of the node "n", neighbors meaning destination of directed edges starting at node n. For all this, the normalization factor used is wrong. Additionally, it has some bugs with division over zero values.
</p>
<p>
These features need to be better redefined for various reasons:
</p>
<p>
a) With directed networks one can compute 4 types of features divided into two subgroups:
</p>
<blockquote>
<p>
a.1) For the neighbors of a node n (by neighbors meaning ending points of directed edges starting at node n) one can compute the Incoming our outgoing degree of a node.
a.2) For all predecessors of node n (meaning all sources of edges finishing in node n) one can compute the very same thing.
</p>
</blockquote>
<p>
b) Additionally, accounting for the average connectivity (or average neighbor degree as a function of degree of a node) things get messy, because then one may compute 8 different features divided into two groups, providing different information:
</p>
<blockquote>
<p>
b.1) Consider all the neighbors (defined earlier) of node n. Consider all the nodes n in the net. For each node n compute the (indegree, outdegree) of their neighbors, then average over all n nodes of (indegree, outdegree) 'k'.
</p>
</blockquote>
<blockquote>
<p>
b.2) The same for predecessors of degree n.
</p>
</blockquote>
<p>
The current code can be adapted to do so, using the function G.reverse() to overcome the difficulty in quickly computing the predecessors of a node while keeping the code structure. But the documentation need to be rewritten and the normalization of the averages redone.
</p>
<p>
Reference : Serrano, M.A., Maguitman, A., Boguna, M., Fortunato, S. & Vespignani, A. Decoding the structure of the WWW: facts versus sampling biases. Main 10 (2005).at <<a class="extlink" href="http://arxiv.org/abs/cs/0511035"><span class="icon"></span>http://arxiv.org/abs/cs/0511035</a>>
</p>
<p>
Simple example showing what I mean:
Case 1: Error in normalization division by 0
</p>
<p>
In <a class="changeset" href="https://networkx.lanl.gov/trac/changeset/1/networkxsvnarchive" title="initial svn layout">[1]</a>: import networkx as nx
</p>
<p>
In <a class="changeset" href="https://networkx.lanl.gov/trac/changeset/2/networkxsvnarchive" title="python interface to graphviz, initial directory
">[2]</a>: G=nx.<a class="missing wiki">DiGraph?</a>()
</p>
<p>
In <a class="changeset" href="https://networkx.lanl.gov/trac/changeset/3/networkxsvnarchive" title="projects area
">[3]</a>: G.add_edges_from((<a class="source" href="https://networkx.lanl.gov/trac/log/networkxsvnarchive/?revs=12">[1,2]</a>,<a class="source" href="https://networkx.lanl.gov/trac/log/networkxsvnarchive/?revs=1%2C3">[1,3]</a>,<a class="source" href="https://networkx.lanl.gov/trac/log/networkxsvnarchive/?revs=1%2C4">[1,4]</a>))
</p>
<p>
In <a class="changeset" href="https://networkx.lanl.gov/trac/changeset/6/networkxsvnarchive" title="cvsignore properties added
">[6]</a>: nx.average_in_degree_connectivity(G)
</p>
<hr />
<p>
<a class="missing wiki">ZeroDivisionError?</a> Traceback (most recent call last)
/Users/ugalss/<ipythoninput6<a class="missing changeset" rel="nofollow" title="No changeset e2e455d286f8 in the repository">e2e455d286f8</a>> in <module>()
</p>
<hr />
<p>
/opt/local/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/sitepackages/networkx1.5py2.7.egg/networkx/algorithms/neighbor_degree.pyc in average_in_degree_connectivity(G, nodes, weighted)
</p>
<blockquote>
<p>
205 raise nx.NetworkXError("Not defined for undirected graphs.")
206 degree_method = G.in_degree
</p>
</blockquote>
<p>
> 207 return _avg_deg_conn(G, degree_method, nodes=nodes, weighted=weighted)
</p>
<blockquote>
<p>
208 average_in_degree_connectivity.<span class="underline">doc</span>=average_degree_connectivity.<span class="underline">doc</span>
209
</p>
</blockquote>
<p>
/opt/local/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/sitepackages/networkx1.5py2.7.egg/networkx/algorithms/neighbor_degree.pyc in _avg_deg_conn(G, degree_method, nodes, weighted)
</p>
<blockquote>
<p>
141 dc[k]=avg
142 if avg > 0:
</p>
</blockquote>
<p>
> 143 dc[k]/=dnorm[k]
</p>
<blockquote>
<p>
144 return dc
145
</p>
</blockquote>
<p>
<a class="missing wiki">ZeroDivisionError?</a>: float division by zero
</p>
<p>
Case 2: Wrong computation of neighbor degree (incoming):
</p>
<p>
In <a class="changeset" href="https://networkx.lanl.gov/trac/changeset/7/networkxsvnarchive" title="Images were corrupted? Why?
">[7]</a>: G.add_edges_from((<a class="source" href="https://networkx.lanl.gov/trac/log/networkxsvnarchive/?revs=23">[2,3]</a>,<a class="source" href="https://networkx.lanl.gov/trac/log/networkxsvnarchive/?revs=34">[3,4]</a>,<a class="source" href="https://networkx.lanl.gov/trac/log/networkxsvnarchive/?revs=2%2C4">[4,2]</a>))
In <a class="changeset" href="https://networkx.lanl.gov/trac/changeset/8/networkxsvnarchive" title="Path names to lowercase
">[8]</a>: nx.average_neighbor_in_degree(G)
Out<a class="changeset" href="https://networkx.lanl.gov/trac/changeset/8/networkxsvnarchive" title="Path names to lowercase
">[8]</a>: {1: 6.0, 2: 1.0, 3: 1.0, 4: 1.0} # This is wrong. The average indegree should be 2 for neighbors of node 1.
</p>
<p>
I attach a new version of neighbor_degree.py with proposed (and commented) changes...
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/639#changelog
https://networkx.lanl.gov/trac/ticket/640
https://networkx.lanl.gov/trac/ticket/640#640: Pearson r calculation for all possible pairs (in in, out out, out in, in out)Tue, 27 Sep 2011 12:17:08 GMTOleguer Sagarra <oleguer.sagarra@…><p>
As done in the reference given at the end of the note, I propose to add to the module: networkx.mixing the following features:
</p>
<p>
For directed networks add the option to compute the 'r' coefficient (function networkx.algorithms.mixing.degree_pearsonr) of pairs (InIn, OutIn, OutOut, InOut)
</p>
<ul><li>For weighted networks add the option to compute the r weighted degree coefficient
</li><li>For directed weighted networks add both.
</li></ul><p>
I add a proposal to apply the changes...
</p>
<p>
Reference:
Foster, J.G., Foster, D.V., Grassberger, P. & Paczuski, M. Edge direction and the structure of networks. Proceedings of the National Academy of Sciences of the United States of America 107, 1081520 (2010).
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/640#changelog
https://networkx.lanl.gov/trac/ticket/641
https://networkx.lanl.gov/trac/ticket/641#641: Add flow betweenness centralityTue, 27 Sep 2011 12:53:34 GMTaric<p>
Add maxflow betweenness centrality and mincost maxflow betweenness centrality. See
Centrality Indices, Koschutzki, D. et al., U. Brandes and T. Erlebach (eds.), Network Analysis: Methodological Foundations. Berlin: Springer, 2005.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/641#changelog
https://networkx.lanl.gov/trac/ticket/642
https://networkx.lanl.gov/trac/ticket/642#642: max_flow_min_cost/network_simplex should support disconnected graphsTue, 27 Sep 2011 12:55:54 GMTaric<p>
The current network_simplex() doesn't support disconnected graphs.
It would be useful (required) for the mincost maxflow betweenness algorithm to work <a class="assigned ticket" href="https://networkx.lanl.gov/trac/ticket/641" title="enhancement: Add flow betweenness centrality (assigned)">#641</a>.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/642#changelog
https://networkx.lanl.gov/trac/ticket/651
https://networkx.lanl.gov/trac/ticket/651#651: Implement ChuLiu/Edmonds algorithmFri, 04 Nov 2011 14:33:33 GMThectorvd@…<p>
The wikipedia article for MST states:
</p>
<p>
"For <strong>directed graphs</strong>, the minimum spanning tree problem is called the
Arborescence problem and can be solved in quadratic time using the
ChuLiuEdmonds algorithm."
</p>
<p>
<a class="extlink" href="http://en.wikipedia.org/wiki/Edmonds'_algorithm"><span class="icon"></span>http://en.wikipedia.org/wiki/Edmonds'_algorithm</a>
</p>
<p>
This is currently not implemented in networkx.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/651#changelog
https://networkx.lanl.gov/trac/ticket/655
https://networkx.lanl.gov/trac/ticket/655#655: Restructure names of readwrite modulesMon, 28 Nov 2011 03:31:24 GMTaric<p>
Consider changing names of graph readers and writers to standardize in modules like this:
</p>
<div class="code"><pre> nx<span class="o">.</span>graphml<span class="o">.</span>read<span class="p">(</span>path<span class="p">)</span>
nx<span class="o">.</span>graphml<span class="o">.</span>write<span class="p">(</span>path<span class="p">)</span>
</pre></div><p>
Then we could optionally import some modules if we want and access them with e.g.
</p>
<pre class="wiki">>>> from networkx import graphml
>>> G = graphml.read(path)
</pre>Resultshttps://networkx.lanl.gov/trac/ticket/655#changelog
https://networkx.lanl.gov/trac/ticket/662
https://networkx.lanl.gov/trac/ticket/662#662: Add graph coarsening functionsWed, 07 Dec 2011 19:24:12 GMTaric<p>
Add functions to generate "coarse" graphs.
See <a class="closed ticket" href="https://networkx.lanl.gov/trac/ticket/634" title="task: refactor spectrum.py (closed: fixed)">#634</a> and code at <a class="attachment" href="https://networkx.lanl.gov/trac/attachment/ticket/643/multiscale.py" title="Attachment 'multiscale.py' in Ticket #643">attachment:ticket:643:multiscale.py</a><a class="tracrawlink" href="https://networkx.lanl.gov/trac/rawattachment/ticket/643/multiscale.py" title="Download"></a>
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/662#changelog
https://networkx.lanl.gov/trac/ticket/663
https://networkx.lanl.gov/trac/ticket/663#663: Add knot algorithmWed, 07 Dec 2011 21:40:08 GMTrachel.bobbins@…<p>
A knot in a directed graph is a collection of vertices and edges with the property that every vertex in the knot has outgoing edges, and all outgoing edges from vertices in the knot terminate at other vertices in the knot.
</p>
<p>
There should be an algorithm that detects whether a knot exists in a directed graph.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/663#changelog
https://networkx.lanl.gov/trac/ticket/669
https://networkx.lanl.gov/trac/ticket/669#669: triangles, clustering coefficent for directed graphsMon, 02 Jan 2012 02:11:54 GMTanonymous<p>
based on Newmann book Networks: An Introduction (2010) one can count triangles see chapter 7.9 : "It is however possible to generalize transitivity to take account of directed links. If we have a directed relation between vertices such as “u likes v” then we can say that a triple of vertices is closed or transitive if u likes v, v likes w, and also u likes w. (Note that there are many distinct ways for such a triple to be transitive, depending on the directions of the edges. The example given here is only one of six different possibilities.) One can calculate a clustering coefficient or fraction of transitive triples in the obvious fashion for the directed case, counting all directed paths of length two that are closed and dividing by the total number of directed paths of length two."
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/669#changelog
https://networkx.lanl.gov/trac/ticket/685
https://networkx.lanl.gov/trac/ticket/685#685: bug in from_pydot with subgraphsWed, 08 Feb 2012 05:30:21 GMTjseabold<p>
The nodes in subgraphs in pydot were not properly traversed. Attached you can find a fix for this. To replicate the problem, you can do run the code found here:
</p>
<p>
<a class="extlink" href="http://www.pastie.org/3338627"><span class="icon"></span>http://www.pastie.org/3338627</a>
</p>
<p>
As you can see there graph.node does not have the custom attribute information for all the nodes.
</p>
<p>
You can find a git patch attached that corrects this.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/685#changelog
https://networkx.lanl.gov/trac/ticket/687
https://networkx.lanl.gov/trac/ticket/687#687: Cutoff distance in centrality algorithmsMon, 13 Feb 2012 09:20:13 GMTgil.jorge@…<p>
To provide the option for a cutoff distance in the network centrality algorithms (degree, closeness and betweenness). This is already available in the general shortest path algorithms.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/687#changelog
https://networkx.lanl.gov/trac/ticket/688
https://networkx.lanl.gov/trac/ticket/688#688: directed clustering coefficientTue, 14 Feb 2012 14:34:10 GMTvhatzopoulos@…<p>
The directed clustering coefficient was introduced in
'Clustering in complex directed networks'
</p>
<blockquote>
<p>
Phy.Rev.E 76, 026107 (2007)
</p>
</blockquote>
<p>
This coefficient can be implemented both for weighted and unweighted versions.
</p>
<p>
The coefficient can be further subdivided into four components 'cycle','middle','in','out', when taking into account the direction of edges and the isomorphisms of all possible triangles.
</p>
<p>
A function signature could take the form directed_clustering(G,nodes=None,weight=None,type)
with type:string('cycle','middle','in','out')
</p>
<p>
I am willing to provide a draft or assist with any more information.
Thanks for your time, Vasilis
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/688#changelog
https://networkx.lanl.gov/trac/ticket/691
https://networkx.lanl.gov/trac/ticket/691#691: Canonical labellingTue, 21 Feb 2012 10:24:56 GMTflorian.goebels@…<p>
I would like to have a method that returns the canonical labelling for a given graph.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/691#changelog
https://networkx.lanl.gov/trac/ticket/692
https://networkx.lanl.gov/trac/ticket/692#692: Dominators and Dominator treesTue, 21 Feb 2012 10:47:44 GMTgpellegrino@…<p>
Hi all,
</p>
<p>
I have a directed graph G=(V,E) with source s \in V and sink t \in V. I'd need to calculate:
1) the dominator tree of G, and
2) the set of dominators of each n \in N where N \subseteq V
</p>
<p>
It would be great for me to have a little help on this from networkx.
</p>
<p>
Despite of the direct solution, there are two better approaches:
</p>
<ul><li>"A Simple, Fast Dominance Algorithm" by Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy (<a class="extlink" href="http://delivery.acm.org/10.1145/360000/357071/p121lengauer.pdf?ip=155.56.68.217&acc=ACTIVE%20SERVICE&CFID=67214941&CFTOKEN=14735343&__acm__=1329819099_4b02f8ad00f486a7d1a332230d14d64e"><span class="icon"></span>http://delivery.acm.org/10.1145/360000/357071/p121lengauer.pdf?ip=155.56.68.217&acc=ACTIVE%20SERVICE&CFID=67214941&CFTOKEN=14735343&__acm__=1329819099_4b02f8ad00f486a7d1a332230d14d64e</a>)
</li><li>"A fast algorithm for finding dominators in a flowgraph" by Lengauer Thomas and Tarjan Robert Endre (<a class="extlink" href="http://www.hipersoft.rice.edu/grads/publications/dom14.pdf"><span class="icon"></span>http://www.hipersoft.rice.edu/grads/publications/dom14.pdf</a>)
</li></ul><p>
Also, I've found that the Boost libraries provide an implementation of the dominator tree calculated with the Lengauer Tarjan algorithm (<a class="extlink" href="http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/lengauer_tarjan_dominator.htm"><span class="icon"></span>http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/lengauer_tarjan_dominator.htm</a>).
</p>
<p>
BR,
</p>
<p>
Giancarlo
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/692#changelog
https://networkx.lanl.gov/trac/ticket/700
https://networkx.lanl.gov/trac/ticket/700#700: Approximation algorithms in NetworkXWed, 29 Feb 2012 04:17:12 GMTnick.mancuso<p>
Approximation algorithms for NPHard graph/network problems are quite useful in practice. I have a small library of approximation algorithms that would be better put to use in NetworkX rather than a separate library. The current code is located here <a class="extlink" href="https://bitbucket.org/nmancuso/apxa"><span class="icon"></span>https://bitbucket.org/nmancuso/apxa</a>. The code is currently supported with tests and documentation. Some of the shorter algorithms can easily be merged into NetworkX, while a few rely on a custom priority queue class that might need more input from developers.
</p>
<p>
But before I begin creating tickets for merging in the code, how would the developers like it structured? Should there be a separate module (like bipartite) or should it coincide with the regular algorithms list? For example, I have a greedy maximal matching algorithm that serves as a basis for many 2OPT algorithms. That could go sidebyside with the maximum matching function.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/700#changelog
https://networkx.lanl.gov/trac/ticket/703
https://networkx.lanl.gov/trac/ticket/703#703: Add two random graph generators geared specifically to model online social networksTue, 13 Mar 2012 10:41:55 GMTadelbert_chang@…<p>
Abstract/paper here: <a class="extlink" href="http://www.cs.ucsb.edu/~ravenben/publications/abstracts/socialmodelwww10.html"><span class="icon"></span>http://www.cs.ucsb.edu/~ravenben/publications/abstracts/socialmodelwww10.html</a>
</p>
<p>
Add modified Nearest Neighbor and Random Walk as described in the publication which have been shown to reflect real online social network graph structures, assuming properly tweaked parameters.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/703#changelog
https://networkx.lanl.gov/trac/ticket/706
https://networkx.lanl.gov/trac/ticket/706#706: Diffusion model implementationSat, 17 Mar 2012 12:52:27 GMThhchen@…<p>
Two famous diffusion models are implemented: Independent Cascade (IC) model and Linear Threshold (LT) model.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/706#changelog
https://networkx.lanl.gov/trac/ticket/710
https://networkx.lanl.gov/trac/ticket/710#710: Optionally return residual graph and maybe also the cut in ford_fulkersonFri, 30 Mar 2012 15:07:53 GMTjtorrents<p>
Given that ford_fulkerson requires a fair amount of time to compute, and that its result and byproducts can be used for many things, I think that we should find a way to allow users to obtain whatever they want without forcing them to run ford_fulkerson more than once, or to perform additional computations for common stuff, such as obtaining the cut associated to a maximum flow.
</p>
<p>
See the discussion of ticket <a class="new ticket" href="https://networkx.lanl.gov/trac/ticket/625" title="enhancement: Add flow based connectivity and cutsets functions (new)">#625</a> (add flow based connectivity and cuts) for context and for a use case of the residual network. See also the patches to maxflow.py attached to that ticket (1) for two different approaches, the first adds a function to maxflow.py to compute the cut, the second only adds an option to optionally return the residual graph instead of the flow_dict.
</p>
<p>
I'm not sure which is the best approach. Also, we should consider that returning too many things from a single function can be confusing.
</p>
<p>
(1)
<a class="extlink" href="https://networkx.lanl.gov/trac/attachment/ticket/625/maxflow_cutset.patch"><span class="icon"></span>https://networkx.lanl.gov/trac/attachment/ticket/625/maxflow_cutset.patch</a>
<a class="extlink" href="https://networkx.lanl.gov/trac/attachment/ticket/625/maxflow_residual.patch"><span class="icon"></span>https://networkx.lanl.gov/trac/attachment/ticket/625/maxflow_residual.patch</a>
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/710#changelog
https://networkx.lanl.gov/trac/ticket/712
https://networkx.lanl.gov/trac/ticket/712#712: Add Global Reaching Centrality as measure of hierarchyThu, 05 Apr 2012 16:44:39 GMTconradlee<p>
Currently networkx implements one measure to measure how 'hierarchical' the structure of a directed graph is, located at networkx.hierarchy.flow_hierarchy.
</p>
<p>
Here I suggest another measure called "Global Reaching Centrality" suggested in the paper
</p>
<pre class="wiki">@article{mones2012hierarchy,
title={Hierarchy measure for complex networks},
author={Mones, E. and Vicsek, L. and Vicsek, T.},
journal={Arxiv preprint arXiv:1202.0191},
year={2012}
}
</pre><p>
I think the appropriate location for this measure is in networkx.hierarchy
</p>
<p>
This measure is defined for unweighted directed graphs, weighted directed graphs, and unweighted undirected graphs. I will at least implement the measure for both weighted and unweighted directed graphs.
</p>
<p>
I plan to submit this implementation as a pull request on the github repository.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/712#changelog
https://networkx.lanl.gov/trac/ticket/717
https://networkx.lanl.gov/trac/ticket/717#717: single_source_dijkstra algorithms with multiple target nodesMon, 16 Apr 2012 03:15:22 GMTt.r.etherington@…<p>
I need to apply Dijkstra's algorithm to calculate the shortest paths from a single source node to a subset of other nodes on what will be a large graph.
</p>
<p>
Given the subset of nodes I'm interested in are generally going to be quite "close" to the source node, I don't want to have to apply Dijkstra's algorithm across the whole graph as the shortest paths to my subset of nodes will probably be found well before the entire graph has been processed.
</p>
<p>
Presently I can use single_source_dijkstra and specify a target node to stop the algorithm once a single node from my subset has been reached, but doing this for each node in my subset of target nodes is also going to be computationally wasteful, as on each occasion Dijkstra's algorithm will have to start again from scratch, and will have to repeat the same initial searches multiple times.
</p>
<p>
I'm wondering if it would be possible to extend the "target" parameter of single_source_dijkstra to accept not just a single node, but also a list of nodes?
</p>
<p>
It would also be very useful to have such an option with single_source_dijkstra_path and single_source_dijkstra_path_length as I will have occasions when I only need the paths or the path lengths.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/717#changelog
https://networkx.lanl.gov/trac/ticket/720
https://networkx.lanl.gov/trac/ticket/720#720: Enhanced graphicality testingFri, 27 Apr 2012 20:48:29 GMTbrian.cloteaux@…<p>
I have implemented lineartime graphicality testing. I also implemented testing for directed, multigraphic, and pseudographic sequences. I also updated the HavelHakimi graph generator and added a directed HavelHakimi graph generator.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/720#changelog
https://networkx.lanl.gov/trac/ticket/725
https://networkx.lanl.gov/trac/ticket/725#725: doc/Makefile clean  please remove also generated file in doc/source/Sat, 12 May 2012 10:10:07 GMTmorph<p>
Hello,
preparing a new Debian package, I just noted that doc/Makefile will not remove generated files from doc/source, like
</p>
<blockquote>
<p>
'doc/source/networkxdocumentation.zip'
'doc/source/networkx_reference.pdf'
'doc/source/networkx_tutorial.pdf'
</p>
</blockquote>
<p>
just adding doc/source/*.pdf doc/source/*.zip to clean target would be enough
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/725#changelog
https://networkx.lanl.gov/trac/ticket/729
https://networkx.lanl.gov/trac/ticket/729#729: split_pass_through_node_digraphThu, 31 May 2012 16:49:35 GMTanonymous<pre class="wiki">def split_pass_through_node_digraph(G):
"""
The operation splits passthrough nodes (i.e. nodes with both incoming edges and outgoing edges), into pairs of nodes connected by a directed edges indicating the flow direction.
For each new edge, the tail node has all the incoming old edges and the head node has all the outgoing old edges.
For example, since B has both incoming and outgoing edge in the following digraph, B is split.::
A>B>C
The result is::
A>B:i>B:o>C
For a digraph like the following, since B has both incoming and outgoing edge, split it at B::
D+

v
A>B>C

+>E
we have::
D+

v
A>Bi>Bo>C

+>E
>>> G=nx.DiGraph()
>>> G.add_edge(1,2)
>>> G.add_edge(2,3)
>>> split_pass_through_node_digraph(G)
>>> print G.nodes()
['2:o', 1, 3, '2:i']
>>> print G.edges()
[('2:o', 3), (1, '2:i'), ('2:i', '2:o')]
>>> G=nx.DiGraph()
>>> G.add_edge(1, 3)
>>> G.add_edge(2, 3)
>>> G.add_edge(3, 4)
>>> G.add_edge(3, 5)
>>> split_pass_through_node_digraph(G)
>>> print G.nodes()
[1, 2, '3:i', 4, 5, '3:o']
>>> print G.edges()
[(1, '3:i'), (2, '3:i'), ('3:i', '3:o'), ('3:o', 4), ('3:o', 5)]
"""
if not G.is_directed():
raise nx.NetworkXError('This function only works for directed graphs.')
for n in list(G):
if G.in_degree(n) > 0 and G.out_degree(n) > 0:
n_i = ':'.join((str(n), 'i'))
n_o = ':'.join((str(n), 'o'))
for p in G.predecessors_iter(n):
G.add_edge(p, n_i)
for s in G.successors_iter(n):
G.add_edge(n_o, s)
G.remove_node(n)
G.add_edge(n_i, n_o)
</pre>Resultshttps://networkx.lanl.gov/trac/ticket/729#changelog
https://networkx.lanl.gov/trac/ticket/731
https://networkx.lanl.gov/trac/ticket/731#731: Adding multigraph handling to astar_path functionSun, 10 Jun 2012 11:20:36 GMTrtk08@…<p>
Version 1.6 astar_path function does not support shortest path calculation for multigraphs  a NetworkXError exception is thrown.
</p>
<p>
Finding the shortest path with an A Star algorithm for a multigraph currently requires reducing it to a graph with single (directed or not) edges between any two nodes. This is very inefficient, particularly if the graph in question is large.
</p>
<p>
I will modify the the astar_path function to handle path finding in multigraphs.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/731#changelog
https://networkx.lanl.gov/trac/ticket/732
https://networkx.lanl.gov/trac/ticket/732#732: Add function to produce edges in all simple pathsTue, 12 Jun 2012 21:29:08 GMTaric<p>
The all_simple_paths() function produces nodes. Add a function that produces the edges with optional data.
</p>
<p>
This ticket continues <a class="closed ticket" href="https://networkx.lanl.gov/trac/ticket/713" title="enhancement: Add function to generate all simple paths. (closed: fixed)">#713</a>.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/732#changelog
https://networkx.lanl.gov/trac/ticket/740
https://networkx.lanl.gov/trac/ticket/740#740: current flow betweenness centrality runtimeThu, 05 Jul 2012 15:41:42 GMTanonymous<p>
The runtime for current_flow_betweenness_centrality() seems to increase drastically with each new version of NetworkX. On a sparse graph of a few thousand nodes, NetworkX 1.4 computes the current flow betweenness in 6 minutes, NetworkX 1.6 finishes in 6 hours, and NetworkX 1.7 has taken over 20 hours without completing. On smaller graphs, they all produce the same results.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/740#changelog
https://networkx.lanl.gov/trac/ticket/741
https://networkx.lanl.gov/trac/ticket/741#741: fix/rewrite tests that rely on dictionary orderingFri, 06 Jul 2012 19:19:27 GMTaric<p>
Hash randomization is now switched on by default in Python3.3 (security fix). So tests that rely on ordering of Python dictionaries may fail.
</p>
<p>
For doctests this may mean using sorted() to order nodes or edges.
</p>
<p>
For the unit tests the helper functions introduced in <a class="closed ticket" href="https://networkx.lanl.gov/trac/ticket/658" title="enhancement: Add testing helper functions (closed: fixed)">#658</a> can be used  assert_edges_equal() and assert_nodes_equal(). Those functions can be improved or others added to aid in testing equality of nodes, edges, and graphs.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/741#changelog
https://networkx.lanl.gov/trac/ticket/742
https://networkx.lanl.gov/trac/ticket/742#742: Feature request: Multisource Inflow computation, as used e.g. for water flow on terrain graphsWed, 11 Jul 2012 10:04:45 GMThenrikblunck@…<p>
I want to suggest and check your future plans for providing flow computations with multiple sinks. Specifically, I am interestered in computing the incoming flow for each node in a graph, where the outgoing flow from each node may be simply defined, e.g. as 1 unit for each node in the graph.
Such computations are widely used, e.g. in rain and water flow analysis on terrain data graphs.
</p>
<p>
Many thanks in advance for any information on the matter!
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/742#changelog
https://networkx.lanl.gov/trac/ticket/744
https://networkx.lanl.gov/trac/ticket/744#744: Measures for weighted networksThu, 12 Jul 2012 18:08:44 GMTanonymous<p>
Upon detailed inspection I found out that networkx does not support any measures for weighted networks. A possibility could be to implement the algorithms in TNet of Tore Opsahl.
</p>
<p>
I have implemented a weighted version of density on group and individual level. I will try to contribute accordingly.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/744#changelog
https://networkx.lanl.gov/trac/ticket/745
https://networkx.lanl.gov/trac/ticket/745#745: Reciprocity for networks and nodesThu, 12 Jul 2012 18:08:45 GMTplotti@…<p>
I noticed that there is no reciprocity measure both for the overall network and for each node. Since this measure is quite handy it should be implemented.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/745#changelog
https://networkx.lanl.gov/trac/ticket/746
https://networkx.lanl.gov/trac/ticket/746#746: Bipartite Generic Weighted Projection Function Needs Node ArgsThu, 12 Jul 2012 18:08:47 GMTdan@…<p>
The generic weight function for bipartite projection could be improved by providing the two nodes as arguments and not just their neighborhoods.
</p>
<p>
The current weight function signature:
</p>
<pre class="wiki">getWeight(unbrs, vnbrs)
</pre><p>
Proposed weight function signature:
</p>
<pre class="wiki">getWeight(g, u, v, unbrs, vnbrs)
</pre><p>
This would give more flexibility when calculating edge weights. For example, if the edges in the original graph already had edge weights, they could be taken into account when calculating the new weights.
</p>
<pre class="wiki">def getWeight(g, u, v, unbrs, vnbrs):
weight = 0
for nbr in unbrs & vnbrs:
weight += g.edge[u][nbr]['weight'] + g.edge[v][nbr]['weight']
return weight
</pre><p>
Version: networkx1.7
</p>
<p>
File: networkx/algorithms/bipartite/projection.py:473
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/746#changelog
https://networkx.lanl.gov/trac/ticket/747
https://networkx.lanl.gov/trac/ticket/747#747: max_flow (ford_fulkerson) fails for simple graph with capacity 0 linkSat, 14 Jul 2012 18:54:23 GMTaric<pre class="wiki">import networkx as nx
G2=nx.Graph()
G2.add_edge('s','t',capacity=0)
print ("flow=",nx.max_flow(G2,'s','t'))
</pre><p>
produces the error
</p>
<pre class="wiki">Traceback (most recent call last):
File "nf.py", line 4, in <module>
print ("flow=",nx.max_flow(G2,'s','t'))
File "/home/aric/.local/lib/python2.7/sitepackages/networkx/algorithms/flow/maxflow.py", line 331, in max_flow
return ford_fulkerson(G, s, t, capacity=capacity)[0]
File "/home/aric/.local/lib/python2.7/sitepackages/networkx/algorithms/flow/maxflow.py", line 204, in ford_fulkerson
capacity=capacity)
File "/home/aric/.local/lib/python2.7/sitepackages/networkx/algorithms/flow/maxflow.py", line 80, in _create_flow_dict
flow[u][v] = abs(G[u][v][capacity]  H[v][u][capacity])
KeyError: 's'
</pre>Resultshttps://networkx.lanl.gov/trac/ticket/747#changelog
https://networkx.lanl.gov/trac/ticket/748
https://networkx.lanl.gov/trac/ticket/748#748: grabbing images from graphml ImageNodesWed, 18 Jul 2012 17:14:12 GMTzwerg44@…<p>
It would be nice to grab images from <a class="missing wiki">ImageNodes?</a> while reading graphml.
</p>
<p>
My solution in attachment.
see lines:
353376
495503
</p>
<p>
My platform: networkx 1.7, python27, windows
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/748#changelog
https://networkx.lanl.gov/trac/ticket/199
https://networkx.lanl.gov/trac/ticket/199#199: Draw multiple paths in a graph.Tue, 02 Dec 2008 19:33:43 GMTqrancik<p>
Hi all,
</p>
<p>
First of all  thanks a lot for NetworkX ! It is something I was looking for: easy to use, flexible and powerful.
</p>
<p>
I would like to contribute to the project. I have written a module to draw paths in a graph. I find it quite handy. It smoothly integrates with the existing drawing functions such as nx.draw().
</p>
<p>
To make the visualization nicer and easier to digest, the path corners are rounded with the help of quadratic and cube Bezier curves. Moreover, if two or more paths traverse the same edge, they are automatically shifted to make them all visible.
</p>
<p>
I attach the module and two figures generated with it. Looking forward to your comments!
</p>
<p>
qrancik
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/199#changelog
https://networkx.lanl.gov/trac/ticket/292
https://networkx.lanl.gov/trac/ticket/292#292: draw multigraphSat, 14 Nov 2009 23:47:33 GMTorlovics@…<p>
Networkx can not draw multidigraph (multiple edges).
nx.to_agraph() also has a bug, it does not work for multidigraph.
It says that problem is>
</p>
<blockquote>
<p>
File "/usr/lib/python2.6/sitepackages/networkx/drawing/nx_agraph.py", line 152, in to_agraph
</p>
<blockquote>
<p>
for u,v,key,edgedata in N.edges_iter(data=True):
</p>
</blockquote>
</blockquote>
<p>
<a class="missing wiki">ValueError?</a>: need more than 3 values to unpack
</p>
<p>
I think it would work if it has keys=True.
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/292#changelog
https://networkx.lanl.gov/trac/ticket/448
https://networkx.lanl.gov/trac/ticket/448#448: allow nodes with different shapes in a single graphWed, 13 Oct 2010 20:26:16 GMTrainer.hilscher@…<p>
follow the same approach as with node color ... list with shape information
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/448#changelog
https://networkx.lanl.gov/trac/ticket/743
https://networkx.lanl.gov/trac/ticket/743#743: Matplotlib.pylab drawingThu, 12 Jul 2012 18:08:43 GMTjjkoehler9@…<p>
Hi all,
</p>
<p>
I posted to the matplotlib users list concerning issues drawing to two figures (at different times) in wxPython. After some investigation the problem seemed to rest with networkx's integration with matplotlib.pylab. The trouble was with getting the correct figure. Someone in the discussion opened up the source code and suggested the possible cause. In the meantime, there is a workaround but he suggested it might be good to report this deficiency to you guys.
</p>
<p>
Here is the link to the discussion:
</p>
<p>
<a class="extlink" href="http://sourceforge.net/mailarchive/forum.php?thread_name=CAAXu2r%3DQ8M3z0HK_u7cL9%2BNPoCC%2B6fJWdn0LQVMoSyq%2BADT8Q%40mail.gmail.com&forum_name=matplotlibusers"><span class="icon"></span>http://sourceforge.net/mailarchive/forum.php?thread_name=CAAXu2r%3DQ8M3z0HK_u7cL9%2BNPoCC%2B6fJWdn0LQVMoSyq%2BADT8Q%40mail.gmail.com&forum_name=matplotlibusers</a>
</p>
<p>
The fourth post is the most relevant.
</p>
<p>
Thanks,
</p>
<p>
Josh
</p>
Resultshttps://networkx.lanl.gov/trac/ticket/743#changelog
https://networkx.lanl.gov/trac/ticket/117
https://networkx.lanl.gov/trac/ticket/117#117: Error building pygraphviz in WindowsWed, 20 Jun 2007 11:57:43 GMTmiquelet<p>
<em>When trying to install pygraphviz in Windows I have the following WARNING and ERROR:</em>
</p>
<p>
C:\pygraphviz0.34>python setup.py install
running install
running build
running build_py
running build_ext
building 'pygraphviz._graphviz' extension
warning: I don't know what to do with 'runtime_library_dirs': <a class="missing wiki">usr/lib/graphviz?</a>
error: don't know how to set runtime library search path for MSVC++
</p>
<p>
<em>I have MS Visual Studio 2003 installed
</em></p>
<p>
Thanks<em>
</em></p>
Resultshttps://networkx.lanl.gov/trac/ticket/117#changelog