Hi I need help on a problem implementing a reduction of edges.

bool reduction();

If a vertex u has only one outgoing arc towards another vertex s and at least one incoming arc, then we will replace all the arcs of the form (p,u) if they exist, by (p,s), then we delete the vertex u and all the arcs which are adjacent to it.

We perform the symmetric operation where a vertex u has only one incoming arc and at least one outgoing arc.

here s a brief description of my class :

template <class T>
class Digraph
{
public:
    Digraph();
    ~Digraph();

bool acyclic(T u, T v) const;
bool reduction();


private:
    std::map<T, std::set<T>> graphe;
}


    /*
Here s an exemple of adjacency list
        0 : 5
        1 : 0, 2, 6, 7
        2 : 
        3 : 2, 4, 8, 9
        4 : 10, 13
        5 : 1
        6 : 11
        7 : 3
        8 : 13
        9 : 13
        10 : 4
        11 : 5, 7, 11, 12
        12 : 7, 13
        13 :     
    */

Can someone help me with the implementation ? some hints, or anything ? Thanks a lot

EDIT :

How many iterations of reductions should be done? Until no more can be done?

• Perform reductions until none are possible.

Which vertex should reduction be started from?

• Start from any vertex (changing this constraint, for example, to vertex with greatest outgoing/ingoing degree is straightforward)

CodePudding user response：

The question has ambiguities, such as:

1. How many iterations of reductions should be done? Until no more can be done?
2. Which vertex should reduction be started from?
3. What is the significance of declaring bool acyclic(T u, T v) const in your Digraph class? (Aside: since your Digraph is templated, T should have a well-defined == operator overloaded).

To be able to answer your question, let us make the following assumptions:

1. Perform reductions until none are possible.
2. Start from any vertex (changing this constraint, for example, to vertex with greatest outgoing/ingoing degree is straightforward)

A solution could be:

1. Maintain a data structure map<T, DegreeCount> degreeCountMap where DegreeCount is a defined as follows (note: degree definition)

struct DegreeCount
{
   DegreeCount() : d_inDegrees(0), d_outDegrees(0){}
   int d_inDegrees;
   int d_outDegrees;
}

2. Iterate through the vertices in your graph (a map<T, set<T>>), and for each vertex over its set of adjacent vertices. This gives you a directed edge u -> v. For each such edge, update degreeCountMap by incrementing the d_inDegrees of v and incrementing the d_outDegrees of u by 1.
3. If degreeCountMap is none empty, pick the first vertex that has an d_outDegrees of exactly one, and an d_inDegrees of at least 1. If none exist, try the symmetric operation. That is, pick the first vertex that has an d_inDegrees of exactly one, and an d_outDegrees of at least 1. If none exist, try the symmetric operation. If none exist, no more reductions are possible and we are done.
4. If a vertex was picked in step 3, let's call it w, we can remove it. To do so, assuming the "first case", iterate over graph excluding w, if a w is a member of graph[x], remove w from graph[x] and decrement degreeCountMap[x].d_outDegrees by 1. Then delete w key from the map graph and the map degreeCountMap. Similar logic for "symmetric case". Then repeat step 3.

When Step 3 above can no longer be performed, no more reductions are possible and the algorithm is done.

Rough Algorithm Analysis:

• Runtime complexity: O(|V|^3) where |V| is the number of unique vertices. Intuitively, this is because we preprocess the edge set in step 2 taking O(|V|^2) there, and process the continually decreasing edge set at most |V| in step 3 & 4, thus that piece results in O(|V|^3) operations, and leads the total runtime.
• Space complexity: O(|V|) since only store a struct (constant size) for each vertex.

CodePudding user response：

We don't know what your method (bool acyclic(T u, T v)const;) do, we need to see your code so we ll see how to use it because u said " I don't have right to add structures to my Class".