a mathematical structure that contains a collection of vertices or 'nodes' and a collection of edges that connect pairs of vertices

learn more… | top users | synonyms

6
votes
1answer
187 views

Heuristic Approach for Flexible DIFF Implementation

I have created a DIFF implementation to compare document revisions at work. It is based on An O(ND) Difference Algorithm and Its Variations. One thing that has become important is to take the list ...
3
votes
1answer
103 views

Merge directed acyclic graphs minimizing number of nodes

I have some DAGs (directed acylic graphs) and I want to merge them in order to minimize the number of nodes (we could say that every node has a cost, while edges are free). These four different DAGs ...
2
votes
1answer
173 views

Data structures and algorithms for a directed rooted tree with inherited properties?

I need to represent a directed rooted tree in memory. The caveat is, that nodes have properties. And those properties are inherited (but not 100%) by the child nodes, recursively. What would be a ...
0
votes
1answer
140 views

Big graph traversal with OOP

I'm trying to solve a algorithmic contest's problem. I have a matrix 2000x2000. I want to represent it as graph and traverse it with BFS/DFS. I have time limits on app running (2s). Simple vertices ...
0
votes
1answer
148 views

Find 'Connected Components' in undirected, unweighted graph coded as a 2d array

Given an undirected, unweighted graph coded as a 2d array, how can I find the number of different connected components? Example There is the following 2d array (I'm not putting any brackets to ...
3
votes
0answers
81 views

Graph visualization algorithm

I need a 2d or 3d graph visualization algorithm by which adding/removing a node or a relationship does not have a butterfly effect on the positions of other nodes. (We are talking about a directed ...
2
votes
0answers
51 views

How to implement efficient heterogeneous microservice data queries?

Our team has an idea of implementing a simple declarative DSL that would let users query the enterprise's domain model via a single interface without caring which specific microservices to call to get ...
2
votes
0answers
231 views

Understanding Tarjan's Bridge-finding algorithm

Tarjan's algorithm for finding bridges in a graph is found here: http://en.wikipedia.org/wiki/Bridge_(graph_theory)#Tarjan.27s_Bridge-finding_algorithm. However, I don't understand the condition for ...
1
vote
0answers
41 views

Domination algorithm in graphs

I'm working on a project, on an app, that can visualize undirected graphs and show on this domination algorithm. There are some examples: I have some open questions about programmable solution of ...
1
vote
0answers
27 views

Codeforces : 505C. Mr. Kitayuta, the Treasure Hunter

Question : Is the attached logic correct? I am asking since my code based on this logic failed. Here is the problem link. Reproducing here verbatim : The Shuseki Islands are an archipelago of ...
1
vote
0answers
93 views

Representation of time expanded graph

I want to build a time expanded graph with time discretization Dt that starts at t = 0 and ends at t = T where between the node (n1, t) and the node (n2, t') is an arc if and only if (n1, n2) were ...
0
votes
0answers
45 views

algorithm for group reassignment of points

I have a list of clustered points but they are not in the cluster which has the center closest to them. The objective is to reassign them to minimize the total distance of each point to its cluster ...
0
votes
0answers
51 views

All clustering possibilities for a graph

Is there a known algorithm for finding all clustering possibilities for a directed graph? EDIT: By cluster i mean a weakly connected sub-graph G, so that E(G) > 0. By a clustering possibility I ...
0
votes
0answers
19 views

A heuristic approach to Clique problem over undirected Graph

I'm trying to get all complete subgraph given a graph G. Needless to say it is an NP-problem complete: Clique_problem. I understand getting the full set is not possible in real time(since it'll take ...
0
votes
0answers
71 views

using internal or external iterators over graph edges

I've written some code to manipulate sparse graphs for school work I'm doing, and I have an operation which requires me to loop over all the edges of a graph. The interface I need to implement is some ...