[C] Graph In C

* 해당 글은 학과 수업으로 배운 내용과 코드가 포함되어 있으며 개인적 공부 목적으로 업로드하였습니다.

 

Graph는 점처럼 표시된 vertices 혹은 nodes가 line으로 표시된 edges와 연결된 형태를 나타낸다. 

각 edge는 한쌍의 vertices를 연결하고 있으며 두 vertices 사이에 최대 1개의 edge가 존재할 수 있다.

 

우리가 이 게시글에서 다룰 graph는

 - undirected : edge(B, A) = edge(A, B)

- no self-edges : (v, v) 사이에는 edge가 존재하지 않는다

graph는 vertices와 edge pair로 나타낼 수 있다. 

G = (V, E)

 

어떤 vertex의 neigbors는 해당 vertex와 edge를 통해 연결된 모든 vertices를 말한다. 

 

Lightsout

Lightsout은 n*n lights board에서 move를 통해서 직접 누른 light뿐만 아니라 주변 light까지 꺼지면 키고 켜지면 끄는 형식으로 진행하는 게임이며 모든 불이 다 꺼지면 끝나는 게임이다. 

 

이를 그래프로 생각하자면 vertex가 각 board configuration이고 각 움직임이 edge로 표현된다. 

-light를 두번 누르면 다시 이전 상태의 board로 돌아오게 된다. 

-self-edge가 없기 때문에 움직임은 무조건 새로운 board를 만든다.

 

해당 board를 풀기 위해서 우리는 모든 불을 끌 move sequence를 찾아야 한다. 

 

edge를 통해서 연결된 여러개의 vertices는 path라고 부른다. 

-즉 edge로 연결된 vertices series를 의미한다. 

-따라서 두 vertices 사이에 path는 다양하게 여러개 있을 수 있다. 

-따라서 board를 solve하는 것은 path를 찾는것과 마찬가지이다. 

 

n*n lightout에서 우리는 n*n 개의 move를 만들 수 있고 2^(n*n) board configuration이 존재할 수 있다.

graph로 나타내면

2^(n*n) vertices가 존재할 수 있고 n*n * 2^(n*n) / 2 edges가 존재할 수 있다. 

-undirected이기 때문에 2로 나눠준다. 

 

Graph는 conceptual model이 될 수도 있고 data structure만 될 수 도 있다. 

 

Data structure로 나타내기 위해서는

-graph 자체

-graph vertices (vertex type) : 이는 unsigned int로 정의된다

- graph edges

들을 나타내야 한다. 

 

graph를 활용한 기본 operation에는

-graph_new(n) : n vertices를 가진 새로운 graph를 만드는 것

-graph_size(G) : G의 vertices 개수를 return 하는 것

-graph_hasedge(G, v,w): G가 (v,w) 사이에 edge를 가지고 있는지 확인하는 것

-graph_addedge(G, v, w) : graph G에 (v, w) edge를 더한다. 

-graph_free(G) : graph를 free 시킨다. 

typedef unsigned int vertex;
typedef struct graph_header* graph_t;

graph_t graph_new(unsigned int numvert);
//@ensures \result!=NULL;

void graph_free(graph G);
//@requires G!=NULL;

unsigned int graph_size(graph_t G);
//@requires G!=NULL;

bool graph_hasedge(graph_t G, vertex v, vertex w);
//@requires G!=NULL;
//@requires v<graph_size(G) && w<graph_size(G);

void graph_addedge(graph_t G, vertex v, vertex w);
//@requires G!=NULL;
//@requires v<graph_size(G) && w<graph_size(G);
//@requires v!= w && !graph_hasedge(G, v,w); //오직 새로운 edge만 추가 가능

예시로 새로운 graph를 만들어보자

graph_t G = graph_new(5);
graph_addedge(G, 0, 1);
graph_addedge(G, 0, 4);
graph_addedge(G, 1, 2);
graph_addedge(G, 1, 4);
graph_addedge(G, 2, 3);
graph_addedge(G, 2, 4);

그림으로 나타내면 아래와 같이 나타낼 수 있다. 

이는 graph_hasedge(G, 3, 2) == true이지만

graph_hasedge(G, 3, 1) == false가 된다. 

 

Neighbors

neighbors 역시 비슷하게 interface로 나타낼 수 있다. 

abstrac type of neighbors: neighbors_t

Operations:

-graph_get_neighbors(G, v) : G의 vertex v의 neighbor를 return할 수 있다.

-graph_hasmore_neighbors(nbors) : 추가적인 neighbors가 있는지 체크한다.

-graph_next_neighbor(nbors) : 다음 neighbor를 return한다.

-graph_free_neighbors(nbors): unexamined 된 이웃들을 free 시킨다. 

typedef struct neighbor_header* neighbors_t;

neighbors_t graph_get_neighbors(graph_t G, vertex v);
//@requires G!=NULL && v<graph_size(G);
//@ensures \result !=NULL;

bool graph_hasmore_neighbors(neighbors_t nbors);
//@requires nbors!=NULL;

vertex graph_next_neighbor(neighbors_t nbors);
//@requires nbors != NULL;
//@requires graph_hasmore_neighbors(nbors);

void graph_free_neighbors(neighbors_t nbors);
//@requires nbors != NULL;

위 만들어놓은 graph를 활용해 예시를 들어보자 

neighbors_t n4 = graph_get_neighbors(G, 4);

-> n4는 0,1,2를 가지게 된다.

vertex a = graph_next_neighbor(n4);

-> a 는 0,1,2 모두가 될 수 있다. 

-> 여기서 1이라고 가정해보자

vertex a = graph_next_neighbor(n4);

-> a는 0, 2가 될 수 있다. 

-> 여기서 0이라고 가정해보자

vertex a = graph_next_neighbor(n4);

-> a는 2여야만 한다. 

graph_hasmore_neighbors(n4);

-> 모든 vertex를 다 보았으므로 false를 return 해야한다.

 

이러한 graph를 실제로 implement하기 위해서는

-linked list of edges

-hash set이 필요하다

 

Cost Operations

만약 graph가 v개의 vertices가 있다면 edges는

-0개에서 v(v-1)/2개가 될수 있다. 

따라서 e∈ O(v^2)이다.

 

각 linked list 와 hash set edges의 cost를 살펴보면

	Linked list of edges	Hash set of edges
graph_hasedge	O(e)	O(1) avg
graph_addedge	O(1)	O(1) avg+ amortized

특정 vertex의 neighbor를 찾는 것은 모든 edge를 확인해야 하는 것과 같다. 

-> graph_get_neighbors는 O(e)의 cost를 가진다는 뜻이다. 

 

하나의 vertex에 총 몇개의 neighbors가 있을 수 있을까?

최대 v-1: 만약 vertex가 다른 모든 vertices와 edge가 있을 경우

최대 e: graph edges보다 많은 neighbors는 있을 수 없다. 

 

따라서 하나의 vertex는 O(min(v,e)) neighbors가 존재한다. 

위의 표와 종합해보면

	linked list of edges	hash set of edges
graph_hasedge	O(e)	O(1) avg
graph_addedge	O(1)	O(1) avg+amort
graph_get_neighbors	O(e)	O(e)
iterating through neighbors	O(min(v,e))	O(min(v,e))

 

graph를 나타내는 두가지의 representation을 살펴보자

 

Adjacency Matrix Representation

-graph를 v*v boolean matrix로 나타낼 수 있다. 

만약 i 와 j 사이에 edge가 있다면 M[i,j]== true 

그렇지 않다면 M[i,j] == false

이때 M을 adjacency matrix라고 부른다. 

 

matrix로 각 operation cost를 계산해보면

graph_hasedge(G, v, w) = O(1)

graph_addedge(G, v, w) = O(1)

graph_get_neighbors(G,v) = O(v)

-v vertex의 row를 다 거쳐야 한다. 

 

필요한 space: O(v^2)

 

Adjacency List Representation

각 vertex v별로 그 neighbors를 list에 저장해놓은 형태를 

adjacency list of v라고 한다. 

각 operation cost를 계산해보면

graph_hasedge(G, v, w) = O(min(v,e))

graph_addedge(G, v, w) = O(1)

graph_get_neighbors(G,v) = O(v)

 

필요한 space: O(v+e)

- v element array 와 2e list items

O(v+e) 는 O(max(v,e))로 쓰인다. 

 

matrix와 list별 cost를 정리해보면

	Adjacency Matrix	Adjacency List
space	O(v^2)	O(v+e)
graph_hasedge	O(1)	O(min(v,e))
graph_addedge	O(1)	O(1)
graph_get_neighbors	O(v)	O(1)
iterating through neighbors	O(min(v,e))	O(min(v,e))

그렇다면 어떤 representation을 언제 써야할까?

dense graph: edge가 많은 경우 

sparse graph: 상대적으로 edge가 적은 경우

 

Dense graph의 cost

	Adjacency matrix	Adjacency list
space	O(v^2)	O(v+e) -> O(v^2)
graph_hasedge	O(1)	O(min(v,e)) -> O(v)
graph_addedge	O(1)	O(1)
graph_get_neighbors	O(v)	O(1)
iterating through neighbors	O(min(v,e)) -> O(v)	O(min(v,e)) -> O(v)

graph_has_edge는 matrix가 빠르고

graph_get_neighbors는 list가 빠르다.

따라서 dense graphs는 두 representations은 같은 비용을 가지지만 graph_hasedge는 matrix가 더 빠르다. 

-> matrix를 사용하는 것이 더 효율적이다. 

 

Sparse graph의 cost

	Adjacency matrix	Adjacency list
space	O(v^2)	O(v+e) -> O(v)
graph_hasedge	O(1)	O(min(v,e)) -> O(v)
graph_addedge	O(1)	O(1)
graph_get_neighbors	O(v)	O(1)
iterating through neighbors	O(min(v,e)) -> O(v)	O(min(v,e)) -> O(v)

list가 훨씬 더 적은 space를 요구한다는 것을 확인할 수 있다. 

graph_has_edge는 matrix가 빠르고

graph_get_neighbors는 list가 빠르다.

따라서 sparse graphs의 경우 두 representations은 같은 비용을 가지지만 list가 더 적은 space가 사용되기 때문에 list를 사용하는 것이 더 효율적이다. 

 

Adjacency list는 vertices가 각 node인 null-terminated list와 같다. 

이 graph data structure의 경우

graph vertices개수와 그 개수만큼의 array인 adjacency list가 존재한다

typedef struct adjlist_node adjlist;
struct adjlist_node{
  vertex vert;
  adjlist* next;
};

typedef struct graph_header graph;
struct graph_header{
  unsigned int size;
  adjlist** adj;
};

이 interface는 또한 vertex를 아래와 같이 정의한다.

typedef unsigned int vertex;

bool is_vertex(graph* G, vertex v){
  REQUIRES(G !=NULL);
  return v <G->size; //v가 unsigned int 타입이라서 0<= v는 따로 쓰지 않아도 된다. 
}

vertex는 0과 graph size사이에 있는 값이어야 valid하다

 

graph의 경우 

-non-NULL

-length of adjacency listr가 graph size와 동일해야 하고

-각 adjacency list가 valid 해야한다. 

bool is_graph(graph* G){
  if(G==NULL) return false;
  //@assert(G->size==\length(G->adj));
  for (unsigned int i=0; i<G->size; i++){
    if(!is_adjlist(G, i, G->adj[i])) return false;
  }
  return true;
}

각 adjacency list의 경우

-Null-terminated

-각 vertex가 valid해야하고

-self-edges가 없어야하고

-모든 outgoing edges는 다시 돌아올 edge가 있어야 하고

-duplicate edge가 없어야 한다. 

bool is_adjlist(graph* G, vertex v, adjlist* L){
 REQUIRES(G!=NULL)
 //@requires (G->size == \length(G, adj));
 if (!is_acyclic(L)) return false;
 while(L!=NULL){
   vertex w = L->vert; //w is a neighbor of v
   
   //neighbors are legal vertices
   if (!is_vertex(G, w)) return false;
   
   //no self-edges
   if (v==w) return false;
   
   //every outgoing edge has corresponding edge coming back to it
   if (!is_in_adjlist(G->adj[w],v)) return false;
   
   //Edges aren't duplicated
   if (is_in_adjlist(L->next, w)) return false;
   
   L = L->next;
  }
  return true;
}

Basic operations

-graph_size: size를 return한다. (O(1))

unsigned int graph_size(graph* G){
  REQUIRES(is_graph(G));
  return G->size;
}

-graph_new : empty adjacency list를 만든다.

O(v) : v 개의 positions을 만들어야 한다.

graph* graph_new(unsigned int size){
  graph* G = xmalloc(sizeof(graph));
  G->size = size;
  G->adj = xcalloc(size, sizeof(adjlist*));
  ENSURES(is_graph(G));
  return G;
}

-graph_free는 모든 adjacency list, array, graph header를 free해야 한다. 

O(v+e): adjacency lists에 있는 2e nodes + v array positions

void graph_free(graph* G){
  REQUIRES(is_graph(G));
  for (unsigned int i=0; i<G->size; i++){
    adjlist* L = G->adj[i];
    while (L!=NULL){
      adjlist*tmp = L->next;
      free(L)
      L = L->next;
    }
  }
  free(G->adj);
  free(G);
}

-graph_hasedge(G, v, w)는 v positions의 adjacency list에 w를 Linear search로 찾아나간다. 

O(min(v,e))

bool graph_hasedge(graph* G, vertex v, vertex w){
  REQUIRES(is_graph(G));
  REQUIRES(is_vertex(G, v)&&is_vertex(G,w));
  
  for (adjlist* L = G->adj[v]; L!=NULL; L = L->next){
    if(L->vert==w) return true;
  }
  return false;
}

-graph_addedge(G, v,w): v와 w 사이에 edge를 추가한다.

-w를 v의  neighbor로, v를 w의 neighbor로 

O(1)

void graph_addedge(graph* G, vertex v, vertex w){
  REQUIRES(is_graph(G));
  REQUIRES(is_vertex(G,v) && is_vertex(G,w));
  REQUIRES(v!=w && !graph_hasedge(G, v, w));
  
  adjlist*L;
  
  L = xmalloc(sizeof(adjlist));
  L->vert = w;
  L->next = G->adj[v];
  G->adj[v] = L;
  
  L = xmalloc(sizeof(adjlist));
  L->vert = v;
  L->next = G->adj[w];
  G->adj[w] = L;
  
  ENSURES(is_graph(G));
  ENSURES(graph_hasedge(G, v, w));
  }

vertex의 adjaceny list 를 neighbors의 representation으로 나타낼 수 있다. 

typedef struct neighbor_header neighbors;
struct neighbor_header{
  adjlist* next_neighbor;
}

graph_get_neighbors(G,v)는

새로운 neighbor struct를 만들고 next_neighbor가 adjacency list v를 point하도록 하고 이 struct를 return 해야 한다. 

O(1)

neighbors* graph_get_neighbors(graph* G, vertex v){
   REQUIRES (is_graph(G) && is_vertex(G, v));
   
   neighbors* nbors = xmalloc(sizeof(neighbors));
   nbors->next_neighbor = G->adj[v];
   ENSURES(is_neighbors(nbors));
   return nbors;
 }

graph_next_neighbor는 말그대로 next_neighbor를 return하고 이것이 adjacency list에서 다음 field를 point하도록 한다. 

O(1)

vertex graph_next_neighbor(neighbors* nbors){
  REQUIRES(is_neighbors(nbors));
  REQUIRES(graph_hasmore_neighbors(nbors));
  
  vertex v = nbors->next_neighbor->vert;
  nbors->next_neighbor = nbors->next_neighbor->next;
  return v;
}

graph_hasmore_neighbors: adjacency list의 끝에 다다랐는지 확인한다. 

O(1)

bool graph_hasmore_neighbors(neighbors* nbors){
  REQUIRES(is_neighbors(nbors));
  return nbors->next_neighbor !=NULL;
}

graph_free_neighbors는 neighbor header만 free시킨다.

(adjacency list를 free하지 않도록 해야한다. )

O(1)

void graph_free_neighbors(neighbors* nbors){
  REQUIRES(is_neighbors(nbors));
  free(nbors);
}

cost를 종합해보자면

	Adjacency list
space	O(v+e)
graph_new	O(v)
graph_free	O(v+e)
graph_size	O(1)
graph_hasedge	O(min(v,e))
graph_addedge	O(1)
graph_get_neighbors	O(1)
graph_hasmore_neighbors	O(1)
graph_next_neighbor	O(1)
graph_free_neighbor	O(1)

 

graph interface를 활용해서 graph를 print할 수 있는 client function을 작성해보자

void graph_print(graph_t G){
  for (vertex v = 0; v < graph_size(G); v++){
    printf("Vertices connected to %u: ", v);
    neighbors_t nbors = graph_get_neighbors(G, v);
    while(graph_hasmore_neighbors(nbors)){
       vertex w = graph_next_neighbors(nbors);
       printf("%u", w);
    }
    graph_free_neighbors(nbors);
    printf("\n");
  }
}

adjacency list representation을 고려하여 v vertices와 e edges가 있다고 했을때

void graph_print(graph_t G){
  for (vertex v = 0; v < graph_size(G); v++){     //v times
    printf("Vertices connected to %u: ", v);      //O(1)          O(v)
    neighbors_t nbors = graph_get_neighbors(G, v);  //O(1)        O(v) 
    while(graph_hasmore_neighbors(nbors)){         //O(min(v,e))  O(v min(v,e))
       vertex w = graph_next_neighbors(nbors);     //O(1)         O(v min(v,e))
       printf("%u", w);
    }
    graph_free_neighbors(nbors);                   //O(1)         O(v min(v,e))
    printf("\n");
  }
}

cost: O(vmin(v,e))

 

하지만 이때 전체 graph_print는 모든 edge를 두번씩 방문한다는 점을 생각해야 한다. 

따라서 내부 while loop는 O(e)임을 알 수 있다. 

void graph_print(graph_t G){
  for (vertex v = 0; v < graph_size(G); v++){     //v times
    printf("Vertices connected to %u: ", v);      //O(1)          O(v)
    neighbors_t nbors = graph_get_neighbors(G, v);  //O(1)        O(v) 
    while(graph_hasmore_neighbors(nbors)){         //O(e)         O(v + e)
       vertex w = graph_next_neighbors(nbors);     //O(1)         O(v + e)
       printf("%u", w);
    }
    graph_free_neighbors(nbors);                   //O(1)         O(v + e)
    printf("\n");
  }
}

따라서 실제 cost는 O(v+e)이다.

 

같은 graph_print를 matrix representation으로 본다면

void graph_print(graph_t G){
  for (vertex v = 0; v < graph_size(G); v++){     //v times
    printf("Vertices connected to %u: ", v);      //O(1)          O(v)
    neighbors_t nbors = graph_get_neighbors(G, v);  //O(v)        O(v^2) 
    while(graph_hasmore_neighbors(nbors)){         //O(e)         O(v^2 + e)
       vertex w = graph_next_neighbors(nbors);     //O(1)         O(v^2 + e)
       printf("%u", w);
    }
    graph_free_neighbors(nbors);                   //O(1)         O(v^2 + e)
    printf("\n");
  }
}

matrix representation에서의 graph_print의 실제 cost는 O(v^2+e)이다.