Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.javascript > #32452 > unrolled thread

Backtracking algorithms and graph connection

Back to article view | Back to comp.lang.javascript

Contents

  Backtracking algorithms and graph connection jonas.thornvall@gmail.com - 2017-02-03 01:19 -0800
    Re: Backtracking algorithms and graph connection jonas.thornvall@gmail.com - 2017-02-03 01:53 -0800
    Re: Backtracking algorithms and graph connection Silvio <silvio@internet.com> - 2017-02-03 11:09 +0100
      Re: Backtracking algorithms and graph connection jonas.thornvall@gmail.com - 2017-02-03 03:28 -0800
    Re: Backtracking algorithms and graph connection "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-02-03 11:03 -0800
      Re: Backtracking algorithms and graph connection jonas.thornvall@gmail.com - 2017-02-03 17:16 -0800
        Re: Backtracking algorithms and graph connection jonas.thornvall@gmail.com - 2017-02-03 17:18 -0800
          Re: Backtracking algorithms and graph connection jonas.thornvall@gmail.com - 2017-02-03 17:32 -0800
            Re: Backtracking algorithms and graph connection jonas.thornvall@gmail.com - 2017-02-03 17:59 -0800
        Re: Backtracking algorithms and graph connection "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-02-04 10:26 -0800
          Re: Backtracking algorithms and graph connection jonas.thornvall@gmail.com - 2017-02-04 23:07 -0800

#32452 — Backtracking algorithms and graph connection

To check if a graph connected seem to be a pretty hard problem, i was thinking making chains of nodes linked connections, and then after the chains created check for interrelationships between the chains. So as one chain ends you start a new one and if any the nodes in the new chain link back to any other, you do not have to check anymore until the new chain broken is again. So as you progress the set of linked nodes get bigger and bigger.

So i only check if the new chain have any connection to the masterchain?

Does it seem as a reasonable approach, i can't come up with any faster.
What time complexity would such a chain backtracking algorithm have?

[toc] | [next] | [standalone]

#32453

Den fredag 3 februari 2017 kl. 10:20:06 UTC+1 skrev jonas.t...@gmail.com:
> To check if a graph connected seem to be a pretty hard problem, i was thinking making chains of nodes linked connections, and then after the chains created check for interrelationships between the chains. So as one chain ends you start a new one and if any the nodes in the new chain link back to any other, you do not have to check anymore until the new chain broken is again. So as you progress the set of linked nodes get bigger and bigger.
> 
> So i only check if the new chain have any connection to the masterchain?
> 
> Does it seem as a reasonable approach, i can't come up with any faster.
> What time complexity would such a chain backtracking algorithm have?

One problem i can see is that you will create not just one chain but alot of chains and if your unlucky they are not resolved until the last chain is inspected. Well they may not be resolved at all, but then the graph is not connected.

I have the first part done the chainer of nodes, but now i must make it handle more chains simultaneously and finally check for interconnections to build upon the masterchain of nodes.

[toc] | [prev] | [next] | [standalone]

#32454

On 02/03/2017 10:19 AM, jonas.thornvall@gmail.com wrote:
> To check if a graph connected seem to be a pretty hard problem, i was thinking making chains of nodes linked connections, and then after the chains created check for interrelationships between the chains. So as one chain ends you start a new one and if any the nodes in the new chain link back to any other, you do not have to check anymore until the new chain broken is again. So as you progress the set of linked nodes get bigger and bigger.
>
> So i only check if the new chain have any connection to the masterchain?
>
> Does it seem as a reasonable approach, i can't come up with any faster.
> What time complexity would such a chain backtracking algorithm have?
>

Look into breadth first and depth first searching algorithms. Are the 
graphs annotated, for example with XY locations or such? In that case 
look into prioritized breadth first (A*-akin) searching.

[toc] | [prev] | [next] | [standalone]

#32456

Den fredag 3 februari 2017 kl. 11:09:23 UTC+1 skrev Silvio:
> On 02/03/2017 10:19 AM, jonas.thornvall@gmail.com wrote:
> > To check if a graph connected seem to be a pretty hard problem, i was thinking making chains of nodes linked connections, and then after the chains created check for interrelationships between the chains. So as one chain ends you start a new one and if any the nodes in the new chain link back to any other, you do not have to check anymore until the new chain broken is again. So as you progress the set of linked nodes get bigger and bigger.
> >
> > So i only check if the new chain have any connection to the masterchain?
> >
> > Does it seem as a reasonable approach, i can't come up with any faster.
> > What time complexity would such a chain backtracking algorithm have?
> >
> 
> Look into breadth first and depth first searching algorithms. Are the 
> graphs annotated, for example with XY locations or such? In that case 
> look into prioritized breadth first (A*-akin) searching.

Each node (is an object/datatype) and have links/edges in a subarray, and each node do have a X,Y cordinade.

What I try to do forming chains seem like a depth approach. Second step is to find out the interconnections between them.

I have only programmed the first part making a chain.

function sort_connection()
{
   connected = true;
   var j = 0;
   var i = 0;
   var tempnode = 0;
   var tnode = new Array();
   //Så länge i är mindre än antal noder
   while(i < nodes)
   {
      //Så länge som k är mindre än antal element i "tnode array"
      for(var k = 0; k < tnode.length; k ++ )
      {
         //Jämför tnode=k med tempnode=0s länk j++ om lika hämta nästa länk  
         if (arr[tempnode].nodelinks[j] == tnode[k])
         {
            j ++ ;
         }
      }
      tnode.sort(compareNumeric);
      if (j > links)
      {
         t = 0;
         while (t == tnode[t])
         {
            t ++ ;
         }
         connected = false;
         if (arr[tempnode].nodelinks.length == 0)t ++ ;
         tempnode = t;
         tnode[tnode.length] = tempnode;
         printnode[i] = tempnode;
         i ++ ;
         j = 0;
      }
      else
      {
         tempnode = arr[tempnode].nodelinks[j];
         tnode[tnode.length] = tempnode;
         printnode[i] = tempnode;
         i ++ ;
         j = 0;
      }
     
   }
   return printnode;
}

[toc] | [prev] | [next] | [standalone]

#32459

jonas.t...@gmail.com wrote:
> To check if a graph connected seem to be a pretty hard problem, 

That depends on your definition of "hard"

> i was thinking making chains of nodes linked connections, and then after the chains created check for interrelationships between the chains. So as one chain ends you start a new one and if any the nodes in the new chain link back to any other, you do not have to check anymore until the new chain broken is again. So as you progress the set of linked nodes get bigger and bigger.
> 
> So i only check if the new chain have any connection to the masterchain?
> 
> Does it seem as a reasonable approach, i can't come up with any faster.

Just do a BFS/DFS on the graph and mark the the nodes visited. If every node is visited then the graph is connected.

> What time complexity would such a chain backtracking algorithm have?

O(|V| + |E|) with the BFS approach

[toc] | [prev] | [next] | [standalone]

#32460

Den fredag 3 februari 2017 kl. 20:03:28 UTC+1 skrev Michael Haufe (TNO):
> jonas.t...@gmail.com wrote:
> > To check if a graph connected seem to be a pretty hard problem, 
> 
> That depends on your definition of "hard"
> 
> > i was thinking making chains of nodes linked connections, and then after the chains created check for interrelationships between the chains. So as one chain ends you start a new one and if any the nodes in the new chain link back to any other, you do not have to check anymore until the new chain broken is again. So as you progress the set of linked nodes get bigger and bigger.
> > 
> > So i only check if the new chain have any connection to the masterchain?
> > 
> > Does it seem as a reasonable approach, i can't come up with any faster.
> 
> Just do a BFS/DFS on the graph and mark the the nodes visited. If every node is visited then the graph is connected.
> 
> > What time complexity would such a chain backtracking algorithm have?
> 
> O(|V| + |E|) with the BFS approach

I see that BFS is a linear approach and time complexity, and i realise my is much much faster. So it must be another approach.

I implement mine 2 or 3 times before with alot of grief, but maybe this time i have a better datastructure.

[toc] | [prev] | [next] | [standalone]

#32461

Den lördag 4 februari 2017 kl. 02:16:20 UTC+1 skrev jonas.t...@gmail.com:
> Den fredag 3 februari 2017 kl. 20:03:28 UTC+1 skrev Michael Haufe (TNO):
> > jonas.t...@gmail.com wrote:
> > > To check if a graph connected seem to be a pretty hard problem, 
> > 
> > That depends on your definition of "hard"
> > 
> > > i was thinking making chains of nodes linked connections, and then after the chains created check for interrelationships between the chains. So as one chain ends you start a new one and if any the nodes in the new chain link back to any other, you do not have to check anymore until the new chain broken is again. So as you progress the set of linked nodes get bigger and bigger.
> > > 
> > > So i only check if the new chain have any connection to the masterchain?
> > > 
> > > Does it seem as a reasonable approach, i can't come up with any faster.
> > 
> > Just do a BFS/DFS on the graph and mark the the nodes visited. If every node is visited then the graph is connected.
> > 
> > > What time complexity would such a chain backtracking algorithm have?
> > 
> > O(|V| + |E|) with the BFS approach
> 
> I see that BFS is a linear approach and time complexity, and i realise my is much much faster. So it must be another approach.
> 
> I implement mine 2 or 3 times before with alot of grief, but maybe this time i have a better datastructure.

Sorry was thinking wrong my approach is definitly linear.

[toc] | [prev] | [next] | [standalone]

#32462

Den lördag 4 februari 2017 kl. 02:18:16 UTC+1 skrev jonas.t...@gmail.com:
> Den lördag 4 februari 2017 kl. 02:16:20 UTC+1 skrev jonas.t...@gmail.com:
> > Den fredag 3 februari 2017 kl. 20:03:28 UTC+1 skrev Michael Haufe (TNO):
> > > jonas.t...@gmail.com wrote:
> > > > To check if a graph connected seem to be a pretty hard problem, 
> > > 
> > > That depends on your definition of "hard"
> > > 
> > > > i was thinking making chains of nodes linked connections, and then after the chains created check for interrelationships between the chains. So as one chain ends you start a new one and if any the nodes in the new chain link back to any other, you do not have to check anymore until the new chain broken is again. So as you progress the set of linked nodes get bigger and bigger.
> > > > 
> > > > So i only check if the new chain have any connection to the masterchain?
> > > > 
> > > > Does it seem as a reasonable approach, i can't come up with any faster.
> > > 
> > > Just do a BFS/DFS on the graph and mark the the nodes visited. If every node is visited then the graph is connected.
> > > 
> > > > What time complexity would such a chain backtracking algorithm have?
> > > 
> > > O(|V| + |E|) with the BFS approach
> > 
> > I see that BFS is a linear approach and time complexity, and i realise my is much much faster. So it must be another approach.
> > 
> > I implement mine 2 or 3 times before with alot of grief, but maybe this time i have a better datastructure.
> 
> Sorry was thinking wrong my approach is definitly linear.

So the linearity in my graph is that each node of course will be travered, and each node have links but my approach do not need travelse every edge/link of the node it settles when it find a new one, and that may make it faster it do not need to traverse all the edges/links of all the nodes.

I think that BFS traverse all edges? So if there is 1000's of edges/links from each node my algorithm will be a timesaver? Becuse it doesn't care it just form chains. And check the interconnections, it seem for bad and good my algorithm do not care about the underlying tree, just the viable chaining.

[toc] | [prev] | [next] | [standalone]

#32463

Den lördag 4 februari 2017 kl. 02:32:30 UTC+1 skrev jonas.t...@gmail.com:
> Den lördag 4 februari 2017 kl. 02:18:16 UTC+1 skrev jonas.t...@gmail.com:
> > Den lördag 4 februari 2017 kl. 02:16:20 UTC+1 skrev jonas.t...@gmail.com:
> > > Den fredag 3 februari 2017 kl. 20:03:28 UTC+1 skrev Michael Haufe (TNO):
> > > > jonas.t...@gmail.com wrote:
> > > > > To check if a graph connected seem to be a pretty hard problem, 
> > > > 
> > > > That depends on your definition of "hard"
> > > > 
> > > > > i was thinking making chains of nodes linked connections, and then after the chains created check for interrelationships between the chains. So as one chain ends you start a new one and if any the nodes in the new chain link back to any other, you do not have to check anymore until the new chain broken is again. So as you progress the set of linked nodes get bigger and bigger.
> > > > > 
> > > > > So i only check if the new chain have any connection to the masterchain?
> > > > > 
> > > > > Does it seem as a reasonable approach, i can't come up with any faster.
> > > > 
> > > > Just do a BFS/DFS on the graph and mark the the nodes visited. If every node is visited then the graph is connected.
> > > > 
> > > > > What time complexity would such a chain backtracking algorithm have?
> > > > 
> > > > O(|V| + |E|) with the BFS approach
> > > 
> > > I see that BFS is a linear approach and time complexity, and i realise my is much much faster. So it must be another approach.
> > > 
> > > I implement mine 2 or 3 times before with alot of grief, but maybe this time i have a better datastructure.
> > 
> > Sorry was thinking wrong my approach is definitly linear.
> 
> So the linearity in my graph is that each node of course will be travered, and each node have links but my approach do not need travelse every edge/link of the node it settles when it find a new one, and that may make it faster it do not need to traverse all the edges/links of all the nodes.
> 
> I think that BFS traverse all edges? So if there is 1000's of edges/links from each node my algorithm will be a timesaver? Becuse it doesn't care it just form chains. And check the interconnections, it seem for bad and good my algorithm do not care about the underlying tree, just the viable chaining.

Probably it is my storage structure of connections that make it viable, each node carry its own set of outgoing links/edges.

I do not need to traverse to make chains. The edges/links are attributes to the nodes.

  arr[m] ={nodelinks : []}

[toc] | [prev] | [next] | [standalone]

#32465

jonas.t...@gmail.com wrote:
> Michael Haufe (TNO):
> > jonas.t...@gmail.com wrote:

> > Just do a BFS/DFS on the graph and mark the the nodes visited. If every node is visited then the graph is connected.
> > 
> > > What time complexity would such a chain backtracking algorithm have?
> > 
> > O(|V| + |E|) with the BFS approach
> 
> I see that BFS is a linear approach and time complexity, and i realise my is much much faster. So it must be another approach.
> 
> I implement mine 2 or 3 times before with alot of grief, but maybe this time i have a better datastructure.

It is possible to be faster than linear, but there are a few constraints. I suggest buying a standard text on Algorithms. For example, Chapter 21 of: 

<https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844/ref=sr_1_1?s=books&ie=UTF8&qid=1486232373&sr=1-1&keywords=introduction+to+algorithms+third+edition>

"Data Structures for Disjoint Sets"

Simply speaking, stick with the BFS/DFS approach. It's easier to understand and implement and probably "good-enough" for your application.

[toc] | [prev] | [next] | [standalone]

#32469

Den lördag 4 februari 2017 kl. 19:26:15 UTC+1 skrev Michael Haufe (TNO):
> jonas.t...@gmail.com wrote:
> > Michael Haufe (TNO):
> > > jonas.t...@gmail.com wrote:
> 
> > > Just do a BFS/DFS on the graph and mark the the nodes visited. If every node is visited then the graph is connected.
> > > 
> > > > What time complexity would such a chain backtracking algorithm have?
> > > 
> > > O(|V| + |E|) with the BFS approach
> > 
> > I see that BFS is a linear approach and time complexity, and i realise my is much much faster. So it must be another approach.
> > 
> > I implement mine 2 or 3 times before with alot of grief, but maybe this time i have a better datastructure.
> 
> It is possible to be faster than linear, but there are a few constraints. I suggest buying a standard text on Algorithms. For example, Chapter 21 of: 
> 
> <https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844/ref=sr_1_1?s=books&ie=UTF8&qid=1486232373&sr=1-1&keywords=introduction+to+algorithms+third+edition>
> 
> "Data Structures for Disjoint Sets"
> 
> Simply speaking, stick with the BFS/DFS approach. It's easier to understand and implement and probably "good-enough" for your application.

http://anybase.co.nf/

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.javascript

csiph-web