I have set of nodes and edges and i used Dijkstra's algorithm to find the shortest closed cycles.My cycles are connected to each other (small black cycles in the graph). that mean, for 2 cycles, there is a common edge. Now, I want to get the Most outer cycles (red cycle in the figure), which contains all the shortest cycles. I think this is a kind of union. Not sure. is there any specific method or algorithmic method to obtain the most outer cycle from the available shortest closed cycles within the graph? How would be implement this?

Here, i tag the question under c++ also, as most programmers do know how to get the union of connected cycles and i also wish to implement this in c++. thank you in advance.

I have edited and upload a figure to my original post, as this was not clear for others.

As I understand your question, you're trying to find an edge-maximal face of a connected planar graph. There's an algorithm for enumerating faces of a planar graph in the Boost library: Planar Face Traversal. You may use it to iterate over graph's faces and find the one with most edges involved.

Notes:

- This will really only work for
**planar graphs** - For many graphs, the solution is
**not unique**, consider graph of a regular polyhedron - here, all faces have the same degree, so it's not well defined which one of them is the 'outer cycle' you're looking for

- What 'face with most edges involved' means is different for graphs which are
**2-connected**and which are not. If it is not 2-connected, there will be "branches" reaching into some of the faces, and by definition, the same face lies on both sides of such a branch. Depending on your liking/needs you may either count such edges into the length of the face or omit them, getting different results.

Similar Questions

Recently I am working on windows and I found that lot of data structures are defined as struct with union as member variables. Example of this would be EVT_VARIANT in Windows. I failed to understand w

If I have a class like this: class Component (val name, val description, var subElements : Set[Component]) How can I test if a Component contains cycles inside (with a Boolean function) and who start

I don' mind admitting that this is a homework task that has me stumped. Any push in the right direction would be useful. I'm required to write a function that returns the union of the two given lists.

I was asked this question during one of my interviews. Can you do JOIN using UNION keyword? Can you do UNION using JOIN keyword? That is - 1. I should get same output as JOIN without using JOIN keywo

Immutable classes are great but there is one big problem i cant think of a sensible way to solve - cycles. class Friend { Set<Friend> friends(); } How does one model Me having You as a friend w

I am running QNX, I used a function to get clock cycles per second, uint64_t clockPerSec = getCPS(); uint64_t currentClockCycle = getCurrentCycle(); functions uint64_t getCPS() { return (~(uint64_t)

shared_ptr is a reference counting smart pointer in the Boost library. The problem with reference counting is that it cannot dispose of cycles. I am wondering how one would go about solving this in C+

I have an undirected graph and what I would like to do is detect cycles that have three or more nodes in them. Is there a library in R that would do this? If not is there a simple algorithm that I cou

I want to use extra-cpu cycles to do some of my own processing, and I was wondering if someone could point me in the right direction as to how to get started on this?

In the following code: typedef struct { union U { int a; char b; }U1; }A; typedef struct { union U { int a; char b; }U1; }B; The compiler gives an error [Error] redefinition of 'union U' . But thes

typedef union status { int nri; char cit[2]; }Status; int main() { Status s; s.nri = 1; printf(%d \n,s.nri); printf(%d,%d,\n,s.cit[0],s.cit[1]); } OUTPUT: 1 0,1 I know this output on the second

What would be the differences between using simply a void* as opposed to a union? Example: struct my_struct { short datatype; void *data; } struct my_struct { short datatype; union { char* c; int* i;

I've read that MySQL can cache UNION's, but at the same time I have read that.. Avoid comment (and space) in the start of the query – Query Cache does simple optimization to check if query can be cac

I have a custom node class in python that is built into a graph (which is a dictionary). Since these take a while to create, I'd like to pickle them so that I don't have to reconstruct them everytime

I have been writing code to get all the possible cycles in a directed graph. Here is an implementation that keeps track of back edges and whenever one back edge is found, it return true that one cycle

I'd like to solve the min-cost flow problem for graphs by cancelling negative cycles. Goldberg and Tarjan published a paper with this title in 1989 but I am unable to track down either a copy of the o

I have three calculation to get the curent cpu frequency: (cycles per second) _initialCycles = rdtsc(); //rdtsc function calculates the cpu cycles since init. first: ------ unsigned int initialMillise

Is there a way of modifing the algorithm in Finding all cycles in undirected graphs to consider edges as directed and only cycles of length <= k ?

When you have a dependency graph of a set of items you can do a standard topical sort to check if the graph contains cycles. If there is a cycle then there is a dependency that can not be satisfied wi

What means cycles per byte for the performance of algorithm?

Does anyone have a demo of a jQuery accordion that cycles through content automatically with an option to set the number of loops or cycles?

I'm doing a UNION of two queries, both of them have a WHERE clause. My question is, is there a difference in the performance if I do the WHERE after UNIONing the queries compared to performing the UNI

In my time dimensions i have 2013,2014,2015. How can i make a Union in this mdx so i get the results from this mdx for all thoose years and not only for 2014 like in the example.. select NON EMPTY {

Could you help me optimize the following Union All Query? Any idea where to start? Details: SQL Plan shows | 7 | TABLE ACCESS FULL | DELAY_DATE | 17533 | 171K| 25 (0)| 00:00:01 | | 8 | TABLE ACCESS F

Can bitfields be used in union?

I hava data in an Oracle table that is organized as a graph that can contain cycles (see example). CREATE TABLE T (parent INTEGER, child INTEGER) AS select 1 parent, 2 child from dual union all selec

If I have a union, C standard guarantees that the union itself will be aligned to the size of the largest element. union U { long l; int i; short s; char c[2]; } u; But what does it say about alignme

How do I match union cases dynamically in F# when there are value declarations? Non working code: let myShape = Shape.Square expect myShape Shape.Circle type Shape = | Circle of int | Square of int |

I want to get a union of subqueries in MySQL. This alone is pretty simple. (subquery A) union (subquery B limit 15) union (subquery C limit 15) But it's important that the union of B and C total 30 r

I have a canvas where I draw rectangles and move them randomly with the help of a storyboard. After a few cycles the storyboard.completed event does not fire any more. Does anybody know? here is my xa

How to measure cycles spent in accessing shared remote cache say L3. I need to get this cache access information both system-wide and for per-thread. Is there any specific tool/hardware requirements.

This one got me the other day. What would you expect the following to return? SELECT 'X' AS line UNION SELECT 'X ' AS line Notice the space in the second SELECT. Well apparently SQL 2000 and 2005 bot

I have graphs with thousands of nodes to millions of nodes. I want to detect all possible cycles in such graphs. I use hash table to store the edges. ( (source node,edge weight) -> (target node) )

Clang has new feature called ARC. Concept looks cool. Is this feature support detecting cycles?

I need to union two sets of XElements into a single, unique set of elements. Using the .Union() extension method, I just get a union all instead of a union. Am I missing something? var elements = xD

I want to find all the cycles in a directed graph. Starting Depth-first search from one node will find some cycles(finding back-edges). So, i applied dfs to all the nodes in the graph(i.e. each time t

say we have the following SQL: select * from ( select Id from table1 union all select id from table2 union all select id from table3 ) as X where Id in (1,2,3) Is the SQL optimizer smart enough to ap

Is there an algorithm or heuristics for graph isomorphism? Corollary: A graph can be represented in different different drawings. What s the best approach to find different drawing of a graph?

Possible Duplicate: C: Where is union practically used? I know the concept of union but I don't see the actual case in real world coding that I should use union data structure. I will be very apprec

i want to union, merge in a List that contains both references, so this is my code, how can i define a list ready for this porpouses ? if (e.CommandName == AddtoSelected) { List<DetalleCita> l

I have a union type of array of three integers (4 bytes each), a float (4 bytes), a double (8 bytes) and a character (1 byte). if I assign 0x31313131 to each of the three integer elements and then pri

I have a union, ok. This union is inside a struct, and that union is unnamed (something) like that. typedef enum TYPES {INT, FLOAT, CHAR, POINTER TO FUNCTION /* Please pay attention on this */}; typed

I am having some trouble writing an algorithm that returns all the paths forming simple cycles on an undirected graph. I am considering at first all cycles starting from a vertex A, which would be, fo

Previous code : struct Inet_address{ char v4[4]; }; extern C Inet_address Inet_loopback = { {127,0,0,1} }; After modifying: I have made Inet_address a union Here Inet address is a union union Inet_

In Crypto communities it is common to measure algorithm performance in cycles/byte. My question is, which parameters in the CPU architecture are affecting this number? Except the clockspeed ofcourse :

I have created a union comprising a uint64_t and a struct. I would like the union constructor to construct the inner struct but I can't seem to get it working. Here's a couple of variations I have tri

How many clock cycles does these fours instructions take? #Macro Instructions li $t0, 32 # 1 or 2 cycles ? # # Based on MIPS Assembly Language Programming by Robert Britton : # # lui $at, Upper 16-bit

As there are some instructions that are being used in MIPS Architecture, which doesn't require all 5 cycles for its successful completion, like the store instruction doesn't need to use 5th stage. So

My code for calculating clock cycles for creating thread is # include <Windows.h> # include <stdio.h> # include <conio.h> # define RUN 20000 DWORD WINAPI Calc(LPVOID Param){} int ma

Does anyone have source code implementing this algorithm for finding cycles, preferably in a modern statically-typed language like SML, OCaml, Haskell, F#, Scala?