O módulo de grafos apresenta uma metodologia para o armazenamento e manipulação de grafos em bancos de dados geográficos através da definição de um conjunto de tabelas relacionais que descrevam os metadados e a semântica do grafo.

Para a representação do grafo em memória é definido uma interface abstrata contendo as principais funcionalidades de um grafo, permitindo assim a criação de novos tipos concretos de grafos. Estratégias de busca dos elementos no banco de dados também são definidas, assim como uma estrutura de cache para o controle dos dados em memória.

Uma visão geral deste módulo pode ser visto na figura abaixo.

• Graph:Conjunto de classes utilizado para representar os diversos tipos de grafos.

• GraphMetadata: São classes utilizadas armazenar os metadados dos grafos.

• Data: As classes deste grupo representam os dados dos grafos.

• Iterators: São estruturas que permitem maneiras diferentes de se percorrer um grafo.

• Cache: Estrutura que controla os dados do grafo em memória.

• Loader: Conjunto de classes para a definição de estratégias para a recuperação dos dados do grafo na fonte de dados.

O modelo conceitual define as tabelas que representam os metadados e os dados no grafo no banco de dados relacional.

As tabelas pertencentes ao grupo Graph Metadata Tables são utilizadas para descrever os metadados relacionados ao grafos e atributos dos grafos.

O grupo de tabelas Graph Tables são apenas exemplos de como um grafo pode ser armazenado no banco de dados, seja como uma “lista” de arestas ou “lista” de vértices. O mesmo acontece com as tabelas do grupo Graph Attribute Tables que apenas servem para indicar que os atributos associados aos grafos não precisam necessariamente estar fisicamente na mesma tabela dos grafos.

Apresenta os metadados dos grafos. Possui os seguintes atributos:

• graph_id: identificação única do grafo no banco de dados.
• graph_name: nome associado ao grafo.
• graph_type: identificação do tipo do grafo (serve para indicar como o grafo esta armazenado no banco de dados).
• graph_table_name: nome da tabela contendo os dados do grafo.
• graph_description: breve descrição sobre o grafo (normalmente utilizado para indicar como o grafo foi gerado).

Apresenta os metadados dos atributos associados aos grafos. Possui os seguintes atributos:

• attr_id: identificação única do atributo.
• attr_table: nome da tabela onde esta este atributo.
• attr_column: nome do atributo.
• attr_link_column: nome do atributo utilizado como ligação com o grafo
• attribute_type: utilizado para indicar se este atributo é associado ao vértice ou à aresta.

O modelo de dados tem como função representar os elementos do grafo em memória. Foram utilizadas algumas implementações abstratas para dar maior flexibilidade na utilização dos componentes a facilitar sua expansão.

Conjunto de classes utilizado para representar os diversos tipos de grafos. Toda implementação concreta de um grafo deve extender de uma classe virtual chamada AbstractGraph.

Essa classe virtual define uma interface com a maioria das operações comuns aos grafos.

São classes utilizadas armazenar os metadados dos grafos. Os metadados dos atributos associados ao vértices ou arestas também são descritos aqui e não juntos aos atributos (EdgeProperty e VertexProperty).

Podemos destacar alguns metadados dos grafos:

• srid: identificação da referencia espacial do grafo.
• type: tipo do grafo (direcional, não-direcional, bi-direcional…).
• max_cache_size: informação utilizada pela estrutura de cache que define quantos elementos (vértices e arestas) podem estar contidos em um pacote de dados da memória.
• max_vec_cache_size: informação também utilizada pela estrutura de cache para definir quantos pacotes de dados podem estar presentes na memória.

As classes deste grupo representam os dados dos grafos. Para auxiliar no controle dos dados em memória foi criado o conceito GraphData, que são pacotes de elementos do grafo. Esse metodologia foi criada visando a facilitar a busca dos elementos na fonte de dados e também no momento de descartar informações presentes na memória.

• GraphData: Classe que define um pacote de elementos de um grafo.
  • id: identificação única do pacote.
  • dirty: flag utilizada para identificar se algum elemento deste pacote foi alterado.
  • vertex_map: estrutura chave-valor com um conjunto de vértices.
  • edge_map: estrutura chave-valor com um conjunto de arestas.

• Edge: Classe que representa uma aresta de um grafo.
  • id: identificação única desta aresta.
  • attrs: conjunto de atributos associados a esta aresta.
  • vertexIdFrom: identificação do vértice de origem desta aresta.
  • vertexIdTo: identificação do vértice de destino desta aresta.
  • dirty: flag utilizada para indicar se este elemento sofreu alterações.
  • new: flag utilizada para indicar que este é um novo elemento do grafo.

• Vertex: Classe que representa um vértice de um grafo.
  • id: identificação única deste vértice.
  • attrs: conjunto de atributos associados a este vértice.
  • *prodecessors: identificação de todas as arestas que chegam a este vértice.
  • *successors: identificação de todas as arestas que saem deste vértice.
  • *neighborhood: identificação dos elementos vizinhos a este vértice.
  • dirty: flag utilizada para indicar se este elemento sofreu alterações.
  • new: flag utilizada para indicar que este é um novo elemento do grafo.

Os atributos marcados com * apenas são preenchidos em tipos específicos de grafos.

São estruturas que permitem maneiras diferentes de se percorrer um grafo. Uma classe abstrata chamada AbstractIterator define métodos virtuais que devem ser implementados por suas derivações concretas.

As implementações concretas que foram implementadas são as seguintes:

• Box: Percorre os elementos de grafo pertencentes a uma região em específico.
• Sequence: Percorre de maneira sequencial todos os elementos do grafo.
• Query: Percorre todos os elementos que satisfazem uma clausula de restrição.

Alguns dos métodos presentes na interface abstrata do Iterator são:

• getFirstVertex(): Recupera o primeiro vértice.
• getNextVertex(): Próximo vértice.
• getFirstEdge(): Recupera a primeira aresta.
• getNextEdge(): Próxima aresta.

Lembrando que a ordem dos elementos é definida pela estratégia adotada (Box, Sequence, Query).

Podemos entender o cache como sendo o histórico de tudo que já foi acessado. Se tivermos um bom tamanho desse histórico e quanto mais inteligente ele for ao descartar informações, melhor proveito ele terá. Fazendo uma simples analogia, podemos entender a classe Graph como sendo o processador principal de um computador onde se tem acesso direto e muito rápido a um pequeno conjunto de elementos, a classe GraphCache sendo a memória RAM tendo uma parte dos dados carregada e com um acesso não tão rapido e por último a classe GraphDataManager sendo nossa fonte de dados com um acesso lento.

Uma vez atingido o limite máximo de pacotes em memória e ainda é necessário carregar mais elementos do grafo, é necessário a remoção de pacotes da memória. Essa operação é realizado através de estratégias de policiamento, são elas:

• FIFO (First In First Out): conceito de uma fila comum, o primeiro pacote a entrar será o primeiro pacote a sair;

• LFU (Least Frequency Used): pode ser visto como uma fila também, só que a cada vez que um pacote é usado ele é movido para o começo da fila e as remoções são feitas no fim da fila.

Essa política passa a ser simples devido ao fato de os elementos estarem agrupados em pacotes. O controle é feito por pacotes e não por elementos individuais, evitando uma sobrecarga de checagens e controles

A classe AbstractGraphLoaderStrategy define o conceito de LoaderStrategy que determina como um dado deve ser carregado. Algumas estratégias propostas foram definidas:

• Box: carrega um conjunto de objetos tendo como objeto central o elemento procurado;
• Sequence: carrega um conjunto de objetos de forma sequencial, tendo como objeto inicial o elemento procurado.

Para acessar os dados de um grafo estando armazenados em um banco de dados relacional, utilizando o modelo de arestas para seu armazenamento, a recuperação é feita definindo-se uma SQL que recupera em um único passo as informações das arestas e vértices.

SELECT * FROM teste_model_edge AS edges 
JOIN teste_attr_model_vertex AS v1 
	ON (edges.vertex_from = v1.vertex_id) 
JOIN teste_attr_model_vertex AS v2 
	ON (edges.vertex_to = v2.vertex_id)

A cláusula Where desta SQL é definida dependendo de qual estratégia se está utilizando, seja por Box, Query ou Sequence.

Os extratores são funções capazes de gerar um grafo a partir de um processamento sobre uma base de dados, como por exemplo, dados vetoriais, imagens e mesmo tabelas de dados. Os extratores implementados são:

Um LDD (Local Drain Directions) é uma matriz com valores bem definidos, resultado de um processo de extração de fluxos locais em um MNT (Modelo Numérico de Terreno) que indicam a direção do fluxo em cada pixel.Percorrendo a matriz do LDD é possível extrair o grafo representando os fluxos. Cada pixel será um vértice do grafo e as arestas serão geradas baseadas no valor do pixel.

A extração do grafo é feita através de um dado vetorial contendo uma representação geométrica e uma tabela de dados representando os fluxos, sendo que essa tabela deve ser composta por colunas que indiquem a origem e o destino do fluxo.

RAG (Region Adjacency Graphs) é uma estrutura de grafo extraída a partir de um conjunto polígonos, associando um vértice a cada região e uma aresta a cada par de regiões adjacentes.

O layer de grafos é uma extensão do te::map::AbstractLayer. Diferentemente dos outros não possui um DataSet interno, mas sim um ponteiro para um te::graph::AbstractGraph.

Faz uso do estilo (te::se::Style) do layer para definir como os vértices (pontos) e arestas (linhas) serão desenhados.

Para o desenho do grafo é definido um iterador por box (te::graph::BoxIterator) com a área a ser desenhada. Assim o iterador irá acessar apenas os elementos de interesse.

te::graph::AbstractGraph* g = layer->getGraph();
 
//set iterator
te::gm::Envelope* box = new te::gm::Envelope(...);
 
te::graph::BoxIterator* it = new te::graph::BoxIterator(g, box);
 
g->setIterator(it);
 
te::graph::Edge* edge = g->getFirstEdge();
 
while(it->isEdgeIteratorAfterEnd() == false)
{
  //draw graph
}

How to create a graph:

// data source information
std::map<std::string, std::string> connInfo;
connInfo["host"] = "localhost";
connInfo["user"] = "postgres";
connInfo["dbname"] = "t5graph";
 
// graph type
std::string graphType = "GRAPH";
 
// graph information
std::map<std::string, std::string> graphInfo;
graphInfo["GRAPH_NAME"] = "teste";
graphInfo["GRAPH_STRATEGY_LOADER"] = "BOX_LOADER_STRATEGY";
graphInfo["GRAPH_CACHE_POLICY"] = "FIFO";
 
//create output graph
te::graph::AbstractGraph * graph = te::graph::AbstractGraphFactory::make(graphType, connInfo, graphInfo);

Podemos observar que alguns parametros de conexão definem o grafo e comportamento do grafo:

• GRAPH_STRATEGY_LOADER : implica em como o grafo será carregado da fonte de dados.
• GRAPH_CACHE_POLICY : define qual a politica de cache a ser utilizada.

How to open a graph:

// data source information
std::map<std::string, std::string> connInfo;
connInfo["host"] = "localhost";
connInfo["user"] = "postgres";
connInfo["dbname"] = "t5graph";
 
// graph type
std::string graphType = "DIRECTEDGRAPH";
 
// graph information
std::map<std::string, std::string> graphInfo;
graphInfo["GRAPH_DATA_SOURCE_TYPE"] = "POSTGIS";
graphInfo["GRAPH_ID"] = "1";
graphInfo["GRAPH_STORAGE_MODE"] = te::graph::Globals::sm_edgeStorageMode;
graphInfo["GRAPH_STRATEGY_LOADER"] = te::graph::Globals::sm_factoryLoaderStrategyTypeSequence;
graphInfo["GRAPH_CACHE_POLICY"] = "FIFO";
 
//open graph
te::graph::AbstractGraph* graph = te::graph::AbstractGraphFactory::open(graphType , connInfo, graphInfo);

Para a abertura do grafo também é necessário informar como o grafo esta armazenado no banco de dados, neste caso o grafo esta armazenado como “lista” de arestas.

• GRAPH_STORAGE_MODE: indica como o grafo esta armazenado.

How to add elements:

//create graph attrs
te::gm::GeometryProperty* gProp = new te::gm::GeometryProperty("coords");
gProp->setGeometryType(te::gm::PointType);
gProp->setSRID(...);
graph->addVertexProperty(gProp);
 
// create vertex 0
Vertex* v0 = new Vertex(0);
v0->setAttributeVecSize(graph->getVertexPropertySize());
te::gm::Point* p0 = new te::gm::Point(...);
v0->addAttribute(0, p0);
graph->add(v0);
 
//create vertex 1
Vertex* v1 = new Vertex(1);
v1->setAttributeVecSize(graph->getVertexPropertySize());
te::gm::Point* p1 = new te::gm::Point(...);
v1->addAttribute(0, p1);
graph->add(v1);
 
//create edge
Edge* e = new Edge(0, 0, 1);
graph->add(e);

How to use iterators:

//get current iterator
te::graph::AbstractIterator* oldIt = g->getIterator();
 
te::gm::Envelope* box = new te::gm::Envelope(...);
 
//set iterator
te::graph::BoxIterator* it = new te::graph::BoxIterator(g, box);
 
g->setIterator(it);
 
te::graph::Edge* edge = g->getFirstEdge();
 
// operation
while(edge)
{
  ...
  edge = g->getNextEdge();
}
 
g->setIterator(oldIt);
 
delete it;

How to create new iterators:

A classe abstrata AbstractIterator possui dois atributos, ambos te::da::DataSet, um para os vértices e outro para as arestas. Esses datasets terão os elementos no qual o iterador deverá percorrer. Caso um novo iterador seja criado, apenas duas funções deverão ser implementadas:

/*!
  \brief It returns a pointer to the first vertex element of a graph
 
  \return A valid vertex point if the element was found and a null pointer in other case.
*/
virtual te::graph::Vertex* getFirstVertex() = 0;
 
/*!
  \brief It returns a pointer to the first edge element of a graph
 
  \return A valid edge point if the element was found and a null pointer in other case.
*/
virtual te::graph::Edge* getFirstEdge() = 0;

Que são as funções que irão popular os dataset's. Uma vez feito isso, as funções para percorrer o dataset já estão definidas na classe AbstractIterator.

Caso uma nova estratégia de busca dos elementos do grafo seja feita, é necessário apenas a implementação das funções virtuais definidas na classe AbstractGraphLoaderStrategy.

/*!
  \brief Function used to load a group of vertex elements given a base element
 
  \param vertexId   Attribute used to identify the base element
 
  \param g          Pointer to a graph, parent of this element
 
  \param gc         This is a optional attribute, if present the cache will be check if the already been loaded
 
*/
virtual void loadDataByVertexId(int vertexId, te::graph::AbstractGraph* g, te::graph::GraphCache* gc = 0) = 0;
 
/*!
\brief Functio used to load a group of edges elements given a base element
 
  \param edgeId     Attribute used to identify the base element
 
  \param g          Pointer to a graph, parent of this element
 
  \param gc         This is a optional attribute, if present the cache will be check if the already been loaded
 
*/
virtual void loadDataByEdgeId(int edgeId, te::graph::AbstractGraph* g, te::graph::GraphCache* gc = 0) = 0;

Os arquivos que fazem parte deste módulo se encontram organizados da seguinte forma no repositório:

• Core: Classes that represent the main structures of the graph.
• Graphs: Implementations of the types of graphs (directional, undirectional, bi-directional…).
• Loaders: Definition of the search strategies of the elements of the graph in the data source.
• Drivers: Concrete implementation of the functions of storage and retrieval of the elements of the graph.
• Cache: Structure used to control the elements of the graph in memory.
• Builders: Functions used to extract a graph from a data source.
• Iterators: Definition of iterators for traversing graphs.
• MapTools: Definition of a layer and renderer for the graph structures.
• Functions: Auxiliary functions.

-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
C++                             48           2030           1440           5256
C/C++ Header                    52           2205           3334           1630
-------------------------------------------------------------------------------
SUM:                           100           4235           4774           6886
-------------------------------------------------------------------------------

Este módulo foi baseado na dissertação de mestrado de Eric Silva Abreu, o trabalho completo pode ser encontrado através deste link.