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

0
votes
2answers
147 views

The way to implement a configurable (at run-time) default style

I am coding a visualizer of graph algorithms. Each vertex of the graph has a style (color, size etc.). As long as the algorithm has done nothing to a vertex, that vertex has a default style. The ...
7
votes
1answer
235 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 ...
0
votes
1answer
269 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 ...
5
votes
0answers
125 views

Modelling a complex schedule of work

I've got a real-world problem that I'm trying to represent and automate. I've simplified and abstracted it down to the following: There are n places of work (P1, P2, ..., Pn). Each place, Pn has a ...
3
votes
0answers
39 views

How to describe a set of paths in a graph with as few nodes as possible?

I have modeled a problem as a graph that consists of many trees. Some of the nodes in the graph may belong to more than one tree. I am trying to describe a subset of paths in the graph with as few ...
3
votes
0answers
78 views

Determine equality of a DAG

Given a fairly traditional node class (below), whats the best way to implement equality on a given graph? If our node looks like this public abstract class Node{ private final Set<Node> ...
2
votes
0answers
32 views

Finding subgraphs in non-directed graph

Problem at hand: Finding separate subgraphs. Update on adding or removing edges. First I've been thinking about running DFS after every operation from both ends of the edge, but if I keep ...
2
votes
0answers
43 views

Filter out noise in line graphs

I have a question regarding finding relevant events in a line graph. The following graphs show the views (y-axis) of a video over time (x-axis). Certain events lead to an huge increase in views and ...
1
vote
0answers
25 views

Algorithm to generate all paths between two vertices of a graph in F#

Following a functional programming approach (no mutable data structures, recursion, etc) I have written a script in F# to generate all paths between two vertices of an undirected, unweighted graph. I ...
1
vote
0answers
32 views

efficient graph clustering algorithm for weighted directed graphs based on node and edge weights

I'm looking for an algorithm to cluster weighted directed graphs that have weights on both edges and vertices. I'm using graphs with multiple weights(labels) on vertices and a weight on edges that ...
1
vote
0answers
46 views

Graph grouping with criteria

I start with a list of adjacent tetrahedra, where there are tight seals to one another along faces for two tetrahedra that are adjacent. The vertices belonging to these faces for both tetrahedra are ...
1
vote
0answers
94 views

Belman-Ford 2d array variation problem

I've got a problem with applying a Bellman-Ford algorithm to 2D Array (not to graph) Input array has m x n dimensions: s[1,1] s[1,2] ... s[1,n] -> Exit s[2,1] s[2,2] ... s[2,...
1
vote
0answers
165 views

Approaches to Modeling a Graph Database over the Google App Engine Datastore?

I want to model a graph database over the Google App Engine Datastore. I am currently working on creating a Link entity to model the concepts of link/edge/relationship to the graph of objects. I am ...
1
vote
0answers
81 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 ...
1
vote
0answers
49 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
64 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
132 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 ...
1
vote
0answers
84 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 ...
0
votes
0answers
46 views

Benefit and graphical representation of directed acyclic graph in code development

I think the relationship amongst the modules of a code can be represented by a directed acyclic graph (DAG) where a vertex represents a module and a directed edge from vertex a to vertex b represents ...
0
votes
0answers
90 views

Decision making algorithm

I'm currently solving an optimisation problem of my own design, just to experiment and learn a little something. Here's the concept: I have a user that starts at home. The objective of this user is ...
0
votes
0answers
66 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 ...