123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534 |
- /*!
- Temelia - Adjacency matrix implementation structure graph
- Copyright (C) 2008 Ceata (http://ceata.org/proiecte/temelia)
- @author Dascalu Laurentiu
- This program is free software; you can redistribute it and
- modify it under the terms of the GNU General Public License
- as published by the Free Software Foundation; either version 3
- of the License, or (at your option) any later version.
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- */
- #include "include/graph.h"
- #include "include/graph_matrix.h"
- #include "include/matrix.h"
- #include <stdlib.h>
- struct _graph_matrix_t
- {
- int size;
- matrix_t adjacency_matrix;
- };
- typedef struct _graph_matrix_t *graph_matrix_t;
- void *graph_matrix_new(int size)
- {
- graph_matrix_t graph;
- LOGGER("[graph matrix new] size %d\n", size);
- _ASSERT(size, <=, 0, NULL_POINTER, NULL);
- graph = (graph_matrix_t) _new(sizeof(struct _graph_matrix_t));
- _ASSERT(graph, ==, NULL, NULL_POINTER, NULL);
- graph->size = size;
- graph->adjacency_matrix = matrix_new(size, size);
- if (graph->adjacency_matrix == NULL)
- {
- _delete(graph);
- return NULL;
- }
- return graph;
- }
- void graph_matrix_delete(void *graph)
- {
- graph_matrix_t m_graph = (graph_matrix_t) graph;
- _ASSERT(m_graph, ==, NULL, NULL_POINTER, );
- LOGGER("[graph matrix delete] graph %p, matrix %p\n", graph,
- m_graph->adjacency_matrix);
- matrix_delete(m_graph->adjacency_matrix);
- _delete(m_graph);
- }
- void graph_matrix_resize(void *graph, int size)
- {
- graph_matrix_t m_graph = (graph_matrix_t) graph;
- LOGGER("[graph matrix resize] graph %p, new size %d\n", graph, size);
- _ASSERT(m_graph, ==, NULL, NULL_POINTER,);
- matrix_resize(m_graph->adjacency_matrix, size, size);
- }
- void graph_matrix_add_edge(void *graph, unsigned int src, unsigned int dest,
- edge_t edge)
- {
- graph_matrix_t m_graph = (graph_matrix_t) graph;
- LOGGER(
- "[graph matrix add edge] graph %p, source %u, destination %u, edge %p\n",
- graph, src, dest, edge);
- _ASSERT(graph, ==, NULL, NULL_POINTER,);
- _ASSERT(edge, ==, NULL, NULL_POINTER,);
- _ASSERT(src, >=, (unsigned int) m_graph->size, INVALID_INPUT,);
- _ASSERT(dest, >=, (unsigned int) m_graph->size, INVALID_INPUT,);
- matrix_set_key_at(m_graph->adjacency_matrix, src, dest, edge);
- }
- edge_t graph_matrix_remove_edge(void *graph, unsigned int vertex1,
- unsigned int vertex2)
- {
- graph_matrix_t m_graph = (graph_matrix_t) graph;
- edge_t edge;
- LOGGER("[graph matrix remove edge] graph %p, source %u, destination %u\n",
- graph, vertex1, vertex2);
- _ASSERT(graph, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(vertex1, >=, (unsigned int) m_graph->size, INVALID_INPUT, NULL);
- _ASSERT(vertex2, >=, (unsigned int) m_graph->size, INVALID_INPUT, NULL);
- edge = matrix_get_key_at(m_graph->adjacency_matrix, vertex1, vertex2);
- matrix_set_key_at(m_graph->adjacency_matrix, vertex1, vertex2, NULL);
- return edge;
- }
- edge_t graph_matrix_get_edge(void *graph, unsigned int vertex1,
- unsigned int vertex2)
- {
- graph_matrix_t m_graph;
- LOGGER("[graph matrix get edge] graph %p, source %u, destination %u\n",
- graph, vertex1, vertex2);
- m_graph = (graph_matrix_t) graph;
- _ASSERT(graph, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(vertex1, >=, (unsigned int) m_graph->size, INVALID_INPUT, NULL);
- _ASSERT(vertex2, >=, (unsigned int) m_graph->size, INVALID_INPUT, NULL);
- return matrix_get_key_at(m_graph->adjacency_matrix, vertex1, vertex2);
- }
- vertex_t graph_matrix_first_vertex(void *graph, unsigned int vertex,
- void **context)
- {
- graph_matrix_t m_graph = (graph_matrix_t) graph;
- matrix_t m_matrix;
- unsigned int i, size, *init;
- edge_t edge;
- LOGGER("[graph matrix first vertex] graph %p, vertex %u, context %p\n",
- graph, vertex, context);
- _ASSERT(graph, ==, NULL, INVALID_INPUT, NULL);
- m_matrix = (matrix_t) m_graph->adjacency_matrix;
- size = m_graph->size;
- init = _new(sizeof(unsigned int));
- for (i = 0; i < size; i++)
- {
- edge = matrix_get_key_at(m_matrix, vertex, i);
- if (edge)
- {
- *init = i;
- *((unsigned int **) context) = init;
- return edge_get_vertex2(edge);
- }
- }
- _delete(init);
- return NULL;
- }
- void graph_matrix_delete_vertex_context(void **context)
- {
- unsigned int **m_context = (unsigned int **) context;
- _ASSERT(context, ==, NULL, NULL_POINTER, );
- _delete(*m_context);
- }
- vertex_t graph_matrix_next_vertex(void *graph, unsigned int vertex,
- void **context)
- {
- graph_matrix_t m_graph = (graph_matrix_t) graph;
- edge_t m_edge;
- unsigned int it;
- LOGGER("[graph matrix next vertex] graph %p, vertex %u, context %p\n",
- graph, vertex, context);
- _ASSERT(graph, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(vertex, >=, (unsigned int) m_graph->size, NULL_POINTER, NULL);
- _ASSERT(context, ==, NULL, NULL_POINTER, NULL);
- it = **(unsigned int **) context;
- _ASSERT(it, >= , (unsigned int) m_graph->size, INVALID_INPUT, NULL);
- while (++it < (unsigned int) m_graph->size)
- {
- m_edge = matrix_get_key_at(m_graph->adjacency_matrix, vertex, it);
- if (m_edge)
- {
- **(unsigned int **) context = it;
- return edge_get_vertex2(m_edge);
- }
- }
- _delete(*(unsigned int **) context);
- return NULL;
- }
- edge_t graph_matrix_first_edge(void *graph, unsigned int vertex, void **context)
- {
- graph_matrix_t m_graph = (graph_matrix_t) graph;
- matrix_t m_matrix;
- edge_t edge;
- unsigned int i, size, *init;
- LOGGER("[graph matrix first edge] graph %p, vertex %u, context %p\n",
- graph, vertex, context);
- _ASSERT(graph, ==, NULL, INVALID_INPUT, NULL);
- m_matrix = (matrix_t) m_graph->adjacency_matrix;
- size = m_graph->size;
- init = _new(sizeof(unsigned int));
- for (i = 0; i < size; i++)
- {
- edge = matrix_get_key_at(m_matrix, vertex, i);
- if (edge)
- {
- *init = i;
- *((unsigned int **) context) = init;
- return edge;
- }
- }
- _delete(init);
- return NULL;
- }
- void graph_matrix_delete_edge_context(void **context)
- {
- unsigned int **m_context = (unsigned int **) context;
- _ASSERT(context, ==, NULL, NULL_POINTER, );
- _delete(*m_context);
- }
- edge_t graph_matrix_next_edge(void *graph, unsigned int vertex,
- void **context)
- {
- graph_matrix_t m_graph = (graph_matrix_t) graph;
- edge_t m_edge;
- unsigned int it;
- LOGGER("[graph matrix next edge] graph %p, vertex %u, context %p\n", graph,
- vertex, context);
- _ASSERT(graph, ==, NULL, NULL_POINTER, NULL);
- _ASSERT(vertex, >=, (unsigned int) m_graph->size, NULL_POINTER, NULL);
- _ASSERT(context, ==, NULL, NULL_POINTER, NULL);
- it = **(unsigned int **) context;
- _ASSERT(it, >= , (unsigned int) m_graph->size, INVALID_INPUT, NULL);
- while (++it < (unsigned int) m_graph->size)
- {
- m_edge = matrix_get_key_at(m_graph->adjacency_matrix, vertex, it);
- if (m_edge)
- {
- **(unsigned int **) context = it;
- return m_edge;
- }
- }
- _delete(*(unsigned int **) context);
- return NULL;
- }
- void graph_matrix_iterate(void *graph, void(*iterate)(vertex_t src,
- vertex_t dest, double cost, char *label, void *key, int type))
- {
- int i, j, n;
- graph_matrix_t m_graph = (graph_matrix_t) graph;
- edge_t m_edge;
- LOGGER("[graph matrix iterate] graph %p, iterating function %p\n", graph,
- iterate);
- _ASSERT(graph, ==, NULL, NULL_POINTER,);
- n = m_graph->size;
- for (i = 0; i < n; i++)
- {
- for (j = 0; j < n; j++)
- {
- m_edge
- = (edge_t) matrix_get_key_at(m_graph->adjacency_matrix, i,
- j);
- if (m_edge)
- {
- iterate(edge_get_vertex1(m_edge), edge_get_vertex2(m_edge),
- edge_get_cost(m_edge), edge_get_label(m_edge),
- edge_get_key(m_edge), edge_get_type(m_edge));
- }
- }
- }
- }
- void graph_matrix_iterate_edges(void *graph, void edge_handler(edge_t e,
- void *context), void *context)
- {
- int i, j, n;
- graph_matrix_t m_graph = (graph_matrix_t) graph;
- edge_t m_edge;
- LOGGER(
- "[graph matrix iterate edges] graph %p, iterating function %p, context %p\n",
- graph, edge_handler, context);
- _ASSERT(graph, ==, NULL, NULL_POINTER,);
- n = m_graph->size;
- for (i = 0; i < n; i++)
- {
- for (j = 0; j < n; j++)
- {
- m_edge
- = (edge_t) matrix_get_key_at(m_graph->adjacency_matrix, i,
- j);
- if (m_edge)
- edge_handler(m_edge, context);
- }
- }
- }
- void graph_matrix_transpose(void *graph)
- {
- int i, j, n;
- graph_matrix_t m_graph = (graph_matrix_t) graph;
- edge_t m_edge1, m_edge2;
- LOGGER("[graph matrix transpose] graph %p\n", graph);
- _ASSERT(graph, ==, NULL, NULL_POINTER,);
- n = m_graph->size;
- for (i = 0; i < n; i++)
- {
- for (j = i + 1; j < n; j++)
- {
- // First edge
- m_edge1 = (edge_t) matrix_get_key_at(m_graph->adjacency_matrix, i,
- j);
- edge_switch_vertices(m_edge1);
- // Second edge
- m_edge2 = (edge_t) matrix_get_key_at(m_graph->adjacency_matrix, j,
- i);
- edge_switch_vertices(m_edge2);
- // Swap operation
- matrix_set_key_at(m_graph->adjacency_matrix, i, j, m_edge2);
- matrix_set_key_at(m_graph->adjacency_matrix, j, i, m_edge1);
- }
- }
- }
- unsigned int graph_matrix_vertex_degree(void *graph, unsigned int vertex)
- {
- int i, n, degree;
- graph_matrix_t m_graph = (graph_matrix_t) graph;
- LOGGER("[graph matrix vertex degree] graph %p, vertex %u\n", graph, vertex);
- _ASSERT(graph, ==, NULL, NULL_POINTER, -1);
- n = m_graph->size;
- degree = 0;
- for (i = 0; i < n; i++)
- {
- if (matrix_get_key_at(m_graph->adjacency_matrix, vertex, i))
- degree++;
- if (matrix_get_key_at(m_graph->adjacency_matrix, i, vertex))
- degree++;
- }
- return degree;
- }
- unsigned int graph_matrix_vertex_in_degree(void *graph, unsigned int vertex)
- {
- int i, n, in_degree;
- graph_matrix_t m_graph = (graph_matrix_t) graph;
- _ASSERT(graph, ==, NULL, NULL_POINTER, -1);
- n = m_graph->size;
- in_degree = 0;
- for (i = 0; i < n; i++)
- {
- if (matrix_get_key_at(m_graph->adjacency_matrix, i, vertex))
- in_degree++;
- }
- return in_degree;
- }
- unsigned int graph_matrix_vertex_out_degree(void *graph, unsigned int vertex)
- {
- int i, n, out_degree;
- graph_matrix_t m_graph = (graph_matrix_t) graph;
- _ASSERT(graph, ==, NULL, NULL_POINTER, -1);
- n = m_graph->size;
- out_degree = 0;
- for (i = 0; i < n; i++)
- {
- if (matrix_get_key_at(m_graph->adjacency_matrix, vertex, i))
- out_degree++;
- }
- return out_degree;
- }
- unsigned int graph_matrix_dimension(void *graph)
- {
- int i, j, n, dimension;
- graph_matrix_t m_graph = (graph_matrix_t) graph;
- _ASSERT(graph, ==, NULL, NULL_POINTER, -1);
- n = m_graph->size;
- dimension = 0;
- for (i = 0; i < n; i++)
- {
- for (j = 0; j < n; j++)
- {
- if (matrix_get_key_at(m_graph->adjacency_matrix, i, j))
- dimension++;
- }
- }
- return dimension;
- }
- void graph_matrix_delete_vertex_edges(void *graph, unsigned int vertex,
- void(*edge_delete)(edge_t edge))
- {
- int i, n;
- graph_matrix_t m_graph = (graph_matrix_t) graph;
- _ASSERT(graph, ==, NULL, NULL_POINTER,);
- _ASSERT(vertex, >=, (unsigned int) m_graph->size, NULL_POINTER,);
- n = m_graph->size;
- for (i = 0; i < n; i++)
- {
- edge_delete(matrix_get_key_at(m_graph->adjacency_matrix, i, vertex));
- matrix_set_key_at(m_graph->adjacency_matrix, i, vertex, NULL);
- edge_delete(matrix_get_key_at(m_graph->adjacency_matrix, vertex, i));
- matrix_set_key_at(m_graph->adjacency_matrix, vertex, i, NULL);
- }
- }
- void graph_matrix_load(void *graph_src, void *graph_dest)
- {
- graph_matrix_t m_graph_src = (graph_matrix_t) graph_src;
- graph_matrix_t m_graph_dest = (graph_matrix_t) graph_dest;
- int i, j, size;
- _ASSERT(graph_src, ==, NULL, NULL_POINTER,);
- _ASSERT(graph_dest, ==, NULL, NULL_POINTER,);
- _ASSERT(m_graph_src->size, != , m_graph_dest->size, INVALID_INPUT,);
- size = m_graph_src->size;
- for (i = 0; i < size; i++)
- {
- for (j = 0; j < size; j++)
- matrix_set_key_at(m_graph_dest->adjacency_matrix, i, j,
- matrix_get_key_at(m_graph_src->adjacency_matrix, i, j));
- }
- }
- void *graph_matrix_store(void *graph_src)
- {
- graph_matrix_t m_graph = (graph_matrix_t) graph_src;
- graph_matrix_t m_clone;
- _ASSERT(graph_src, ==, NULL, NULL_POINTER, NULL);
- m_clone = (graph_matrix_t) _new(sizeof(struct _graph_matrix_t));
- m_clone->size = m_graph->size;
- m_clone->adjacency_matrix = matrix_clone(m_graph->adjacency_matrix);
- return m_clone;
- }
- void graph_matrix_debug(void *graph)
- {
- }
- graph_implementation_t graph_matrix_get_implementation()
- {
- static struct _graph_implementation_t _graph_adjacency_matrix_implementation;
- _graph_adjacency_matrix_implementation.new_g = graph_matrix_new;
- _graph_adjacency_matrix_implementation.delete_g = graph_matrix_delete;
- _graph_adjacency_matrix_implementation.resize = graph_matrix_resize;
- _graph_adjacency_matrix_implementation.add_edge = graph_matrix_add_edge;
- _graph_adjacency_matrix_implementation.remove_edge = graph_matrix_remove_edge;
- _graph_adjacency_matrix_implementation.get_edge = graph_matrix_get_edge;
- _graph_adjacency_matrix_implementation.first_vertex = graph_matrix_first_vertex;
- _graph_adjacency_matrix_implementation.delete_vertex_context = graph_matrix_delete_vertex_context;
- _graph_adjacency_matrix_implementation.next_vertex = graph_matrix_next_vertex;
- _graph_adjacency_matrix_implementation.first_edge = graph_matrix_first_edge;
- _graph_adjacency_matrix_implementation.delete_edge_context = graph_matrix_delete_edge_context;
- _graph_adjacency_matrix_implementation.next_edge = graph_matrix_next_edge;
- _graph_adjacency_matrix_implementation.iterate_edges = graph_matrix_iterate_edges;
- _graph_adjacency_matrix_implementation.transpose = graph_matrix_transpose;
- _graph_adjacency_matrix_implementation.vertex_degree = graph_matrix_vertex_degree;
- _graph_adjacency_matrix_implementation.vertex_in_degree = graph_matrix_vertex_in_degree;
- _graph_adjacency_matrix_implementation.vertex_out_degree = graph_matrix_vertex_out_degree;
- _graph_adjacency_matrix_implementation.dimension = graph_matrix_dimension;
- _graph_adjacency_matrix_implementation.delete_vertex_edges = graph_matrix_delete_vertex_edges;
- _graph_adjacency_matrix_implementation.load = graph_matrix_load;
- _graph_adjacency_matrix_implementation.store = graph_matrix_store;
- _graph_adjacency_matrix_implementation.debug = graph_matrix_debug;
- return &_graph_adjacency_matrix_implementation;
- }
|