Graph simplification????

From: moon (only_forme4_at_hotmail.com)
Date: 07/05/04 

Date: 5 Jul 2004 01:46:39 -0700

I am in the process of writing a program that simplifies a directed
graph into a sequence of serial boxes. I really don't which is the
wright algorithm to use for such a program. I found a lot of
algorithms to construct the graph and traverse it but not to simplify
it. I think that there a lot of application based on such algorithm
such as circuit analysis, system reliability, etc…

So to describe what the algorithm should do, here the details:

# Graph description:

* You have a set of nodes.
* They are connected by directed edges (only one direction)
* Two connected nodes are connected by only one edge.

# Parallel definition (I hope that I will be clear enough in my
description =) :

* If a node has two or more edges directed outward of it, then the
paths starts from these nodes are considered parallel and should be
grouped in one box.

# Serial definition

* If a node has one edge directed outward of it, then the node next to
it is considered serially connected.

A===>B===>E====>G====
|| || /\ ||
|| || // ||
|| V // V
||===>C===>D====>F==>H

This is an example, who can simplify it for me!!!!!!! Along with the
algorithim??? (When I tried to solve it, I found out that ‘D' is part
of two parallel boxes, which confused me , and I did not how to solve
the problem! I think that another rule should be specified in the
description of the system???? Please don't hesitate if you also know
what is the missed rule!!!

I hope that I was really clear in my description, and I hope really to
hear from you as soon as possible.

Yours,

Relevant Pages

  • Re: Shortish paths
    ... For how many nodes and how many edges will the actual algorithm run ... original graph. ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
    (comp.theory)
  • Re: Standard graph API?
    ... isomorphism graph library. ... It's pretty uniformly agreed that there is no standard graph ... the algorithm can't be specialized for the graph at ... My thought is to use some sort of templating system. ...
    (comp.lang.python)
  • Difference between two systems of DAGs
    ... I am looking for a graph algorithm, ... carry no label or other information except direction. ... edit operations are to change the label of a vertex or the ...
    (comp.theory)
  • Re: Vertex Cover implementation
    ... i code this simple greedy algorithm for the vertex cover: ... As you are constructing your graph you can update the vertex ... each edge appears on two adjacency lists. ... reason to use a priority queue for your algorithm. ...
    (comp.theory)
  • Re: combinatorial optimization problem (six-pick wager grouping)
    ... versed in graph theoretic approaches could comment on my ideas below - ... I'n not a graph theorist, nor a graph algorithm buff, so I can't really ... attempt to merge it with each bet already in the pool. ... million edges when I ignored wager size. ...
    (comp.programming)