Componentele conexe ale unui graf neorientat

Program in C care afla componentele conexe dintr-un graf neorientat, folosind o parcurgere DFS. Din fisierul graf.txt se citesc numarul de noduri si perechile de noduri reprezentand fiecare muchie.

#include "stdio.h"

int n, a[20][20], viz[20];

void citire()
{ FILE * f = fopen("graf.txt","r");
fscanf(f,"%d", &n); int i,j;
while(!feof(f))
{ fscanf(f,"%d %d", &i, &j);
a[i][j]=1; a[j][i]=1; a[i][i]=1; a[j][j]=1; }
}

/* afisare componente conexe pt graf neorientat */

void df(int vf)
{ int i; viz[vf]=1;
printf("%d ",vf); //afisare
for(i=1; i<=n; i++)
if(a[vf][i]==1 && viz[i]==0)
df(i);
}


int main()
{ int p,i; p=0;
citire();
for (i=1; i<=n; i++)
if(viz[i]==0)
{ df(i); printf("\n"); p++; }
if(p==1)
printf(" graf conex\n");
else
printf("are %d componente conexe\n", p);
return 0;
}

Algoritmul lui Kruskal, folosind operatii cu multimi disjuncte

Arborele minim de acoperire (AMA) pentru un graf se defineste pentru grafuri neorientate si conexe (toate nodurile grafului se afla in aceeasi componenta conexa).

Dandu-se un graf conex si neorientat G=(V, E), unde V = multimea nodurilor, iar E multimea muchiilor grafului G, se numeste arbore minim de acoperire un graf conex si neorientat G' = (V, E'), unde E' inclus in E cu proprietatile:
- G' este este un arbore (graf aciclic);
- suma costurilor muchiilor din E' sa fie minima.

Dintre algoritmii clasici care se ocupa de determinarea arborelui minim de acoperire amintim: algoritmul Kruskal si algoritmul Prim.

=== Pseudocod ===

Fie G=(V, E), graf neorientat si conex
1) AMA = multimea vida
2) Pentru fiecare nod din V
creeaza_multime(v)
3) Sorteaza muchiile din E crescator dupa cost
4) Pentru fiecare muchie (u, v) din E in ordine crescatoare
- Daca gaseste_multime(u) != gaseste_multime(v)
a) Se adauga muchia (u, v) in AMA
b) reuneste(u, v)

=== Implementare in C ===

#include "stdio.h"
#include "stdlib.h"
#define MAX 100
#define INF -1

int n,m,**b;
typedef struct multime {
int c; //contorul multimii
int S[MAX]; //elementele multimii
} Set;

typedef struct muchie {
int x; int y; int cost;
} Muchie;

Muchie mu[MAX];
Set C[MAX]; //colectia
int nset; //nr de seturi

void citire()
{ FILE *f=fopen("in","r");
fscanf(f,"%d",&n);
int i,j,k,cost;
fscanf(f,"%d",&m); //nr muchii
for(i=0;i<=m-1;i++)
{ fscanf(f,"%d %d %d",&j,&k,&cost); mu[i].x=j; mu[i].y=k; mu[i].cost=cost; }
}


/* functii pt multimi disjuncte */

void Make_Set (int n)
{ int i; nset=n;
for(i=0; i<=n-1; i++)
{ C[i].c=1;
C[i].S[0]=i; }
}

void Print_Set()
{ int i,j;
for(i=0; i<=nset-1; i++)
{ for(j=0; j<=C[i].c-1 ; j++)
printf("%d ",C[i].S[j]);
printf("\n"); }
}

//identific a cata multime este multimea in care se afla un element
int Find(int x)
{ int j,i;
for(i=0;i<=nset-1;i++) // pt fiecare set
{ for(j=0; j<=C[i].c-1; j++)
if(x==C[i].S[j])
return i;
}
return -1;
}


void Set_Union(int a,int b) // reuniunea se face in C[a],se sterge C[b]
{ int i;
for(i=0;i<=C[b].c-1;i++)
if(Find(C[b].S[i])!=a)
{ C[a].S[C[a].c]=C[b].S[i]; C[a].c++; }
for(i=b; i<=nset-1; i++)
C[i]=C[i+1];
nset--;
}

void print_muchii()
{ int i;
for(i=0;i<=m-1;i++)
printf("%d %d %d \n",mu[i].x,mu[i].y,mu[i].cost);
}

Muchie arc_min() //gaseste arcul de cost minim si apoi il sterge!
{ int i,min=mu[0].cost,poz=0;
Muchie x=mu[0];
for(i=1; i<=m-1; i++)
if(mu[i].cost < min)
{ min=mu[i].cost; poz=i; x=mu[i]; }
for(i=poz; i<=m-2; i++)
mu[i]=mu[i+1];
m--;
return x;
}

void kruskal()
{
Make_Set(n);
Muchie a;
int u,v,i,j;
b=(int **)malloc(n*sizeof(int *));
for(i=0; i<=n-1; i++)
b[i]=(int *)malloc(n*sizeof(int));
for(i=0; i<=n-1; i++)
for(j=0; j<=n-1; j++)
{ if(i!=j)
b[i][j]=INF;
else
b[i][j]=0; }

int nm=0;
while (nm < n-1) // cat timp nu am atins n-1 muchii
{ a=arc_min();
u=a.x; v=a.y;
if(Find(u)!=Find(v)) // daca se afla in seturi diferite
{ Set_Union(Find(u),Find(v));
b[u][v]=a.cost; b[v][u]=a.cost; nm++; } //adaug muchie la graf nou
}
}

int *viz;

void afisare(int vf)
{
int i; viz[vf]=1;
printf("%d ",vf);

for(i=0; i<=n-1; i++)
if(b[vf][i]>=0 && viz[i]==0)
afisare(i);
}

void afisare2()
{ int i,j,w;
for(i=0; i<=n-1; i++)
for(j=i+1; j<=n-1; j++)
{ w=b[i][j];
if(w > 0)
printf("muchia %d-%d cost %d\n", i,j, w);
}
}

int main()
{ citire();
kruskal();
viz=(int *)malloc(n*sizeof(int));
int i;
for(i=0; i<=n-1 ;i++)
viz[i]=0;
afisare2();
free(viz);
return 0;
}

Implementarea unei stive in Clips

; fapte de indeplinit

(deffacts init

(push 5)

(pop)

(push abc)

(push 12)

(top)

(pop)

(top)

)

(defrule stack_init

; nu avem nici o condiţie în LHS; regula se execută la începutul programului

=>

; se iniţializează stiva cu un fapt vid

; celelalte reguli nu se vor aprinde decât dacă există un fapt stack

(assert (stack))

)

(defrule stack_push

?f1 <- (push ?element)

?f2 <- (stack $?stacklist)

=>

; o regulă se aplică o singură dată pentru aceeaşi condiţie

; în acest caz se şterge f1 pentru că se schimbă f2 şi deci se schimbă LHS ca întreg

(retract ?f1 ?f2)

; se introduce elementul în stivă

(assert (stack ?element $?stacklist))

(printout t "Push: " ?element crlf)

)

(defrule stack_pop

?f1 <- (pop)

?f2 <- (stack ?element $?stacklist)

=>

(retract ?f1 ?f2)

; se scoate elementul din stivă

(assert (stack $?stacklist))

(printout t "Pop: " ?element crlf)

)

(defrule stack_top

(top)

(stack ?element $?stacklist)

=>

(printout t "Top: " ?element crlf)

; aici nu avem nevoie să ştergem fapte, LHS rămâne neschimbată

)

CLIPS

;; rezolvarea problemei cu lupul, capra, varza si taranul care trebuie sa treaca podul

(deffacts fapte

(fail 0 1 1 0)

(fail 1 0 0 0)

(fail 0 1 1 1)

(fail 1 1 0 0)

(fail 0 0 1 1)

(fail 1 0 0 1)

(stop 0 0 0 0)

)

(deffunction fct

(?x)

(mod (+ 1 ?x) 2)

)

(defrule Taran

(stop ?t ?l ?c ?v)

(not (fail ?t1&~?t ?l ?c ?v))

=>

(assert (stop (fct ?t) ?l ?c ?v))

)

(defrule Capra

(stop ?t ?l ?t ?v)

(not (fail ?t1&~?t ?l ?c1&~?t ?v))

=>

(assert (stop (fct ?t) ?l (fct ?t) ?v))

)

(defrule Varza

(stop ?t ?l ?c ?t)

(not (fail ?t1&~?t ?l ?c ?v1&~?t))

=>

(assert (stop (fct ?t) ?l ?c (fct ?t)))

)

(defrule Lup

(stop ?t ?t ?c ?v)

(not (fail ?t1&~?t ?l1&~?t ?c ?v))

=>

(assert (stop (fct ?t) (fct ?t) ?c ?v))

)

;; un program care filtreaza numai elementele pozitive dintr-un sir

;; REZOLVARE

;; folosim un mic truc, retragem elementele negative.

;; pentru conditii mai complexe, se putea folosi not pe

;; conditia ceruta in problema.

(deffacts pb3 (rez3 6 -5 4 3 -2 -1 0))

(defrule filter-pos

?f <- (rez3 $?start ?x&:(< ?x 0) $?end)

=>

(retract ?f)

(assert (rez3 $?start $?end)))

Demonstrarea unui scop cf. unui set de clauze Horn

-- Un nucleu pentru demonstrarea unui scop conform unui set de clauze Horn.

-- Procedura de inferenta: rezolutie

-- Metoda de demonstrare: reducere la absurd

-- Strategie control: parcurgere in adincime a arborelui AND-OR al demonstratiei

-- CG mai, 2010

module Resolution where

data Subst a = VoidSubst | Bindings [(String,a)] deriving Show

solve goal all_props = solve' [goal] all_props VoidSubst where

solve' [] props subst = (True,subst) -- Frunza

solve' goals [] subst = (False,subst)

solve' (goal:goals) (prop:props) subst = -- nod OR

let (flag1,subst1) = unify goal (head prop) subst

in if flag1

then let (flag2,subst2) = solve' ((tail prop)++goals) all_props subst1 --nod AND

in if flag2 then (True,subst2)

else solve' (goal:goals) props subst

else solve' (goal:goals) props subst

unify term1 term2 subst = (term1==term2,VoidSubst)

--- O reprezentare simpla pentru termeni fara variabile

data Constant = Maria | Ion | Fred | Gigi deriving (Eq,Show)

data Predicate a = Iubeste a a | Human a | Prieten a a deriving (Eq,Show)

{-

1. Un termen este reprezentat ca un tuplu (predicat val1 val2 ... valn)

De exemplu tuplul (Iubeste Maria Ion) sta pentru iubeste(Maria,Ion)

2. O propozitie este o implicatie (clauza Horn) term1 ^ term2 ^ ... ^ termn => term, n>=1,

si este reprezentata prin lista [term, term1, term2, ..., termn]

De exemplu,

[Human Ion, Iubeste Maria Ion, Human Maria] sta pentru propozitia

iubeste(Maria,Ion) ^ human(Maria) => human(Ion)

3. Propozitia particulara True => term (axioma) este reprezentata prin term

De exemplu,

[Human Maria] sta pentru propozitia True => human(Maria)

4. Propozitiile sunt date ca o lista [prop1,prop2,...,propm]

-}

propozitii = [

[Human Maria],

[Human Ion, Iubeste Maria Ion, Human Maria],

[Human Fred, Human Ion, Prieten Ion Fred],

[Human Gigi],

[Prieten Ion Fred],

[Iubeste Maria Ion]

]

{-

solve (Human Ion) propozitii

solve (Human Fred) propozitii

solve (Human Gigi) propozitii

-}