c++ - graphs - graph representations

Implementación de gráficos dirigidos

Question

Necesito implementar un dígrafo (gráfico dirigido) en c ++ como parte de una tarea y tengo algunos problemas con la forma de representar los vértices y los tipos de datos de los bordes.
¿Puede alguien señalarme un ejemplo o una clase simple de C ++ que implemente esto para que pueda estudiarlo y extenderlo desde allí?

He buscado en Google un poco, pero solo encontré resultados sobre el uso de Boost u otras bibliotecas, solo necesito algo simple que no dependa de ninguna biblioteca.

Gracias.

Answer 1

En términos generales, hay dos formas sencillas de representar gráficos:

1. Matriz de conexión
2. Lista de listas

Cada uno tiene ventajas / desventajas, dependiendo de la aplicación.

# 2 implicará un montón de tocar el puntero.

# 1 es a menudo más fácil de usar al hacer transformaciones de gráficos.

En cualquiera de los dos, vas a tener algo como esto:

template<typename T>
class node
{
   public:
   T data;
};

Y la matriz y la lista de clases de lista apuntarán a los node asignados dinámicamente.

La implicación es que tendrás una clase de graph y una clase de node .

Answer 2

Este documento de la universidad podría ayudarte.

No es el más completo, pero te da una idea quizás. Lo encontré bastante útil, también es para una conferencia por lo que no hay riesgo de copiar algo que no debería.

Answer 3

Hay dos formas principales de representar los dígrafos con estructuras de datos:

Nodo centrado . Este método representa cada nodo como un objeto dentro de su programa, y ​​cada nodo contiene información sobre otros nodos a los que se vincula. Los otros nodos pueden ser tan simples como una lista de nodos donde existe un borde dirigido entre el nodo actual y el nodo objetivo.

Edge céntrico . Este método representa cada borde como un objeto dentro de su programa, y ​​cada borde contiene información sobre los nodos a los que se conecta. En un dígrafo, cada borde tendrá exactamente un nodo "fuente" y "destino" (que puede ser el mismo nodo si está considerando bucles automáticos). Este método es esencialmente una lista de pares ordenados.

Según el problema que esté resolviendo, una de estas dos formas básicas terminará siendo la más adecuada. Algoritmos más específicos podrían necesitar agregar más información a las estructuras básicas anteriores, como por ejemplo una lista de todos los nodos accesibles desde el nodo actual.

Answer 4

Pruebe un vector< NodeType > con un multimap< NodeType *, EdgeType> .

multimap no admite la suscripción [ x ] por lo que deberá usar edges.lower_bound() lugar.

Alternativamente, un map< pair< NodeType *, NodeType * >, EdgeType > puede ayudar a buscar un borde dado dos nodos. Usé exactamente eso en un programa bastante resistente.

Aquí hay un ejemplo para la primera sugerencia:

struct NodeType {
    int distance;
    NodeType( int d ) { distance = d; }
};
struct EdgeType  {
    int weight;
    NodeType *link;
    EdgeType( int w, NodeType *l ) { weight = w; link = l }
};

vector< NodeType > nodes;
nodes.reserve( 3 );
nodes.push_back( NodeType( 0 ) );
nodes.push_back( NodeType( 0 ) );
nodes.push_back( NodeType( 0 ) );

multimap< NodeType *, EdgeType > edges;
edges.insert( make_pair( &nodes[0], EdgeType( 4, &nodes[2] ) ) );
edges.insert( make_pair( &nodes[0], EdgeType( 1, &nodes[1] ) ) );
edges.insert( make_pair( &nodes[2], EdgeType( 2, &nodes[0] ) ) );

for ( multimap< NodeType *, EdgeType >::iterator iter = edges.lower_bound( &nodes[1] ),
  end = edges.upper_bound( &nodes[1] ); iter != end; ++ iter ) {
    cerr << "1 connects to " << iter->second.link - nodes.begin() << endl;
}

Answer 5

template<class T>
class node
{
public:
    T data;
    vector<node<T>*> edges;
}

Lo más probable es que también desee almacenar una list<node<dataType>*> de todos los nodos.