CODEWITHSUNDEEP
graph
Krzysztof Lewko
Krzysztof Lewko

Reputation: 1002

Building DAG from given edges

Let's have graph with N verticles with no edges.

Let's have list of edges:

x1 y1
x2 y2
x3 y3
.
.
.
xk yk

We'll have to process all edges from 1 to k. We'll have to say if x-th edge is making cycle in graph. If it's not, add it to the graph.

How to do something like this efficiently ? I mean not to check with DFS if x-th edge is making a cyclic graph everytime.

Is there something faster ? It's Polish SPOJ problem 

https://pl.spoj.pl/problems/XIWTPZF/

Thanks for any help. Chris

Upvotes: 0

Views: 692

Answers (2)

Lee Louviere
Lee Louviere

Reputation: 5262

Create a edge object. In the edge object you have two flags. A trace flag and an added flag. Build your object model from the list of edges you want to check. Add all edges, and connect edges that link using pointers in the edge object. When adding an edge to the model, link to the newly added edge all previously added edges that end at the newly added edge's start point.

When you test for an edge, first set it's added flag temporarily. Then trace recursively, setting trace flags as you go. If you collide upon an already traced edge, return false, and clear trace flags on the way out. The important part is that you do not trace down edges that have not set the added flag.

If you do not collide, you return true for every edge that terminates without hitting a trace flag.

If true is returned, move to the next edge in your ordered list. If false is returned, clear the added flag.

At the end of the tracing, check the added flags.

Seriously psuedo code at this location (so don't correct my C++ syntax): http://pastebin.com/dT2bFmqp

Upvotes: 1

Brian Stinar
Brian Stinar

Reputation: 1109

I'm not certain of an efficient way of doing this, in general. I think you could gain some efficiency by partitioning your graph into disjoint sets, but that really depends on the layout of your specific input graph on how much this will gain you. Additionally, you could take a few other shortcuts (like checking to see if the edge you are connecting to has any edges on it), but again that will depend on properties of your specific graph on whether or not it will help you much.

Here's the algorithm I came up with, which likely isn't as efficient as you'd like:

# No cycles on an empty list
for edge in edgeList:
    graph.addEdge(edge)
    cycles = detectCycle(graph)
    if cycles
        graph.removeEdge(edge)

Upvotes: 0

Related Questions