Istoric

Prima pagină » Cum se dezvoltă »

Sprintul din noiembrie 2009

  • Lansarea este pe 01-12-2009.
  • Sprint-ul din 12-2009 va conține task-uri ce n-au fost realizate în acest sprint.
  • Se lucrează doar pe versiune instabilă din Temelia
    • unstable SVN/git branch

Descriere

  1. Generarea unui code tracer pentru Temelia
    1. Temelia va fi disponibilă sub o forma depanabilă ușor
      • printf-uri la începutul/sfârșitul funcțiilor
      • printf-uri în branch-uri, loop-uri etc
    2. De adaptat gramtica de C din exemplele ANTLR-ului pentru codul din Temelia
  2. Dezvoltarea grafului și a algoritmilor pe grafuri
    • Separarea implementării grafui de algoritmi
      • Algoritmii nu trebuie să știe ce fel de reprezentare are graful: matrice de adiacență, listă de adiacență etc
    • Pași propuși
      1. Studierea actualei implementări și propunerea noii structuri de graf
      2. Implementarea noii structuri de graf
      3. Portarea algoritmilor să funcționeze pe noua implementare
      4. Realizare de teste complexe: exemple și teste de performanță

Evoluție

  • Aici puteți scrie ce anume ați făcut până în prezent

14-11-2001

  • sana:
    1. Analizez gramatica de C din exemplele ANTLR-ului și analizez dacă se poate adapta la Temelia pentru generarea unui logger
      • Abandonez ideea pentru că nu am control asupra contextului în care se inserează primitive de afișare
        • Nu doresc logarea la nivel de instrucțiune C și nici la nivel de funcții C
        • Îmi doresc o logare dependetă de numele funcției (unele funcții sunt mai importante/complexe decât altele) => acționare manuală
    2. Structura actuală de graf este:
       1 struct _graph_t
 2 {
 3     /*! Maximum number of vertices. */
 4     unsigned int size;
 5 
 6     /*! Array of vertices. */
 7     vector_t vertices;
 8 
 9     /*! Adjacency Matrix. */
10     matrix_t adjacency_matrix;
11 };
      • Problema cu această abordare este că reprezentarea grafului este hardcodată la matrice de adiacență.
      • Trebuie modificată structura astfel încât clientul structurii să nu fie limitat la o anumită reprezentare.
      • Propunerea mea este
         1 struct _graph_call_back_t
 2 {
 3     // Constructor - întoarce o nouă reprezentare de graf
 4     // Acest pointer la funcție va întoarce o structură ce poate conține o matrice, o listă sau
 5     // orice altă structură de date necesară menținerii stării grafului
 6     void *new(int size);
 7 
 8     // Destructor - eliberează memoria alocată pentru acest graf
 9     void delete(void *graph);
10 
11     // Întoarce numărul de noduri din graf
12     int get_size(void *graph);
13 
14     // Întoarce următorul vecin nevizitat al nodului node
15     unsigned int next_neightbor(void *graph, unsigned int node);
16 
17     // Alți pointeri la funcții de care avem nevoie
18 }
19 
20 typedef struct _graph_callback_t graph_call_back_t;
21 
22 struct _graph_t
23 {
24     /*! Maximum number of vertices. */
25     unsigned int size;
26 
27     /*! Array of vertices. */
28     vector_t vertices;
29 
30     /*! Graph internal representation. */
31     void *graph_representation;
32 
33     /*! Graph callback function. */
34     graph_callback_t *graph_call_back;
35 }
      • Funcțiile care folosesc graph_t, inițial algoritmii pe grafuri, vor apela funcții din graph_call_back_t.
      • Variabila de tip graph_call_back_t se va da în constructorul grafului și va avea două valori predefinite
        1. O structură umplută cu metode callback către o reprezentare cu matrice de adiacență
        2. O structură umplută cu metode callback către o reprezentare cu liste de adiacență
      • Utilizatorul va putea să-și construiască propria structură de tip graph_call_back_t și algoritmii pe grafuri o vor folosi pe aceea, fără recompilarea bibliotecii
        • Exemplu de alte implementări: arbori AVL, Roșu-Negru etc de adiacență; în loc să ținem o listă de vecini, punem toți vecinii într-un arbore și obținem performanțe bune pentru operațiile de inserare, ștergere, căutare

21-11-2001

  1. sana
    • Am refăcut implementarea matricilor
      • Reprezentarea internă a unei matrici este sub forma de array
         1 struct _matrix_t
 2 {
 3     /*! Number of columns */
 4     int columns;
 5 
 6     /*! Number of rows */
 7     int rows;
 8 
 9     /*! Elements of the matrix */
10     void **data;
11 };
12 // Nu are rost să trec de la void ** la vector_t pentru că operațiile asupra array-ului sunt triviale
      • În trecut era
        1 struct _matrix_t
2 {
3 ...
4 void ***data;
5 };
      • Am adăugat o funcție care poate schimba dimensiunea unei matrici
        1 /*!
2  * @brief Resizes a matrix, keeping the old matrix alignment.
3  * @param Matrix
4  * @param Rows number
5  * @param Columns number
6  */
7 void matrix_resize(matrix_t matrix, int rows, int columns);
    • Am început lucrul la grafuri
      1. Structura grafului asupra căreia m-am decis este
         1 // Structura este definită în graph.c și conține doi membri importanți: graph și implementation
 2 // Biblioteca va folosi graph pe post de context și va face apeluri în implementation pentru
 3 // acest context, in vederea aflării răspunsurilor la întrebările: există muchie între u și v? ce cost are (u,v)?
 4 struct _graph_t
 5 {
 6     /*! Maximum number of vertices */
 7     unsigned int size;
 8 
 9     /*! Array of vertices */
10     vector_t vertices;
11 
12     /*! Graph context */
13     void *graph;
14 
15     /*! Pointer to the graph implementation */
16     graph_implementation_t implementation;
17 };
        • Pointerul la structură graph_implementation_t are tipul cunoscut, pentru că utilizatorul poate avea propria lui implementare de operații pe graf
           1 /*!
 2  * @brief Common interface for graph implementation.
 3  * It contains pointers to functions; you may initialize
 4  * them with the values you want to hook in the library's
 5  * graph algorithms.
 6  *
 7  * Graph algorithms uses this interface to build generic
 8  * solution, instead of depending on the graph implementation.
 9  *
10  * Temelia comes with two default implementations: adjacency matrix
11  * and adjancency list. You can define your own implementation by
12  * implementing the functions in this interface - look at
13  * current solutions for details.
14  */
15 struct _graph_implementation_t
16 {
17     // Returns an empty graph with given size
18     void *(*new)(int size);
19 
20     // Frees the memory occupied by graph
21     void (*delete)(void *graph);
22 
23     // Actualizes graph's size
24     void (*resize)(void *graph, int size);
25 
26     // Adds new edge to graph
27     void (*add_edge)(void *graph, unsigned int vertex1, unsigned int vertex2,
28             double cost, char *label, void *key);
29 
30     // Removes edge from graph
31     edge_t (*remove_edge)(void *graph, unsigned int vertex1,
32             unsigned int vertex2);
33 
34     // Retrives the reference of edge from graph
35     edge_t (*get_edge)(void *graph, unsigned int vertex1, unsigned int vertex2);
36 
37     // Iterator over vertice's neighbor
38     /*!
39      * @brief Returns the first neighbor vertex of given vertex in graph
40      * @param Graph implementation
41      * @param Vertex
42      * @param Pointer to context; here your implementation
43      * may save a context (what's the current vertex, other references etc)
44      */
45     vertex_t (*first_vertex)(void *graph, unsigned int vertex, void **context);
46 
47     /*!
48      * @brief Returns the next neighbor vertex of given vertex in graph
49      * @param Graph implementation
50      * @param Vertex
51      * @param Pointer to context; information about the last visited
52      * neighbor should be here and it may be actualized
53      */
54     vertex_t (*next_vertex)(void *graph, unsigned int vertex, void **context);
55 };
56 
57 typedef struct _graph_implementation_t *graph_implementation_t;
      2. Fișierele pe care dezvolt
        1. Lista de adiacență. Status: [neînceput] se raportează următorului sprint
          • src/graph_list.c
          • src/include/graph_list.h
        2. Matrice de adiacență. Status: [în lucru] terminat în sprintul curent
          • src/graph_matrix.c
          • src/include/graph_matrix.h
        3. Algoritmi pe grafuri. Status: [neînceput] terminat în sprintul curent
          • src/graph.c
          • src/include/graph.h

Disponibil și în: HTML TXT