0
$\begingroup$

I am working in a different domain and I have very basic information about the graph theory concepts. Trying to map my problem into graph theory and looking for the concepts and algorithms applicable to my problem.

Part 1- Essentially, I am looking for graph discovery/exploration algorithm that should find out the entire graph, given a starting vertex and its edges to all its immediate neighbors. Assuming that the edges are non-directional and of same weight.

Part 2- Once the graph is found, we need to find out if there is any cycles in the graph. Not sure if this is even possible.

Part 3- Here it gets tricky for me to explain. The real world application is such that any node(vertex) will only have one parent and possibly 0-n children. I need to find out a node in the graph that is sort of in the center of the graph, i.e. the distance to reach from that node to any node that has 0 children, should be minimum. To my understanding the graph is similar to minimum spanning tree, as all the vertices are included and there is no cycle in the graph, what I am not sure is how find the root that is at the minimum distance to the leaf nodes.

I am looking for algorithms, pointers to algorithms, similar concepts applicable to this scenario.

$\endgroup$
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Cycle_(graph_theory)#Cycle_detection $\endgroup$ – mvw Jul 16 '15 at 8:18
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Graph_center $\endgroup$ – Gerry Myerson Jul 16 '15 at 8:56
  • 1
    $\begingroup$ Could you give some context on what your domain is and what kind of application needs this particular approach? Each of the parts you describe are standard graph-theoretical concepts and I'm very curious what uses they have in their pristine form (students are always eager to know such things). $\endgroup$ – dtldarek Jul 16 '15 at 9:46
  • $\begingroup$ I am working in power grid systems, which has many nodes and the connections between them are like edges in the graph. The nodes in the grid becomes online and offline and therefore a graph discovery is needed. Similarly, the distance from the supply to the outer nodes plays a significant role. $\endgroup$ – Novice Jul 17 '15 at 4:40
1
$\begingroup$

Some assumptions: loop free, not a multi graph, that is, no edges from a node to itself, at most 1 edge between any two nodes.

For part 1: Take the set of discovered nodes E, and the set of discovered edges E. Add all nodes connected to by an edge in E to N. Add all edges touch by any node in N to E. Repeat until N and E no longer get bigger.

To slightly optimize this keep track of the last nodes found and then last edges found, add them to the global Nodes/Edges, perform discovery on them and then update them with the newly discovered Nodes/Edges.

2: assuming a loop free non-multigraph, count the number of edges. If the number of edges is more than |N|-1, that is the number of nodes -1

3: For the center of the graph, 1) Find the shortest distance between every pair of Nodes (easy in this case as it is the only path between every two Nodes. 2) On all Nodes, find the Ones which have the smallest max over all their distances.

You could easily collapse parts 1 and 3 so that as you discover the graph you update the distances, which would amortize the cost of that center algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.