// Este arquivo: GRAPHlists.h // Data: 2019-12-31 // Autor: Paulo Feofiloff // // Este é a rascunho da interface de uma biblioteca de manipulação de grafos // representados por listas de adjacência. Os grafos não têm arcos paralelos nem // laços. Grafos não-dirigidos (= undirected) são um tipo especial de grafo: // cada aresta de um grafo não-dirigido é um par (v-w, w-v) de arcos // antipralelos. // // Os grafos têm custos (= weights) nos arcos, mas muitas das funções ignoram os // custos. Na documentação das funções desta biblioteca usaremos a palavra // "custo", mas em certas situações seria mais apropriado dizer "capacidade". // // Tudo foi extraído de www.ime.usp.br/~pf/algoritmos_para_grafos/, que copiou // muita coisa do livro "Algorithms", 3rd.ed., part 5, de Sedgewick. //////////////////////////////////////////////////////////////////////////////// #ifndef _GRAPHlists_h #define _GRAPHlists_h #include "STACK.h" // pilha #include "QUEUE.h" // fila #include "PQ.h" // fila priorizada "de mínimo" (min priority queue) #include "maxPQ.h" // fila priorizada "de máximo" (max priority queue) #include "UF.h" // union-find #include "MYTOOLS.h" // string, mallocc(), randInteger(), ... #include // strtol(), qsort(), etc. #include #include // strtok(), etc. #include // INT_MAX, etc. #include #define min( A, B) ((A) < (B) ? (A) : (B)) #define max( A, B) ((A) > (B) ? (A) : (B)) // Estruturas de dados básicas //////////////////////////////////////////////////////////////////////////////// // Vértices de grafos são representados por objetos do tipo vertex. Os vértices // são inteiros positivos (0,1,2,...). Em raras ocasiões, uma variável do tipo // vertex pode ter valor -1 com o significado de "não definido". #define vertex int // A lista de adjacência de um vértice v é composta por nós do tipo node. Cada // nó da lista corresponde a um arco e contém um vizinho w de v e o endereço do // nó seguinte da lista. Um link é um ponteiro para um node. Além dos campos // essenciais w e next, cada nó contém outros quatro campos, que são usados // apenas por algumas funções da biblioteca. O campo c é usado para armazenar o // custo ou a capacidade do arco. Os campos flow, type e twin são usados apenas // pelas funções que calculam um fluxo máximo no grafo. typedef struct node *link; struct node { vertex w; int c; int flow; int type; link twin; link next; }; // A estrutura graph representa um grafo. O campo adj é um ponteiro para o vetor // de listas de adjacência, o campo V é o número de vértices e o campo A é o // número de arcos. Suporemos sempre que V >= 1. struct graph { int V; int A; link *adj; }; // Um objeto do tipo Graph contém o endereço de um graph. typedef struct graph *Graph; // O tipo UGraph é um sinônimo de Graph. Esse tipo tem a missão de deixar claro, // para o leitor humano, que o grafo é não-dirigido. (O "U" de "UGraph" é uma // abreviatura de "undirected".) #define UGraph Graph // O tipo Dag é um sinônimo de Graph. Esse tipo tem a missão de deixar claro, // para o leitor humano, que o grafo é acíclico. #define Dag Graph // O projeto de muitas das funções desta biblioteca, precisa enfrentar a // seguinte decisão de projeto: // - ou o cliente (usuário da biblioteca) aloca um vetor onde a função // depositará seus resultados // - ou a própria função aloca um vetor e devolve o seu endereço ao cliente. // Em qualquer caso, a desalocação do vetor deverá ser feita pelo cliente. A // primeira alternativa parece mais limpa pois o cliente trata tanto da alocação // (mallocc) quanto da desalocação (free). // Ferramentas para construção de grafos //////////////////////////////////////////////////////////////////////////////// // Algumas funções têm duas versões, uma para grafos sem custos nos arcos e // outra para grafos com custos; o nome da segunda versão tem um sufixo "_c". // Em alguns casos -- como o da árvore geradora de custo mínimo -- o sufixo // "_c" é omitido porque a função só faz sentido para grafos com custos. // A função GRAPHinit() constrói e devolve um grafo com vértices 0 1 ... V-1 e // nenhum arco. Graph GRAPHinit( int V); // Idem para grafo não-dirigido. #define UGRAPHinit GRAPHinit // A função GRAPHinsertArc() insere um arco v-w no grafo G. A função supõe que // v e w são distintos e menores que G->V. Se o grafo já tem um arco v-w, a // função não faz nada. void GRAPHinsertArc( Graph G, vertex v, vertex w); // A função GRAPHinsertArc_c() insere um arco v-w com custo c no grafo G. A // função supõe que v e w são distintos e menores que G->V. Se o grafo já tem // um arco v-w, o novo custo c substitui o antigo. void GRAPHinsertArc_c( Graph G, vertex v, vertex w, int c); // A função UGRAPHinsertEdge() insere uma aresta v-w no grafo não-dirigido G. // A função supõe que v e w são distintos e menores que G->V. Se o grafo já tem // uma aresta v-w, a função não faz nada. void UGRAPHinsertEdge( UGraph G, vertex v, vertex w); // Esta função insere uma aresta v-w com custo c no grafo não-dirigido G. A // função supõe que v e w são distintos e menores que G->V. Se o grafo já tem // uma aresta v-w, a função não faz nada. void UGRAPHinsertEdge_c( UGraph G, vertex v, vertex w, int c); // A função GRAPHremoveArc() remove o arco v-w do grafo G. Se não existe arco // v-w, a função não faz nada. void GRAPHremoveArc( Graph G, vertex v, vertex w); // A função UGRAPHremoveEdge() remove aresta v-w do grafo não-dirigido G. Se não // existe aresta v-w, a função não faz nada. void UGRAPHremoveEdge( UGraph G, vertex v, vertex w); // Para cada vértice v do grafo G, esta função imprime, em uma linha da saída // padrão, todos os vértices adjacentes a v. void GRAPHshow( Graph G); #define UGRAPHshow GRAPHshow // Para cada vértice v do grafo G, esta função imprime, em uma linha da saída // padrão, todos os vértices adjacentes a v e os respectivos custos. void GRAPHshow_c( Graph G); #define UGRAPHshow_c GRAPHshow_c // Esta função imprime, na saída padrão, todos os arcos de G. Cada linha da // saída tem a forma v w, sendo v a ponta inicial e w a ponta final de um arco. void GRAPHshowArcs( Graph G); // Esta função imprime, na saída padrão, todos os arcos de G. Cada linha da // saída tem a forma v w (c), sendo v a ponta inicial, w aponta final e c o // custo de um arco. void GRAPHshowArcs_c( Graph G); // Esta função devolve uma cópia do grafo G. Graph GRAPHcopy( Graph G); #define UGRAPHcopy GRAPHcopy // Decide se os grafos G e H são iguais. bool GRAPHequal( Graph G, Graph H); // Esta função desaloca toda a memória usada pela estrutura de dados que // representa o grafo G. void GRAPHdestroy( Graph G); #define UGRAPHdestroy GRAPHdestroy // Esta função decide se o grafo G é não-dirigido. bool GRAPHundir( Graph G); // Esta função devolve o grau de entrada do vértice v no grafo G. A função é // cara: consome tempo proporcional ao tamanho do grafo. int GRAPHindeg( Graph G, vertex v); // Esta função devolve o grau de saída do vértice v no grafo G. int GRAPHoutdeg( Graph G, vertex v); // Calcula o grau de um vértice v de um grafo não-dirigido G. #define UGRAPHdeg GRAPHoutdeg // Constrói o reverso do grafo G. (O reverso tem um arco w-v para cada arco v-w // de G.) Graph GRAPHreverse( Graph G); // Esta função devolve a soma dos custos dos arcos do grafo G. Se o cálculo da // soma causar overflow aritmético, imprime mensagem e para. int GRAPHcost( Graph G); // Esta função devolve a soma dos custos das arestas do grafo não-dirigido G. // (A função supõe que cada um dos dois arcos que formam uma aresta tem custo // igual ao da aresta.) Se o cálculo da soma causar overflow aritmético, imprime // mensagem e para. int UGRAPHcost( UGraph G); // Esta função constrói o grafo descrito no arquivo infile, que deve ter o // seguinte formato: primeiro o número de vértices e o número de arcos, depois // os pares de vértices que definem os arcos. As demais linhas do arquivo são // ignoradas (podendo ser usadas para comentários). Exemplo: // 6 // 10 // 0-4 // 0-1 // 2-4 // 2-3 // 2-0 // 3-5 // 3-4 // 4-5 // 4-1 // 5-1 // A função devolve NULL se, por qualquer motivo, o grafo não puder ser // construído. Graph GRAPHinputArcs( FILE *infile); // Idem para grafos não-dirigidos, trocando "arco" por "aresta". UGraph UGRAPHinputEdges( FILE *infile); // Esta função constrói o grafo com custos nos arcos descrito no arquivo infile. // Formato do arquivo: primeiro o número de vértices e o número de arcos, depois // os pares de vértices que definem os arcos, seguidos dos respectivos custos. // As demais linhas do arquivo são ignoradas (podendo ser usadas para // comentários). Exemplo: // 6 10 // 0-4 91 // 0-1 92 // 2-4 88 // 2-3 99 // 2-0 99 // 3-5 88 // 3-4 77 // 4-5 66 // 4-1 55 // 5-1 44 // A função devolve NULL se, por qualquer motivo, o grafo não puder ser // construído. Graph GRAPHinputArcs_c( FILE *infile); // Idem para grafos não-dirigidos, trocando "arco" por "aresta". UGraph UGRAPHinputEdges_c( FILE *infile); #define LINE_MAX 1000 // Esta função constrói o grafo descrito no arquivo infile. Formato: A primeira // linha do arquivo contém o número V de vértices do grafo (devemos ter V >= 1). // Cada uma das V linhas seguintes contém a lista de adjacência de um dos // vértices do grafo; cada uma dessas linhas tem a forma // v w1 w2 ... wk // sendo w1 w2 ... wk os vizinhos do vértice v. As demais linhas de infile são // ignoradas (podendo ser usadas para comentários). Exemplo: // 7 // 0: 6 1 // 1: 0 6 3 // 2: 4 // 3: 1 // 4: 2 // 5: // 6: 0 1 // Cada linha do arquivo infile deve ter < LINE_MAX caracteres (contando o \n // final). Devemos ter LINE_MAX >= 2. Todos os caracteres das V+1 primeiras // linhas devem ser dígitos decimais, espaços, e '\n'. Cada uma das V+1 // primeiras linhas tem pelo menos um dígito decimal. // No grafo construído, a ordem dos vértices em cada lista de adjacência é // igual à ordem em que os vértices aparecem na linha correspondente de infile. Graph GRAPHinputAdjLists( FILE *infile); #define UGRAPHinputAdjLists GRAPHinputAdjLists // Esta função constrói o grafo descrito no arquivo infile. Formato: A primeira // linha do arquivo contém o número V de vértices do grafo (devemos ter V >= 1). // Cada uma das V linhas seguintes contém a lista de adjacência de um dos // vértices do grafo; cada uma dessas linhas tem a forma // v w1 c1 w2 c2 ... wk ck // sendo w1 w2 ... wk os vizinhos do vértice v e c1 c2 ... ck os custos dos // arcos v-w1 v-w2 ... v-wk respectivamente. As demais linhas de infile são // ignoradas (podendo ser usadas para comentários). Exemplo: // 7 // 0: 6 90 1 91 // 1: 0 92 6 93 3 94 // 2: 4 95 // 3: 1 96 // 4: 2 97 // 5: // 6: 0 98 1 99 // Cada linha do arquivo infile deve ter < LINE_MAX caracteres (contando o \n // final). Devemos ter LINE_MAX >= 2. Todos os caracteres das V+1 primeiras // linhas devem ser dígitos decimais, espaços, e '\n'. Cada uma das V+1 // primeiras linhas tem pelo menos um dígito decimal. // No grafo construído, a ordem dos vértices em cada lista de adjacência é // igual à ordem em que os vértices aparecem na linha correspondente de infile. Graph GRAPHinputAdjLists_c( FILE *infile); #define UGRAPHinputAdjLists_c GRAPHinputAdjLists_c // Armazena as arestas do grafo não-dirigido G no vetor e[0..E-1], sendo E = // G->A/2. void UGRAPHedges( UGraph G, edge *e); // Numerações e permutações de vértices //////////////////////////////////////////////////////////////////////////////// // Converte a permutação perm[0..V-1] dos vértices 0..V-1 de um grafo na // correspondente numeração num[0..V-1] dos vértices. (Teremos num[perm[i]] // == i.) void perm2num( int V, vertex *perm, int *num); // Converte a numeração injetiva num[0..V-1] dos vértices de um grafo na // correspondente permutação perm[0..V-1] dos vértices. O vetor num[] deve ser // uma bijeção entre o conjunto dos vértices e o conjunto de números 0..V-1. void inum2perm( int V, int *num, vertex *perm); // Converte a numeração num[0..V-1] dos vértices de um grafo na correspondente // permutação perm[0..V-1] dos vértices. A numeração num[] pode não ser // injetiva; basta que atribua um número inteiro positivo a cada vértice. void num2perm( int V, int *num, vertex *perm); // Armazena em vv[0..V-1] uma permutação dos vértices do grafo G em ordem // crescente de graus de saída. void increasingDegrees( Graph G, vertex *vv); // Versão de increasingDegrees() com ordenação estável. void increasingDegrees2( Graph G, vertex *vv); // Grafos topológicos //////////////////////////////////////////////////////////////////////////////// // Uma numeração num[] dos vértices é topológica se num[v] < num[w] para cada // arco v-w. Uma numeração num[] é anti-topológica se num[v] > num[w] para cada // arco v-w. Uma permutação vv[] dos vértices é topológica se i < j para cada // arco vv[i]-vv[j] do grafo. Uma permutação vv[] dos vértices é anti- // -topológica se i > j para cada arco vv[i]-vv[j] do grafo. // Decide se o grafo G é topológico. Em caso afirmativo, armazena no vetor // topo[0..V-1] uma numeração topológica dos vértices de G. (A função implementa // o algoritmo de eliminação iterada de fontes.) (Veja também a função // GRAPHdag() que é mais completa e tão eficiente quanto esta.) bool GRAPHtopol( Graph G, int *topo); // Grafos aleatórios //////////////////////////////////////////////////////////////////////////////// // Esta função devolve um vértice aleatório do grafo G. (Vamos supor que G->V // <= RAND_MAX.) Ela é apenas um invólucro para a função rand() da biblioteca // stdlib, que produz um número inteiro aleatório no intervalo fechado // 0..RAND_MAX. vertex randV( Graph G); // Constrói grafo aleatório com vértices 0..V-1 e exatamente A arcos. A função // supõe que A <= V*(V-1). Se A for próximo de V*(V-1), a função consume // muuuito tempo. Por isso, a função não deve ser usada para gerar grafos muito // densos. Graph GRAPHrand( int V, int A); // Constrói grafo não-dirigido aleatório com vértices 0..V-1 e exatamente E // arestas. A função supõe que E <= V*(V-1)/2. Se E for proximo de V*(V-1)/2, // a função consume muuuito tempo. Por isso, a função não deve ser usada para // gerar grafos muito densos. UGraph UGRAPHrand( int V, int E); // Esta é a versão de GRAPHrand() para grafos com custos nos arcos. Os custos // dos arcos são escolhidos aleatoriamente no intervalo fechado [cmin,cmax]. Graph GRAPHrand_c( int V, int A, int cmin, int cmax); // Esta é a versão de UGRAPHrand() para grafos não-dirigidos com custos nas // arestas. Os custos são escolhidos aleatoriamente no intervalo fechado // [cmin,cmax]. UGraph UGRAPHrand_c( int V, int E, int cmin, int cmax); // Constrói um grafo aleatório com vértices 0..V-1. Cada um dos V*(V-1) // possíveis arcos é inserido com probabilidade p, sendo p calculado de modo que // o número esperado de arcos seja A. A função supõe que V >= 2 e A <= V*(V-1). // A função é mais usada para gerar grafos densos. O sufixo "ER" é uma // abreviaura de "modelo de Erdős-Rényi". Graph GRAPHrandER( int V, int A); // Esta é a versão de GRAPHrandER() para grafos com custos nos arcos. Os custos // dos arcos são escolhidos aleatoriamente no intervalo fechado [cmin,cmax]. Graph GRAPHrandER_c( int V, int A, int cmin, int cmax); // Constrói um grafo não-dirigido aleatório com vértices 0..V-1. Cada uma das // V*(V-1)/2 possíveis arestas é inserida com probabilidade p, sendo p calculado // de modo que o número esperado de arestas seja E. A função supõe que V >= 2 e // E <= V*(V-1)/2. A função é mais usada para gerar grafos não-dirigidos densos. // O sufixo "ER" é uma abreviatura de "modelo de Erdős-Rényi". UGraph UGRAPHrandER( int V, int E); // Esta é a versão de UGRAPHrandER() para grafos não-dirigidos com custos nas // arestas. Os custos das arestas são escolhidos aleatoriamente no intervalo // semi-aberto [cmin,cmax). UGraph UGRAPHrandER_c( int V, int E, int cmin, int cmax); // Construtores de grafos //////////////////////////////////////////////////////////////////////////////// // Constrói um grafo completo com V vértices. Graph GRAPHbuildComplete( int V); // Constrói um torneio aleatório (as direções dos arcos são aleatórias) com V // vértices. Graph GRAPHrandTournament( int V); // Constrói um grafo-caminho com V vértices. (É claro que V >= 1.) Graph GRAPHrandPath( int V); // Constrói um grafo-caminho não-dirigido com V vértices. (É claro que V >= 1.) UGraph UGRAPHrandPath( int V); // Constrói um grafo-ciclo com V >= 2 vértices. Graph GRAPHrandCycle( int V); // Constrói um grafo-circuito (não-dirigido) com V >= 3 vértices. UGraph UGRAPHrandCircuit( int V); // Constrói uma árvore radicada aleatória com V vértices. Graph GRAPHrandRootedTree( int V); // Constroi uma árvore (não-dirigida, não-radicada) aleatória com V vértices. UGraph UGRAPHrandTree( int V); // Constroi uma árvore (não-dirigida, não-radicada) aleatória com V vértices. Os // custos das arestas são escolhidos aleatoriamente no intervalo fechado // [cmin,cmax]. UGraph UGRAPHrandTree_c( int V, int cmin, int cmax); // Constroi um grafo não-dirigido aleatório conexo com V vértices e E arestas. // A função supõe que V-1 <= E <= V*(V-1). UGraph UGRAPHrandConnected( int V, int E); // Constroi um grafo não-dirigido aleatório conexo com V vértices e E arestas. // Os custos das arestas são escolhidos aleatoriamente no intervalo fechado // [cmin,cmax]. A função supõe que V-1 <= E <= V*(V-1). UGraph UGRAPHrandConnected_c( int V, int E, int cmin, int cmax); // Constroi um grafo não-dirigido bipartido aleatório com m >= 1 vértices // "brancos", n >= 1 vértices "vermelhos" e E <= m*n arestas. UGraph UGRAPHrandBipartite( int m, int n, int E); // Constroi um grafo não-dirigido bipartido aleatório com m >= 1 vértices // "brancos", n >= 1 vértices "vermelhos" e E <= m*n arestas. Os custos das // arestas são escolhidos aleatoriamente no intervalo semi-aberto [cmin,cmax). UGraph UGRAPHrandBipartite_c( int m, int n, int E, int cmin, int cmax); // Constrói uma grade (dirigida) m-por-n. Quando percorremos a grade "da // esquerda para a direita" e "de cima para baixo", a sequência de vértices é // uma permutação aleatória de 0 1 ... m*n-1. Veja um exemplo 3-por-3 em que a // permutação dos vértices é trivial: // // 0--1--2 // | | | // 3--4--5 // | | | // 6--7--8 // // No caso de uma permutação trivial, os vértices são disposto assim: // // 0 1 2 3 ... n-1 // n n+1 n+2 n+3 ... n+n-1 // 2n 2n+1 2n+2 2n+3 ... 2n+n-1 // . . . . . . // . . . . . . // (m-1)n (m-1)n+1 (m-1)n+2 (m-1)n+3 ... (m-1)n+n-1 // // Todos os arcos são dirigidos "para a direita" e "para baixo". A função supõe // que m*n < INT_MAX. Graph GRAPHrandDiGrid( int n, int m); // Constrói uma grade (dirigida) m-por-n em que as direções dos arcos são // aleatórios: "para a direita" e "para baixo" com probabilidade 0.5 e "para a // esquerda" e "para cima" com probabilidade 0.5. Graph GRAPHrandGrid( int n, int m); // Constrói uma grade não-dirigida m-por-n. UGraph UGRAPHrandGrid( int m, int n); // Constrói um subgrafo gerador não-dirigido aleatório de uma grade não-dirigida // m-por-n. Cada uma das arestas da grade deve ser incluída no subgrafo com // probabilidade p, sendo p calculado de modo que o número esperado de arestas // seja E. Supõe que E <= 2*m*n - m - n. UGraph UGRAPHrandSubGrid( int m, int n, int E); // Constrói um cubo de dimensão n. UGraph UGRAPHbuildCube( int n); // Constrói uma escada de Möbius com vértices 0..2n-1. UGraph UGRAPHmoebius( int n); // Constrói um grafo da dama (do jogo de xadrez) t-por-t. UGraph UGRAPHchessQueen( int t); // Caminhos e ciclos em grafos //////////////////////////////////////////////////////////////////////////////// // O comprimento de um caminho ou ciclo é o número de arcos do caminho. // A propósito, um número x é dito positivo de x >= 0 e negativo se x < 0. // (Isso mesmo: as definições não são simétricas.) // Acessibilidade (caminho de um vértice a outro) //////////////////////////////////////////////////////////////////////////////// // Recebe vértices s e t de um grafo G e decide se t está alcance de s (ou seja, // se existe um caminho de s a t). bool GRAPHreach( Graph G, vertex s, vertex t); #define UGRAPHreach GRAPHreach // Verifica se o vetor característico ch[] de um subconjunto do conjunto de // vértices é um certificado de inexistência de caminho de s a t em G. bool isDirectedCut( Graph G, vertex s, vertex t, bool *lbl); // Busca em profundidade (= depth-first search = DFS) //////////////////////////////////////////////////////////////////////////////// // A função GRAPHdfs() faz uma busca em profundidade no grafo G, numera os // vértices em pré-ordem e pós-ordem, e constrói a floresta DFS da busca. Os // resultados são armazenados nos vetores pre[], post[] e pa[] respectivamente, // todos indexados pelos vértices (e alocados pelo cliente da biblioteca). A // numeração em pré- e pós-ordem e o vetor de pais são definidos assim: // - se x é o k-ésimo vértice descoberto então pre[x] = k, // - se x é o k-ésimo vértice a morrer então post[x] = k, // - se v é o pai de um vértice w na floresta DFS então pa[w] = v, // - se w é uma raiz da floresta então pa[w] = w. void GRAPHdfs( Graph G, int *pre, int *post, vertex *pa); // Esta função é uma versão iterativa (não-recursiva) de GRAPHdfs(). void GRAPHdfs_i( Graph G, int *pre, int *post, vertex *pa); // Ciclos e dags //////////////////////////////////////////////////////////////////////////////// // Um passeio (= walk) é uma sequência de vértices dotada da seguinte // propriedade: se v e w são vértices consecutivos na sequência então v-w é um // arco do grafo. Um passeio é fechado se tem pelo menos dois arcos e seu // primeiro vértice coincide com o último. Um caminho (= path) é um passeio sem // arcos repetidos. Um ciclo (= cycle) é um caminho fechado. // Decide se o grafo G tem ciclo. bool GRAPHcycle0( Graph G); // Esta é uma versão on-the-fly de GRAPHcycle0(). bool GRAPHcycle( Graph G); // Decide se o grafo G é um dag. bool GRAPHdag( Graph G); // Recebe um grafo G e devolve um vértice z de um ciclo ou -1. No primeiro caso, // a regressão z pa[z] pa[pa[z]] ... z é o reverso de um ciclo. No segundo caso, // G é um dag e post[] é uma numeração anti-topológica. (A função é uma extensão // de GRAPHcycle().) int GRAPHfindCycle( Graph G, int *post, vertex *pa); // Componentes conexas (de grafos não-dirigidos) //////////////////////////////////////////////////////////////////////////////// // Calcula as componentes conexas do grafo não-dirigido G. Devolve o número de // componentes conexas de G e armazena no vetor cc[0..V-1] (alocado pelo cliente // da biblioteca) uma numeração dos vértices tal que dois vértices v e w // pertencem à mesma componente conexa se e somente se cc[v] == cc[w]. int UGRAPHconComps( UGraph G, int *cc); // Decide se o grafo não-dirigido G é conexo. bool UGRAPHcon( UGraph G); // Caminhos de comprimento mínimo //////////////////////////////////////////////////////////////////////////////// // SPT = shortest-paths tree = árvore de caminhos curtos. // Esta função recebe um dag G com V vértices, uma permutação topológica // vv[0..V-1] dos vértices de G, e um vértice s de G. A função armazena em pa[] // o vetor de pais de uma SPT do subgrafo induzido pelos vértices que estão ao // alcance de s. Se um vértice v não está ao alcance de s, teremos pa[v] == -1. // As distâncias (contadas em número de arcos) a partir de s são armazenadas no // vetor dist[]. (O espaço para os vetores pa[0..V-1] e dist[0..V-1] deve ser // alocado pelo cliente.) void DAGspt( Dag G, vertex *vv, vertex s, vertex *pa, int *dist); // Busca em largura (= breadth-first search = BFS) //////////////////////////////////////////////////////////////////////////////// // Algoritmo de caminhos mínimos //////////////////////////////////////////////////////////////////////////////// // SPT = shortest-paths tree = árvore de caminhos curtos. // Esta função recebe um grafo G e um vértice s de G e armazena em pa[0..V-1] o // vetor de pais de uma SPT do subgrafo induzido pelos vértices que estão ao // alcance de s. Se um vértice v não está ao alcance de s, teremos pa[v] == -1 e // dist[v] == G->V. As distâncias a partir de s (contadas em número de arcos) // são armazenadas no vetor dist[0..V-1]. (O espaço para os vetores dist[] e // pa[] deve ser alocado pelo cliente.) void GRAPHspt( Graph G, vertex s, int *dist, vertex *pa); // Circuitos e florestas (não-radicadas) //////////////////////////////////////////////////////////////////////////////// // Um circuito (= circuit) num grafo não-dirigido é um ciclo dotado da seguinte // propriedade: se um arco v-w pertence ao ciclo então o arco antiparalelo w-v // não pertence ao ciclo. // Esta função decide se o grafo não-dirigido G tem um circuito. Em caso de // resposta negativa, G é uma floresta. bool UGRAPHcircuit( UGraph G); // Recebe um grafo não-dirigido G e devolve um inteiro w. Se w == -1, o grafo é // uma floresta, senão o grafo tem um circuito. No segundo caso, w é um vértice // e a regressão w-p[w]-pa[pa[w]]-... é um circuito. int UGRAPHfindCircuit( UGraph G, vertex *pa); // Decide se o grafo não-dirigido G é uma floresta. bool UGRAPHforest( UGraph G); // Decide se o grafo não-dirigido G é uma árvore. bool UGRAPHtree( UGraph G); // Grafos aresta-biconexos (= edge-biconnected) //////////////////////////////////////////////////////////////////////////////// // Um grafo não-dirigido é aresta-biconexo se for conexo e não tiver pontes, ou // seja, se cada uma de suas arestas estiver em um circuito. // Decide se o grafo não-dirigido G é aresta-biconexo. (Implementa a versão on- // -the-fly do algoritmo de Tarjan. O algoritmo é linear: consome V+E unidades // de tempo. bool UGRAPHebicon( UGraph G); // Componentes aresta-biconexas (= edge-biconnected components) //////////////////////////////////////////////////////////////////////////////// // Esta função devolve o número (quantidade) de componentes aresta-biconexas do // grafo não-dirigido G. Também atribui um rótulo ebc[v] (os rótulos são 0,1, // 2,...) a cada vértice v de G de modo que dois vértices tenham o mesmo rótulo // se e somente se os dois pertencem à mesma componente aresta-biconexa. (A // função é linear: consome tempo proporcional ao tamanho do grafo. Implementa o // algoritmo de Tarjan.) int UGRAPHebiconComps( UGraph G, int *ebc); // Grafos fortemente conexos (= strongly connected) //////////////////////////////////////////////////////////////////////////////// // Decide se o grafo G é fortemente conexo. (A função implementa a versão // on-the-fly do algoritmo de Tarjan.) bool GRAPHstrongT2( Graph G); // Componentes fortes (= strong components) //////////////////////////////////////////////////////////////////////////////// // Algoritmo de Tarjan para componentes fortes //////////////////////////////////////////////////////////////////////////////// // Esta função devolve o número (quantidade) de componentes fortes do grafo G. // Também atribui um rótulo sc[v] a cada vértice v de G de modo que dois // vértices tenham o mesmo rótulo se e somente se os dois pertencem à mesma // componente forte. (Os rótulos pertencem ao intervalo 0..V-1, mas nem todo // inteiro nesse intervalo é rótulo de alguma componente forte.) A função é // linear: consume tempo proporcional a V+A. int GRAPHstrongCompsT( Graph G, int *sc); // Algoritmo de Kosaraju para componentes fortes //////////////////////////////////////////////////////////////////////////////// // Esta função devolve o número (quantidade) de componentes fortes do grafo G. // Também atribui um rótulo sc[v] (os rótulos são 0,1,2,...) a cada vértice v de // G de modo que dois vértices tenham o mesmo rótulo se e somente se os dois // pertencem à mesma componente forte. A função é linear: consome tempo // proporcional a V+A. int GRAPHstrongCompsK( Graph G, int *sc); // Coloração de vértices //////////////////////////////////////////////////////////////////////////////// // Esta função calcula uma coloração válida dos vértices do grafo não-dirigido G // e devolve o número de cores usadas. A coloração é armazenada no vetor // color[]. A função procura usar poucas cores, mas em geral usa muito mais // cores que o mínimo necessário. (A função implementa a heurística da // "coloração sequencial".) int UGRAPHseqColoring( UGraph G, int *color); // Calcula uma coloração válida dos vértices do grafo não-dirigido G e devolve o // número de cores usadas. A coloração é armazenada no vetor color[]. A função // implementa o algoritmo DSatur de D. Brélaz. O número de cores é, em geral, // maior o mínimo necessário. int UGRAPHcolorBrelaz( UGraph G, int *color); // Calcula uma coloração válida dos vértices do grafo não-dirigido G com número // mínimo de cores. A função devolve o número de cores e armazena a coloração no // vetor color[0..V-1]. (Usa um algoritmo força-bruta de backtracking e portanto // consome tempo exponencial no tamanho do grafo.) int UGRAPHbruteColoring0( UGraph G, int *color); // Versão de UGRAPHbruteColoring0() que começa por encontrar e colorir uma // clique maximal. int UGRAPHbruteColoring1( UGraph G, int *color); // Clique máxima //////////////////////////////////////////////////////////////////////////////// // Esta função calcula uma clique maximal no grafo não-dirigido G e devolve o // número de vértices da clique. Armazena em clique[0..V-1] o vetor // característico da clique calculada. (A função se esforça para encontrar uma // clique grande.) int UGRAPHmaximalClique( UGraph G, bool *clique); // Grafos bipartidos e circuitos ímpares //////////////////////////////////////////////////////////////////////////////// // Decide se o grafo não-dirigido G admite bipartição. Em caso afirmativo, // atribui uma "cor", 0 ou 1, a cada vértice de G de tal forma que toda aresta // tenha pontas de cores diferentes. As cores dos vértices são armazenadas no // vetor color[] indexado pelos vértices. bool UGRAPHtwoColor( UGraph G, int *color); // Recebe um grafo não-dirigido G e devolve true ou false. No primeiro caso, // armazena uma bicoloração dos vértices de G (as duas cores são 0 e 1) no // vetor color[0..V-1]. No segundo caso, armazena (a sequência de vértices de) // um circuito ímpar no vetor oddc[0..k], sendo k >= 1 o menor índice tal que // v[k] == v[0]. bool UGRAPHtwoColorOrOddCircuit( UGraph G, int *color, int *oddc); // Emparelhamentos (= matchings) //////////////////////////////////////////////////////////////////////////////// // Um emparelhamento é representado por um vetor match[0..V-1] de vértices // indexado por vértices. Se o emparelhamento casa um vértice v com um vértice // w, temos match[v] == w e match[w] == v. Se v é solteiro (ou seja, não incide // em aresta alguma do empaelhamento), então match[v] == -1. É claro que vale a // seguinte propriedade: se match[v] != -1 então match[match[v]] == v. // Um emparelhamento é máximo se não existe outro maior. Um emparelhamento M é // maximal se não existe outro maior que contenha M. // Calcula um emparelhamento maximal no grafo G. Armazena o emparelhamento no // vetor match[] e devolve o tamanho do emparelhamento. int UGRAPHmaximalMatching( UGraph G, vertex *match); // Um caminho é alternante (= alternating) em relação a um emparelhamento M se // for simples e se suas arestas estiverem alternadamente em M e fora de M. // Um caminho alternante é aumentador (= augmenting) se começa e termina num // vértice solteiro e tem comprimento maior que 0. // Emparelhamentos em grafos bipartidos (= bipartite matching) //////////////////////////////////////////////////////////////////////////////// // Esta função calcula um emparelhamento máximo M e uma cobertura mínima K no // grafo não-dirigido bipartido G. A bipartição de G é dada pelo vetor // color[0..V-1], que tem valores 0 e 1. A função devolve o tamanho comum de M // e K. Também armazena uma representação de M no vetor match[0..V-1] e o vetor // característico de K no vetor cover[]. (A função usa busca BFS para procurar // caminhos aumentadores. A função não está no livro de Sedgewick.) int UGRAPHbipMatching( UGraph G, int *color, vertex *match, bool *cover); // Algoritmo de Prim para árvores geradoras de custo mínimo (= MST = minimal // spanning tree) //////////////////////////////////////////////////////////////////////////////// // Recebe um grafo não-dirigido conexo G com custos arbitrários nas arestas e // devolve o custo de uma MST de G. (Se G não for conexo, calcula uma MST da // componente conexa de G que contém o vértice 0.) Também armazena no vetor // pa[0..V-1], alocado pelo cliente, o vetor de pais que representa uma MST. A // função supõe que a soma de todos os custos positivos é menor que INT_MAX e a // soma de todos os custos negativos é maior que INT_MIN. (Esta é uma // implementação ingênua do algoritmo de Prim. A função é quadrática: consome // V*E unidades de tempo no pior caso.) int UGRAPHmstP0( UGraph G, vertex *pa); // Recebe um grafo não-dirigido conexo G com custos arbitrários nas arestas e // devolve o custo de uma MST de G. (Se G não for conexo, calcula uma MST da // componente conexa de G que contém o vértice 0.) Também armazena no vetor // pa[0..V-1], alocado pelo cliente, o vetor de pais que representa uma MST. A // função supõe que a soma de todos os custos positivos é menor que INT_MAX e a // soma de todos os custos negativos é maior que INT_MIN. (Esta é uma // implementação eficiente do algoritmo de Prim apropriada para grafos densos. // A função consome V^2 unidades de tempo no pior caso.) int UGRAPHmstP1( UGraph G, vertex *pa); // Recebe um grafo não-dirigido conexo G com custos arbitrários nas arestas e // devolve o custo de uma MST de G. (Se G não for conexo, calcula uma MST da // componente conexa de G que contém o vértice 0.) Também armazena no vetor // pa[0..V-1], alocado pelo cliente, o vetor de pais que representa uma MST. A // função supõe que a soma de todos os custos positivos é menor que INT_MAX e a // soma de todos os custos negativos é maior que INT_MIN. (Esta é uma // implementação eficiente do algoritmo de Prim apropriada para grafos esparsos. // Consome E log V unidades de tempo no pior caso.) int UGRAPHmstP2( UGraph G, vertex *pa); // Algoritmo de Kruskal para árvores geradoras de custo mínimo (= MST = minimal // spanning tree) //////////////////////////////////////////////////////////////////////////////// // Recebe um grafo não-dirigido conexo G com custos arbitrários nas arestas e // devolve o custo de uma MST de G. Também armazena no vetor mst[0..V-2] // (alocado pelo cliente) as arestas de uma MST. A função supõe que a soma de // todos os custos positivos é menor que INT_MAX e a soma de todos os custos // negativos é maior que INT_MIN. (Esta é uma implementação ingênua do algoritmo // de Kruskal. A função consome V*(E+V) unidades de tempo no pior caso.) int UGRAPHmstK0( UGraph G, edge mst[]); // Recebe um grafo não-dirigido conexo G com custos arbitrários nas arestas e // devolve o custo de uma MST de G. Também armazena no vetor mst[0..V-2] // (alocado pelo cliente) as arestas de uma MST. A função supõe que a soma de // todos os custos positivos é menor que INT_MAX e a soma de todos os custos // negativos é maior que INT_MIN. (Esta é uma implementação eficiente do // algoritmo de Kruskal. Consome V*(E+V) log^* V unidades de tempo no pior // caso.) int UGRAPHmstK1( UGraph G, edge mst[]); // Caminhos de custo mínimo (CPT) //////////////////////////////////////////////////////////////////////////////// // CPT = cheapest-paths tree = árvore de caminhos de custo mínimo. // Algoritmo de Bellman-Ford para caminhos mínimos (custo arbitrário) //////////////////////////////////////////////////////////////////////////////// // Custos nos arcos são arbitrários (positivos e negativos). // Recebe um vértice s e um grafo G com custos arbitrários nos arcos. Devolve -1 // ou um vértice z. No primeiro caso, G não tem ciclo negativo ao alcance de s. // Nesse caso, armazena em pa[] o vetor de pais de uma CPT com raiz s do // subgrafo de G induzido pelo conjunto de vértices ao alcance de s e armazena // em dist[] o vetor das distâncias a partir de s. (Se algum vértice v não // estiver ao alcance de s, pa[v] valerá -1 e dist[v] valerá INT_MAX.) No // segundo caso, z pertence a um ciclo negativo que está ao alcance de s; o // ciclo propriamente dito é o inverso de z-pa[z]-pa[pa[z]]-...-z. (Esta é uma // implementação "com fila FIFO" do algoritmo de Bellman-Ford. A função supõe // que a soma de todos os custos positivos é menor que INT_MAX e a soma de todos // os custos negativos é maior que INT_MIN.) vertex GRAPHcptBF( Graph G, vertex s, vertex *pa, int *dist); // Caminhos baratos em dags (custos arbirários) //////////////////////////////////////////////////////////////////////////////// // Esta função recebe um dag G com custos arbitrários nos arcos, uma permutação // topológica vv[] de G, e um vértice s de G. A função armazena uma CPT com raiz // s no vetor de pais pa[]. Se um vértice v não está ao alcance de s, teremos // pa[v] == -1. As distâncias a partir de s são armazenadas no vetor dist[]. Os // vetores pa[0..V-1] e dist[0..V-1] devem ser alocados pelo cliente. A função // supõe que a soma de todos os custos positivos é menor que INT_MAX e a soma de // todos os custos negativos é maior que INT_MIN. void DAGcpt( Dag G, vertex *vv, vertex s, vertex *pa, int *dist); // Algoritmo de Dijkstra para caminhos mínimos sob custos positivos //////////////////////////////////////////////////////////////////////////////// // Recebe um grafo G com custos positivos nos arcos e um vértice s. Armazena uma // CPT de G com raiz s no vetor de pais pa[]. Se um vértice v não estiver ao // alcance de s, pa[v] valerá -1. As distâncias a partir de s são armazenadas // no vetor dist[]. Os vetores pa[] e dist[] devem ser alocados pelo cliente. // Esta é uma implementação ingênua do algoritmo de Dijkstra. Ela consome V*A // unidades de tempo. void GRAPHcptD0( Graph G, vertex s, vertex *pa, int *dist); // Recebe um grafo G com custos positivos nos arcos e um vértice s. Armazena uma // CPT de G com raiz s no vetor de pais pa[]. Se um vértice v não estiver ao // alcance de s, pa[v] valerá -1. As distâncias a partir de s são armazenadas no // vetor dist[]. Os vetores pa[] e dist[] devem ser alocados pelo cliente. Esta // é uma implementação do algoritmo de Dijkstra. Ela consome V^2 unidades de // tempo. void GRAPHcptD1( Graph G, vertex s, vertex *pa, int *dist); // Recebe um grafo G com custos positivos nos arcos e um vértice s. Armazena uma // CPT de G com raiz s no vetor de pais pa[]. Se um vértice v não estiver ao // alcance de s, pa[v] valerá -1. As distâncias a partir de s são armazenadas no // vetor dist[]. Os vetores pa[] e dist[] devem ser alocados pelo cliente. Esta // é uma implementação do algoritmo de Dijkstra. Ela consome A log V unidades de // tempo. void GRAPHcptD2( Graph G, vertex s, vertex *pa, int *dist); // Implementação default do algoritmo de Dijkstra. #define GRAPHcptD GRAPHcptD2 // Caminhos de comprimento máximo (= longest path) e de custo máximo //////////////////////////////////////////////////////////////////////////////// // Recebe um grafo G e vértices s e t. Devolve o comprimento de um caminho // simples de comprimento máximo de s a t. (Em particular, devolve 0 se s == t.) // Se não existe caminho algum de s a t, devolve -1 (que representa infinito // negativo). Cuidado! Esta função só é razoável para grafos MUITO PEQUENOS. int GRAPHmaxPath( Graph G, vertex s, vertex t); // Recebe um grafo G com custos positivos nos arcos e vértices s e t. Devolve o // custo de um caminho simples de custo máximo de s a t. (Em particular, devolve // 0 se s == t.) Se não existe caminho algum de s a t, devolve -1 (que // representa infinito negativo). Cuidado! Esta função só é razoável para grafos // MUITO PEQUENOS. int GRAPHmaxCostPath( Graph G, vertex s, vertex t); // Fluxo máximo (max flow) //////////////////////////////////////////////////////////////////////////////// // A implementação do algoritmo de fluxo máximo usa os campos flow, twin e type // dos nós (nodes) das lista de adjacência. // Esta função constrói o grafo capacitado descrito no arquivo infile. Formato // do arquivo: primeiro o número de vértices e o número de arcos, depois o // vértice inicial e o vértice final, depois os pares de vértices que definem os // arcos, seguidos das respectivas capacidades. As demais linhas do arquivo são // ignoradas (podendo ser usadas para comentários). Exemplo: // 6 10 // 1 3 // 0-4 91 // 0-1 92 // 2-4 88 // 2-3 99 // 2-0 99 // 3-5 88 // 3-4 77 // 4-5 66 // 4-1 55 // 5-1 44 // Os vértice inicial é armazenado em *ps e o final e *pt. A função devolve NULL // se, por qualquer motivo, o grafo não puder ser construído. Graph GRAPHinputArcsFlow( FILE *infile, int *ps, int *pt); // Recebe um grafo G com fluxo representado nos campos flow dos nós das listas // de adjacência. Devolve o saldo de fluxo no vértice s, ou seja, a quantidadade // de fluxo que sai de s menos a quantidadede fluxo que entra em s. int GRAPHflowIntensity( Graph G, vertex s); // Recebe um grafo G com vértice inicial s, vértice final t, e um fluxo de s a t // representado nos campos flow dos nós das listas de adjacência. Imprime uma // macarronada (ou seja, uma coleção de caminhos de s a t) que representa o // fluxo. Cuidado: esta função altera os campos flow dos nós das listas de // adjacência. void GRAPHflowDecomp( Graph G, vertex s, vertex t); // Todos os arcos devem ter capacidade (estritamente) menor que MCAP. #define MCAP INT_MAX // Esta função devolve a intensidade de um fluxo no grafo capacitado G com // vértice inicial s e vértice final t distintos. O fluxo tem intensidade máxima // dentre os que respeitam as capacidades e é armazenado nos campos flow dos nós // das listas de adjacência. Também armazena em visited[] o vetor característico // da margem superior de um corte de capacidade mínima dentre os que separam s // de t. (De acordo com o Teorema do Fluxo Máximo e Corte Mínimo, a intensidade // do fluxo é igual à capacidade do corte.) A função supõe que todos os arcos // têm capacidade menor que a constante MCAP. Esta versão da função usa // pseudocaminhos aumentadores de comprimento mínimo. int GRAPHmaxFlow1( Graph G, vertex s, vertex t, bool visited[]); // Esta é uma variante da função GRAPHmaxFlow1() que usa pseudocaminhos // aumentadores de máxima capacidade. int GRAPHmaxFlow2( Graph G, vertex s, vertex t, bool visited[]); #endif