I need an algorithm that can verify that a new edge insertion into a DAG won't create cycles

I guess the easiest way is to copy the dag and check if cycles were created
dag_copy = copy(dag)
dag_add(a, b, dag_copy)
if topological_sort(dag_copy) == null then
return false
else
dag = dag_copy

But it seems terribly ugly

>It's no tree either, if some node in branch A can connect to a node in branch B.
you're right sir, please forgive me I have dark skin.
why don't you recursively check the ending node is not an ancestor as I saif è_é

Just DFS a from b.

I wonder if this works:
1) for the graph, maintain a tree created by BFS or DFS
2) on adding new edge, find the From node of the edge on free and iterate up to root, checking if you don't find To node.
if you do find To node then it would create a cycle
proof needed: if you don't find To node then it would not create a cycle
3) somehow need to update the tree. doing BFS again is an option, but there might be something quicker. trees from BFS or DFS are not balanced anyway, so I guess nothing will give you O(log n) on this

Dude, stop being retarded, just insert the edge and then traverse the tree with any ordering you want.
If the program terminates, there's no cycle. As an optimization you could write some simple algorithm to determine if the travessal will terminate without even running it

So this?

there needs to be some O(1) way to update this with new edge
if you don't care for minimal length properties that new DFS would give you, just also maintain an information about what node is a root of the tree for each node
if To's and From's root is different then just add this path to the shadow tree as well and you keep the properties in O(1) way

>see thread like this
>feel like absolute brainlet

Attached: apu hammertime.gif (487x560, 898K)

No, the guy is using a topological sort. I'm saying just insert the node and check if travessal in preorder/postorder terminates. Much easier

well technically you don't even need to maintain the info of who is root, you can just iterate up on both nodes and see if they end on the same or different root
but what bothers me is that all of this is O(n), so the same worst-case complexity that DFS is

>check the ending node is not an ancestor
So walk the dag backwards?
I thought of that but I'm not completely sure I catch every case.
But it seems plausible.
Thanks, I will give it a shot.
It's very elegant if it works.

can't you do like uh union find

To check if inserting edge (u,v) will create a cycle in a DAG, how about checking if a path exists from v to u (bfs / dfs)
You can also maintain a graph in which all nodes contain a set of all reachable nodes, allowing you to check the insertion in O(1), but updating it on valid insertion can be a bitch.

no it doesn't work, crap
consider graph V:{A,B,C}, E:{A->B, A->C, B->C}, edge in guestion is C->B
shadow tree is only E:{A->B,A->C}
tree would have to omit the edge B->C, C is not parent of B in the shadow tree
same story with union-find. it just doesn't work for directed graphs I guess

how is the update not O(n^2)?

i think this runs into the counting to infinity problem when the graph is sufficiently large

same user,
my best guess is keeping a list/hash of every edge inserted into the graph but in reverse (heads become tails) and upon insertion see if your edge connects to a head in the reverse list earlier than your node? probably not 100% right but maybe another user can expand

Just see if they have common root, O(n) worst case.

Dynamically update the transitive closure
dl.acm.org/citation.cfm?id=1033207
And learn how to web search, I just found it on SO

Post the dag and node definition.

Go down, see if any vertex has lower topological ordering than A, starting with A of course. I think this has a linear time complexity.

function insert(nodea, nodeb)
{
if(firstIsAncestorOfSecond(nodeb, nodea))
return false;
else
{
nodea.addChild(nodeb);
return true;
}
}

function firstIsAncestorOfSecond(nodeb, nodea)
{
var parents = nodea.parents;

for(let i in parents)
if(parents[i] = nodeb)
return true;

for(let i in parents)
if(firstIsAncestorOfSecond(nodeb, parents[i])
return true;

return false;
}

And constant time complexity I think

>dag and node definition
Dictionaries/Maps and lists:
A: [B, C]
B: [C, E, F]
C: [D]
F: [C, C]

Lists can contain duplicates, cycles are forbidden.
I hope what I wrote is a dag and I didn't embarrass myself with a typo

there is only abstract, not the algorithms

That's an odd way to store a dag. Why not a bool matrix?
Anyway: from the new node, go to each possible other node whilst passing a (unique) set of traversed nodes. Return false at the first duplicate insert attempt. True else.

>Why not
I want the easiest representation with the least abstraction and transformation
>from the new node, go to each possible other node whilst passing a (unique) set of traversed nodes.
So walk backwards from the destination node towards the root (my dag is guaranteed to have only one root) like said?

Takes few minutes to familiarize yourself with graph theory concepts. Its not that hard once you understand the concepts.

en.wikipedia.org/wiki/Disjoint-set_data_structure#Applications