Exemplo de Grafos em C

Já nesta wiki se encontra uma classe de grafos em C++. É, no entanto, também interessante usar grafos em C. Como a classe de C++ tem alguns problemas de performance, tentei-me focar mais isso agora.

As funções disponiveis são minimalistas, para maior versatilidade. Para fazer algo para além do básico, pode ser necessário mexer nas directamente nas estruturas de dados, não se sintam mal por o fazer.

Este código depende de xalloc e list, que também se encontram nesta wiki.

No fim encontra-se um pequeno exemplo.

graph.h:

/*
 *  GPL
 *
 *  Written by Diogo Sousa aka orium
 *  Copyright (C) 2008 Diogo Sousa
 *
 *  This program is free software: you can redistribute it and/or 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, see <http://www.gnu.org/licenses/>.
 */

#ifndef GRAPH_H_
#define GRAPH_H_

#include <stdbool.h>
#include "list.h"

#define inf (1.0/0.0)

enum edge_type
{
    UNIDIRECTIONAL,
    BIDIRECTIONAL
};

struct edge
{
    struct vertex *vertex;

    double weight;

    void *data;
};

struct vertex
{
    void *data;

    list edges;

    struct dijkstra_data
    {
        double distance;
        struct vertex *parent;

        bool visited;
    } dijkstra_data;

    /* Internal use: see graph_copy() for details,
     * it should only be used there.
     */
    int vertex_no;
};

struct graph
{
    list vertices;

    bool weighted;
    bool unidirectional;
};

typedef struct graph * graph;
typedef struct vertex * vertex;
typedef struct edge * edge;

extern void graph_init(graph *);
extern void graph_copy(graph, graph);

extern vertex graph_add_vertex(graph);
extern edge graph_link_vertices(graph, vertex, vertex, enum edge_type, double);
extern int graph_unlink_vertices(vertex, vertex);
extern int graph_unlink_vertex(vertex, vertex);
extern int graph_rm_vertex(graph, vertex);

extern void *graph_vertex_data(vertex);
extern void *graph_vertex_set_data(vertex, void *);

extern void *graph_edge_data(edge);
extern void *graph_edge_set_data(edge, void *);

extern vertex graph_dfs(graph, bool (*)(vertex, void *), void *);
extern vertex graph_dfs_by_vertex(vertex, bool (*)(vertex, void *), void *);
extern vertex graph_bfs(graph, bool (*)(vertex, void *), void *);
extern vertex graph_bfs_by_vertex(vertex, bool (*)(vertex, void *), void *);

extern void graph_search(graph, bool (*)(vertex, void *), void *);

extern void graph_walk_df(graph, void (*)(vertex));
extern void graph_walk_bf(graph, void (*)(vertex));
extern void graph_walk(graph, void (*)(vertex));

extern void graph_dijkstra_shortest_path(graph, vertex, bool (*)(vertex));
extern double graph_dijkstra_distance(vertex);
extern vertex graph_dijkstra_parent(vertex);

extern void graph_free(graph);

#endif

graph.c:

/*
 *  GPL
 *
 *  Written by Diogo Sousa aka orium
 *  Copyright (C) 2008 Diogo Sousa
 *
 *  This program is free software: you can redistribute it and/or 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, see <http://www.gnu.org/licenses/>.
 */

/* This library allows:
 *
 *  Various edges between the same vertices
 *  Weighted edges
 *  One-way-only edges
 *
 */

#define _GNU_SOURCE

#include <stdlib.h>
#include <search.h>
#include <assert.h>
#include "graph.h"
#include "xalloc.h"

#define EPSILON 1e-15

static void vertex_init(struct vertex *);
static void vertex_copy(struct graph *, struct vertex *, struct vertex *, 
            struct vertex **);
static void set_edge(struct edge *, struct vertex *, double);
static struct edge *link_vertices(struct vertex *, struct vertex *, double);
static int vertex_cmp(const void *, const void *);
static void dummy_do_nothing(void *);
static struct vertex *depth_first_search_vertex_recursive(struct vertex *, void **,
                              void (*)(struct vertex *),
                              bool (*)(struct vertex *, 
                                   void *),
                              void *);
static struct vertex *depth_first_search(struct graph *, 
                     void (*)(struct vertex *),
                     bool (*)(struct vertex *, void *),
                     void *);
static struct vertex *breadth_first_search_vertex(struct vertex *, void **,
                          void (*)(struct vertex *),
                          bool (*)(struct vertex *,
                               void *),
                          void *);
static struct vertex *breadth_first_search(struct graph *, 
                       void (*)(struct vertex *),
                       bool (*)(struct vertex *, void *),
                       void *);
static struct vertex *walk(struct graph *,
               void (*)(struct vertex *),
               bool (*)(struct vertex *, void *),
               void *);
static void free_vertex(struct vertex *);
static void free_vertex_from_list(void *);
static void free_edge(struct edge *);
static void free_edge_from_list(void *);
static void unlink_every_edge_from(struct graph *, struct vertex *);
static void unlink_every_edge_to(struct graph *, struct vertex *);
static struct vertex * min_dijkstra_distance_node(struct graph *);
static void init_dijkstra(struct graph *);
static void init_vertex_dijkstra_data(struct vertex *);

void 
graph_init(struct graph **graph)
{
    *graph=xmalloc(sizeof(**graph));
    list_init(&(*graph)->vertices);
    (*graph)->weighted=false;
    (*graph)->unidirectional=false;
}

static void
vertex_copy(struct graph *graph, 
        struct vertex *vertex_dest, struct vertex *vertex_src, 
        struct vertex **vertices)
{
    list_node *edge_l;
    struct edge *edge;

    graph_vertex_set_data(vertex_dest,graph_vertex_data(vertex_src));
    vertex_dest->dijkstra_data=vertex_src->dijkstra_data;

    for (edge_l=list_tail(&vertex_src->edges); 
         edge_l != NULL; 
         edge_l=list_node_prev(edge_l))
    {
        edge=list_node_data_ptr(edge_l,struct edge);

        graph_link_vertices(graph,vertex_dest,
                    vertices[edge->vertex->vertex_no],
                    UNIDIRECTIONAL,edge->weight);
    }
}

/* graph_dest must be initialized
 * Vertices data pointer *will be copied*
 */
void 
graph_copy(struct graph *graph_dest, struct graph *graph_src)
{
    list_node *vertex_l;
    struct vertex *vertices[list_size(&graph_src->vertices)];
    int i;

    assert(!list_size(&graph_dest->vertices));

    graph_dest->weighted=graph_src->weighted;
    graph_dest->unidirectional=graph_src->unidirectional;

    for (i=list_size(&graph_src->vertices)-1; i >= 0; i--)
        vertices[i]=graph_add_vertex(graph_dest);


    for (vertex_l=list_head(&graph_src->vertices), i=0; 
         vertex_l != NULL;
         vertex_l=list_node_next(vertex_l), i++)
        list_node_data(vertex_l,struct vertex).vertex_no=i;

    assert(i == list_size(&graph_src->vertices));

    for (vertex_l=list_head(&graph_src->vertices), i=0; 
         vertex_l != NULL; 
         vertex_l=list_node_next(vertex_l), i++)
    {
        struct vertex *vertex_src;
        struct vertex *vertex_dest;

        vertex_src=list_node_data_ptr(vertex_l,struct vertex);
        vertex_dest=vertices[i];

        vertex_copy(graph_dest,vertex_dest,vertex_src,vertices);
    }   
}

void *
graph_vertex_set_data(struct vertex *vertex, void *data)
{
    return vertex->data=data;
}

void *
graph_vertex_data(struct vertex *vertex)
{
    return vertex->data;
}

void *
graph_edge_data(struct edge *edge)
{
    return edge->data;
}

void *
graph_edge_set_data(struct edge *edge, void *data)
{
    return edge->data=data;
}

static void 
vertex_init(struct vertex *vertex)
{
    vertex->data=NULL;
    list_init(&vertex->edges);
}

struct vertex *
graph_add_vertex(struct graph *graph)
{
    struct vertex *vertex;

    vertex=malloc(sizeof(*vertex));

    vertex_init(vertex);

    list_add(&graph->vertices,vertex);

    return vertex;
}

static void 
set_edge(struct edge *edge, struct vertex *vertex, double weight)
{
    edge->vertex=vertex;
    edge->weight=weight;
    edge->data=NULL;
}

static struct edge *
link_vertices(struct vertex *vertex1, struct vertex *vertex2, double weight)
{
    struct edge *edge;

    edge=xmalloc(sizeof(*edge));

    set_edge(edge,vertex2,weight);

    list_add(&vertex1->edges,edge);

    return edge;
}

struct edge *
graph_link_vertices(struct graph *graph, struct vertex *vertex1,
            struct vertex *vertex2, enum edge_type edge_type,
            double weight)
{
    struct edge *edge;

    switch (edge_type)
    {
    case BIDIRECTIONAL: 
        link_vertices(vertex2,vertex1,weight);
        /* Fall through */
    case UNIDIRECTIONAL: 
        edge=link_vertices(vertex1,vertex2,weight);
    }

    if (abs(weight-1.0) > EPSILON)
        graph->weighted=true;

    if (edge_type == UNIDIRECTIONAL)
        graph->unidirectional=true;

    return (edge_type == BIDIRECTIONAL) ? NULL : edge;
}

static int 
vertex_cmp(const void *n1, const void *n2)
{
    return (int)n1-(int)n2;
}

static void 
dummy_do_nothing(void *foo)
{
}

static struct vertex *
depth_first_search_vertex_recursive(struct vertex *vertex, void **visited,
                    void (*per_vertex_callback)(struct vertex *),
                    bool (*cmp)(struct vertex *, void *),
                    void *needle)
{
    list_node *edges_l;
    struct edge *edge;
    struct vertex *r=NULL;

    if (tsearch(vertex,visited,vertex_cmp) == NULL)
        xmemerror();

    if (per_vertex_callback != NULL)
        per_vertex_callback(vertex);

    if (cmp != NULL 
        && cmp(vertex,needle))
        return vertex;

    for (edges_l=list_head(&vertex->edges);
         edges_l != NULL; 
         edges_l=list_node_next(edges_l))
    {
        edge=list_node_data_ptr(edges_l,struct edge);

        if (tfind(edge->vertex,visited,vertex_cmp) == NULL)
            if ((r=depth_first_search_vertex_recursive(edge->vertex,
                                   visited,
                                   per_vertex_callback,
                                   cmp,needle)) != NULL)
                return r;
    }

    return NULL;
}

static struct vertex *
depth_first_search(struct graph *graph, 
           void (*per_vertex_callback)(struct vertex *),
           bool (*cmp)(struct vertex *, void *),
           void *needle)
{
    void *visited=NULL;
    list_node *vertex_l;
    struct vertex *vertex;
    struct vertex *r=NULL;

    for (vertex_l=list_head(&graph->vertices); 
         vertex_l != NULL; 
         vertex_l=list_node_next(vertex_l))
    {
        vertex=list_node_data_ptr(vertex_l,struct vertex);

        if (tfind(vertex,&visited,vertex_cmp) == NULL)
            if ((r=depth_first_search_vertex_recursive(vertex,
                                   &visited,
                                   per_vertex_callback,
                                   cmp,
                                   needle)) != NULL)
                break;
    }

    tdestroy(visited,dummy_do_nothing);

    return r;
}

struct vertex *
graph_dfs(struct graph *graph, bool (*cmp)(struct vertex *, void *),
      void *needle)
{
    return depth_first_search(graph,NULL,cmp,needle);
}

struct vertex *
graph_dfs_by_vertex(struct vertex *vertex, 
            bool (*cmp)(struct vertex *, void *), void *needle)
{
    void *visited=NULL;
    struct vertex *r;

    r=depth_first_search_vertex_recursive(vertex,&visited,NULL,cmp,needle);

    tdestroy(visited,dummy_do_nothing);

    return r;
}

void 
graph_walk_df(struct graph *graph, void (*callback)(struct vertex *))
{
    depth_first_search(graph,callback,NULL,NULL);
}

static struct vertex *
walk(struct graph *graph,
     void (*per_vertex_callback)(struct vertex *),
     bool (*cmp)(struct vertex *, void *),
     void *needle)
{
    list_node *vertex_l;
    struct vertex *vertex;

    for (vertex_l=list_head(&graph->vertices); 
         vertex_l !=  NULL; 
         vertex_l=list_node_next(vertex_l))
    {
        vertex=list_node_data_ptr(vertex_l,struct vertex);

        if (per_vertex_callback != NULL)
            per_vertex_callback(vertex);

        if (cmp != NULL
            && cmp(vertex,needle))
            return vertex;
    }

    return NULL;
}

static struct vertex *
breadth_first_search_vertex(struct vertex *init_vertex, void **visited,
                void (*per_vertex_callback)(struct vertex *),
                bool (*cmp)(struct vertex *, void *),
                void *needle)
{
    list queue;
    list_node *q_vertex;
    struct vertex *vertex;
    struct vertex *r=NULL;
    list_node *edge_l;

    list_init(&queue);
    list_add_tail(&queue,init_vertex);

    while (list_size(&queue))
    {
        q_vertex=list_head(&queue);

        vertex=list_node_data_ptr(q_vertex,struct vertex);

        list_del(&queue,q_vertex);

        if (per_vertex_callback != NULL)
            per_vertex_callback(vertex);

        if (tsearch(vertex,visited,vertex_cmp) == NULL)
            xmemerror();

        if (cmp != NULL
            && cmp(vertex,needle))
        {
            r=vertex;
            break;
        }

        for (edge_l=list_head(&vertex->edges); 
             edge_l != NULL; 
             edge_l=list_node_next(edge_l))
            if (tfind(list_node_data(edge_l,struct edge).vertex,
                  visited,vertex_cmp) == NULL)
                list_add_tail(&queue,list_node_data(edge_l,struct edge).vertex);
    }

    list_free(&queue,NULL);

    return r;
}

static struct vertex *
breadth_first_search(struct graph *graph,
             void (*per_vertex_callback)(struct vertex *),
             bool (*cmp)(struct vertex *, void *),
             void *needle)
{
    void *visited=NULL;
    list_node *vertex_l;
    struct vertex *vertex;
    struct vertex *r=NULL;

    for (vertex_l=list_head(&graph->vertices); 
         vertex_l != NULL; 
         vertex_l=list_node_next(vertex_l))
    {
        vertex=list_node_data_ptr(vertex_l,struct vertex);

        if (tfind(vertex,&visited,vertex_cmp) == NULL)
            if ((r=breadth_first_search_vertex(vertex,&visited,
                               per_vertex_callback,
                               cmp,needle)) != NULL)
                break;
    }

    tdestroy(visited,dummy_do_nothing);

    return r;
}

struct vertex *
graph_bfs(struct graph *graph, bool (*cmp)(struct vertex *, void *),
      void *needle)
{
    return breadth_first_search(graph,NULL,cmp,needle);
}

struct vertex *
graph_bfs_by_vertex(struct vertex *vertex, 
            bool (*cmp)(struct vertex *, void *), void *needle)
{
    void *visited=NULL;
    struct vertex *r;

    r=breadth_first_search_vertex(vertex,&visited,NULL,cmp,needle);

    tdestroy(visited,dummy_do_nothing);

    return r;
}

void 
graph_walk_bf(struct graph *graph, void (*callback)(struct vertex *))
{
    breadth_first_search(graph,callback,NULL,NULL);
}

void 
graph_walk(struct graph *graph, void (*callback)(struct vertex *))
{
    walk(graph,callback,NULL,NULL);
}

void 
graph_search(struct graph *graph, bool (*cmp)(struct vertex *, void *),
         void *needle)
{
    walk(graph,NULL,cmp,needle);
}


/* Remove the edge between vertex1 and vertex2 in only one way
 */
int
graph_unlink_vertex(struct vertex *vertex1, struct vertex *vertex2)
{
    list_node *edge_l;
    struct edge *edge;
    int r=-1;

    for (edge_l=list_head(&vertex1->edges); 
         edge_l != NULL;
         edge_l=list_node_next(edge_l))
    {
        edge=list_node_data_ptr(edge_l,struct edge);

        if (edge->vertex == vertex2)
        {
            r++;
            list_del(&vertex1->edges,edge_l);
            free(edge);
            break;
        }
    }

    return r;
}

/* Remove the edge between vertex1 and vertex2 in both ways.
 *
 * Return value:
 *         0  - Bidirectional edge removed
 *         -1 - There was only a unidirectional edge, it was removed
 *         -2 - There was no edge between this vertices
 */
int 
graph_unlink_vertices(struct vertex *vertex1, struct vertex *vertex2)
{
    return graph_unlink_vertex(vertex1,vertex2)+
        graph_unlink_vertex(vertex2,vertex1);
}

static void 
free_edge(struct edge *edge)
{
    free(edge);
}

static void 
free_edge_from_list(void *pedge)
{
    struct edge *edge=(struct edge *)pedge;

    free_edge(edge);
}

static void 
free_vertex(struct vertex *vertex)
{
    list_free(&vertex->edges,free_edge_from_list);
    free(vertex);
}

static void 
free_vertex_from_list(void *pvertex)
{
    struct vertex *vertex=(struct vertex *)pvertex;
    free_vertex(vertex);
}

void 
graph_free(struct graph *graph)
{
    list_free(&graph->vertices,free_vertex_from_list);
    free(graph);
}

static void
unlink_every_edge_from(struct graph *graph, struct vertex *vertex)
{
    while (list_size(&vertex->edges))
        while (list_size(&vertex->edges)
               && !graph_unlink_vertices(vertex,
                         list_node_data(list_head(&vertex->edges),struct edge).vertex))
            ;
}

static void
unlink_every_edge_to(struct graph *graph, struct vertex *vertex)
{
    list_node *vertex_l;

    for (vertex_l=list_head(&graph->vertices); 
         vertex_l != NULL; 
         vertex_l=list_node_next(vertex_l))
        while (!graph_unlink_vertex(list_node_data_ptr(vertex_l,
                               struct vertex),
                        vertex))
            ;
}

int
graph_rm_vertex(struct graph *graph, struct vertex *vertex)
{
    list_node *vertex_l;

    for (vertex_l=list_head(&graph->vertices); 
         vertex_l != NULL; 
         vertex_l=list_node_next(vertex_l))
        if (list_node_data_ptr(vertex_l,struct vertex) == vertex)
        {
            struct vertex *vertex2;
            vertex2=list_node_data_ptr(vertex_l,struct vertex);

            list_del(&graph->vertices,vertex_l);

            unlink_every_edge_from(graph,vertex);

            /* If the graph has unidirectional edges this
             * will be a lot slower.
             */
            if (graph->unidirectional)
                unlink_every_edge_to(graph,vertex);

            free(vertex);           

            return 0;
        }

    return -1;
}

static void
init_vertex_dijkstra_data(struct vertex *vertex)
{
    vertex->dijkstra_data.distance=inf;
    vertex->dijkstra_data.parent=NULL;
    vertex->dijkstra_data.visited=false;
}

static void
init_dijkstra(struct graph *graph)
{
    breadth_first_search(graph,init_vertex_dijkstra_data,NULL,NULL);
}

/* This could be improved with a heap.
 */
static struct vertex *
min_dijkstra_distance_node(struct graph *graph)
{
    list_node *vertex_l;
    struct vertex *vertex;
    struct vertex *vertex_min=NULL;
    double distance_min=inf;

    for (vertex_l=list_head(&graph->vertices); 
         vertex_l != NULL; 
         vertex_l=list_node_next(vertex_l))
    {
        vertex=list_node_data_ptr(vertex_l,struct vertex);

        if (!vertex->dijkstra_data.visited
            && vertex->dijkstra_data.distance < distance_min)
        {
            vertex_min=vertex;
            distance_min=vertex->dijkstra_data.distance;
        }
    }

    return vertex_min;
}

/* The function stop determines if the algorithm should stop
 * in some vertex.
 */
void
graph_dijkstra_shortest_path(struct graph *graph, struct vertex *source,
                 bool (*stop)(struct vertex *))
{
    struct vertex *vertex;
    list_node *edge_l;
    struct edge *edge;
    double distance;

    init_dijkstra(graph);

    source->dijkstra_data.distance=0.0; 

    while ((vertex=min_dijkstra_distance_node(graph)) != NULL)
    {
        vertex->dijkstra_data.visited=true;

        if (stop != NULL
            && stop(vertex))
            return;

        for (edge_l=list_head(&vertex->edges); 
             edge_l != NULL; 
             edge_l=list_node_next(edge_l))
        {
            edge=list_node_data_ptr(edge_l,struct edge);

            distance=vertex->dijkstra_data.distance+edge->weight;

            if (distance < edge->vertex->dijkstra_data.distance)
            {
                edge->vertex->dijkstra_data.distance=distance;
                edge->vertex->dijkstra_data.parent=vertex;
            }
        }
    }
}

double
graph_dijkstra_distance(struct vertex *vertex)
{
    return vertex->dijkstra_data.distance;
}

struct vertex *
graph_dijkstra_parent(struct vertex *vertex)
{
    return vertex->dijkstra_data.parent;
}

Exemplo

#include <stdio.h>
#include "graph.h"

bool 
cmp(struct vertex *vertex, void *needle)
{
    return vertex == needle;
}

void 
callback(struct vertex *vertex)
{
    if (graph_vertex_data(vertex) != NULL)
        printf("%s\n",(char *)graph_vertex_data(vertex));
}

int 
main(void)
{
    graph my_graph;
    graph my_graph_cpy;
    vertex vertices[10];
    vertex foo;
    int i;

    graph_init(&my_graph);
    graph_init(&my_graph_cpy);

    for (i=0; i <= 7; i++)
        vertices[i]=graph_add_vertex(my_graph);

    graph_link_vertices(my_graph,vertices[0],vertices[1],BIDIRECTIONAL,1.0);
    graph_link_vertices(my_graph,vertices[1],vertices[2],BIDIRECTIONAL,1.0);
    graph_link_vertices(my_graph,vertices[2],vertices[0],BIDIRECTIONAL,1.0);

    graph_link_vertices(my_graph,vertices[3],vertices[0],BIDIRECTIONAL,1.0);
    graph_link_vertices(my_graph,vertices[3],vertices[1],BIDIRECTIONAL,1.0);
    graph_link_vertices(my_graph,vertices[3],vertices[2],UNIDIRECTIONAL,1.0);

    graph_link_vertices(my_graph,vertices[3],vertices[1],BIDIRECTIONAL,1.0);    

    graph_link_vertices(my_graph,vertices[2],vertices[4],BIDIRECTIONAL,1.0);
    graph_link_vertices(my_graph,vertices[4],vertices[5],BIDIRECTIONAL,2.0);

    graph_link_vertices(my_graph,vertices[5],vertices[6],BIDIRECTIONAL,1.0);
    graph_link_vertices(my_graph,vertices[4],vertices[6],BIDIRECTIONAL,0.3);

    graph_vertex_set_data(vertices[0],"Vertex 0");
    graph_vertex_set_data(vertices[1],"Vertex 1");
    graph_vertex_set_data(vertices[2],"Vertex 2");
    graph_vertex_set_data(vertices[3],"Vertex 3");
    graph_vertex_set_data(vertices[4],"Vertex 4");
    graph_vertex_set_data(vertices[5],"Vertex 5");
    graph_vertex_set_data(vertices[6],"Vertex 6");

    putchar('\n');

    if ((foo=graph_dfs(my_graph,cmp,vertices[2])) == vertices[2])
        printf("%s\n",(char *)graph_vertex_data(foo));

    if ((foo=graph_bfs(my_graph,cmp,vertices[2])) == vertices[2])
        printf("%s\n",(char *)graph_vertex_data(foo));

    putchar('\n');

    graph_unlink_vertices(vertices[0],vertices[1]);

    graph_rm_vertex(my_graph,vertices[3]);

    graph_dijkstra_shortest_path(my_graph,vertices[0],NULL);

    printf("0->6: %f\n",graph_dijkstra_distance(vertices[6]));

    printf("0->7: %f\n",graph_dijkstra_distance(vertices[7]));

    graph_walk_df(my_graph,callback);
    graph_copy(my_graph_cpy,my_graph);

    graph_free(my_graph);

    putchar('\n');

    graph_walk_df(my_graph_cpy,callback);

    graph_free(my_graph_cpy);

    return 0;
}