1

I have some directed graph data where each each row represents one edge. I need to convert such graph data to tree data with python. For example my looks like this:

[{'source': 'a','target': 'b'},
 {'source': 'b','target': 'a'}
 {'source': 'a','target': 'c'}
 {'source': 'c','target': 'd'}
 {'source': 'd','target': 'a'}
 {'source': 'z','target': 'a'}]

Here the first node would be 'a'. Since 'b' has an edge with 'a', it resembles a cycle and in this case I want to rename it like 'a-prime' let's say. Also 'a' can have an edge with 'c' and 'c' have an edge with 'd'and the 'd' can send back to 'a' or even 'c' and again there is a cycle, so the last 'd' will be renamed as 'd-prime'. Last case would be when some random node appears like 'z' with 'a', but that one is fine as it is as it doesn't resemble a cycle. Here is what I tried:

    tmp =[]
    for x in data:
        tmp.append(x['source'])
        if x['target'] in tmp:
            x['target'] = x['target'] + '-prime'

But I realized this handles first case only and then I got stuck. I need somehow to trace each cycle..

Mikael Ken
  • 41
  • 1
  • 10
  • I'm sorry but I the formulation of your question is a bit vague. Which nodes do you want to rename? The ones that "make" the cycles? I mean, the ones that have a target on which you have already passed? – fedest Dec 13 '19 at 14:33
  • To sum it up: if there are cycles, rename last node that matches the source one – Mikael Ken Dec 13 '19 at 14:34
  • The problem you are trying to solve is a bit standard one. https://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph – Raj Dec 13 '19 at 14:34
  • @MikaelKen There is no first or last node in a loop. It just depends on the order of processing. – Raj Dec 13 '19 at 14:36
  • If I have a path like a -> b -> c->d -> a then this last a should become 'a-prime' (just renaming), first a stays the same – Mikael Ken Dec 13 '19 at 14:37
  • Does this answer your question? [How can I label a node that is the initial vertex in a cycle from graph data](https://stackoverflow.com/questions/59333807/how-can-i-label-a-node-that-is-the-initial-vertex-in-a-cycle-from-graph-data) – facehugger Dec 17 '19 at 00:53

0 Answers0