Implementación del gráfico direccionado

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.
¿Alguien puede dirigirme a un ejemplo o una clase simple de C + + que implementa esto para que pueda estudiarlo y extender desde allí?

He buscado en Google por un tiempo 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

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

Nodo centrada. 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 centric. Este método representa cada edge 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.

Dependiendo del 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 2

Este university paper podría ayudarlo.

No es el más completo, pero te da una idea tal vez. 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

sin apretar, hay 2 maneras sencillas de gráficos que representan:

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 manipulación del puntero.

# 1 es a menudo más fácil de usar cuando se realizan 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 será señalando asignado dinámicamente node 's.

La consecuencia es que tendrá una clase y una clase node.

Answer 4

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

multimap no es compatible con la suscripción [ x ] por lo que tendrá que utilizar edges.lower_bound() en su lugar.

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

He aquí un ejemplo de 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 un list<node<dataType>*> de todos los nodos.