0
$\begingroup$

I have a directed graph, and some algorithms in networkx I want to apply to it. Unfortunately when I try to use the algorithms, python tells me that they're only implemented for undirected graphs so far, not directed graphs yet. I don't really want to reimplement these algorithms myself, is there a way to model my directed graph as an undirected graph?

Ultimately, my goal is to identify nodes in the graph that can be removed with minimum disruption. I could just perform reference counting, but this would fail because of cycles. My cycle detection algorithm is one that wasn't yet implemented for digraphs. Likewise for the community detection algorithms. My graph is relatively sparse: it has 1600 nodes but most node has less than 10 outgoing edges, and no node has more than 100.

$\endgroup$
  • 3
    $\begingroup$ It depends on what you're trying to achieve. You can certainly encode directed graphs as undirected ones but there's no reason to assume that the algorithms you're trying to implement will do anything sensible on that kind of encoding. For some problems (e.g., colouring problems, independent sets, etc.), it might be enough to just forget the orientation. For your question to be answerable, you'll need to give more details about what you're trying to do. $\endgroup$ – David Richerby Dec 9 '16 at 16:11
  • $\begingroup$ Okay, I've edited some more information about that in $\endgroup$ – Matt G Dec 9 '16 at 16:28
  • 2
    $\begingroup$ In terms of cycle detection, I guess you're only considering cycles where the edges are consistently oriented? (I.e., 12, 23, 13 wouldn't be a cycle.) In that case, it seems you would need to use specifically directed implementations, since it's hard to imagine any coding of directed graphs as undirected ones that doesn't also include cycles corresponding to inconsistently oriented cycles in the digraph. $\endgroup$ – David Richerby Dec 9 '16 at 16:55
  • 1
    $\begingroup$ Can you give a precise statement of the algorithmic task? I don't know what counts as "minimum disruption". As it stands the question isn't answerable because you haven't told us what the problem statement is. A good way to specify an algorithmic task is to tell us what the inputs are, and tell us what the desired output is. $\endgroup$ – D.W. Dec 9 '16 at 17:52
  • 1
    $\begingroup$ I think it's premature to ask for an algorithm to solve your problem if you haven't nailed down the problem statement yet. As a result I'm not sure that the question is answerable in its current form. $\endgroup$ – D.W. Dec 9 '16 at 20:40

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.