| 624 | } |
| 625 | |
| 626 | QueryGraph **QueryGraph_ConnectedComponents |
| 627 | ( |
| 628 | const QueryGraph *qg |
| 629 | ) { |
| 630 | QGNode *n; // current node |
| 631 | QGNode **q = array_new(QGNode *, 1); // node frontier |
| 632 | void *seen; // has node been visited? |
| 633 | QueryGraph *g = QueryGraph_Clone(qg); // clone query graph |
| 634 | rax *visited; // dictionary of visited nodes |
| 635 | QueryGraph **connected_components; // list of connected components |
| 636 | |
| 637 | // at least one connected component (the original graph) |
| 638 | connected_components = array_new(QueryGraph *, 1); |
| 639 | |
| 640 | // as long as there are nodes to process |
| 641 | while(true) { |
| 642 | visited = raxNew(); |
| 643 | |
| 644 | // get a random node and add it to the frontier |
| 645 | QGNode *s = g->nodes[0]; |
| 646 | array_append(q, s); |
| 647 | |
| 648 | // as long as there are nodes in the frontier |
| 649 | while(array_len(q) > 0) { |
| 650 | n = array_pop(q); |
| 651 | |
| 652 | // mark n as visited |
| 653 | if(!raxInsert(visited, (unsigned char *)n->alias, strlen(n->alias), |
| 654 | NULL, NULL)) { |
| 655 | // we've already processed n |
| 656 | continue; |
| 657 | } |
| 658 | |
| 659 | // expand node N by visiting all of its neighbors |
| 660 | for(int i = 0; i < array_len(n->outgoing_edges); i++) { |
| 661 | QGEdge *e = n->outgoing_edges[i]; |
| 662 | seen = raxFind(visited, (unsigned char *)e->dest->alias, |
| 663 | strlen(e->dest->alias)); |
| 664 | if(seen == raxNotFound) array_append(q, e->dest); |
| 665 | } |
| 666 | |
| 667 | for(int i = 0; i < array_len(n->incoming_edges); i++) { |
| 668 | QGEdge *e = n->incoming_edges[i]; |
| 669 | seen = raxFind(visited, (unsigned char *)e->src->alias, |
| 670 | strlen(e->src->alias)); |
| 671 | if(seen == raxNotFound) array_append(q, e->src); |
| 672 | } |
| 673 | } |
| 674 | |
| 675 | // visited comprise the connected component defined by S |
| 676 | // remove all non-reachable nodes from current connected component. |
| 677 | // remove connected component from graph |
| 678 | QueryGraph *cc = QueryGraph_Clone(g); |
| 679 | uint node_count = QueryGraph_NodeCount(g); |
| 680 | for(uint i = 0; i < node_count; i++) { |
| 681 | void *reachable; |
| 682 | n = g->nodes[i]; |
| 683 | reachable = raxFind(visited, (unsigned char *)n->alias, |