algorithm - How can I convert an undirected graph to directed graph with no cycle (Directed acyclic graph) -


i have undirected graph , wish transform directed graph. have few constraint, such having directed relations.

you trying build dag infrastructure graph. note directed graph dag if , if can topologically sorted.

so, let's go end beginning. first create topological sort, , connect nodes in way obey sort.

  • first, remove "undetermined" edges, , keep have directions for.
  • then, topological sort on graph , find topological sort (if there none, problem cannot solved given restrictions).
  • based on it, first last set direction of each edge such source node 1 lower topological sort.

time complexity of algorithm linear in number of nodes , edges.


Comments

Post a Comment

Popular posts from this blog

Is there a better way to structure post methods in Class Based Views -

i'm using class based views in django , never specify url in ajax calls , omit action parameter in form because know these requests go through post method of class based view. notice view - profile page make many requests depending on user updating on page - post method become convoluted , if/else mess example: def post(self, request, *args, **kwargs): # handle user changing available date if request.post.get('availabledate') != none: self.updateavailabledate(request) return jsonresponse({'result':'success'}) if request.post.get('newprojectname') != none: creative_user = creativeuserprofile.objects.get(id = request.user.id) project = project.create_project(creative_user, request.post['newprojectname']) project.save() return jsonresponse({'projectid': project.id }) if request.post.get('projectimage') != none , request.files['file']: proj...
Read more

reflection - How to access the object-members of an object declaration in kotlin -

say have following, nested object declaration: object father { val fathersfield = "value" object child { val childsfield = 3.141592654 } } when use reflection starting father , i'm able find field fathersfield no member referencing child instance. is possible find inner object declarations via reflection? , if so, how? use nestedclasses kotlin-reflect : father::class.nestedclasses.find { it.simplename == "child" } or, @s1m0nw1 suggested, use java reflection , convert class kclass .kotlin if needed: father::class.java.classes.first { it.simplename == "child" }.kotlin
Read more

php - Doctrine Query Builder Error on Join: [Syntax Error] line 0, col 87: Error: Expected Literal, got 'JOIN' -

i building shipping system ecommerce site using doctrine. have appropriate shipping methods , prices based on product , region data in checkout. i using following code querybuilder: $shippingpricereccords = $this->em->createquerybuilder() ->select('price') ->from('ordershippingprice', 'price') ->innerjoin('ordershippingmethod', 'method', 'price.fkordershippingmethod = method.id') ->innerjoin('ordershippingmethodregionmapping', 'map', 'map.fkordershippingmethod = method.id') ->where('price.fkproducttype = :fkproducttype') ->andwhere('price.fkbrand = :fkbrand') ->andwhere('map.fkregion = :fkregion') ->setparameters([ 'fkproducttype' => $fkproducttype, 'fkbrand' => $fkbrand, ...
Read more