algorithm - graphs - Encontrar todos los ciclos en un gráfico dirigido

graph representations

Question

¿Cómo puedo encontrar (iterar) TODOS los ciclos en un gráfico dirigido desde / hacia un nodo dado?

Por ejemplo, quiero algo como esto:

A->B->A
A->B->C->A

pero no: B-> C-> B

Answer 1

¿No puedes hacer una pequeña función recursiva para atravesar los nodos?

readDiGraph( string pathSoFar, Node x)
{
if(NoChildren) MasterList.add( pathsofar + Node.name ) ;
foreach( child )
{
readDiGraph( pathsofar + "->" + this.name, child)
}
}

si tienes una tonelada de nodos, te quedarás sin pila

Answer 2

Antes que nada, realmente no quieres intentar encontrar literalmente todos los ciclos porque si hay 1, entonces hay un número infinito de ellos. Por ejemplo, ABA, ABABA, etc. O puede ser posible unir 2 ciclos en un ciclo de 8, etc., etc. El enfoque significativo es buscar todos los llamados ciclos simples, aquellos que no se cruzan excepto en el punto de inicio / finalización Entonces, si lo desea, puede generar combinaciones de ciclos simples.

Uno de los algoritmos de referencia para encontrar todos los ciclos simples en un gráfico dirigido es este: hacer un recorrido en profundidad de todas las rutas simples (las que no se cruzan a sí mismas) en el gráfico. Cada vez que el nodo actual tiene un sucesor en la pila, se descubre un ciclo simple. Consiste en los elementos de la pila que comienzan con el sucesor identificado y terminan en la parte superior de la pila. El primer recorrido de profundidad de todas las rutas simples es similar a la primera búsqueda en profundidad, pero no marca / registra nodos visitados que no sean los que se encuentran actualmente en la pila como puntos de detención.

El algoritmo de fuerza bruta anterior es terriblemente ineficiente y, además de eso, genera múltiples copias de los ciclos. Sin embargo, es el punto de partida de múltiples algoritmos prácticos que aplican diversas mejoras para mejorar el rendimiento y evitar la duplicación de ciclos. Me sorprendió descubrir hace algún tiempo que estos algoritmos no están disponibles en los libros de texto y en la web. Así que investigué e implementé 4 algoritmos y 1 algoritmo para ciclos en gráficos no dirigidos en una biblioteca Java de código abierto aquí: http://code.google.com/p/niographs/ .

Por cierto, ya que mencioné gráficos no dirigidos: el algoritmo para esos es diferente. Construya un árbol de expansión y luego cada borde que no forme parte del árbol forma un ciclo simple junto con algunos bordes en el árbol. Los ciclos encontrados de esta manera forman una llamada base de ciclo. Todos los ciclos simples se pueden encontrar combinando 2 o más ciclos básicos distintos. Para más detalles, ver, por ejemplo: http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf .

Answer 3

Comience en el nodo X y verifique todos los nodos secundarios (los nodos padre e hijo son equivalentes si no están dirigidos). Marque esos nodos secundarios como hijos de X. Desde cualquier nodo secundario A, marque sus hijos de ser hijos de A, X '', donde X'' está marcado como a 2 pasos de distancia). Si luego presionas X y lo marcas como un hijo de X '''', eso significa que X está en un ciclo de 3 nodos. Retroceder a sus padres es fácil (como está, el algoritmo no tiene soporte para esto, por lo que encontraría el padre que tenga X '').

Nota: Si el gráfico no está dirigido o tiene bordes bidireccionales, este algoritmo se vuelve más complicado, asumiendo que no desea atravesar el mismo borde dos veces durante un ciclo.

Answer 4

DFS desde el nodo de inicio s, realice un seguimiento de la ruta DFS durante el recorrido, y registre la ruta si encuentra un borde del nodo v en el camino a s. (v, s) es un borde posterior en el árbol DFS y, por lo tanto, indica un ciclo que contiene s.

Answer 5

En cuanto a su pregunta sobre el ciclo de permutación , lea más aquí: https://www.codechef.com/problems/PCYCLE

Puede probar este código (ingrese el tamaño y el número de dígitos):

# include<cstdio>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
int num[1000];
int visited[1000]={0};
int vindex[2000];
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
int t_visited=0;
int cycles=0;
int start=0, index;
while(t_visited < n)
{
for(int i=1;i<=n;i++)
{
if(visited[i]==0)
{
vindex[start]=i;
visited[i]=1;
t_visited++;
index=start;
break;
}
}
while(true)
{
index++;
vindex[index]=num[vindex[index-1]];
if(vindex[index]==vindex[start])
break;
visited[vindex[index]]=1;
t_visited++;
}
vindex[++index]=0;
start=index+1;
cycles++;
}
printf("%d/n",cycles,vindex[0]);
for(int i=0;i<(n+2*cycles);i++)
{
if(vindex[i]==0)
printf("/n");
else
printf("%d ",vindex[i]);
}
}

Answer 6

En el caso del gráfico no dirigido, un documento publicado recientemente ( Lista óptima de ciclos y st-paths en gráficos no dirigidos ) ofrece una solución asintóticamente óptima. Puedes leerlo aquí http://arxiv.org/abs/1205.2766 o aquí http://dl.acm.org/citation.cfm?id=2627951 Sé que no responde a tu pregunta, pero dado que el título de su pregunta no menciona la dirección, aún podría ser útil para la búsqueda de Google

Answer 7

Encontré esta página en mi búsqueda y dado que los ciclos no son lo mismo que los componentes fuertemente conectados, seguí buscando y, finalmente, encontré un algoritmo eficiente que enumera todos los ciclos (elementales) de un gráfico dirigido. Es de Donald B. Johnson y el documento se puede encontrar en el siguiente enlace:

http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

Una implementación de Java se puede encontrar en:

http://normalisiert.de/code/java/elementaryCycles.zip

here puede encontrar una demostración de Mathematica del algoritmo de Johnson; la implementación se puede descargar desde la derecha ( "Descargar el código del autor" ).

Nota: En realidad, hay muchos algoritmos para este problema. Algunos de ellos se enumeran en este artículo:

http://dx.doi.org/10.1137/0205007

Según el artículo, el algoritmo de Johnson es el más rápido.

Answer 8

Hay dos pasos (algoritmos) involucrados en encontrar todos los ciclos en un DAG.

El primer paso es usar el algoritmo de Tarjan para encontrar el conjunto de componentes fuertemente conectados.

1. Comience desde cualquier vértice arbitrario.
2. DFS desde ese vértice. Para cada nodo x, mantenga dos números, dfs_index [x] y dfs_lowval [x]. dfs_index [x] almacena cuando se visita ese nodo, mientras que dfs_lowval [x] = min (dfs_low [k]) donde k es todos los hijos de x que no son los padres directos de x en el árbol dfs-spanning.
3. Todos los nodos con el mismo dfs_lowval [x] están en el mismo componente fuertemente conectado.

El segundo paso es encontrar ciclos (rutas) dentro de los componentes conectados. Mi sugerencia es usar una versión modificada del algoritmo de Hierholzer.

La idea es:

1. Elija cualquier vértice inicial v y siga un rastro de bordes desde ese vértice hasta que regrese a v. No es posible quedarse atascado en ningún vértice que no sea v, porque el grado par de todos los vértices asegura que, cuando el camino entre en otro vértice w debe haber un borde no utilizado dejando w. El recorrido formado de esta manera es un recorrido cerrado, pero puede no abarcar todos los vértices y bordes del gráfico inicial.
2. Mientras exista un vértice v que pertenezca al recorrido actual pero que tenga bordes adyacentes que no forman parte del recorrido, comience otro camino desde v, siga los bordes no utilizados hasta que vuelva a v, y únase al recorrido formado de esta manera al visita previa.

Aquí está el enlace a una implementación de Java con un caso de prueba:

http://stones333.blogspot.com/2013/12/find-cycles-in-directed-graph-dag.html

Answer 9

La elección más simple que encontré para resolver este problema fue usar la lib de python llamada networkx .

Implementa el algoritmo de Johnson mencionado en la mejor respuesta de esta pregunta, pero es bastante simple de ejecutar.

En resumen, necesitas lo siguiente:

import networkx as nx
import matplotlib.pyplot as plt
# Create Directed Graph
G=nx.DiGraph()
# Add a list of nodes:
G.add_nodes_from(["a","b","c","d","e"])
# Add a list of edges:
G.add_edges_from([("a","b"),("b","c"), ("c","a"), ("b","d"), ("d","e"), ("e","a")])
#Return a list of cycles described as a list o nodes
list(nx.simple_cycles(G))

Respuesta: [[''a'', ''b'', ''d'', ''e''], [''a'', ''b'', ''c'']]

Answer 10

La primera búsqueda de profundidad con retroceso debería funcionar aquí. Mantenga una matriz de valores booleanos para realizar un seguimiento de si ha visitado un nodo anteriormente. Si te quedas sin nuevos nodos para ir (sin tocar un nodo que ya has visitado), entonces solo retrocede y prueba con una nueva rama.

El DFS es fácil de implementar si tiene una lista de adyacencia para representar el gráfico. Por ejemplo, adj [A] = {B, C} indica que B y C son los hijos de A.

Por ejemplo, pseudocódigo a continuación. "inicio" es el nodo desde el que comienzas.

dfs(adj,node,visited):
if (visited[node]):
if (node == start):
"found a path"
return;
visited[node]=YES;
for child in adj[node]:
dfs(adj,child,visited)
visited[node]=NO;

Llame a la función anterior con el nodo de inicio:

visited = {}
dfs(adj,start,visited)

Answer 11

Las variantes basadas en DFS con bordes posteriores encontrarán ciclos de hecho, pero en muchos casos NO serán ciclos mínimos . En general, DFS le indica que hay un ciclo pero no es lo suficientemente bueno para encontrar los ciclos. Por ejemplo, imagine 5 ciclos diferentes compartiendo dos bordes. No hay una forma simple de identificar ciclos utilizando solo DFS (incluidas las variantes de retroceso).

El algoritmo de Johnson da todos los ciclos simples únicos y tiene una buena complejidad de tiempo y espacio.

Pero si solo quiere encontrar ciclos MÍNIMOS (lo que significa que puede haber más de un ciclo atravesando cualquier vértice y estamos interesados ​​en encontrar los mínimos) Y su gráfica no es muy grande, puede intentar usar el método simple a continuación. Es MUY simple pero bastante lento comparado con el de Johnson.

Por lo tanto, una de las formas más sencillas de encontrar ciclos MÍNIMOS es usar el algoritmo de Floyd para encontrar caminos mínimos entre todos los vértices usando la matriz de adyacencia. Este algoritmo no es tan óptimo como el de Johnson, pero es tan simple y su bucle interno es tan ajustado que para gráficos más pequeños (<= 50-100 nodos) tiene sentido usarlo. La complejidad del tiempo es O (n ^ 3), la complejidad del espacio O (n ^ 2) si usa el seguimiento principal y O (1) si no lo hace. Antes que nada, busquemos la respuesta a la pregunta si hay un ciclo. El algoritmo es dead-simple. A continuación se muestra un fragmento en Scala.

 val NO_EDGE = Integer.MAX_VALUE / 2
def shortestPath(weights: Array[Array[Int]]) = {
for (k <- weights.indices;
i <- weights.indices;
j <- weights.indices) {
val throughK = weights(i)(k) + weights(k)(j)
if (throughK < weights(i)(j)) {
weights(i)(j) = throughK
}
}
}

Originalmente, este algoritmo opera en un gráfico de borde ponderado para encontrar todas las rutas más cortas entre todos los pares de nodos (de ahí el argumento de ponderaciones). Para que funcione correctamente, debe proporcionar 1 si hay un borde dirigido entre los nodos o NO_EDGE en caso contrario. Después de que el algoritmo se ejecuta, puede verificar la diagonal principal, si hay valores menores que NO_EDGE, este nodo participa en un ciclo de longitud igual al valor. Todos los demás nodos del mismo ciclo tendrán el mismo valor (en la diagonal principal).

Para reconstruir el ciclo en sí, necesitamos usar una versión ligeramente modificada del algoritmo con el seguimiento de los padres.

 def shortestPath(weights: Array[Array[Int]], parents: Array[Array[Int]]) = {
for (k <- weights.indices;
i <- weights.indices;
j <- weights.indices) {
val throughK = weights(i)(k) + weights(k)(j)
if (throughK < weights(i)(j)) {
parents(i)(j) = k
weights(i)(j) = throughK
}
}
}

La matriz de padres inicialmente debe contener el índice de vértices de origen en una celda de borde si hay un borde entre los vértices y -1 en caso contrario. Después de que la función regrese, para cada borde tendrá referencia al nodo padre en el árbol de ruta más corta. Y luego es fácil recuperar ciclos reales.

En general, tenemos el siguiente programa para encontrar todos los ciclos mínimos

 val NO_EDGE = Integer.MAX_VALUE / 2;
def shortestPathWithParentTracking(
weights: Array[Array[Int]],
parents: Array[Array[Int]]) = {
for (k <- weights.indices;
i <- weights.indices;
j <- weights.indices) {
val throughK = weights(i)(k) + weights(k)(j)
if (throughK < weights(i)(j)) {
parents(i)(j) = parents(i)(k)
weights(i)(j) = throughK
}
}
}
def recoverCycles(
cycleNodes: Seq[Int],
parents: Array[Array[Int]]): Set[Seq[Int]] = {
val res = new mutable.HashSet[Seq[Int]]()
for (node <- cycleNodes) {
var cycle = new mutable.ArrayBuffer[Int]()
cycle += node
var other = parents(node)(node)
do {
cycle += other
other = parents(other)(node)
} while(other != node)
res += cycle.sorted
}
res.toSet
}

y un pequeño método principal solo para probar el resultado

 def main(args: Array[String]): Unit = {
val n = 3
val weights = Array(Array(NO_EDGE, 1, NO_EDGE), Array(NO_EDGE, NO_EDGE, 1), Array(1, NO_EDGE, NO_EDGE))
val parents = Array(Array(-1, 1, -1), Array(-1, -1, 2), Array(0, -1, -1))
shortestPathWithParentTracking(weights, parents)
val cycleNodes = parents.indices.filter(i => parents(i)(i) < NO_EDGE)
val cycles: Set[Seq[Int]] = recoverCycles(cycleNodes, parents)
println("The following minimal cycle found:")
cycles.foreach(c => println(c.mkString))
println(s"Total: ${cycles.size} cycle found")
}

y el resultado es

The following minimal cycle found:
012
Total: 1 cycle found

Answer 12

Me dieron esto como una pregunta de entrevista una vez, sospecho que esto te ha sucedido y que vienes aquí en busca de ayuda. Divide el problema en tres preguntas y se vuelve más fácil.

1. ¿Cómo se determina la próxima ruta válida?
2. ¿cómo se determina si un punto se ha utilizado?
3. ¿Cómo evitar cruzar nuevamente el mismo punto?

Problema 1) Use el patrón de iterador para proporcionar una forma de repetir los resultados de la ruta. Un buen lugar para poner la lógica para obtener la siguiente ruta es probablemente el "moveNext" de su iterador. Para encontrar una ruta válida, depende de su estructura de datos. Para mí, era una tabla sql llena de posibilidades de ruta válidas, así que tuve que crear una consulta para obtener los destinos válidos dados una fuente.

Problema 2) Empuje cada nodo mientras los encuentra en una colección a medida que los obtiene, esto significa que puede ver si está "duplicando" un punto muy fácilmente al interrogar la colección que está construyendo sobre la marcha.

Problema 3) Si en algún momento ves que estás retrocediendo, puedes sacar cosas de la colección y "hacer una copia de seguridad". Luego, desde ese punto, intenta "avanzar" nuevamente.

Hack: si está utilizando Sql Server 2008, hay algunas cosas nuevas de "jerarquía" que puede usar para resolver esto rápidamente si estructura sus datos en un árbol.

Answer 13

Me tropecé con el siguiente algoritmo que parece ser más eficiente que el algoritmo de Johnson (al menos para gráficos más grandes). Sin embargo, no estoy seguro de su rendimiento en comparación con el algoritmo de Tarjan.
Además, solo lo he comprobado para triángulos hasta el momento. Si le interesa, consulte "Arboricity and Subgraph Listing Algorithms" por Norishige Chiba y Takao Nishizeki ( http://dx.doi.org/10.1137/0214017 )

Answer 14

Para aclarar:

1. Los componentes fuertemente conectados encontrarán todos los subgráficos que tengan al menos un ciclo en ellos, no todos los ciclos posibles en el gráfico. por ejemplo, si toma todos los componentes fuertemente conectados y contrae / agrupa / fusiona cada uno de ellos en un nodo (es decir, un nodo por componente), obtendrá un árbol sin ciclos (un DAG en realidad). Cada componente (que básicamente es un subgráfico con al menos un ciclo en él) puede contener muchos más ciclos posibles internamente, por lo que SCC NO encontrará todos los ciclos posibles, encontrará todos los grupos posibles que tengan al menos un ciclo, y si agrupa ellos, entonces el gráfico no tendrá ciclos.

2. para encontrar todos los ciclos simples en un gráfico, como otros mencionaron, el algoritmo de Johnson es un candidato.

Answer 15

Si lo que quiere es encontrar todos los circuitos elementales en un gráfico, puede usar el algoritmo EC, de JAMES C. TIERNAN, que se encuentra en un documento desde 1970.

El algoritmo EC muy original ya que pude implementarlo en php (espero que no haya errores se muestra a continuación). También puede encontrar bucles si los hay. Los circuitos en esta implementación (que intenta clonar el original) son los elementos distintos de cero. Cero representa la inexistencia (nulo como lo conocemos).

Aparte de eso, a continuación se incluye otra implementación que le da al algoritmo una mayor independencia, esto significa que los nodos pueden comenzar desde cualquier lugar incluso desde números negativos, por ejemplo, -4, -3, -2, ... etc.

En ambos casos, se requiere que los nodos sean secuenciales.

Es posible que necesite estudiar el documento original, James C. Tiernan Elementary Circuit Algorithm

<?php
echo "<pre><br><br>";
$G = array(
1=>array(1,2,3),
2=>array(1,2,3),
3=>array(1,2,3)
);
define(''N'',key(array_slice($G, -1, 1, true)));
$P = array(1=>0,2=>0,3=>0,4=>0,5=>0);
$H = array(1=>$P, 2=>$P, 3=>$P, 4=>$P, 5=>$P );
$k = 1;
$P[$k] = key($G);
$Circ = array();
#[Path Extension]
EC2_Path_Extension:
foreach($G[$P[$k]] as $j => $child ){
if( $child>$P[1] and in_array($child, $P)===false and in_array($child, $H[$P[$k]])===false ){
$k++;
$P[$k] = $child;
goto EC2_Path_Extension;
} }
#[EC3 Circuit Confirmation]
if( in_array($P[1], $G[$P[$k]])===true ){//if PATH[1] is not child of PATH[current] then don''t have a cycle
$Circ[] = $P;
}
#[EC4 Vertex Closure]
if($k===1){
goto EC5_Advance_Initial_Vertex;
}
//afou den ksana theoreitai einai asfales na svisoume
for( $m=1; $m<=N; $m++){//H[P[k], m] <- O, m = 1, 2, . . . , N
if( $H[$P[$k-1]][$m]===0 ){
$H[$P[$k-1]][$m]=$P[$k];
break(1);
}
}
for( $m=1; $m<=N; $m++ ){//H[P[k], m] <- O, m = 1, 2, . . . , N
$H[$P[$k]][$m]=0;
}
$P[$k]=0;
$k--;
goto EC2_Path_Extension;
#[EC5 Advance Initial Vertex]
EC5_Advance_Initial_Vertex:
if($P[1] === N){
goto EC6_Terminate;
}
$P[1]++;
$k=1;
$H=array(
1=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
2=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
3=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
4=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
5=>array(1=>0,2=>0,3=>0,4=>0,5=>0)
);
goto EC2_Path_Extension;
#[EC5 Advance Initial Vertex]
EC6_Terminate:
print_r($Circ);
?>

entonces esta es la otra implementación, más independiente del gráfico, sin goto y sin valores de matriz, sino que usa claves de matriz, la ruta, el gráfico y los circuitos se almacenan como claves de matriz (use valores de matriz si lo desea, simplemente cambie la líneas). El gráfico de ejemplo comienza desde -4 para mostrar su independencia.

<?php
$G = array(
-4=>array(-4=>true,-3=>true,-2=>true),
-3=>array(-4=>true,-3=>true,-2=>true),
-2=>array(-4=>true,-3=>true,-2=>true)
);
$C = array();
EC($G,$C);
echo "<pre>";
print_r($C);
function EC($G, &$C){
$CNST_not_closed = false; // this flag indicates no closure
$CNST_closed = true; // this flag indicates closure
// define the state where there is no closures for some node
$tmp_first_node = key($G); // first node = first key
$tmp_last_node = $tmp_first_node-1+count($G); // last node = last key
$CNST_closure_reset = array();
for($k=$tmp_first_node; $k<=$tmp_last_node; $k++){
$CNST_closure_reset[$k] = $CNST_not_closed;
}
// define the state where there is no closure for all nodes
for($k=$tmp_first_node; $k<=$tmp_last_node; $k++){
$H[$k] = $CNST_closure_reset; // Key in the closure arrays represent nodes
}
unset($tmp_first_node);
unset($tmp_last_node);
# Start algorithm
foreach($G as $init_node => $children){#[Jump to initial node set]
#[Initial Node Set]
$P = array(); // declare at starup, remove the old $init_node from path on loop
$P[$init_node]=true; // the first key in P is always the new initial node
$k=$init_node; // update the current node
// On loop H[old_init_node] is not cleared cause is never checked again
do{#Path 1,3,7,4 jump here to extend father 7
do{#Path from 1,3,8,5 became 2,4,8,5,6 jump here to extend child 6
$new_expansion = false;
foreach( $G[$k] as $child => $foo ){#Consider each child of 7 or 6
if( $child>$init_node and isset($P[$child])===false and $H[$k][$child]===$CNST_not_closed ){
$P[$child]=true; // add this child to the path
$k = $child; // update the current node
$new_expansion=true;// set the flag for expanding the child of k
break(1); // we are done, one child at a time
} } }while(($new_expansion===true));// Do while a new child has been added to the path
# If the first node is child of the last we have a circuit
if( isset($G[$k][$init_node])===true ){
$C[] = $P; // Leaving this out of closure will catch loops to
}
# Closure
if($k>$init_node){ //if k>init_node then alwaya count(P)>1, so proceed to closure
$new_expansion=true; // $new_expansion is never true, set true to expand father of k
unset($P[$k]); // remove k from path
end($P); $k_father = key($P); // get father of k
$H[$k_father][$k]=$CNST_closed; // mark k as closed
$H[$k] = $CNST_closure_reset; // reset k closure
$k = $k_father; // update k
} } while($new_expansion===true);//if we don''t wnter the if block m has the old k$k_father_old = $k;
// Advance Initial Vertex Context
}//foreach initial
}//function
?>

Analicé y documenté el CE, pero desafortunadamente la documentación está en griego.

Answer 16

Solución de Javascript que utiliza listas vinculadas de conjuntos disjuntos. Se puede actualizar para desunir bosques establecidos para tiempos de ejecución más rápidos.

var input = ''5/nYYNNN/nYYYNN/nNYYNN/nNNNYN/nNNNNY''
console.log(input);
//above solution should be 3 because the components are
//{0,1,2}, because {0,1} and {1,2} therefore {0,1,2}
//{3}
//{4}
//MIT license, authored by Ling Qing Meng
//''4/nYYNN/nYYYN/nNYYN/nNNNY''
//Read Input, preformatting
var reformat = input.split(//n/);
var N = reformat[0];
var adjMatrix = [];
for (var i = 1; i < reformat.length; i++) {
adjMatrix.push(reformat[i]);
}
//for (each person x from 1 to N) CREATE-SET(x)
var sets = [];
for (var i = 0; i < N; i++) {
var s = new LinkedList();
s.add(i);
sets.push(s);
}
//populate friend potentials using combinatorics, then filters
var people = [];
var friends = [];
for (var i = 0; i < N; i++) {
people.push(i);
}
var potentialFriends = k_combinations(people,2);
for (var i = 0; i < potentialFriends.length; i++){
if (isFriend(adjMatrix,potentialFriends[i]) === ''Y''){
friends.push(potentialFriends[i]);
}
}
//for (each pair of friends (x y) ) if (FIND-SET(x) != FIND-SET(y)) MERGE-SETS(x, y)
for (var i = 0; i < friends.length; i++) {
var x = friends[i][0];
var y = friends[i][1];
if (FindSet(x) != FindSet(y)) {
sets.push(MergeSet(x,y));
}
}
for (var i = 0; i < sets.length; i++) {
//sets[i].traverse();
}
console.log(''How many distinct connected components?'',sets.length);
//Linked List data structures neccesary for above to work
function Node(){
this.data = null;
this.next = null;
}
function LinkedList(){
this.head = null;
this.tail = null;
this.size = 0;
// Add node to the end
this.add = function(data){
var node = new Node();
node.data = data;
if (this.head == null){
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this.size++;
};
this.contains = function(data) {
if (this.head.data === data)
return this;
var next = this.head.next;
while (next !== null) {
if (next.data === data) {
return this;
}
next = next.next;
}
return null;
};
this.traverse = function() {
var current = this.head;
var toPrint = '''';
while (current !== null) {
//callback.call(this, current); put callback as an argument to top function
toPrint += current.data.toString() + '' '';
current = current.next;
}
console.log(''list data: '',toPrint);
}
this.merge = function(list) {
var current = this.head;
var next = current.next;
while (next !== null) {
current = next;
next = next.next;
}
current.next = list.head;
this.size += list.size;
return this;
};
this.reverse = function() {
if (this.head == null)
return;
if (this.head.next == null)
return;
var currentNode = this.head;
var nextNode = this.head.next;
var prevNode = this.head;
this.head.next = null;
while (nextNode != null) {
currentNode = nextNode;
nextNode = currentNode.next;
currentNode.next = prevNode;
prevNode = currentNode;
}
this.head = currentNode;
return this;
}
}
/**
* GENERAL HELPER FUNCTIONS
*/
function FindSet(x) {
for (var i = 0; i < sets.length; i++){
if (sets[i].contains(x) != null) {
return sets[i].contains(x);
}
}
return null;
}
function MergeSet(x,y) {
var listA,listB;
for (var i = 0; i < sets.length; i++){
if (sets[i].contains(x) != null) {
listA = sets[i].contains(x);
sets.splice(i,1);
}
}
for (var i = 0; i < sets.length; i++) {
if (sets[i].contains(y) != null) {
listB = sets[i].contains(y);
sets.splice(i,1);
}
}
var res = MergeLists(listA,listB);
return res;
}
function MergeLists(listA, listB) {
var listC = new LinkedList();
listA.merge(listB);
listC = listA;
return listC;
}
//access matrix by i,j -> returns ''Y'' or ''N''
function isFriend(matrix, pair){
return matrix[pair[0]].charAt(pair[1]);
}
function k_combinations(set, k) {
var i, j, combs, head, tailcombs;
if (k > set.length || k <= 0) {
return [];
}
if (k == set.length) {
return [set];
}
if (k == 1) {
combs = [];
for (i = 0; i < set.length; i++) {
combs.push([set[i]]);
}
return combs;
}
// Assert {1 < k < set.length}
combs = [];
for (i = 0; i < set.length - k + 1; i++) {
head = set.slice(i, i+1);
tailcombs = k_combinations(set.slice(i + 1), k - 1);
for (j = 0; j < tailcombs.length; j++) {
combs.push(head.concat(tailcombs[j]));
}
}
return combs;
}

Answer 17

me.utexas.edu/~bard/IP/Handouts/cycles.pdf