Find all nodes that are not in cycle in a graph

StackOverflow https://stackoverflow.com/questions/23625178

  •  21-07-2023
  •  | 
  •  

Frage

The graph is given below.. The first set says the nodes and other set gives all the bridges.

How to find a particular node in cycle or not. {A,B,C,D,E,F,G,H,I,J,K,L,M},{(E,D),(D,A),(A,B),(B,C),(A,C),(C,F),(F,G),(G,H),(H,L),(G,L),(H,M),(M,B),(G,I),(I,J),(J,K)}

Here, E,D,I,J,K are the nodes required(not in cycle). Here E, and K are for sure as they have one branch only How to traverse other D,I and J.

Ex:

In shown graph A,D and F are nodes not in cycle while other are. Graph

War es hilfreich?

Lösung

With your approach I have done this ...

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Challenge I</title>
</head>
<body>
<?php
ini_set( 'xdebug.var_display_max_depth', 4 );
$Input1            = 2;
$Input2            = '({A,B,C},{(A,B),(B,C),(C,A)}),({A,B,C,D,E},{(A,B),(B,C),(C,A),(E,D),(D,A)}),({A,B,C,D,E,F,G,H,I,J,K,L,M},{(E,D),(D,A),(A,B),(B,C),(A,C),(C,F),(F,G),(G,H),(H,L),(G,L),(H,M),(G,I),(I,J),(J,K)})';
$Input2            = '(' . $Input2 . ')';
$Input2            = preg_replace( '/([^\(\)\{\}\[\],]+)/', '"$1"', $Input2 );
$Input2            = preg_replace( '/[\{\(]/', '[', $Input2 );
$Input2            = preg_replace( '/[\}\)]/', ']', $Input2 );
$Input2            = json_decode( $Input2, true );
//var_dump($Input2);
$finalOutputString = NULL;
$newarray          = $Input2;
foreach ( $Input2 as $testcases ) {
    $newarray      = $testcases;
    $critical_count = 1;
    $outputString  = NULL;
    while ( $critical_count != 0 ) {
        $testcases                = $newarray;
        $arrCriticalNodeandBridge = array( );
        $critical_count            = 1;
        $m                        = 0;
        foreach ( $testcases[ 0 ] as $Icelands ) {
            $i                                       = 0;
            $bridgeListFromIcelandarray[ $Icelands ] = array( );
            foreach ( $testcases[ 1 ] as $Bridges ) {
                if ( in_array( $Icelands, $Bridges ) ) {
                    $bridgeListFromIcelandarray[ $Icelands ][ $i++ ] = $Bridges;
                } //in_array( $Icelands, $Bridges )
            } //$testcases[ 1 ] as $Bridges
            $countval = count( $bridgeListFromIcelandarray[ $Icelands ] );
            if ( $countval === 1 ) {
                $Bridges                                    = $bridgeListFromIcelandarray[ $Icelands ][ 0 ];
                $arrCriticalNodeandBridge[ $m ][ 'node' ]   = $Icelands;
                $arrCriticalNodeandBridge[ $m ][ 'bridge' ] = $Bridges;
                $Bridges                                    = json_encode( $Bridges );
                $Bridges                                    = preg_replace( '/"(.*?)"/', '$1', $Bridges );
                $Bridges                                    = preg_replace( '/\[/', '(', $Bridges );
                $Bridges                                    = preg_replace( '/\]/', ')', $Bridges );
                if ( $outputString === NULL )
                    $outputString = $Bridges;
                else
                    $outputString = $outputString . ',' . $Bridges;
                $m++;
            } //$countval === 1
        } //$testcases[ 0 ] as $Icelands
        //var_dump( $bridgeListFromIcelandarray);
        //var_dump( $arrCriticalNodeandBridge);
        $critical_count = count( $arrCriticalNodeandBridge );
        foreach ( $arrCriticalNodeandBridge as $v ) {
            unset( $bridgeListFromIcelandarray[ $v[ 'node' ] ] );
            foreach ( $testcases[ 0 ] as $k => $node ) {
                if ( $node == $v[ 'node' ] ) {
                    unset( $testcases[ 0 ][ $k ] );
                    $testcases[ 0 ] = array_values( $testcases[ 0 ] );
                } //$node == $v[ 'node' ]
            } //$testcases[ 0 ] as $k => $node
            foreach ( $testcases[ 1 ] as $k => $node ) {
                if ( $node == $v[ 'bridge' ] ) {
                    unset( $testcases[ 1 ][ $k ] );
                    $testcases[ 1 ] = array_values( $testcases[ 1 ] );
                } //$node == $v[ 'bridge' ]
            } //$testcases[ 1 ] as $k => $node
        } //$arrCriticalNodeandBridge as $v
        $newarray = $testcases;
    } //$critical_count != 0
    //var_dump($newarray);
    $checkgraph = $newarray[ 1 ];
    foreach ( $checkgraph as $k => $c ) {
        $newgraphsearch = $checkgraph;
        $todel          = $newgraphsearch[ $k ];
        unset( $newgraphsearch[ $k ] );
        $newgraphsearch        = array_values( $newgraphsearch );
        $finaldepthsearchgraph = array( );
        $deletebranch          = json_encode( $todel );
        $number                = 1;
        foreach ( $bridgeListFromIcelandarray as $k => $bd ) {
            $letter     = $k;
            $array_node = array( );
            foreach ( $bd as $k => $h ) {
                if ( $todel == $h ) {
                    unset( $bd[ $k ] );
                    $bd = array_values( $bd );
                } //$todel == $h
            } //$bd as $k => $h
            foreach ( $bd as $k => $h ) {
                foreach ( $h as $nodearray ) {
                    if ( $nodearray !== $letter ) {
                        array_push( $array_node, $nodearray );
                    } //$nodearray !== $letter
                } //$h as $nodearray
            } //$bd as $k => $h
            $finaldepthsearchgraph[ $letter ][ 'vertex' ]     = $letter;
            $finaldepthsearchgraph[ $letter ][ 'visited' ]    = false;
            $finaldepthsearchgraph[ $letter ][ 'neighbours' ] = $array_node;
            $number++;
        } //$bridgeListFromIcelandarray as $k => $bd
        //var_dump($finaldepthsearchgraph);
        $firstnode   = $newarray[ 0 ][ 0 ];
        $returnvalue = breadthFirstSearch( $finaldepthsearchgraph, $firstnode );
        if ( $returnvalue != count( $newarray[ 0 ] ) ) {
            $deletebranch = preg_replace( '/"(.*?)"/', '$1', $deletebranch );
            $deletebranch = preg_replace( '/\[/', '(', $deletebranch );
            $deletebranch = preg_replace( '/\]/', ')', $deletebranch );
            if ( $outputString === NULL )
                $outputString = $deletebranch;
            else
                $outputString = $outputString . ',' . $deletebranch;
        } //$returnvalue != count( $newarray[ 0 ] )
    } //$checkgraph as $k => $c
    if ( $outputString === NULL )
        $outputString = 'NA';
    $outputString = '{' . $outputString . '}';
    if ( $finalOutputString === NULL )
        $finalOutputString = $outputString;
    else
        $finalOutputString = $finalOutputString . ',' . $outputString;
} //$Input2 as $testcases
if ( count( $Input2 ) != 1 )
    $finalOutputString = '{' . $finalOutputString . '}';
echo $finalOutputString;
function breadthFirstSearch( $list, $firstnode )
{
    $queue = array( );
    array_unshift( $queue, $list[ $firstnode ] );
    $list[ $firstnode ][ 'visited' ] = true;
    $str                             = NULL;
    while ( sizeof( $queue ) ) {
        $vertex = array_pop( $queue );
        $str .= $vertex[ 'vertex' ];
        foreach ( $vertex[ 'neighbours' ] as $neighbour ) {
            if ( !$list[ $neighbour ][ 'visited' ] ) {
                $list[ $neighbour ][ 'visited' ] = true;
                array_unshift( $queue, $list[ $neighbour ] );
            } //!$list[ $neighbour ][ 'visited' ]
        } //$vertex[ 'neighbours' ] as $neighbour
    } //sizeof( $queue )
    return strlen( $str );
}
?>
</body>
</html>

Andere Tipps

This is not an exact solution but possible approach.. Using Ante method to simplify graph and then adding this algo. It passed a bit more test cases .... If you find any more test cases please share .. to check the validity 

<?php
$nodes = '{A,B,C,D,E}'; // It is just One Test Case
$bridges = '{(A,B),(B,C),(C,A),(E,D),(D,A)}'; // It is for just one test case
$graph = $nodes.','.$bridges;

function graphStringtoArrayObj()
    {
    // CODE TO CONVERT THE STRING TO ARRAY AND MANIPULATE THE GRAPH HERE
    // preg_replace can be used like in function criticalBridges();
    }
function graphArrayObjtoString()
    {
    // CODE TO CONVERT THE ARRAY TO STRING AND MANIPULATE THE GRAPH HERE
    }   
function simplificationofGraph( string $graph_string)
    {
        // code for simplification of the graph by deleting all the sure critical bridges and nodes
        // Node that has just one bridge 
          $simplified_Value = simplificationofGraph($a);
        // Condition Check : Two cases
        //Case I
            // If just One Node is left after recursive simplification return single node 

        //Case II 
            //return : Simplified Graph 
    }
function checkNodeInCycle($node)
    {
        $nodecheck = $node;
        $stack1 = array();// For putting possible nodes
        $stack2 = array();// For putting the nodes connected to the $nodecheck but not in $stack1;
        $flag = 0;

        //START WHILE
        //while return value from simplificationofGraph($graph_updated) is not a single node
            array_push($stack2, $nodecheckkat);
            arary_pop($stack2);
            //$nodecheckat = popped element from stack2;
            //traverse starts 
            array_push($stack1, $nodecheckat);
            // Check all nodes connected to $nodecheckat.
            // check if $nodecheckat->nodesat in_arrray($stack1) 
            foreach($nodecheckat->nodeat as $nodeelem)
            {
                if(in_arrray($nodeelem , $stack1) )
                {
                    if($nodeelem === $nodecheck)
                    {
                        // this node is in loop and we can break here to check another node of initial simplified graph
                        $flag = 1;
                        break;
                    }
                    else
                    {
                        $flag_stupidnode = 1;
                    }

                }
                else
                {
                    array_push($nodeelem,$stack2);

                }
            }
            if($flag_stupidnode === 1)
            {
                // this means the $nodecheck->node element are already there in the stack1 and have been traversed this means its false loop
                // this node and the bridges connected to it can be removed
                // remove all bridges and then make a new graph 


                // Update the stack1 and Stack2 by removing this node
                simplificationofGraph($graph_updated);
            }

        // END WHILE

        if($flag == 0 )
         {// 'this node is the critical note not in a cycle';}

    }

function criticalBridges($graph) // This gives all the bridge from the node  and we can find the node having just one bridge . take node and the bridge and remove that node and bridge and simplify the graph.
    {
        $Input2 = '('.$graphstring.')';
        $Input2 = preg_replace('/([^\(\)\{\}\[\],]+)/', '"$1"', $Input2);
        $Input2 = preg_replace('/[\{\(]/', '[', $Input2);
        $Input2 = preg_replace('/[\}\)]/', ']', $Input2);
        $Input2 = json_decode($Input2, true);
        $bridgeListFromIcelandarray = array();
        $finalOutputString = NULL;
        foreach($Input2 as $testcases)
        {   
            $outputString = NULL;
            foreach($testcases[0] as $Icelands)
            {
                $i = 0;
                $bridgeListFromIcelandarray[$Icelands] = array();
                foreach($testcases[1] as $Bridges)
                {
                    if(in_array($Icelands,$Bridges) )
                        $bridgeListFromIcelandarray[$Icelands][$i++] = $Bridges;
                }
                $countval = count($bridgeListFromIcelandarray[$Icelands]);
                if($countval === 1)
                {   
                    $Bridges = $bridgeListFromIcelandarray[$Icelands][0];
                    $Bridges = json_encode($Bridges);
                    $Bridges = preg_replace('/"(.*?)"/','$1',$Bridges);
                    $Bridges = preg_replace('/\[/', '(',$Bridges);
                    $Bridges = preg_replace('/\]/', ')',$Bridges);
                    if($outputString === NULL)
                        $outputString = $Bridges;
                    else
                        $outputString = $outputString .','. $Bridges; 
                }
            }
            if($outputString === NULL)
                 $outputString = 'NA';
            $outputString = '{'. $outputString . '}';

            if($finalOutputString === NULL)
                $finalOutputString = $outputString;
            else
                $finalOutputString =    $finalOutputString .','. $outputString;
        var_dump($bridgeListFromIcelandarray);
        }

        if (count($Input2) != 1)
            $finalOutputString = '{'. $finalOutputString . '}';             
        return $finalOutputString; 


    }





?>
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top