그래프 구현, 함수 및 매개 변수. 더 이해가되는 것은 무엇입니까?

Question

그냥 "재미"의 종류에 대해 C에서 Algorithms (Cormen) 서적에 나오는 거의 모든 알고리즘을 개발하고 있습니다. 그래프 챕터에 도달했으며 내 디자인 방법을 잘 모르겠습니다. 함수,하지만 먼저 내 데이터 구조 (이 내 질문을 분명히 할 것입니다 희망) 봐.

typedef struct s_multi_matrix 
    { 
     int     width; 
     int     height; 
     int     depth; 
     multi_matrix_type type; // stores either MMTYPE_INT or MMTYPE_RECORD enums to know where to read values (ivals or rvals) 
     int *    ivals; 
     DT_record *   rvals; 
    } DT_multi_matrix; 

typedef struct s_double_linked_list 
    { 
     DT_record * sentinel; 
    } DT_double_linked_list; 

typedef struct s_record // multi purpose structure 
    { 
     int key; 
     enum e_record_type type; // stores either TYPE_INT, TYPE_SZ, TYPE_FLOAT, TYPE_VOID to know how to use the data union 
     union 
     { 
      int  ival; 
      char * sval; 
      float fval; 
      void * vval; 
     } data; 
     struct s_record * left, // for trees, disjoint sets and linked lists 
         * right, 
         * parent; 
    } DT_record; 


typedef struct s_graph // this is the structure I'm focusing on right now 
    { 
     graph_type    type;  // GRAPH_DIRECTED or GRAPH_UNDIRECTED 
     graph_adj_type   adj_type; // ADJ_LIST or ADJ_MATRIX 
     edge_type   etype; // WEIGHTED or NOT_WEIGHTED 
     union 
     { 
      DT_double_linked_list *  list; 
      DT_multi_matrix *   matrix; 
     } adjacency; 
    } DT_graph; 

그래서, 나는 DT_graph 유형을 조작하는 몇 가지 기능에 대해 생각하고 있어요 :

// takes a pointer to a pointer to a graph, allocates memory and sets properties 
void build_graph(DT_graph ** graph_ptr, graph_type gtype, graph_adj_type atype); 
// prints the graph in file (using graphviz) 
void print_graph(DT_graph * graph, char * graph_name); 

이것은 까다로운 부분, 내 그래프의 형태는 여러 가지 다른 유형의 조합 (방향성이 가중 가장자리를 가지고 있기 때문에,

void dgraph_add_wedge(DT_graph * graph, DT_record * u, DT_record * v, int weight); 
void ugraph_add_wedge(DT_graph * graph, DT_record * u, DT_record * v, int weight); 
void dgraph_add_nwedge(DT_graph * graph, DT_record * u, DT_record * v); 
void ugraph_add_nwedge(DT_graph * graph, DT_record * u, DT_record * v); 

: 감독 및 가중 가장자리, 방향성과 가장자리를 가중하지, 감독하지 무게 가장자리는 ...) 나는 기능을위한 가장 좋은 방법 인 궁금하네요 처음 두 개는 directed/undirected 그래프에 가중치 정점을 추가하고 마지막 두 개는 동일한 것을 수행하지만 에지와 관련된 가중치는 없습니다. 내 마음에 오는 다른 방법은 다음과 같습니다

void graph_add_edge(DT_graph * graph, DT_record * u, DT_record * v, edge_type etype, graph_type gtype); 

이 모든 것을위한 "황금"방법처럼 보인다 및 ETYPE 및 gtype의 값에 따라하면 그래프에서 다른 작업을 할 것입니다.

귀하의 경험과 지식을 바탕으로 Soooooooo는 무엇을 권하고 있습니까?

나는 이것이 내 구현이기 때문에 어느 누구도 이전에 물어 본 것 같습니다.

Answer 1

안심이 C입니다. C++의 경우 이러한 질문 중 일부는 언어의 다형성 기능에 의해 처리됩니다. 반면에 알고리즘을 연구하면 알고리즘의 일부 매끄러운 기능보다는 알고리즘/데이터 구조에 초점을 맞출 수 있습니다.

어쨌든 ... 내 두 센트 : 그래프 형으로 불리는 방법 (들)을 알리기 위해 DT_Graph에 속성을 addomg없는 이유 : D를 선택 또는 U 형 그래프에 관해서

. 결국 이것은 그래프가 생성 될 때 지정됩니다. ==> 빵! 우리는 오직 두 가지 방법으로 만합니다.

가장자리 가중치와 관련하여 ... API를 사용하면 두 가지 방법이 바람직 할 수 있습니다. 이유는 추가 매개 변수를 사용하여 무게가 아닌 경우를 괴롭히는 이유입니다. 구현 방식에 따라 4 가지 경우 모두 가능한 한 많은 로직을 공유 할 수 있습니다. 그리고 솔직히 말해서, 일단이 모든 것을 썼다면, 당신이 제안한 것과 같은 "황금색"하나의 방법으로 여전히 이것을 볼 수 있습니다.

코딩과 함께 행운을 비네!